数学研发论坛

 找回密码
 欢迎注册
楼主: 0→∞

[求助] 果树问题讨论:这两个问题等价么?

  [复制链接]
发表于 2008-8-14 22:20:24 | 显示全部楼层

回复 60# 0→∞ 的帖子

发错了

ps:你怎么把这个主题贴发到茶馆里来了?
ps:你还在坚持人脑思考这个问题么?再次建议还是换个别的吧,这个问题NP-hard,计算机都无法“短”时间内解决的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-15 07:38:07 | 显示全部楼层
昨天就打算把本主题移动到其它更恰当的版块的,
但当天已有些回复,移动后首页上的统计会乱,
今天趁大家尚未开始讨论,马上转移之。

但这个话题看似数学难题,亦有算法交流、编程擂台的味道,
估计这也是当初楼主难以确定版块的缘故吧。
不过茶馆的人气不错,根据讨论的进展还是可以后期调整的。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-15 08:05:13 | 显示全部楼层
原帖由 没——问题 于 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. 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);
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-15 08:11:29 | 显示全部楼层
有个问题

  1.    struct sd
  2.     {   long int father;
  3.         int brother;
  4.         int me;
  5.         char str[4];
  6.     }date[2147483647];//
复制代码
这个定义编译怎么通过得?是不是应该将数组大小改小一些,难道你用的是64位的机器?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-15 09:00:23 | 显示全部楼层
我觉得是编译器通过了
但实际没能分配这么大的数据
32位机器最大的用户空间是3G
如果开启了远指针是48位的地址长度
即32位加16位的段选择子
不过要自己写操作数据的代码了
但似乎单个的数据不能跨越32位的地址长度吧

那个声明是32G数据长度的,超的厉害啊
目前没听说家用机器能这么狠
没问题兄:
有服务器么?
如果用64位服务器加unix或者linux
还差不多吧

[ 本帖最后由 无心人 于 2008-8-15 09:03 编辑 ]
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-15 09:01:12 | 显示全部楼层
另外,没问题兄的程序似乎有点高手的味道
还是整理下为好,mathe给indent下?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-15 09:07:59 | 显示全部楼层
我也上载一下我的程序。程序使用了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:19:21 | 显示全部楼层
原帖由 无心人 于 2008-8-15 09:01 发表
另外,没问题兄的程序似乎有点高手的味道
还是整理下为好,mathe给indent下?

呵呵,这个程序代码直接跟在"{"后面,结果VC的自动排版功能竟然无法处理,还得先手工处理一下。
现在排版过了,而且几个单行用,分开的代码被我换成多行了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-15 09:57:46 | 显示全部楼层
刚去研究万亿次机器了
发现有10万就能装一个
呵呵
什么时候拿10万当零花钱的时候
咱也装两个,一个用,一个开着耗电玩

下辈子能实现
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-15 10:35:45 | 显示全部楼层
如果有万亿次机器,上面程序计算到n=20应该不是问题
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2020-10-24 08:43 , Processed in 0.058080 second(s), 17 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表