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

没——问题

发错了

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分支多个语句用逗号分割，而不使用花括号。不过我觉得还是尽量不要这么用的好

1. 
   
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

有个问题

1. 
   
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应该不是问题