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

没——问题

发错了 ps：你怎么把这个主题贴发到茶馆里来了？ ps：你还在坚持人脑思考这个问题么？再次建议还是换个别的吧，这个问题NP-hard，计算机都无法“短”时间内解决的

gxqcn

昨天就打算把本主题移动到其它更恰当的版块的， 但当天已有些回复，移动后首页上的统计会乱， 今天趁大家尚未开始讨论，马上转移之。 但这个话题看似数学难题，亦有算法交流、编程擂台的味道， 估计这也是当初楼主难以确定版块的缘故吧。 不过茶馆的人气不错，根据讨论的进展还是可以后期调整的。

mathe

原帖由 没——问题 于 2008-8-14 21:28 发表 #include #include #define N 60+20 struct sd { long int father; int brother; int me; char str[4]; }date[2147483647];// ^Q^ int line_num,point_num=0; ...

非常不错，使用了树结构，还没有使用递推，而且代码也不长 不过我第一次看见代码中类似下面的用法 else分支多个语句用逗号分割，而不使用花括号。不过我觉得还是尽量不要这么用的好

2. else date[++end_line].father=now_line,date[end_line].str[0]=n_free[k],date[end_line].str[1]=n_free[m],date[end_line].str[2]=n_free[a],date[end_line].str[3]=n_free[b],date[end_line].me=(++d);

复制代码

mathe

有个问题

2. struct sd
3. { long int father;
4. int brother;
5. int me;
6. char str[4];
7. }date[2147483647];//

复制代码

这个定义编译怎么通过得？是不是应该将数组大小改小一些，难道你用的是64位的机器？

无心人

我觉得是编译器通过了 但实际没能分配这么大的数据 32位机器最大的用户空间是3G 如果开启了远指针是48位的地址长度 即32位加16位的段选择子 不过要自己写操作数据的代码了 但似乎单个的数据不能跨越32位的地址长度吧 那个声明是32G数据长度的，超的厉害啊 目前没听说家用机器能这么狠 没问题兄： 有服务器么？ 如果用64位服务器加unix或者linux 还差不多吧 [ 本帖最后由 无心人 于 2008-8-15 09:03 编辑 ]

无心人

另外，没问题兄的程序似乎有点高手的味道 还是整理下为好，mathe给indent下？

mathe

我也上载一下我的程序。程序使用了Linux下c函数mkdir和Linux外部命令sort，如果要port到windows下面，不知道sort命令参数格式是否相同。 程序的目标是产生在点的数目为NUM_NODES时，边的数目不小于MAX_TOTAL_EDGES - MAX_FREEDOM的所有组合。 其中MAX_TOTAL_EDGES是边总数的一个理论上界，我现在计算的时候通常定义MAX_FREEDOM为3或4. 其中产生数据的代码有两个版本，分别为findmax5.cpp和findmax6.cpp.我本来认为findmax6.cpp应该更加优化，但是在NUM_NODES不大于15的时候，实际计算结果表明findmax5.cpp产生的中间文件更加小。但是findmax5.cpp处理NUM_NODES为16时好像有问题，但是findmax6.cpp没有问题。 而另外一个文件solve2.cpp会处理上面程序产生的数据，根据它们产生一个wxMaxima命令格式的方程组，直接将它复制到wxMaxima就可以让它来帮忙求解了。 比如NUM_NODES宏定义为15,那么运行findmax5.cpp或findmax6.cpp 它会产生一个data目录，在这个目录下面会产生文件s1,t2,s2,t3,s3...,t15,s15.其中s15就是最终结果，其它文件都是中间结果。 不过这些文件都不小，所以要保证拥有足够的磁盘空间（比如预留10G空间）。如果磁盘空间不够，可以修改一下代码，在计算机产生下一个文件后马上删除前一个文件。 程序代码中主要定义了一个node_edge_set模板类，它用于对于一个给定的点线结构，产生一个只同结构有关系的表达方式。也就是说，如果我们将一个点线结构中的点进行置换（当然对应的边跟着变换），那么我们可以得到另外一个结构完全相同的表达方式。而node_edge_set::normalize可以保证对于这样两个输入，产生相同的输出。 orchard.tgz (7.57 KB, 下载次数: 7)

2008-8-15 09:07 上传

点击文件名下载附件

mathe

原帖由 无心人 于 2008-8-15 09:01 发表 另外，没问题兄的程序似乎有点高手的味道 还是整理下为好，mathe给indent下？

呵呵，这个程序代码直接跟在"{"后面，结果VC的自动排版功能竟然无法处理，还得先手工处理一下。 现在排版过了，而且几个单行用,分开的代码被我换成多行了

无心人

刚去研究万亿次机器了 发现有10万就能装一个 呵呵 什么时候拿10万当零花钱的时候 咱也装两个，一个用，一个开着耗电玩 下辈子能实现

mathe

如果有万亿次机器，上面程序计算到n=20应该不是问题