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

zgg___

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

1. // 20tree-2.cpp : Defines the entry point for the console application.
   
2. //
   
3. 
   
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：高考这东西太烦了，我会很少来，希望坛主别因为我长时间不登陆而删除了我的账号。

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

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

我回复如下：

是高中老师还是学生？水平蛮高的嘛！

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

所以，不会删除账号的。

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