果树问题讨论:这两个问题等价么？

zgg___

程序比较土呀。 是在vc2005下，压缩包为工程目录中所有的文件，其中源码如下：

1. // 20tree-2.cpp : Defines the entry point for the console application.
2. //
4. #include "stdafx.h"
5. #include <conio.h>
6. #include <stdlib.h>
7. #include <time.h>
8. #define M 4845
9. #define K 6
10. int show(int sk[],int skn)
11. {
12. int i,k,n;
13. for(i=0;i<skn;i++)
14. {
15. n=sk[i];
16. for(k=0;k<20;k++)
17. {
18. if(n%2==1)printf("%2d,",k+1);
19. n/=2;
20. }
21. printf("\n");
22. }
23. for(k=0;k<20;k++)
24. {
25. for(i=0;i<skn;i++)
26. {
27. if(sk[i]%2==1)printf(" *");else printf(" .");
28. sk[i]/=2;
29. }
30. printf("\n");
31. }
32. return 0;
33. }
34. int zzch(int z[],int zn,int sk,int zz[])
35. {
36. int i,j,s,kk,k,r;
37. r=0;
38. kk=z[sk];
39. for(i=0;i<zn;i++)
40. {
41. k=z[i]&kk;
42. s=0;
43. for(j=0;j<20;j++){s+=k%2;k/=2;}
44. if(s<=1)
45. {
46. zz[r]=z[i];r++;
47. }
48. }
49. return r;
50. }
51. int formatzz(int z[])
52. {
53. int i,j,k,s,ss;
54. ss=0;
55. for(i=0;i<1048576l;i++)
56. {
57. k=i;s=0;
58. for(j=0;j<20;j++){s+=k%2;k/=2;}
59. if(s==4){z[ss]=i;ss++;}
60. }
61. return 0;
62. }
63. int cztoz(int z[],int zz[],int n)
64. {
65. int i;
66. for(i=0;i<n;i++)zz[i]=z[i];
67. return 0;
68. }
69. int _tmain(int argc, _TCHAR* argv[])
70. {
71. int i,j,k,kt,n,nt,skn,zn,m,skm;
72. int z[M],zz[M],zzz[M];
73. int sk[50];
74. formatzz(zzz);
75. srand((unsigned)time(NULL));
76. skm=0;
77. for(m=0;m<100000;m++)
78. {
79. cztoz(zzz,z,M);
80. skn=0;
81. zn=M;
82. for(j=0;zn!=0&&j<50;j++)
83. {
84. n=-1;
85. for(i=0;i<K;i++)
86. {
87. kt=rand()%zn;
88. nt=zzch(z,zn,kt,zz);
89. if(nt>n){n=nt;k=kt;}
90. }
91. zzch(z,zn,k,zz);
92. sk[skn]=z[k];skn++;
93. zn=n;cztoz(zz,z,zn);
94. // printf("k=%d,n=%d.\n",k,n);
95. }
96. if(skn>skm)
97. {
98. show(sk,skn);
99. printf("skn(m=%d)=%d.\n",m,skn);
100. skm=skn;
101. }
102. }
103. printf("End\n");
104. _getch();
105. return 0;
106. }

复制代码

无心人

有30台四核服务器就可以了 你们研究所够不够？

mathe

函数formatzz产生所有直线模板(共4845个?) 看你后面使用rand函数，也就是每次随机选择一条直线，然后淘汰同它不相容的直线

mathe

原帖由 无心人 于 2008-8-15 10:54 发表 有30台四核服务器就可以了 你们研究所够不够？

这个不能瞎用

无心人

资源浪费阿 就和我们的50台高性能便宜机器一样 给学生做AutoCAD练习 一天多少计算资源浪费啊

zgg___

程序没有注释，这里简单解释一下。 我们知道从20个里面选4个，共有4845种选法，我们用formatzz列出它们。然后随机从其中取一个，划掉与这一个冲突的选法，然后循环。zzch就是用来将放在z中的选法，挑出与sk不冲突的选法放在zz中的函数。还有cztoz是用来将z中的结果倒来倒去的，show是显示最终结果的。后来对上面提到的随机选取做了改进，加入了贪婪的因素，贪婪因子K大家是可以调整的，就是先预选K次，然后执行其中冲突最少的选法。所以K越大就越贪婪。 可以看到程序中有许多地方都为了编程容易，没有优化，所以说土呢，呵呵。而且这个程序是不能搜索所有的组合的。

shshsh_0510

随机算法效果就是好

0→∞

恩，早就放弃了 早期是因为很容易就画出了一个20条直线的解，所以低估了这个问题的难度 不过，我准备闭门去学c语言了，争取开学前能看懂你们的程序 我比你们都年轻，最有希望的还是我

没——问题

恩，0→∞努力吧 感谢mathe的排版 我确实没有养成好的习惯，不过这次这么夸张是有原因的： 早期为了练习c语言给自己订了一个原则：低于100行的代码就不留备份 这个代码写完后是150多行（mathe的排版是182行），去掉所有调试性的输出和注释剩120行，想尝试一下到底能缩到多少行，最终还是108行。代码得以保留。 那个2147483647纯属恶搞，只是想试试编译器（我用的是c-free3.5,应该是gcc/g++编译器的）到底允许多大（因为书上没说过）。我想无心人是对的，编译通过了也不可能分配那么多。事实上那个程序也不需要那么多空间： 即使搜索了20个点的所有情况（搜索完所有情况后有一个退出语句，这对pc机用户是没意义的 ），设最多的时候搜到过30行的情况（不现实），即最大深度为30，设兄弟结点数最大为1000（达不到），那么最多只会存储30*1000条线的数据。所以该做30000就可以了，高兴可以写65535 。 最终在这个代码中还有两个未完成的工作： 1、同mathe的node_edge_set所实现的功能 2、读取上次的结果继续搜的功能（现在每次运行都会从头搜） 这个（2）虽说简单，但我那个代码写的易读性太差了，很多变量都为了方便随手命名，而且到处乱用。所以mathe恐怕很难做这个修改（还不如自己重写），而我自己有没时间了囧 另外，还可以通过一些修改使得对某一[线的条数]的搜索更高效。例如代码中有一句注释说的0到4的问题，有兴趣可以试试改成0到4然后搜20点24条线，看看效率下降多少。 还是有点怀疑现有的数学软件能不能用来解这个方程组囧（虽然没用过wxMaxima，但应该也差不多） zgg说的“划掉冲突”的方法，我最初时也想过，但没实施。两个程序的初衷不同。 ps：高考这东西太烦了，我会很少来，希望坛主别因为我长时间不登陆而删除了我的账号。期待着诸位的进展。

gxqcn

原帖由 没——问题 于 2008-8-15 14:56 发表 ps：高考这东西太烦了，我会很少来，希望坛主别因为我长时间不登陆而删除了我的账号。

昨天与 没——问题 短消息交流时，对方曾说：

非常喜欢这个论坛，但迫于高中生活没办法常来"泡"

我回复如下：

是高中老师还是学生？水平蛮高的嘛！ 这是个技术性并带学术性的论坛，欢迎大家常来， 但大家各自都有自己的工作和学习， 只要碰到问题需要解决或分享时，记得来这里就够了。

所以，不会删除账号的。 如果长时间未登陆，而忘了登陆密码时，可以通过“访客留言”给我， 系统会随机生成新密码发到注册信箱中去。