首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 软件管理 > 软件架构设计 >

排列难题,该如何处理

2012-02-12 
排列难题要求:生成N个自然数,满足以下算式:1. N3时任意M1-M2 ! M2-M3(M1,M2,M3为取出的数的排列组合)

排列难题
要求:生成N个自然数,
满足以下算式:
1. N=3时;
任意M1-M2 != M2-M3;(M1,M2,M3为取出的数的排列组合)
如:
1 - 2 != 2 - 4;
4 - 2 != 2 - 1;
2 - 1 != 1 - 4;
4 - 1 != 1 - 2;
1 - 4 != 4 - 2;
2 - 4 != 4 - 1;

{1,2,5}{1,2,7}等亦成立;

2.N > 3时;
任意M1-M2 != M3-M4;(M1,M2,M3,M4为取出的N个数中任意四个数的排列组合);

3.要求N个数中最大的那个数最小的组合情况;
如: 
N=4时;{1,2,5,7}优于{1,2,4,8}
N=5时;{1,2,5,10,12}优于{1,2,4,8,13}优于{1,2,5,7,14};

求解任意N时的最优排列组合。


[解决办法]
那最优解应该不止一种的吧,当
N=4时 {1,2,4,7}和{1,2,5,7}应该都是最优解吧。

----------------------

2.N > 3时;
任意M1-M2 != M3-M4;(M1,M2,M3,M4为取出的N个数中任意四个数的排列组合);

可以转换成 M1+M4 != M2+M3

----------------------

可不可能从N-1的最优解集中推导出N的最优解呢? 呵呵,有趣。
[解决办法]
LZ不用再碰运气了,这题是NPC的,若干年前csdn算法版讨论过n = 36的情况,用到了许多高深的数论知识也只能求得近似解,不是最优,好像在整个世界范围内,都没能求得最优解。

给LZ一个线索,自己看吧,又不少当年大牛级的人物参与讨论,技术含量挺高的
http://topic.csdn.net/t/20020819/23/954026.html

C# code
 

热点排行