是在vc2005下，压缩包为工程目录中所有的文件，其中源码如下：// 20tree-2.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <conio.h>
#include <stdlib.h>
#include <time.h>
#define M 4845
#define K 6
int show(int sk[],int skn)
{
int i,k,n;
for(i=0;i<skn;i++)
{
n=sk;
for(k=0;k<20;k++)
{
if(n%2==1)printf("%2d,",k+1);
n/=2;
}
printf("\n");
}
for(k=0;k<20;k++)
{
for(i=0;i<skn;i++)
{
if(sk%2==1)printf(" *");else printf(" .");
sk/=2;
}
printf("\n");
}
return 0;
}
int zzch(int z[],int zn,int sk,int zz[])
{
int i,j,s,kk,k,r;
r=0;
kk=z;
for(i=0;i<zn;i++)
{
k=z&kk;
s=0;
for(j=0;j<20;j++){s+=k%2;k/=2;}
if(s<=1)
{
zz=z;r++;
}
}
return r;
}
int formatzz(int z[])
{
int i,j,k,s,ss;
ss=0;
for(i=0;i<1048576l;i++)
{
k=i;s=0;
for(j=0;j<20;j++){s+=k%2;k/=2;}
if(s==4){z=i;ss++;}
}
return 0;
}
int cztoz(int z[],int zz[],int n)
{
int i;
for(i=0;i<n;i++)zz=z;
return 0;
}
int _tmain(int argc, _TCHAR* argv[])
{
int i,j,k,kt,n,nt,skn,zn,m,skm;
int z,zz,zzz;
int sk;
formatzz(zzz);
srand((unsigned)time(NULL));
skm=0;
for(m=0;m<100000;m++)
{
cztoz(zzz,z,M);
skn=0;
zn=M;
for(j=0;zn!=0&&j<50;j++)
{
n=-1;
for(i=0;i<K;i++)
{
kt=rand()%zn;
nt=zzch(z,zn,kt,zz);
if(nt>n){n=nt;k=kt;}
}
zzch(z,zn,k,zz);
sk=z;skn++;
zn=n;cztoz(zz,z,zn);
// printf("k=%d,n=%d.\n",k,n);
}
if(skn>skm)
{
show(sk,skn);
printf("skn(m=%d)=%d.\n",m,skn);
skm=skn;
}
}
printf("End\n");
_getch();
return 0;
}
有30台四核服务器就可以了
你们研究所够不够？ 函数formatzz产生所有直线模板(共4845个?)
看你后面使用rand函数，也就是每次随机选择一条直线，然后淘汰同它不相容的直线 原帖由 无心人 于 2008-8-15 10:54 发表 http://bbs.emath.ac.cn/images/common/back.gif
有30台四核服务器就可以了
你们研究所够不够？
这个不能瞎用 :lol
资源浪费阿
就和我们的50台高性能便宜机器一样
给学生做AutoCAD练习
一天多少计算资源浪费啊
补充71层
程序没有注释，这里简单解释一下。我们知道从20个里面选4个，共有4845种选法，我们用formatzz列出它们。然后随机从其中取一个，划掉与这一个冲突的选法，然后循环。zzch就是用来将放在z中的选法，挑出与sk不冲突的选法放在zz中的函数。还有cztoz是用来将z中的结果倒来倒去的，show是显示最终结果的。后来对上面提到的随机选取做了改进，加入了贪婪的因素，贪婪因子K大家是可以调整的，就是先预选K次，然后执行其中冲突最少的选法。所以K越大就越贪婪。
可以看到程序中有许多地方都为了编程容易，没有优化，所以说土呢，呵呵。而且这个程序是不能搜索所有的组合的。 :b:随机算法效果就是好 :)
回复 61# 没——问题 的帖子
恩，早就放弃了早期是因为很容易就画出了一个20条直线的解，所以低估了这个问题的难度
不过，我准备闭门去学c语言了，争取开学前能看懂你们的程序
我比你们都年轻，最有希望的还是我:lol 恩，0→∞努力吧:D
感谢mathe的排版
我确实没有养成好的习惯，不过这次这么夸张是有原因的：
早期为了练习c语言给自己订了一个原则：低于100行的代码就不留备份
这个代码写完后是150多行（mathe的排版是182行），去掉所有调试性的输出和注释剩120行，想尝试一下到底能缩到多少行，最终还是108行。代码得以保留。
那个2147483647纯属恶搞，只是想试试编译器（我用的是c-free3.5,应该是gcc/g++编译器的）到底允许多大（因为书上没说过）。我想无心人是对的，编译通过了也不可能分配那么多。事实上那个程序也不需要那么多空间：
即使搜索了20个点的所有情况（搜索完所有情况后有一个退出语句，这对pc机用户是没意义的:lol ），设最多的时候搜到过30行的情况（不现实），即最大深度为30，设兄弟结点数最大为1000（达不到），那么最多只会存储30*1000条线的数据。所以该做30000就可以了，高兴可以写65535:lol 。
最终在这个代码中还有两个未完成的工作：
1、同mathe的node_edge_set所实现的功能
2、读取上次的结果继续搜的功能（现在每次运行都会从头搜）
这个（2）虽说简单，但我那个代码写的易读性太差了，很多变量都为了方便随手命名，而且到处乱用。所以mathe恐怕很难做这个修改（还不如自己重写），而我自己有没时间了囧
另外，还可以通过一些修改使得对某一[线的条数]的搜索更高效。例如代码中有一句注释说的0到4的问题，有兴趣可以试试改成0到4然后搜20点24条线，看看效率下降多少。
还是有点怀疑现有的数学软件能不能用来解这个方程组囧（虽然没用过wxMaxima，但应该也差不多）
zgg说的“划掉冲突”的方法，我最初时也想过，但没实施。两个程序的初衷不同。
ps：高考这东西太烦了，我会很少来，希望坛主别因为我长时间不登陆而删除了我的账号。期待着诸位的进展。 原帖由 没——问题 于 2008-8-15 14:56 发表 http://bbs.emath.ac.cn/images/common/back.gif
ps：高考这东西太烦了，我会很少来，希望坛主别因为我长时间不登陆而删除了我的账号。
昨天与 没——问题 短消息交流时，对方曾说：非常喜欢这个论坛，但迫于高中生活没办法常来"泡"
我回复如下：是高中老师还是学生？水平蛮高的嘛！ :b:
这是个技术性并带学术性的论坛，欢迎大家常来，
但大家各自都有自己的工作和学习，
只要碰到问题需要解决或分享时，记得来这里就够了。:)
所以，不会删除账号的。
如果长时间未登陆，而忘了登陆密码时，可以通过“访客留言”给我，
系统会随机生成新密码发到注册信箱中去。