一个数列

一个数列 del_c_sharp (摩托～◎～◎～◎)
求一递增整数序列,共36个数,第一个数为1,后面数逐渐增大
要求:任意两个整数的差(大整数减去小整数)均不相同
如:1 2 4 8 .....
求所有情况中第36个数(也就是最大数)最小时的解,即输出这36个数
算法不难,关键是,如何让程序算法效率高,也就是如何在有限的时间内算出结果
计算时间最好在3个小时内
主　　题： del_c_sharp兄的大难题之大家继续讨论
作　　者： Lawrence444 (胖子)
等　　级：
信 誉 值： 100
所属论坛： 专题开发 数据结构与算法
问题点数： 200
回复次数： 115
发表时间： 2002-8-19 23:10:31
这可是目前版上最热的话题了，starfish等大牛为什么还不出来说几句啊，呵呵。
参考文献：以前的讨论：
http://www.csdn.net/expert/topic/931/931488.xml?temp=.9010126
http://www.csdn.net/expert/topic/934/934268.xml?temp=.1472284
del_c_sharp兄给出的题目如下：
求一递增整数序列,共36个数,第一个数为1,后面数逐渐增大
要求:任意两个整数的差(大整数减去小整数)均不相同
如:1 2 4 8 .....
求所有情况中第36个数(也就是最大数)最小时的解,即输出这36个数
本楼欢迎大家对此题目进行多方面的热烈讨论，如：解题的算法、是否NP完全、题目的转换、使用各种算法的可能性等等等等。。。。
不欢迎：
1。说答案是631。早就错了，请看以前的讨论。
2。说用动态规划得最优解。同上。
3。说答案是2^36，这个，应该不多吧。
4。看错题。请注意本题问的是任意两个数的差值均不相同。
~~~~
5。在这里贴未经验证的错误数列。如果算出答案又懒得写验证代码的话，用我的。
输入是一个文件hard.in，里面放数列，空格分割就行了。
#include <stdio.h>
#include <string.h>
void main()
{
int i,j;
int array[50];
int n;
int subval[3000];
i=0;
FILE *fp=fopen("hard.in","r"
memset(subval,0,sizeof(subval));
while(1){
if(fscanf(fp,"%d",&array)==EOF)
break;
i++;
}
n=i;
for(i=0;i<n;i++)
for(j=i+1;j<n;j++) {
if(subval[array[j]-array]){
printf("Wrong at %d %d!",i,j);
return;
}
subval[array[j]-array]++;
}
}
另给出目前网友gofor() 兄和ALNG(?) 兄得到的目前最好的解：
1 5 7 8 32 46 51 61 69 81 103 136 162 194 241 277 328 391 400 497 567 615 699 788 809 909 991 1077 1090 1155 1275 1291 1433 1510 1604 1632
另给出问题规模比较小（远小于36）时gofor()兄用穷举搜出来的最优解：
n 序列
2 2 1
3 4 3 1
3 4 2 1
4 7 6 3 1
4 7 5 2 1
5 12 11 8 3 1
5 12 10 5 4 1
5 12 10 5 2 1
5 12 9 8 3 1
6 18 17 14 8 6 1
6 18 17 14 8 3 1
6 18 17 10 7 5 1
6 18 17 10 6 4 1
6 18 16 11 5 2 1
6 18 15 13 9 2 1
6 18 14 12 9 2 1
6 18 13 11 5 2 1
7 26 25 22 16 8 3 1
7 26 25 19 15 6 3 1
7 26 25 15 10 7 3 1
7 26 24 23 16 10 5 1
7 26 24 21 12 8 2 1
7 26 24 20 17 12 2 1
7 26 24 19 13 5 4 1
7 26 24 19 11 5 2 1
7 26 23 22 14 8 3 1
7 26 22 17 11 4 3 1
8 35 34 31 26 20 13 3 1
8 35 33 23 16 10 5 2 1
9 45 44 40 33 20 18 10 4 1
9 45 42 36 28 26 13 6 2 1
10 56 55 50 46 33 30 22 15 3 1
10 56 54 42 35 27 24 11 7 2 1
11 73 72 69 60 45 40 26 19 9 3 1
11 73 72 64 54 49 42 21 17 15 4 1
11 73 71 65 55 48 34 29 14 5 2 1
11 73 70 59 57 53 32 25 20 10 2 1
12 86 84 80 62 57 46 43 31 18 11 10 1
12 86 77 76 69 56 44 41 30 25 7 3 1
13 107 105 102 82 70 64 48 37 22 18 9 8 1
13 107 100 99 90 86 71 60 44 38 26 6 3 1
回复人： dcyu(Dd) ( ) 信誉：100 2002-8-19 23:44:18 得分:0
不知gofor() 兄和ALNG(?) 的程序？
时间？何种CPU? 是穷举法吗？
挺不错的结果。
Top
回复人： gofor() ( ) 信誉：100 2002-8-20 0:39:09 得分:0
P4 1.5G 128M win2000, C++Builder 5
穷举法，算出n=13,　耗时10分钟。
算出n=36时，一个更好的结果：（耗时几分钟，只是运气好）
1 2 4 8 13 21 31 45 79 105 143 188 230 245 270 298 350 383 404 476 552 625 684 706 802 852 888 1012 1111 1162 1375 1422 1483 1539 1578 1627
Top
回复人： dcyu(Dd) ( ) 信誉：100 2002-8-20 2:02:53 得分:0
可以来这讨论：
http://www.csdn.net/expert/topic/947/947777.xml?temp=.4926569
抢生意了，呵呵！
Top
回复人： ALNG(?) ( ) 信誉：100 2002-8-20 10:05:28 得分:0
gofor, 行啊你！
Top
回复人： ALNG(?) ( ) 信誉：100 2002-8-20 10:15:40 得分:0
我的是PIII 1G 128M
贪心选择+随机算法改造
1632是手工设定了前5项得到的，
没有设定[完全由机器选择]的最好解是1653
1 6 7 9 16 28 39 56 70 74 90 126 165 222 247 288 333 376 448 477 555 581 640 748 850 894 1021 1045 1159 1230 1306 1383 1475 1488 1616 1653
但是再往前走就难了，很可能随机数序列循环出现了。
Top
回复人： ywqzxj(午青) ( ) 信誉：100 2002-8-20 12:35:39 得分:10
n=13
我的程序(死推)8分钟算到
1,3,6,26,38,44,60,71,86,90,99,100,107, elapsed:480971.810624
另一个最优解可能还得更长时间,但是及其比较差:C333,96mb
Top
回复人： ywqzxj(午青) ( ) 信誉：100 2002-8-20 12:51:50 得分:0
还有程序也很差:
{要算其它n 更改inumber,MY_TEST_MAXSHU}
bool inline insertdata(int midelt, int *icha)
{
if(icha[midelt-1] ==0)
icha[midelt-1] =1;
else
return false;
return true;
}
void inline iselect(int& ii,int& i0, int* icha)
{
// int i=0;
while(icha[i0] != 0)
i0++;
ii+=i0;
ii++;
}
#define MY_TEST_MAXSHU 190
void testnp()
{
int icha[MY_TEST_MAXSHU],ibcha[MY_TEST_MAXSHU],ishu[37],max,midelt,inumber;
int i=0,j=0,k=0,n=0,index,i0=0;
bool isok;
char s1s[2048];char *ps1s;
ishu[0]=1;
ishu[1]=1;
memset(icha,0,MY_TEST_MAXSHU*sizeof(int));
memset(ibcha,0,MY_TEST_MAXSHU*sizeof(int));
max=MY_TEST_MAXSHU;
inumber=13;
index=1;
i=ishu[index];
//max=225;
//i=ishu[index]+2;
MY_TEST_REPORT("c:/ss1.txt",NULL)
//MY_TEST_REPORT("c:/ss2.txt",NULL)
//MY_TEST_REPORT("c:/ss3.txt",NULL)
CElapsed ttime;
ttime.Begin();
sprintf(s1s,"number=%d; first=%d,max=%d",inumber,ishu[0],max);
MY_TEST_REPORT("c:/ss1.txt",s1s)
for(;index>0
{
iselect(i,i0,icha);
midelt = (inumber-index)*(inumber-1-index)/2;
if(i+midelt>max)
{
index--;
i0=0;
//{deal icha[]
memset(icha,0,MY_TEST_MAXSHU*sizeof(int));
for(j=0; j<index-1; j++)
{
for(k=j+1; k<index; k++)
{
midelt=ishu[k]-ishu[j];
if(!insertdata( midelt, icha))
AfxMessageBox("Bad"
}
}
memcpy(ibcha,icha,MY_TEST_MAXSHU*sizeof(int));
//}
i=ishu[index];
continue;
}
ishu[index]=i;
ishu[index+1]=i;
isok = true;
for(j=0;j<index;j++)
{
midelt = i - ishu[j];
isok=insertdata( midelt, icha);
if(!isok)
break;
}
/*//MY_TEST_REPORT("c:/ss2.txt",NULL)
ps1s=s1s;
ps1s+=sprintf(ps1s,"number=%d; first=%d,max=%d",inumber,ishu[0],max);
for(j=0;j<=index;j++)
{
ps1s+=sprintf(ps1s," %d=>%d",j+1,ishu[j]);
}
for(j=0;j<MY_TEST_MAXSHU;j++)
{
if(icha[j]!=0)
ps1s+=sprintf(ps1s,"%d,",j+1);
}
ps1s+=sprintf(ps1s,""
MY_TEST_REPORT("c:/ss2.txt",s1s)*/
if(isok)//ok
{
/*ps1s=s1s;
ps1s+=sprintf(ps1s,"number=%d; first=%d,max=%d",inumber,ishu[0],max);
for(j=0;j<=index;j++)
{
ps1s+=sprintf(ps1s," %d=>%d",j+1,ishu[j]);
}
for(j=0;j<MY_TEST_MAXSHU;j++)
{
if(icha[j]!=0)
ps1s+=sprintf(ps1s,"%d,",j+1);
}
ps1s+=sprintf(ps1s,""
MY_TEST_REPORT("c:/ss3.txt",s1s)*/
index++;
i0=0;
if(index<inumber)
{
//{deel ibcha[] from icha[]
memcpy(ibcha,icha,MY_TEST_MAXSHU*sizeof(int));
//}
}
else
{
//OK! write to file
ps1s=s1s;
ps1s+=sprintf(ps1s," "
for(j=0;j<index;j++)
{
ps1s+=sprintf(ps1s,"%d,",ishu[j]);
}
ps1s+=sprintf(ps1s," elapsed:%lf",ttime.End());
MY_TEST_REPORT("c:/ss1.txt",s1s)
max = ishu[index-1];
index -= 2;
//{deal icha[]
if(index<1)index=1;
memset(icha,0,MY_TEST_MAXSHU*sizeof(int));
for(j=0; j<index-1; j++)
{
for(k=j+1; k<index; k++)
{
midelt=ishu[k]-ishu[j];
if(!insertdata( midelt, icha))
AfxMessageBox("Bad"
}
}
memcpy(ibcha,icha,MY_TEST_MAXSHU*sizeof(int));
//}
}
i=ishu[index];
}
else
{
//{deal icha[] from ibcha[]
memcpy(icha,ibcha,MY_TEST_MAXSHU*sizeof(int));
//}
}
}
//write complete to file;
ps1s=s1s;
ps1s+=sprintf(ps1s,""
for(j=0;j<=index+1;j++)
{
ps1s+=sprintf(ps1s,"%d,",ishu[j]);
}
ps1s+=sprintf(ps1s,"i=%d",i);
ps1s+=sprintf(ps1s,", elapsed:%lf",ttime.End());
MY_TEST_REPORT("c:/ss1.txt",s1s)
}
Top
回复人： BinaryTreeEx(狂徒) ( ) 信誉：100 2002-8-20 12:59:56 得分:0
顺便提出一个算法，我时间有限希望有人写出程序。
一共36个数，a1,a2,a3...a36,相邻两个数相减可以得到35个数，他们是：
b12 = a2-a1, b23 = a3-a2,...b3536=a36-a35.题目要求a1 = 1 ,a36为最小
那么就是说，SubSum = b12+b23+...+b3536为最小，这个结论没有异议吧。
由此我提出一个算法。
首先构造一个ai的序列，他们是1，2，3，...35然后根据以下原则进行筛选。
判断相同差值的数是否存在，而且是从序列的右边开始判断，这样可以保证最小。如果存在那么用一个最小的新数替换其中的最大数，重复上面的过程直到求出解。下面详细说明相同差值存在的判断方法。所谓任意两个数之差，对于数列bi来说就是k个连续的数字的和，对于任意的k1,k2数列b中起点不同的两个连续子序列的和不同，那么这样的就是满足要求的解。其中1<=k1,k2<=35。
那么如何保证最小呢？显然我们开始给出的ai序列是最小的，只是有相同的差值。那么我们可以从那个序列开始每次替换一个数字，同时保证新得的到的序列是所有一次替换操作后中最小的（很容易保证）。替换后要求验证存在的相同差值是否减少了一个，如果是那么用同样的方法处理剩下的相同差值，否则继续替换。
Top
回复人： Lawrence444(胖子) ( ) 信誉：100 2002-8-20 14:38:05 得分:0
呵呵，算穷举的朋友们也要加油欧，现在好像还没有一个能快过我的穷举算法的呢。
/* The always right complete search algorithm for hard problem
proposed by del_c_sharp */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
int STOP;
int subval[1000]; // values generated by subtraction
int curlist[50],flist[50]; // flist stores the best list so far, curlist stores
// the current one
int mval=-1;
int prevans[50]={1,2,4,7,12,18,26,35,45,56,73,86,107}; // previous answers
clock_t startc,end;
int gennewsub(int n)
{
int i,j;
for(i=2;i<n;i++) // this way, unsatisfied results
if(subval[curlist[n]-curlist]) // can be generated more quickly
return 0; // and that's what I want
for(i=1;i<n;i++)
subval[curlist[n]-curlist]++;
return 1;
}
void removenewsub(int n)
{
int i,j;
for(i=1;i<n;i++)
subval[curlist[n]-curlist]=0;
}
void startsearch(int n)
{
int start,i,j;
if(n>STOP){
if(curlist[n-1]<mval || mval==-1){
printf("%d",mval = curlist[n-1]);
printf("Current time: %.2f seconds",(clock()-startc)/CLK_TCK);
memcpy(flist,curlist,n*sizeof(int));
for(i=1;i<=STOP;i++)
printf("%d ",flist);
printf(""
}
return;
}
start = n * (n-1) / 2 + 1; // start searching from C(n,2)+1
if(start<=curlist[n-1]){
for(j=1;j<STOP;j++)
if(!subval[j])
break;
start=curlist[n-1]+j; // or, first valid place later than before
}
for(i=start;mval==-1 || i<mval-prevans[STOP-n]+1;i++){
// if i is more than the maximum value to generate a better answer, no need to
// search anymore
curlist[n]=i;
if(n==2){
// the application of 对偶性
if(mval>0 && mval - curlist[2] - prevans[STOP-2] < curlist[2]-1)
break;
else
printf("Second place now searching: %d",i);
}
if(!gennewsub)
continue;
startsearch(n+1);
removenewsub;
}
}
void main()
{
int i,j;
scanf("%d",&STOP);
memset(subval,0,sizeof(subval));
memset(curlist,0,sizeof(curlist));
if(prevans[STOP-2]==0) // we don't search too big numbers!
return;
curlist[1]=1; // of course, the first item is 1
startc = clock();
startsearch(2); // now start searching
end = clock();
printf("%d",mval);
for(i=1;i<=STOP;i++)
printf("%d ",flist);
printf(""
printf("Time elapsed: %.2f seconds",(end-startc)/CLK_TCK);
}
Top
回复人： Lawrence444(胖子) ( ) 信誉：100 2002-8-20 15:33:10 得分:0
突然想起来一条，有能力的人可以试试：
这题用Genetic系列的算法不好解，主要是因为很难交叉出有效的解。
这种题如果有一个好的估值函数，用Heuristic Search效果会很好。
所以：能不能用GA进化一个估值函数出来我们拿来搜？
Top
回复人： laozi(老子) ( ) 信誉：100 2002-8-20 16:58:06 得分:0
具体的代码懒地写了，因为要代码优化，我把思路贴出来，大家看看是否正确。
先从1开始
差数不能取0,因此取1,1+1=2,下个数是2
2：
差数取2(因为它是比前一个差数1大的最小的数),2+2=4,下个数是4
4:
差数取3(同理)，但前两个差数之和为3，也就是4-1=3，所以取4，4+4=8，下个数取8
8：
差数取5，1+2=3，2+4=6，1+2+4=7，都不是5，因此8+5=13，下个数取13
13：
差数取6，但2+4=6，因此取7，发现1+2+4=7，那么取8，下个数取21
21：
....
*******************************************************************
最终只要递推就可以，总的算法是先得到符合条件的35个差数，最终就能得到36个数字序列。令当前递推到的差数是a,共递推出n个差数，现在递推第n+1个差数，首先该差数取a+1,然后在前n个差数中验证是否能取，不能取则取a+2，直到能取为止。那么怎么才算可取差数呢？就是前n个差数任意个连续的差数之和不能和要取的差数相同。可以从2个开始，一直取到n个。比如例子中的差数序列1，2，4，5，8。1+2=3，2+4=6，4+5=9，5+8=13，1+2+4=7，2+4+5=11，4+5+8=17，1+2+4+5=12，2+4+5+8=19，1+2+4+5+8=20，很显然下个差数取10。
*******************************************************************
算法思路就是这样不用穷举法，再加优化处理，比如算差数10的时候，不必要算1+2=3，我想秒级，甚至毫秒级就能算出答案来,因为下一个差数验证，只要有倒数第二个差数参与就可以了。
Top
回复人： mathe() ( ) 信誉：100 2002-8-20 17:14:28 得分:0
1,3,8,16,30,53,78,104,137,190,237,294,322,420,514,622,657,803,947,1030,1085,1161,1279,1352,1384,1418,1476,1507,1545,1563,1587,1606,1617,1623,1626,1627
Top
回复人： ALNG(?) ( ) 信誉：100 2002-8-20 17:16:28 得分:0
laozi,
如果我没有理解错，你讲的就是我们所说的贪心构造，大多数人都这么做过了，得到的是2029.
这个方法速度是不用怀疑的，问题是这样得到的解不能让人满意。
Top
回复人： ALNG(?) ( ) 信誉：100 2002-8-20 17:20:18 得分:30
好，mathe兄也加入了。 这个解与当前最优解相同了，期待进一步突破。
Top
回复人： mathe() ( ) 信誉：100 2002-8-20 17:22:46 得分:0
1,3,8,16,30,53,78,104,137,190,237,294,322,437,492,590,718,762,827,933,1000,1041,1272,1345,1377,1411,1469,1500,1538,1556,1580,1599,1610,1616,1619,1620
Top
回复人： mathe() ( ) 信誉：100 2002-8-20 17:32:36 得分:0
1,3,8,16,30,53,78,104,137,190,237,294,322,447,526,542,694,788,859,961,1007,1187,1263,1336,1368,1402,1460,1491,1529,1547,1571,1590,1601,1607,1610,1611
Top
回复人： ALNG(?) ( ) 信誉：100 2002-8-20 17:44:14 得分:0
哇赛！ 用的是什么算法啊？
Top
回复人： ALNG(?) ( ) 信誉：100 2002-8-20 17:48:17 得分:0
mathe兄的解好像有个特点，小的差值分布在两头。
象这个：
2 5 8 14 23 25。。。。。。。。6 3 1
Top
回复人： mathe() ( ) 信誉：100 2002-8-20 18:14:20 得分:50
那是因为其他解没有时间去搜索，对于n=36,实在速度太慢了
Top
回复人： mathe() ( ) 信誉：100 2002-8-20 19:12:57 得分:0
1,3,8,16,30,53,78,104,137,190,237,294,322,549,647,702,873,885,982,1031,1077,1183,1254,1327,1359,1393,1451,1482,1520,1538,1562,1581,1592,1598,1601,1602
Top
回复人： laozi(老子) ( ) 信誉：100 2002-8-20 20:09:48 得分:0
看了mathe()的答案，我的想法是这道题可化为对35个差数的分析。
也就是使35个不同的数的序列的和最小，其条件是任意个连续的数之和都不能是35个数中一个数。
mathe()兄开阔了我们的思路。
Top
回复人： ALNG(?) ( ) 信誉：100 2002-8-20 20:29:21 得分:0
确实，学好数学(mathe)很重要的哟！
Top
回复人： gofor() ( ) 信誉：100 2002-8-20 23:03:00 得分:40
以下是我的试探算法，得到是最好结果是
1 2 4 8 13 30 38 82 100 141 154 164 197 212 243 285 361 385 412 462 587 634 648 753 857 924 943 1111 1149 1243 1259 1435 1518 1558 1593 1613
历时数小时。
const int u=10; //以下标u为界，其前面的元素采用回溯法，后面的元素采用贪婪法
const int maxn=36;
int m=1700; //存储目前等到的最好结果
bool a[10000];　//元素之差是否已存在
int b[maxn]={1}; //元素序列
bool found=false;
void f(int i)
{//已经放好b,求b[i+1]
int j,k;
if (i==u) {
for (j=i+1; j<maxn; j++) {
for (k=b[j-1]+1;k<m;k++){
for (i=0; i<j && !a[k-b]; i++);
if (i>=j) {
b[j]=k;
for (i=0; i<j; i++) a[k-b]=true;
break;
}
}
if (k>=m) break;
}
if (k<m) {
m=k;
for (j=0; j<maxn; j++) cout<<b[j]<<' ';
cout<<endl;
}
for (i=0; i<m; i++) a=false;
for (j=1; j<=u; j++)
for (k=0; k<j; k++)
a[b[j]-b[k]]=true;
return;
}
for (j=max(b+1,i*(i+1)/2+1); j<b+maxn+10/*此处可调整*/; j++) {
for (k=0; k<=i && !a[j-b[k]]; k++);
if (k>i) {//j无冲突
b[i+1]=j;
for (k=0; k<=i; k++) a[j-b[k]]=true; //mark
f(i+1);
for (k=0; k<=i; k++) a[j-b[k]]=false; //unmark
}
}
}
int main()
{
int i;
for (i=0; i<m; i++) a=false;
f(0);
cout<<"end";
cin>>i;
}
Top
回复人： ALNG(?) ( ) 信誉：100 2002-8-20 23:13:53 得分:0
好！
这是我对mathe 1602解的分析结果：[solute to mathe, and gofor too]
the input solution is:
1 3 8 16 30 53 78 104 137 190 237 294 322 549 647 702 873 885 982 1031 1077 1183 1254 1327 1359 1393 1451 1482 1520 1538 1562 1581 1592 1598 1601 1602
and the adjacent differences are:
2 5 8 14 23 25 26 33 53 47 57 28 227 98 55 171 12 97 49 46 106 71 73 32 34 58 31 38 18 24 19 11 6 3 1
the options made at each step are:
2 4 5 9 14 14 13 15 22 22 20 12 112 50 23 74 4 24 11 9 16 10 7 2 1 3 1 1 1 1 1 1 1 1 1
Top
回复人： ALNG(?) ( ) 信誉：100 2002-8-20 23:16:12 得分:0
这是对gofor兄的次好结果1613的分析。
the input solution is:
1 2 4 8 13 30 38 82 100 141 154 164 197 212 243 285 361 385 412 462 587 634 648 753 857 924 943 1111 1149 1243 1259 1435 1518 1558 1593 1613
and the adjacent differences are:
1 2 4 5 17 8 44 18 41 13 10 33 15 31 42 76 24 27 50 125 47 14 105 104 67 19 168 38 94 16 176 83 40 35 20
the options made at each step are:
1 1 1 1 7 1 19 6 16 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Top
回复人： ALNG(?) ( ) 信誉：100 2002-8-20 23:18:16 得分:0
这是我写的分析工具IUDA
//---------------------------------------------------------------------------
// IUDA - Increasing Uniqe Difference solution Analyer
// copyright alng 2002
//
// utility to analysis a solution to del_c_sharp's
// Increasing Unique Differences problem. [IUD]
//
// This program has not been extensively tested
// Bug reports is welcomed.
//
// usage: put a solution in a text file named
// IUDSol.txt in the same directory
// as this program, and run it
// The solution can be anything separated
// but make sure not to add row number, etc
//
#pragma hdrstop
#define _USE_OLD_RW_STL
// bitset of stlport seems buggy in c++builder 6,
// so use rw instead
#include <iostream>
#include <fstream>
#include <bitset>
#include <iterator>
#include <algorithm>
#include <numeric>
const size = 36, max_diff= 3000;
typedef std::bitset<max_diff> diff_set;
// 从输入文件当前位置起读入一个解[size 个无符号整数]
//
void read_solution(std::ifstream& inf,unsigned numbers[])
{
char c;
for(unsigned i=0; i<size; i++){
while( (c=inf.peek())<'1' || c>'9' )
inf.get(c);
inf>>numbers;
}
}
// 判断解的合法性
//
bool is_legal_solution(unsigned num[])
{
diff_set ds;
for(int i=0; i<size-1; i++)
for(int j=i+1; j<size; j++){
int diff =num[j]-num;
if(diff<=0)
// array passed to check are expected in ascending order!
return false;
if(ds[diff])
// there is a previous difference of diff
return false;
else
ds.set(diff);
}
return true;
}
// this struct is used to reduce calling parameters
//
struct aftp_param{
diff_set& ds;
unsigned *nums; // an array of 'size' element
unsigned position; // the position under examination
unsigned candidate; // the candidate to be examed;
aftp_param(diff_set& ads, unsigned *pnums):
ds(ads),nums(pnums){}
};
// return true if p.candidate is acceptable for p.pos
// and modify p.ds to reflect the acceptance
// of p.candidate if modify_ds is true;
// return false if otherwise and p.ds is untact
//
// [rem] this is a frequently used workhorse, so reduction
// in stack usage could be economic both in space
// and speed
//
bool acceptable_for_this_position(
aftp_param& p, bool modify_ds
){
int diff;
diff_set ds(p.ds);
for(unsigned i=0; i<p.position; i++){
// if candidate - p.nums is already
// in ds, then candidate cannot be placed here
diff = p.candidate - p.nums;
if(diff<=0 || ds[diff])
return false;
ds.set(diff);
}
if(modify_ds) p.ds = ds;
return true;
}
// 在特定的位置上，nums给出的解究竟选取了第几个
// 可行[不产生冲突]的数，我称之为option number
// 这个向量对于刻画一个解可能比adjacent difference
// 更有力，所以要分析一个解，不能不考虑其options 向量
//
void get_opts(unsigned nums[],unsigned opts[])
{
diff_set ds;
unsigned opt;
aftp_param p(ds,nums);
unsigned diff;
for(unsigned i=1; i<size; i++){ //对每一个决策点
//diff = nums-nums[i-1];
diff_set lds(ds);
p.position = i;
for(p.candidate=nums[i-1]+1,opt=1;
p.candidate != nums
p.candidate++
){
if(acceptable_for_this_position(p,false))
opt++;
}
// call to modify p.ds
(void)acceptable_for_this_position(p,true);
opts = opt;
}
}
#pragma argsused
int main(int argc, char* argv[])
{
unsigned numbers[size];
unsigned diffs[size];
unsigned opts[size];
// it's harmless to combine diffs and opts as one
// here I opt to differentiate them for readability
using namespace std;
ifstream inf("IUDSol.txt"
read_solution(inf,numbers);
if(!is_legal_solution(numbers)){
cout<<"this is not a good solution.";
return 1;
}
adjacent_difference(numbers,numbers+size,diffs);
cout<<"the input solution is:";
copy(numbers,numbers+size,
ostream_iterator<unsigned,char>(cout," &quot
);
cout<<"the adjacent differences are:";
copy(diffs+1,diffs+size,
ostream_iterator<unsigned,char>(cout," &quot
);
get_opts(numbers,opts);
cout<<"options made at each step are:";
copy(opts+1,opts+size,
ostream_iterator<unsigned,char>(cout," &quot
);
cout<<endl;
return 0;
}
//---------------------------------------------------------------------------
Top
回复人： gofor() ( ) 信誉：100 2002-8-20 23:20:47 得分:0
这是我的穷举算法，目前算出当n=13时，最大数为107，历时10分钟。
const int maxn=36;
int n=1;
bool a[10000];
int b[maxn]={1};
int c[maxn]={1,2,4,7,12,18,26,35,45,56,73,86,107};
bool found=false;
void f(int i)
{//b已放好，求b[i-1]
int j,x,y;
if (i==1) { //output b;
for (j=0; j<n; j++) cout<<b[j]<<' ';
cout<<endl;
c[n-1]=b[n-1];
found=true;
return;
}
y=c[i-1];
for (x = b-1; x>=y; x--) {
for (j=i; j<n && !a[b[j]-x] && x-1!=b[j]-x; j++);
if (j>=n && !a[x-1]) {
b[i-1]=x;
for (j=i; j<n; j++) a[b[j]-x]=true; //mark
a[x-1]=true;
f(i-1);
for (j=i; j<n; j++) a[b[j]-x]=false; //unmark
a[x-1]=false;
if (found) return; //只求一个解
}
}
}
int main(int argc, char* argv[])
{
int i;
for (n=2; n++){
cout<<"n="<<n<<endl;
for (i=0; i<3000; i++) a=false;
found = false;
for (b[n-1]=c[n-2]+n-1/*此处用到一个未经证明的假设，n-1改为1更严格，但速度慢些*/;!found; b[n-1]++) {
cout<<b[n-1]<<endl;
f(n-1);//注意进入函数f前，b[0]=1,b[n-1]均已放好
}
}
cout<<"end";
cin>>i;
}
Top
回复人： gofor() ( ) 信誉：100 2002-8-20 23:43:18 得分:0
ALNG，用你的分析工具分析mathe的结果不合适，但分析我的结果很对。
mathe的算法可能是先求出相临元素的差序列，再得出元素序列。在求差序列时，按递增次序，先放最前一个，再放最后一个；再放次最前，次最后；...交错进行，不断往中间靠，所以他的回溯也是从中间开始，由于规模太大，两端很难回溯到，其前12个，后14个均无变化。这种方法是有道理的，因为中间元素的间距比两端元素的间距大的概率要大些。
Top
回复人： gofor() ( ) 信誉：100 2002-8-21 0:08:29 得分:0
我试图发现一些解的分布规律时，发现这样的情况：
对n=12，最小的最大数是86，但不存在最大数为87~90的解序列，最大数为91时也仅有一对，为92时开始增多，有5对。
1 10 11 18 31 43 46 57 62 80 84 86
1 3 7 25 30 41 44 56 69 76 77 86
1 8 14 24 29 53 54 56 65 73 87 91
1 5 19 27 36 38 39 63 68 78 84 91
1 7 11 16 28 36 52 59 78 89 91 92
1 3 13 24 31 37 51 66 83 88 91 92
1 5 7 23 28 47 54 62 79 82 91 92
1 8 17 28 32 42 54 71 84 89 90 92
1 2 5 10 27 42 56 62 69 80 90 92
1 6 7 15 31 41 53 72 74 85 89 92
1 2 11 14 31 39 46 65 70 86 88 92
1 4 8 19 21 40 52 62 78 86 87 92
1 2 4 15 34 41 57 65 77 82 86 92
1 3 4 9 22 39 51 61 65 76 85 92
Top
回复人： mathe() ( ) 信誉：100 2002-8-21 7:35:48 得分:0
break through 1600
1,3,8,16,30,53,78,104,145,161,240,284,333,422,457,522,620,714,827,860,962,1053,1129,1214,1261,1320,1373,1404,1442,1460,1484,1503,1514,1520,1523,1524
Top
回复人： mathe() ( ) 信誉：100 2002-8-21 7:36:38 得分:0
Wa, near to 1500 now!
1,3,8,16,30,49,77,107,142,197,250,313,339,401,532,556,613,746,800,871,1041,1079,1121,1158,1236,1281,1330,1381,1413,1449,1465,1488,1499,1505,1508,1509
Top
回复人： mathe() ( ) 信誉：100 2002-8-21 7:43:10 得分:0
gofor说的很对，我是对差值成一个三角形形式然后进行分解，分解以后，搜索的顺序是从中间开始的。
Top
回复人： ALNG(?) ( ) 信誉：100 2002-8-21 8:41:45 得分:0
mathe加油！
gofor好样的，我要说的都被你说了。你的方法用我的工具一分析就很明白了，但是这种思路真的很不简单。应该是你的对偶规律的一个应用。
Top
回复人： mathe() ( ) 信誉：100 2002-8-21 8:46:51 得分:0
break through 1500
1,3,8,19,34,51,81,115,142,197,253,282,290,409,504,567,646,668,800,884,961,1044,1146,1159,1197,1272,1330,1389,1401,1429,1454,1475,1489,1495,1498,1499
Top
回复人： ywqzxj(午青) ( ) 信誉：100 2002-8-21 8:53:39 得分:0
厉害！加油！
Top
回复人： ALNG(?) ( ) 信誉：100 2002-8-21 9:00:30 得分:0
input solution:
1 3 8 16 30 53 78 104 145 161 240 284 333 422 457 522 620 714 827 860 962 1053 1129 1214 1261 1320 1373 1404 1442 1460 1484 1503 1514 1520 1523 1524
the options made at each step are:
2 4 5 9 14 14 13 21 4 29 18 18 33 11 14 25 22 26 6 12 10 9 5 3 3 1 1 1 1 1 1 1 1 1 1
input solution:
1 3 8 16 30 49 77 107 142 197 250 313 339 401 532 556 613 746 800 871 1041 1079 1121 1158 1236 1281 1330 1381 1413 1449 1465 1488 1499 1505 1508 1509
the options made at each step are:
2 4 5 9 11 16 15 15 26 22 26 10 16 49 6 8 34 14 10 31 8 2 1 5 4 1 1 2 1 1 1 1 1 1 1
Top
回复人： mathe() ( ) 信誉：100 2002-8-21 9:01:21 得分:0
1,3,8,19,36,55,87,95,151,213,251,306,332,389,474,581,596,716,837,994,1025,1059,1130,1203,1246,1283,1313,1374,1387,1416,1437,1462,1476,1482,1485,1486
And difference array:
2, 5, 11, 17, 19, 32, 8, 56, 62, 38, 55, 26, 57, 85, 107, 15, 120, 121, 157, 31, 34, 71, 73, 43, 37, 30, 61, 13, 29, 21, 25, 14, 6, 3, 1
Top
回复人： ALNG(?) ( ) 信誉：100 2002-8-21 9:10:54 得分:0
看起来lawrence兄的估计---最优解的最大值在1100左右是比较合理的。
mathe你好强啊！看起来数学的威力比CPU还要强啊！加油。
输入解:
1 3 8 16 30 53 78 104 145 161 240 284 333 422 457 522 620 714 827 860 962 1053 1129 1214 1261 1320 1373 1404 1442 1460 1484 1503 1514 1520 1523 1524
该解的路由选择如下:
2 4 5 9 14 14 13 21 4 29 18 18 33 11 14 25 22 26 6 12 10 9 5 3 3 1 1 1 1 1 1 1 1 1 1
输入解:
1 3 8 16 30 49 77 107 142 197 250 313 339 401 532 556 613 746 800 871 1041 1079 1121 1158 1236 1281 1330 1381 1413 1449 1465 1488 1499 1505 1508 1509
该解的路由选择如下:
2 4 5 9 11 16 15 15 26 22 26 10 16 49 6 8 34 14 10 31 8 2 1 5 4 1 1 2 1 1 1 1 1 1 1
输入解:
1 3 8 19 34 51 81 115 142 197 253 282 290 409 504 567 646 668 800 884 961 1044 1146 1159 1197 1272 1330 1389 1401 1429 1454 1475 1489 1495 1498 1499
该解的路由选择如下:
2 4 8 11 9 18 17 15 21 27 9 1 32 31 11 26 4 24 16 13 14 13 1 2 4 2 1 1 1 1 1 1 1 1 1
修改后的UDISA--解分析工具：[可一次性分析多个解。邻差没有多大意义，去掉了]
//---------------------------------------------------------------------------
// UDISA - Unique Differences Increasing Sequence solution Analyer
// copyright alng 2002
//
// utility to analysis a solution to del_c_sharp's
// Unique Differences Increasing Sequence problem. [UDIS]
//
// This program has not been extensively tested
// Bug report is welcomed.
//
// usage: put a solution in a text file named
// IUDSol.txt in the same directory
// as this program, and run it
// The solution can be anything separated
// but make sure not to add row number, etc
// mutiple solutions is accepted
//
#pragma hdrstop
#define _USE_OLD_RW_STL
// bitset of stlport seems buggy in c++builder 6,
// so use rw instead
#include <iostream>
#include <fstream>
#include <bitset>
#include <iterator>
#include <algorithm>
#include <numeric>
const size = 36, max_diff= 3000;
typedef std::bitset<max_diff> diff_set;
// 从输入文件当前位置起读入一个解[size 个无符号整数]
//
bool read_a_solution(std::ifstream& inf,unsigned numbers[])
{
char c;
for(unsigned i=0; i<size; i++){
while(!inf.eof() && (c=inf.peek())<'1' || c>'9' )
inf.get(c);
if(inf.eof())
return false;
inf>>numbers;
}
return true;
}
// 判断解的合法性
//
bool is_legal_solution(unsigned num[])
{
diff_set ds;
for(int i=0; i<size-1; i++)
for(int j=i+1; j<size; j++){
int diff =num[j]-num;
if(diff<=0 || ds[diff])
// array passed to check are expected in ascending order!
// or there is a previous difference of diff
return false;
else
ds.set(diff);
}
return true;
}
// this struct is used to reduce calling parameters
//
struct aftp_param{
diff_set& ds;
unsigned *nums; // an array of 'size' element
unsigned position; // the position under examination
unsigned candidate; // the candidate to be examed;
aftp_param(diff_set& ads, unsigned *pnums):
ds(ads),nums(pnums){}
};
// return true if p.candidate is acceptable for p.pos
// and modify p.ds to reflect the acceptance
// of p.candidate if modify_ds is true;
// return false if otherwise and p.ds is untact
//
// [rem] this is a frequently used workhorse, so reduction
// in stack usage could be economic both in space
// and speed
//
bool acceptable_for_this_position(
aftp_param& p, bool modify_ds
){
int diff;
diff_set ds(p.ds);
for(unsigned i=0; i<p.position; i++){
// if candidate - p.nums is already
// in ds, then candidate cannot be placed here
diff = p.candidate - p.nums;
if(diff<=0 || ds[diff])
return false;
ds.set(diff);
}
if(modify_ds) p.ds = ds;
return true;
}
// 在特定的位置上，nums给出的解究竟选取了第几个
// 可行[不产生冲突]的数，我称之为option number
// 这个向量对于刻画一个解可能比adjacent difference
// 更有力，所以要分析一个解，不能不考虑其options 向量
//
void get_opts(unsigned nums[],unsigned opts[])
{
diff_set ds;
unsigned opt;
aftp_param p(ds,nums);
unsigned diff;
for(unsigned i=1; i<size; i++){ //对每一个决策点
//diff = nums-nums[i-1];
p.position = i;
for(p.candidate=nums[i-1]+1,opt=1;
p.candidate != nums
p.candidate++
){
if(acceptable_for_this_position(p,false))
opt++;
}
// call to modify p.ds
(void)acceptable_for_this_position(p,true);
opts = opt;
}
}
#pragma argsused
int main(int argc, char* argv[])
{
unsigned numbers[size];
unsigned diffs[size];
unsigned opts[size];
// it's harmless to combine diffs and opts as one
// here I opt to differentiate them for readability
using namespace std;
ifstream inf("IUDSol.txt"
while(read_a_solution(inf,numbers)){
cout<<"输入解:";
copy(numbers,numbers+size,
ostream_iterator<unsigned,char>(cout," &quot
);
cout<<endl;
if(!is_legal_solution(numbers)){
cout<<"这不是一个合法解.";
continue;
}
get_opts(numbers,opts);
cout<<"该解的路由选择如下:";
copy(opts+1,opts+size,
ostream_iterator<unsigned,char>(cout," &quot
);
cout<<endl;
}
return 0;
}
//---------------------------------------------------------------------------
Top
回复人： ALNG(?) ( ) 信誉：100 2002-8-21 10:23:54 得分:0
增加了对解的对偶解的同时分析，这样看来mathe的方法很有特色，其解和对偶解很相似，头尾小，中间大，后6-10位差不多都是1, 这种对称性说明其解已经比较靠近最优解[？]。
输入解:
1 3 8 16 30 53 78 104 145 161 240 284 333 422 457 522 620 714 827 860 962 1053 1129 1214 1261 1320 1373 1404 1442 1460 1484 1503 1514 1520 1523 1524
该解的路由选择如下:
2 4 5 9 14 14 13 21 4 29 18 18 33 11 14 25 22 26 6 12 10 9 5 3 3 1 1 1 1 1 1 1 1 1 1
其对偶解的路由选择如下:
1 2 3 5 11 12 7 19 8 17 20 15 26 19 28 28 13 21 19 18 10 3 11 6 2 2 1 1 1 1 1 1 1 1 1
输入解:
1 3 8 16 30 49 77 107 142 197 250 313 339 401 532 556 613 746 800 871 1041 1079 1121 1158 1236 1281 1330 1381 1413 1449 1465 1488 1499 1505 1508 1509
该解的路由选择如下:
2 4 5 9 11 16 15 15 26 22 26 10 16 49 6 8 34 14 10 31 8 2 1 5 4 1 1 2 1 1 1 1 1 1 1
其对偶解的路由选择如下:
1 2 3 5 13 9 17 16 23 21 16 31 13 9 7 44 17 8 24 8 1 12 6 2 2 1 1 1 1 1 1 1 1 1 1
输入解:
1 3 8 19 34 51 81 115 142 197 253 282 290 409 504 567 646 668 800 884 961 1044 1146 1159 1197 1272 1330 1389 1401 1429 1454 1475 1489 1495 1498 1499
该解的路由选择如下:
2 4 8 11 9 18 17 15 21 27 9 1 32 31 11 26 4 24 16 13 14 13 1 2 4 2 1 1 1 1 1 1 1 1 1
其对偶解的路由选择如下:
1 2 3 8 13 13 14 5 22 25 32 14 2 24 21 20 15 33 3 7 9 6 13 1 1 2 1 1 1 1 1 1 1 1 1
输入解:
1 3 8 19 36 55 87 95 151 213 251 306 332 389 474 581 596 716 837 994 1025 1059 1130 1203 1246 1283 1313 1374 1387 1416 1437 1462 1476 1482 1485 1486
该解的路由选择如下:
2 4 8 12 11 21 2 24 31 17 21 8 13 23 29 6 22 26 37 10 6 6 4 4 1 1 1 1 1 1 1 1 1 1 1
其对偶解的路由选择如下:
1 2 3 8 15 13 13 7 21 10 10 9 18 16 5 4 31 29 24 4 12 14 5 1 1 1 1 1 1 1 1 1 1 1 1
作为对比，看看gofor兄用另外一种也很有创造性的中间搜索法得到两组也比较好的解，其解和对偶解明显不对称:
输入解:
1 5 7 8 32 46 51 61 69 81 103 136 162 194 241 277 328 391 400 497 567 615 699 788 809 909 991 1077 1090 1155 1275 1291 1433 1510 1604 1632
该解的路由选择如下:
4 2 1 17 8 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
其对偶解的路由选择如下:
28 93 76 136 16 110 56 12 67 56 68 12 48 42 20 25 28 3 15 7 5 5 2 5 1 1 1 1 1 1 1 1 1 1 1
输入解:
1 2 4 8 13 21 31 45 79 105 143 188 230 245 270 298 350 383 404 476 552 625 684 706 802 852 888 1012 1111 1162 1375 1422 1483 1539 1578 1627
该解的路由选择如下:
1 1 1 1 1 1 1 8 6 9 8 9 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
其对偶解的路由选择如下:
49 39 53 57 44 189 48 84 98 32 35 61 11 28 36 34 28 6 8 6 4 3 1 1 1 1 1 1 1 1 1 1 1 1 1
Top
回复人： gofor() ( ) 信誉：100 2002-8-21 12:45:18 得分:0
我们等待mathe贴出完整程序
Top
回复人： mathe() ( ) 信誉：100 2002-8-21 13:11:25 得分:0
//This is one version of my code,
//I have used several versions.
//Since the it is impossible for computer to search all possible combination,
//I suggest you adding some other hints to constrain the searching space.
//In the following code, only a step is used so that each branch will only search for 2 most possible number.
#include <stdio.h>
#define MAX_SUM 10000
#include <stdio.h>
#define MAX_N 50
#define MAX_SUM 10000
char sum[MAX_N][MAX_SUM];
char dif[MAX_N][MAX_SUM];
int left[MAX_N];
int right[MAX_N];
int depth;
int max_n[MAX_N];
int l_index,r_index;
int n;
int dir;
int max_sum;
void init(){
int i,j;
memset(sum,0,sizeof(sum));
memset(dif,0,sizeof(dif));
memset(left,0,sizeof(left));
memset(right,0,sizeof(right));
memset(max_n,0,sizeof(max_n));
l_index=r_index=0;
dir=1;
sum[0][0]=1;
dif[0][0]=1;
max_sum=2*n*n;
depth=0;
if(max_sum>=MAX_SUM)
max_sum=MAX_SUM-1;
#if 0
left[0]=1;
left[1]=4;
left[2]=13;
left[3]=28;
right[0]=2;
right[1]=8;
right[2]=18;
right[3]=25;
l_index=r_index=4;
for(i=0;i<l_index;i++)for(j=0;j<r_index;j++){
int cur_sum=left+right[j];
if(cur_sum>max_n[0])max_n[0]=cur_sum;
sum[0][cur_sum]=1;
}
for(i=0;i<l_index;i++)for(j=0;j<i;j++){
int cur_dif=left-left[j];
dif[0][cur_dif]=1;
}
for(i=0;i<r_index;i++)for(j=0;j<i;j++){
int cur_dif=right-right[j];
dif[0][cur_dif]=1;
}
#endif
}
void check_result(){
int i,j;
int t=left[l_index-1]+right[r_index-1];
if(t>max_sum)
return;
if(t<max_n[depth])return;//in fact, array max_n does not needed anymore.
for(i=l_index;i<n-2;i++){
left=t - right[n-3-i];
if(left<=0)return;
if(sum[depth][left])//invalid
return;
sum[depth][left]=1;
for(j=0;j<n-3-i;j++){
if(left+right[j]>=t)
return;
if(sum[depth][left+right[j]])
return;
sum[depth][left+right[j]]=1;
}
}
for(i=r_index;i<n-2;i++){
right=t - left[n-3-i];
if(right<=0)return;
if(sum[depth][right])
return;
sum[depth][right]=1;
for(j=0;j<n-3-i;j++){
if(right+left[j]>=t)
return;
if(sum[depth][right+left[j]])
return;
sum[depth][right+left[j]]=1;
}
}
//a valid result found
printf("%d(%d)",n,t);
j=n-3;
for(i=0;i<n-3-j;i++)printf(" "
printf("%4d",t-left[j]);
for(i=1;i<=j;i++){
printf(",%4d",t-left[j-i]-right[i-1]);
}
printf(",%4d",t-right[j]);
j=1;
printf("%d",j);
for(i=0;i<=n-3;i++){
j+=t-left[n-3-i]-right[i-1];
printf(",%d",j);
}
j+=t-right[n-3];
printf(",%d",j);
fflush(stdout);
max_sum=t;
}
int exist_better(){
int left_count=n-1-l_index-r_index;
int prev=0;
int i,t;
if(l_index+r_index<=3)
return 1;
if(left_count<=1)return 1;
if(l_index>0)prev=left[l_index-1];
if(r_index>0&&prev<right[r_index-1])prev=right[r_index-1];
for(i=prev+1,t=0;i<max_sum;i++){
if(!sum[l_index+r_index]&&!dif[l_index+r_index]){
t++;
if(t==left_count-1)prev=i;
else if(t==left_count)
return t+prev<=max_sum;
}
}
return 0;
}
void search(){
// if(!exist_better())
// return;
if(dir<2){
int i,j;
int start;
int step=0;
l_index++;
depth++;
dir++;
if(l_index<=1)start=1;
else start=left[l_index-2]+1;
for(i=start;i<max_sum;i++){
if(sum[depth-1])continue;
if(dif[depth-1])continue;
for(j=0;j<r_index;j++){
if(i+right[j]>max_sum){
dir--;
l_index--;
depth--;
return;
}
if(sum[depth-1][i+right[j]])break;
}
if(j<r_index)continue;
for(j=0;j<l_index-1;j++){
if(dif[depth-1][i-left[j]])
break;
}
if(j<l_index-1)continue;
step++;
memcpy(sum[depth],sum[depth-1],sizeof(sum[0][0])*max_sum);
memcpy(dif[depth],dif[depth-1],sizeof(dif[0][0])*max_sum);
max_n[depth]=max_n[depth-1];
sum[depth]=1;
if(i>max_n[depth])
max_n[depth]=i;
for(j=0;j<r_index;j++){
sum[depth][i+right[j]]=1;
if(i+right[j]>max_n[depth])
max_n[depth]=i+right[j];
}
dif[l_index+r_index]=1;
for(j=0;j<l_index-1;j++){
dif[depth][i-left[j]]=1;
}
left[l_index-1]=i;
if(l_index+r_index==n-1){
check_result();
}else
search();
if(l_index+r_index!=n-1&&step==2)//do not constrain on step if we want to search for optimal result
break;
}
dir--;
l_index--;
depth--;
}else{
int i,j;
int start;
int step=0;
r_index++;
depth++;
dir++;
dir&=3;
if(r_index<=1)start=0;
else start=right[r_index-2]+1;
for(i=start;i<max_sum;i++){
if(sum[depth-1])continue;
if(dif[depth-1])continue;
for(j=0;j<l_index;j++){
if(i+left[j]>max_sum){
dir--;
dir&=3;
r_index--;
depth--;
return;
}
if(sum[depth-1][i+left[j]])break;
}
if(j<l_index)continue;
for(j=0;j<r_index-1;j++){
if(dif[depth-1][i-right[j]])break;
}
if(j<r_index-1)continue;
step++;
memcpy(sum[depth],sum[depth-1],sizeof(sum[0][0])*max_sum);
memcpy(dif[depth],dif[depth-1],sizeof(dif[0][0])*max_sum);
max_n[depth]=max_n[depth-1];
sum[depth]=1;
if(i>max_n[depth])
max_n[depth]=i;
for(j=0;j<l_index;j++){
sum[depth][i+left[j]]=1;
if(i+left[j]>max_n[depth])
max_n[depth]=i+left[j];
}
dif[depth]=1;
for(j=0;j<r_index-1;j++){
dif[depth][i-right[j]]=1;
}
right[r_index-1]=i;
if(l_index+r_index==n-1){
check_result();
}else
search();
if(l_index+r_index!=n-1&&step==2)
break;
}
dir--;
dir&=3;
r_index--;
depth--;
}
}
void main(){
n=36;
{
init();
search();
}
}
Top
回复人： mathe() ( ) 信誉：100 2002-8-21 13:15:35 得分:0
The following is all solution I found less than 1500
1,3,8,19,34,51,81,115,142,197,253,282,290,409,504,567,646,668,800,884,961,1044,1146,1159,1197,1272,1330,1389,1401,1429,1454,1475,1489,1495,1498,1499
1,3,8,16,30,53,78,127,158,192,249,295,333,384,505,564,605,754,766,839,951,998,1074,1176,1234,1289,1324,1390,1416,1434,1458,1477,1488,1494,1497,1498
1,3,8,16,30,53,79,141,153,199,267,301,352,383,442,511,546,723,820,836,1010,1043,1085,1165,1197,1264,1321,1362,1400,1428,1453,1472,1483,1489,1492,1493
1,3,8,16,30,53,78,104,172,206,241,298,356,388,464,547,631,664,832,911,955,1060,1088,1174,1220,1273,1329,1360,1409,1427,1451,1470,1481,1487,1490,1491
1,3,8,19,36,55,87,95,151,213,251,306,332,389,474,581,596,716,837,994,1025,1059,1130,1203,1246,1283,1313,1374,1387,1416,1437,1462,1476,1482,1485,1486
1,3,9,18,30,55,85,121,156,204,244,300,380,427,488,521,602,748,786,878,896,995,1074,1134,1185,1247,1291,1325,1384,1389,1415,1434,1447,1454,1457,1458
Top
回复人： ALNG(?) ( ) 信誉：100 2002-8-21 13:30:01 得分:0
well done, mathe!
one question, when did you start to study this problem?
Top
回复人： mathe() ( ) 信誉：100 2002-8-21 14:08:56 得分:0
Should be last Friday
Top
回复人： ywqzxj(午青) ( ) 信誉：100 2002-8-21 14:44:39 得分:0
mathe() 兄,能否指点一下,怎样用你的程序算得最优解(比如n=13)?
Top
回复人： mathe() ( ) 信誉：100 2002-8-21 16:23:34 得分:0
搜索最优解只要将我程序中所有用到step的代码去掉就可以了，不过程序的速度也不快，如果要计算n=13恐怕要花费很长时间。倒是我最早写的一个直接搜索的代码可以在几个小时内完成n=13,但是对于n=14也已经无能为力了。那个代码的优势是剪枝做的要好一些。我现在还不知道n=14时的最优解应该是多少
Top
回复人： qiushuiwuhen(秋水无恨) ( ) 信誉：100 2002-8-21 16:32:41 得分:0
n=14我算是129，不知道算不算最优
1,8,10,18,23,39,58,59,62,86,92,104,118,129
Top
回复人： orcsvr1() ( ) 信誉：100 2002-8-21 16:44:18 得分:0
1,3,8,16,30,49,77,112,142,167,199,288,356,393,501,580,611,681,743,871,944,1027,1118,1171,1213,1237,1249,1366,1392,1430,1446,1469,1480,1486,1489,1490
Top
回复人： bjay(ben) ( ) 信誉：100 2002-8-21 23:05:35 得分:0
to:mathe
which C compile and version are you using ?
Top
回复人： Lawrence444(胖子) ( ) 信誉：100 2002-8-21 23:11:42 得分:0
用ALNG的分析器分析8－13的第一个最优解如下。
输入解:
1 3 6 26 38 44 60 71 86 90 99 100 107
该解的路由选择如下:
2 2 17 9 3 9 2 2 1 1 1 1
输入解:
1 3 7 25 30 41 44 56 69 76 77 86
该解的路由选择如下:
2 3 15 3 6 2 2 1 1 1 1
输入解:
1 2 5 14 29 34 48 55 65 71 73
该解的路由选择如下:
1 2 6 9 2 4 2 1 1 1
输入解:
1 2 7 11 24 27 35 42 54 56
该解的路由选择如下:
1 4 3 6 2 1 1 1 1
输入解:
1 2 6 13 26 28 36 42 45
该解的路由选择如下:
1 3 4 7 1 2 1 1
输入解:
1 2 5 10 16 23 33 35
该解的路由选择如下:
1 2 2 2 1 1 1
大家有没有注意到第三个路由有一个大跳跃啊？
Top
回复人： mathe() ( ) 信誉：100 2002-8-22 8:19:24 得分:0
gcc 2.95.2
But the code I am running is slightly different(I am trying to use some different pruning method).
Now the best result I got is
1,3,8,16,32,54,79,120,172,184,227,297,356,405,433,477,579,664,678,821,917,984,1078,1111,1192,1248,1293,1316,1358,1390,1408,1427,1438,1444,1447,1448
I think it's near the limitation of such kinds of program. We need a better algorithm to break through 1400.
And the path selection in my algorithm is:
1,1,1,1,1,1,1,2,1,2,1,2,2,3,2,1,1,1,2,1,1,1,2,1,1,1,2,1,1,1,1,1,1,1
Top
回复人： ywqzxj(午青) ( ) 信誉：100 2002-8-22 8:36:29 得分:0
n=14, now,
1,5,7,21,36,53,60,78,79,87,90,100,123,128
请gofor()兄给出n=13之后的正确解.
Top
回复人： ywqzxj(午青) ( ) 信誉：100 2002-8-22 8:37:51 得分:5
n=14,
1,6,29,39,42,50,51,69,76,93,108,122,124,128
Top
回复人： ALNG(?) ( ) 信誉：100 2002-8-22 8:43:34 得分:0
Lawrence444(胖子)兄，你这个贴子含金量可真高啊！
mathe() 加油啊！想不到这么快就靠近1400了。
你的path selection定义好像很独特，能解释一下吗？
Top
回复人： mathe() ( ) 信誉：100 2002-8-22 10:28:15 得分:0
就是我代码中出现的step,将它变成一个数组来记录就可以了。
Top
回复人： ALNG(?) ( ) 信誉：100 2002-8-22 11:25:20 得分:0
mathe, 你的算法好厉害，一起动就到了1553， 不过现在僵在这里了。
Top
回复人： Lawrence444(胖子) ( ) 信誉：100 2002-8-22 11:47:47 得分:0
555, 我进化了1000代，进化出这么一个估值函数（化简以后）：
8*A2+3*A9（越大越好）
欲哭无泪。。。。
主要是采样分布不好，mathe的样本用的太多了，我再来搞一些比较次的样本加上去试试。
Top
回复人： xiaonian_3654(小周) ( ) 信誉：100 2002-8-22 14:09:37 得分:0
好热闹！up一下！
Top
回复人： ALNG(?) ( ) 信誉：100 2002-8-23 11:20:54 得分:0
看起来现在是举步维艰了。如果没有算法上的突破，更好的解是很难出来的了。
不管怎样，mathe的算法令人耳目一新。 我想del_c_sharp的300分应该按照赢家独得原则，全部给mathe。这个问题暂时告一段落，直到有人有更好的算法再重开讨论，大家觉得如何？
Top
回复人： JavaVsNet(JavaVsNet) ( ) 信誉：100 2002-8-23 18:41:18 得分:0
我觉得用他们的差值可以更直观的找这些数：
假如对5个数先给出他们之间的差值的初始值为：1，2，3，4；构造下列矩阵：
10 0 0 0
6 9 0 0
3 5 7 0
1 2 3 4
第一列可以认为是后四个数减第一个数的差
第二烈是后三个数减第二个数的差
如此类推；
其实这个矩阵反映的就是这五个数之间的差值。
现在只要使这个矩阵的下三角形中的数个不相同就求出了该数列，该数列为1和第一列个数加一的值。
优化这个矩阵的方法是：找出相同的数为一组，每组包含两个数（社为a(i,j)，b(x,y)),如果i-j>x-y,则对b所在的斜列与矩阵的对角线说组成的平行四边形内的所有数加一或者减去一，
其实本质就是增加或者减少数之间的差值
例如上例：
10 0 0 0
6 9 0 0
3 5 7 0
1 2 3 4
3与3成组，因为3-1<4-3,所以对平行四边形中的六个数：
10
6 9
5 7
3
各加一，得到新矩阵：
11 0 0 0
7 10 0 0
3 6 8 0
1 2 4 4
如此反复直到没有相同的数出现。
我现在还没想到应怎样判断什么时候对平行四边形中的数加一还是减去一。
我现在这里有一个只是用加一的c程序，比较粗糙，望大家对我的算法和程序给以改进：
#include <stdio.h>
#define N 35
void main()
{
int a[N][N];
int b[1000][3][2];
int i,j,i2,j2,bi,bj,n;
int c[1000];
int bk=0,ck=0,flag=1;
FILE *fp=fopen("hard.in","w"
printf(""
a[N-1][0]=1;
for(i=N-2;i>=0;i--) {
a[0][i+1]=0;
a[0]=a[i+1][0]+(N-1)-i+1;
}
for(i=0;i<N;i++)
printf("%d ",a[0]);
getch();
for(j=1;j<N;j++)
for(i=1;i<N;i++) {
if(i<j)
a[j]=0;
else if(i>=j)
a[j]=a[i-1][j-1]-a[N-1][j-1];
}
printf(""
printf("****************************************"
printf("****************************************"
for(i=0;i<N;i++) {
for(j=0;j<N;j++)
printf("%4d ",a[j]);
printf(""
}
printf("****************************************"
printf("****************************************"
getch();
/*$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$*/
bk=1;
while(bk!=0) {
bk=0;
printf("****************************************"
printf("****************************************"
for(i=0;i<N;i++) {
for(j=0;j<N;j++)
printf("%4d ",a[j]);
printf(""
}
printf("****************************************"
printf("****************************************"
for(j=0;j<N-1;j++)
for(i=j;i<N;i++)
for(j2=j+1;j2<N;j2++)
for(i2=j2;i2<N;i2++) {
/*if(i==9&&j==3&&i2==N-1&&j2==N-1) {
printf("[9][3]=%d , a[N-1][N-1]=%d",a[j],a[i2][j2]);
getch();
printf(""
}*/
if(a[j]==a[i2][j2]) {
b[bk][0][0]=i;
b[bk][0][1]=j;
b[bk][1][0]=i2;
b[bk][1][1]=j2;
bk++;
}
}
printf("bk=%d",bk);
if(bk==0)
break;
for(i=0;i<bk;i++) {
bi=b[0][0];
bj=b[0][1];
printf("%4d ",a[bi][bj]);
bi=b[1][0];
bj=b[1][1];
printf("%4d;;",a[bi][bj]);
}
printf(""
printf(""
for(i=0;i<bk;i++) {
if(b[0][0]-b[0][1]<b[1][0]-b[1][1]) {
b[2][0]=b[0][0];
b[2][1]=b[0][1];
}else{
b[2][0]=b[1][0];
b[2][1]=b[1][1];
}
}
for(i=0;i<bk;i++)
printf("#%d:%d,%d; ",i+1,b[2][0],b[2][1]);
printf(""
c[0]=b[0][2][0]-b[0][2][1];
ck++;
flag=1;
for(i=1;i<bk;i++) {
for(j=0;j<ck;j++) {
if(b[2][0]-b[2][1]==c[j])
flag=0;
}
if(flag){
c[ck]=b[2][0]-b[2][1];
ck++;
}
flag=1;
}
for(i=0;i<ck;i++)
printf("%d ",c);
printf(""
for(n=0;n<ck;n++)
for(j=0;j<=c[n];j++)
for(i=j;i<N-c[n]+j;i++)
a[i-j]++;
for(i=0;i<bk;i++)
for(j=0;j<3;j++)
for(n=0;n<2;n++)
b[j][n]=0;
for(i=0;i<ck;i++)
c=0;
ck=0;
}
printf(""
printf("1 "
fprintf(fp,"1 "
for(i=N-1;i>=0;i--) {
printf("%d ",a[0]+1);
fprintf(fp,"%d ",a[0]+1);
}
}
Top
回复人： kuchong(苦虫) ( ) 信誉：100 2002-8-24 15:07:41 得分:0
关注
Top
回复人： freshboy0913(红绿灯) ( ) 信誉：100 2002-8-24 16:17:19 得分:0
只谈穷举算法的穷举范围的确定：
首先这道题目从已经求得的部分位数较少的最优解序列中，（如n=1时为1，n=3时为1,2,4 n=5时...）目前最好的结果好像已有人求出n=13时的最优解了吧!从结果上来看基本上没有什么规律可言，除了穷举之外更巧妙的算法我好像还没有听人提过，也没人提出过正确的其他的解法，所以我看只有拼CPU了。
但也不是必须全部都举出来，从以前计算的结果看至少有两点假设可以值得研究：
（1）第n位上的解的最小值:由于n个递增的数共和n(n-1)/2个差值，很容易想到：当n=36时，至少有36(36-1)/2个差值即630个，即使这个解唯一（即合理的解只有一个时）第36位上的值也得630才能满足差值不重复的要求。但实际情况是当n>=5时解就不再唯一（虽最后一位的数是一定的），所以这个最小值还必须扩大才行。且出现了另一种情况：每一个解的每一个位上都有一个最小值（当然不同于上面所说的必须满足差值不重复而须有的最小值），n(1)>=1 n(2)>=2 n(3)>=4 n(4)>=7 n(5)>=12...n(12)>=86至于n(13)...n(36)我想同样有一个最小值,不过这个值暂时无法得到确却的值，不过根据后面的第（2）点假设我可以推出后面的值，第36位上的最小值是674（当然是指穷举应从这个数开始穷举）。
（2）第n位上的解的最大值:从以有的计算结果看：第n位上的解的取得最可能出现在Q(n-1)+n附近，我检验了从n=1到12时的所有解都满足这个假设：即n=6时的第6位上的解应在12+6附近（实际情况是解为18，最理想），n=7时的第7位上的解Q(7)=Q(6)+7=18+7=25附近，(实际情况是26)，再往后直到n=11时这个假设有一个偏差，但当n=12时，这一规律又出现了Q(12)=Q(11)+12=73+12=85附近（实际情况是解为86)。由此可以大胆的假定Q(13),Q(14）...Q(36),Q(37)，Q(38)时的解值区域。可以还求得Q(36)=674(最小值）,Q(37)=711,Q（38）=749,当Q(37)的解非常理想就是711时，Q(36)的解值区域为674..710,当Q(37)的解非常糟为748时，Q（36)的解值区域为674...747。
由此可以确定第36位上的解值区域为674...747)
----如果要穷举的话应从674这个数开始，请多见教
Top
回复人： Birch(白桦树) ( ) 信誉：100 2002-8-24 16:26:13 得分:0
关注！
Top
回复人： skyfine(skyfine) ( ) 信誉：100 2002-8-24 19:52:29 得分:0
非常佩服mathe() ,这个同题我也开过一个帖子。所以请在这个帖子结帖时，请一并到http://www.csdn.net/expert/topic/954/954010.xml?temp=.2789881接分。
Top
回复人： _Shakespeare(网络骑士) ( ) 信誉：100 2002-8-24 20:28:29 得分:0
关注
Top
回复人： mathe() ( ) 信誉：100 2002-8-26 8:25:38 得分:0
验证了一下，ywqzxj(午青) 提供的"1,5,7,21,36,53,60,78,79,87,90,100,123,128"的确是n=14时的最优解。
我们可以看到，在n>=12以后，最优解的差值分布中，小的数据已经不再留在边上了
12: 9, 1, 7, 13, 12, 3, 11, 5, 18, 4, 2
13: 7, 1, 9, 4, 15, 11, 16, 6, 12, 20, 3, 2
14: 5, 23, 10, 3, 8, 1, 18, 7, 17, 15, 14, 2, 4
所以，我上面的程序虽然可以快速搜索到较优的解，但是离最优解差距应该还非常之大。
Top
回复人： mathe() ( ) 信誉：100 2002-8-26 8:42:43 得分:0
想起了过去有人提到的计算costas矩阵的题目，http://www.csdn.net/expert/topic/663/663090.xml?temp=.3872187
那道题目也挺有意思，挺相似的。
看看是否有谁能够计算出一个24阶costas阵。
Top
回复人： ywqzxj(午青) ( ) 信誉：100 2002-8-26 9:06:24 得分:0
mathe()，我查看过你出过的一些很有意思的题目，比如田忌赛马，1234.-^()等，不如这样，把你出过的或者看到的有意思的题目一并归结到这里，好不好？
Top
回复人： mathe() ( ) 信誉：100 2002-8-26 9:22:05 得分:0
goto http://members.lycos.co.uk/huidu/
Top
回复人： Lawrence444(胖子) ( ) 信誉：100 2002-8-26 10:49:56 得分:0
mathe你是怎么验证的？穷搜么？
如果能有有效的验证算法的话，就应该可以有有效的求解算法吧。
Top
回复人： mathe() ( ) 信誉：100 2002-8-26 11:40:05 得分:0
穷举，花了1天半的时间
Top
回复人： javafish(小鱼儿) ( ) 信誉：100 2002-8-26 11:52:57 得分:0
收藏ing
Top
回复人： del_c_sharp(摩托～◎～◎～◎) ( ) 信誉：100 2002-8-27 23:06:09 得分:0
**************************************
最近很忙，好久没来了，来这里一看，感动、流泪。。。。
××××××××××××××××××××××××××××××××
to mathe：
谢谢老兄的努力，大家都看到你的成果。我同意ALNG(?) 的意见，这两个帖子我也该结了。
同样谢谢再次开帖讨论这个问题的几位老兄。希望大家继续关注。我会再次开帖，给大家讨论的空间！谢谢
Top
回复人： del_c_sharp(摩托～◎～◎～◎) ( ) 信誉：100 2002-8-27 23:16:09 得分:0
http://www.csdn.net/expert/topic/975/975461.xml?temp=.885647
Top
回复人： zhyx21century(zhyx) ( ) 信誉：100 2002-8-29 8:52:40 得分:0
..
Top
回复人： Dreamer7901() ( ) 信誉：100 2002-8-29 18:17:38 得分:0
我不明白为什么这么难。我记错题错了，算了一下32个数的数列，最后一个加数为190多（记不清了，在单位算的），数列中最后一个数10000左右。总共只算了不到1秒中。也许是我哪里想错了。现在我在网吧里，等我回家把算法程序和结果贴出来，让大家看看对不对。
Top
回复人： Dreamer7901() ( ) 信誉：100 2002-8-29 18:21:09 得分:0
不好意思，请斑竹把我的贴子删了吧！全想错了：（
Top
回复人： del_c_sharp(摩托～◎～◎～◎) ( ) 信誉：100 2002-8-29 20:59:36 得分:0
呵呵,没关系,继续!
Top
回复人： leeseon() ( ) 信誉：100 2002-8-30 22:07:11 得分:0
收藏先。
Top
回复人： 野男孩() ( ) 信誉：100 2002-8-31 10:00:51 得分:0
天啊,想自杀!
我算出来的是2027
Top
回复人： flyfash(生生之本,本立道生.山风山石山峦怪,河) ( ) 信誉：100 2002-8-31 14:24:49 得分:0
1,3,+4 7,+8 15,+16 (1+1+1=3)
4 5,6 8,9,10,11,12,13,14
31,+32 (3+1=4)
,18,19,20,21,22,23,24,25,26,27,28,29,30
63,+64 (4+1=5)
...
127,+128
... (5+1=6)
...min_number=64*(2^(32-5)) (31+1=32)
Top
回复人： o3y(想飞的菜鸟) ( ) 信誉：100 2002-8-31 16:38:09 得分:0
flyfash兄你那个min_number=64*(2^(32-5))=2^13也太大了吧，你看看楼上mathe兄给的解，才1400多
Top
回复人： intfree() ( ) 信誉：100 2002-9-2 18:27:34 得分:0
学过数学的就是不一样。
我一个搞数学竞赛的朋友，从我问他，没有2个小时，就手算（用计算器）出了一个1186的答案
Top
回复人： intfree() ( ) 信誉：100 2002-9-2 18:29:24 得分:0
1 5 46 64 151 161 200 324 345 378 400 407 467 498 510 513 566 571 579 598 636 650 680 700 728 775 855 861 951 1058 1067 1069 1092 1093 1109 1186
Top
回复人： intfree() ( ) 信誉：100 2002-9-2 18:42:05 得分:60
根据他的方法（虽然我完全不懂），用计算机得到一个序列
1 11 100 128 148 157 161 178 192 230 262 318 330 385 401 425 427 428 450 504 543 628 633 639 719 764 782 915 923 974 981 1027 1068 1087 1102 1149
Top
回复人： skyfine(skyfine) ( ) 信誉：100 2002-9-2 19:23:28 得分:0
能说说他的方法吗？
Top
回复人： gofor() ( ) 信誉：100 2002-9-2 19:29:54 得分:0
令我惊奇。结果完全正确。
请intfree公布算法。
Top
回复人： intfree() ( ) 信誉：100 2002-9-2 20:17:56 得分:0
是构造法，复杂度O(n^3)
{$APPTYPE CONSOLE}
const
n = 16;
p = n + 1; // p is a prime.
q = n * p;
type
Tans = array[1 .. n] of integer;
function pow(a, n, m: integer): integer; // return a^n mod m
var
i: integer;
begin
result := 1;
for i := 1 to n do
result := (result * a) mod m;
end;
function check(d: Tans): boolean; // check array d
var
used: array[0 .. q] of boolean;
i, j: integer;
begin
check := false;
fillchar(used, sizeof(used), false);
for i := 1 to n do
for j := i + 1 to n do
if not used[abs(d - d[j])] then
used[abs(d - d[j])] := true
else
exit;
check := true;
end;
procedure sort(var d: Tans); // sort array d
var
i, j, k: integer;
begin
for i := 1 to n do
for j := i + 1 to n do
if d > d[j] then
begin
k := d;
d := d[j];
d[j] := k;
end;
end;
var
d, best: Tans;
i, k, minp, now, v: integer;
begin
best[n] := maxint;
for i := 1 to n do
begin
// Construct
for k := 1 to n do
begin
d[k] := p * (k - 1) - (p - 1) * pow(i, k - 1, q);
d[k] := (d[k] mod q + q) mod q;
end;
// Adjust
sort(d);
minp := 0;
now := d[n] - d[1];
for k := 1 to n - 1 do
begin
v := d[k] - d[k + 1] + q;
if d[n] - d[k + 1] > v then
v := d[n] - d[k + 1];
if v < now then
begin
now := v;
minp := k;
end;
end;
now := d[minp + 1] - 1;
for k := 1 to n do
d[k] := ((d[k] - now) mod q + q) mod q;
sort(d);
// Update
if check(d) and (d[n] < best[n]) then
best := d;
end;
for i := 1 to n do
write(best, ' ');
writeln;
end.
Top
回复人： intfree() ( ) 信誉：100 2002-9-2 20:22:00 得分:0
复杂度还可以降到O(n^2logn)，找到两个：
1 11 100 128 148 157 161 178 192 230 262 318 330 385 401 425 427 428 450 504 543 628 633 639 719 764 782 915 923 974 981 1027 1068 1087 1102 1149
1 48 63 82 123 169 176 227 235 368 386 431 511 517 522 607 646 700 722 723 725 749 765 820 832 888 920 958 972 989 993 1002 1022 1050 1139 1149
他说中国队一次数学选拔赛（或类似的比赛）曾经考过，所以他一下子就做出来了。
（两个小时是手算啊）
Top
回复人： Lawrence444(胖子) ( ) 信誉：100 2002-9-2 21:21:12 得分:0
太强了！！！
是最优解么？
Top
回复人： Lawrence444(胖子) ( ) 信誉：100 2002-9-2 21:27:44 得分:0
一点都不懂。
有没有人可以解释一下？
Top
回复人： Lawrence444(胖子) ( ) 信誉：100 2002-9-2 21:29:22 得分:0
是不是和中国剩余定理有关？
Top
回复人： aliceZOOZ(alice) ( ) 信誉：100 2002-9-2 22:15:56 得分:0
第一行显然写错了，不是n=16，应该是n=36。
Top
回复人： intfree() ( ) 信誉：100 2002-9-2 22:58:54 得分:0
to aliceZOOZ(alice)：
是写错了，我调试的时候用的是n=16。
to Lawrence444(胖子)：
肯定不是最优解，这个序列是构造出来的，当n很小的时候，与最优解相差特别远。我估计n=36时，最优解在1000以下。
Top
回复人： mathe() ( ) 信誉：100 2002-9-3 7:50:57 得分:0
果然厉害！
这种解法的最强的地方就是一开始就求解不超过n(n+1)的解。而且这种方法本身能够找到的合法的解的数目也不会很多。
很有意思之处在于它将这道题同Costas阵联系了起来。（我在前几个星期提到过的）。
这种方法最难的还不在于它的构造性的解法，而是这方法的出发点就不是求最优解，而最后得到非常好的结果。
Top
回复人： mathe() ( ) 信誉：100 2002-9-3 8:08:29 得分:0
我可以解释一下这种方法的思路
这种方法只处理p=n+1是素数的情况。
首先，如果存在这样一个序列；而且最大数小于q=p(p-1)
那么，我们只要考虑满足同样条件的模q序列就可以了（不过其实这种说法是不完全正确的，这也是为什么我认为这种方法可以得到合法的解的数目不多的原因，这在后面再解释）。
命题1：对于任何小于q的数，我们可以唯一表示为
u*p+v*(p-1) mod(q)
其中0<=u<p-1,0<=v<p
命题2：如果一个p-1阶Costas阵列（http://www.csdn.net/expert/topic/663/663090.xml?temp=.3872187)
第i+1列非0数在v(i)行,那么，数列
i*p+v(i)*(p-1)mod(q), i=0,1,...,p-2
中任两个数的差关于模q互不相同。
命题3：如果p是素数，g为其一个原根，那么对于0<=i<p-1,
将p-1阶方阵第i+1列第g^i (mod p)行设为1，而这一列其它行的数据都是0，
那么得到的是一个p-1阶Costas阵列。
命题4：如果数列a(1),a(2),...,a(p-1)关于模q两两差互不相同，也就是
对于任何i<j, a(j)-a(i)(mod q)不会重复出现,那么，对于任何0<=b<q,
数列a(1)+b,a(2)+b,...,a(p-1)+b满足同样的性质。
还可以利用的一个性质是如果(d,q)=1,那么
d*a(1),d*a(2),...,d*a(p-1)也满足同样的性质。
Top
回复人： mathe() ( ) 信誉：100 2002-9-3 8:29:52 得分:0
现在分析一下为什么说这种方法得到的不是最优解。
1。在将任何一个数唯一分解为u*p+v*(p-1) (mod q)的形式后；
我们并没有要求不同的数对应的u和v都不相同，而只要有一个不同就可以了，而转化为Costas阵列以后，由于要求每一行每一列都只有一个1，也就是要求不同的数对应的u,v同时不相等，会丢失不少机会。
2。命题3构造Costas阵列的方法并不能得到所有的Costas阵列。而枚举所有的Costas阵列对于较大的n是一个还没有解决的问题。
3。这两个问题不完全等价，问题出在下面一句话：
>>如果存在这样一个序列；而且最大数小于q=p(p-1)
那么，我们只要考虑满足同样条件的模q序列就可以了.
实际上并非如此，这是因为我们需要对最终得到的模q序列进行重排序。
比如原先的序列是a(1),a(2),a(3),...,a(p-1)
在取了模q以后，我们需要对数列进行重新排列，为简单起见，假设重排序只改变了a(2)同a(1)的位置；那么在原先序列中，我们有
a(2)-a(1), a(3)-a(2),a(3)-a(1),...,互不相同，
而现在要求的是
a(1)-a(2), a(3)-a(2),a(3)-a(1),...,互不相同。
这就要求新出现的差值a(1)-a(2)=-(a(2)-a(1))同原先的差值都不会相同才行。（不然，上面的代码就不需要check函数了)
继续对我们的特殊序列分析这种交换对差值重复进行分析：
如果对于i>j, s<t有
a(i)-a(j)=a(s)-a(t)
即
(i-j)*p + (g^i-g^j)*(p-1) = (s-t)*p + (g^s - g^t)*(p-1) (mod q)
也就是
i-j = (p-1-s+t)
g^i - g^j = g^s - g^t (mod p)
i-t=j-s=(p-1)/2
也就是只有对那些距离正好是(p-1)/2的差值对，交换了其中一组数而没有交换另一组数，那么就会出现重复的差值。
而这样的差值对应该有C(p-1,2)/2=(p-1)(p-2)/4对，如果在重排序中各组差值对是否交换完全都独立，那么每一组都不交换的概率将非常之小，为
(1/2)^((p-1)(p-2)/4);所幸的是这些差值之间的相关性很强，按现在实际计算结果来看，还是存在解的，而且这是一个确定的问题，我们不能用概率来计算。但是是否对于一切的素数这样的解都存在，那就很难说了，需要进一步的分析。
Top
回复人： littlepu2001() ( ) 信誉：100 2002-9-3 13:58:49 得分:0
intfree老兄：
你的算法在n较小时得不到最优解，你能给出一个通用的算法，以满足对较小的n可以得到最优解（最好是所有最优解），而n较大时能得到较好的解甚至是最优解吗？谢谢！
Top
回复人： hquwl(东北大汉) ( ) 信誉：100 2002-9-3 15:09:32 得分:0
好热的题哦。
Top
回复人： mathe() ( ) 信誉：100 2002-9-3 15:43:42 得分:0
代碼中
if d[n] - d[k + 1] > v then
v := d[n] - d[k + 1];
没有必要
为了测试这段代码，我下载了一个Pascal编译器，结果发现对于n=36,上面的代码没有任何解。我修改了一下代码后，对于n=36就可以求出158种不重复的解。
不过用同样的代码试验n=40,42,46都没有解，看来n=36已经是最段代码可用的最大范围了，好像很凑巧。
program test;
const
n = 36;
p = n + 1; // p is a prime.
q = n * p;
type
Tans = array[1 .. n] of integer;
function pow(a, n, m: integer): integer; // return a^n mod m
var
i: integer;
begin
pow := 1;
for i := 1 to n do
pow := (pow * a) mod m;
end;
function check(d: Tans): boolean; // check array d
var
used: array[0 .. q] of boolean;
i, j: integer;
begin
check := false;
fillchar(used, sizeof(used), false);
for i := 1 to n do
for j := i + 1 to n do
if not used[abs(d - d[j])] then
used[abs(d - d[j])] := true
else
exit;
check := true;
end;
procedure sort(var d: Tans); // sort array d
var
i, j, k: integer;
begin
for i := 1 to n do
for j := i + 1 to n do
if d > d[j] then
begin
k := d;
d := d[j];
d[j] := k;
end;
end;
var
d, best: Tans;
i, k, minp, now, v,s,t: integer;
begin
best[n] := maxint;
for i := 1 to n do
begin
for s := 1 to n do
begin
for t := 1 to n do
begin
// Construct
for k := 1 to n do
begin
d[k] := s *p * (k - 1) - t*(p - 1) * pow(i, k - 1, q);
d[k] := (d[k] mod q + q) mod q;
end;
for now := 1 to n do
begin
minp :=d[now]-1;
for k := 1 to n do
d[k] := ((d[k] - minp) mod q + q) mod q;
sort(d);
// Update
if check(d) then
begin
for k :=1 to n do
write(d[k], ' ');
writeln();
end;
end;
end;
end;
end;
end.
Top
回复人： gofor() ( ) 信誉：100 2002-9-3 18:20:44 得分:0
是否有其他更好的构造函数呢？
Top
回复人： ALNG(?) ( ) 信誉：100 2002-9-3 18:54:47 得分:0
老天，几天没来，又有了这么大的突破。
数学真是太伟大了。
感谢intfree的参与。intfree也是我在这个论坛里很佩服的高手之一。
顺便说一下，在这个问题的探讨中，mathe, intfree, gofor, lawrence的表现令人侧目。
就象看金庸武侠，精彩迭出，一山更比一山高，真是过瘾！
Top
回复人： tender_edge(温柔一刀) ( ) 信誉：100 2002-9-4 18:50:02 得分:0
那是你的Pascal编译器太差了，原本的代码就可以得出有效解，
并且对于n=40,42,46也都有解
Top
回复人： gofor() ( ) 信誉：100 2002-9-4 22:35:26 得分:0
一个略次于1149的解：
1 13 29 77 115 122 130 252 254 258 399 400 430 449 467 472 496 556 583 634 666 784 793 845 855 888 899 924 945 958 980 1043 1057 1131 1148 1151
Top
回复人： aliceZOOZ(alice) ( ) 信誉：100 2002-9-5 8:16:50 得分:5
没有必要得到那么多解嘛，只要是最优解就可以了。
我一个同学说，只要i是n+1的原根，n+1是质数，就可以得到可行解。
他做过一道题目，就是求当n+1是质数时，求n个(0,n(n+1)]的数，满足条件，
解法和intfree的一样。
Top
回复人： ALNG(?) ( ) 信誉：100 2002-9-5 8:43:42 得分:0
aliceZOOZ(alice)， mathe好像讲过这样得到的不是最优解。
解释一下没什么不好吧，我想会来关注这个贴子的应该都希望知道算法的原理。
Top
回复人： mathe() ( ) 信誉：100 2002-9-5 9:47:36 得分:0
aliceZOOZ(alice)说的没错，只要i是n+1的原根，n+1是质数，就可以得到可行解（不是最优解）。我原先在分析中计算错了一步，而且我下载的Pascal编译器也欺骗了我（该死的16位编译器 ）。
证明在g是p=n+1的原根，对应的是一个可行解并不难
对于 0<=k<n，记
a[k]=p*k+(p-1)*g^k (mod q) (其中q=p*(p-1))
只要证明
对于一切0<=u,v,s,t<n
a-a[v]=a-a[t] （mod q) (1)
那么必然有
u=s且v=t
或者
u=v且t=s.
由(1)可以得到
p*(u-v)+(p-1)*(g^u-g^v)
=p*(s-t)+(p-1)*(g^s-g^t) (mod q)
两边同时对p-1求模，得到
u-v=s-t (mod p-1)
不妨设u>=s,记h=u-s,
那么v-t=u-s=h (mod p-1) (2)
对(1)式再两边同时对p求模，得到
g^u-g^s = g^v-g^t (mod p)
g^s*(g^(u-s)-1)=g^t(g^(v-t)-1) (mod p) (3)
由（2）可以知道
g^(u-s) = g^(v-t) (mod p)
所以必然有
g^s = g^t (mod p)
或则
g^(u-s)=1 (mod p)
这分别对应与s=t且u=v或u=s且t=v.
得证。
也就是对序列进行任意排序后都没有关系。
Top
回复人： bjay(ben) ( ) 信誉：100 2002-9-6 22:13:18 得分:0
这贴子已经到第3页了，顶上去。
BTW：在一个问题解不出最优解时，先找到解，再一步一步优化，也是一种方法。
Top
回复人： Lawrence444(胖子) ( ) 信誉：100 2002-9-7 21:39:59 得分:0
用了点动态规划的思想，我的搜索快了三倍。顺便顶顶帖。
这个算法可能可以搜15了。谁的机器快，可以试试。我这里只有450，搜13用了12分钟。
/* The always right complete search algorithm for hard problem
proposed by del_c_sharp */
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <iostream>
using namespace std;
int STOP;
int subval[1000]; // values generated by subtraction
int curlist[50],flist[50];
// flist stores the best list so far,
// curlist stores the current one
int marray[20][20];
// marray[j] denotes the smallest answer in i numbers
// without using ax-ay=z,z<=j
int mval;
// previous answers
const int prevans[50]={1,2,4,7,12,18,26,35,45,56,73,86,107,128};
double startc,end;
void startsearch(int n)
{
int start,i,j,k;
if(n>STOP){
if(curlist[n-1]<mval || mval==-1){
printf("%d",mval = curlist[n-1]);
printf("Current time: %.2f seconds",(float)(clock()-startc)/CLK_TCK);
memcpy(flist,curlist,n*sizeof(int));
for(i=1;i<=STOP;i++)
printf("%d ",flist);
printf(""
}
return;
}
for(k=1;k<STOP;k++)
if(!subval[k])
break;
start=curlist[n-1]+k;
if(k>19) // if too large
k=19; // use the ones we have
if(marray[STOP-n+1][k]==0) // if didn't calced
k=0; // use normal ones(prevans)
for(i=start;mval==-1 || i<mval-marray[STOP-n+1][k]+1;i++){
// if i is more than the maximum value to generate a better
// answer, no need to search anymore
curlist[n]=i;
if(n==2){
// the application of 对偶性
if(mval>0 && mval - curlist[2] - prevans[STOP-2] < curlist[2]-1)
break;
else
printf("Second place now searching: %d",i);
}
for(j=1;j<n;j++)
if(subval[curlist[n]-curlist[j]])
break;
if(j<n)
continue;
for(j=1;j<n;j++)
subval[curlist[n]-curlist[j]]++;
startsearch(n+1);
for(j=1;j<n;j++)
subval[curlist[n]-curlist[j]]=0;
if(n==STOP) // In the last step, it's no use to
break; // search for a further result
}
}
void main()
{
int i,j,k;
int rstop; // real stop
scanf("%d",&rstop);
memset(curlist,0,sizeof(curlist));
if(prevans[rstop-2]==0) // we don't search too big numbers!
return;
curlist[1]=1; // of course, the first item is 1
startc = clock();
for(i=0;i<14;i++)
marray[i+1][0]=prevans;
for(i=2;i<rstop/2+1;i++) // fill up marray
{
STOP=i;
for(j=1;j<20;j++)
{
mval = -1;
memset(subval,0,sizeof(subval));
for(k=1;k<=j;k++)
subval[k]=1;
startsearch(2);
marray[j]=mval;
}
}
mval = -1;
memset(subval,0,sizeof(subval));
STOP = rstop;
startsearch(2); // now real search
end = clock();
printf("%d",mval);
for(i=1;i<=STOP;i++)
printf("%d ",flist);
printf(""
printf("Time elapsed: %.2f seconds",(float)(end-startc)/CLK_TCK);
}
Top
回复人： gofor() ( ) 信誉：100 2002-9-8 7:50:00 得分:0
1 7 8 16 29 41 52 76 90 93 95 122 132 148 152
以上很可能是n=15时的最优解。之所以说“很可能”，是因为我用了几个未被证明的假设：
1、第1个差值小于第2个差值
2、使用1,2,4,9,13,22,33,42,54,70,77,100,123,138而不是1,2,4,7,12,18,26,35,45,56,73,86,107,128做为各位置的最小值。
3、仅搜索了142~152的区间。
历时约12小时。
Top
回复人： Lawrence444(胖子) ( ) 信誉：100 2002-9-8 15:49:00 得分:0
昨天晚上的程序有一个bug，改掉了。又增加了一下对偶性的利用，现在搜n=13用10分钟了（CPU: 450MHz)。
/* The always right complete search algorithm for hard problem
proposed by del_c_sharp */
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <iostream>
using namespace std;
int STOP;
int subval[1000]; // values generated by subtraction
int curlist[50],flist[50];
// flist stores the best list so far,
// curlist stores the current one
int marray[20][60];
// marray[j] denotes the smallest answer in i numbers
// without using ax-ay=z,z<=j
int mval;
// previous answers
const int prevans[50]={1,2,4,7,12,18,26,35,45,56,73,86,107,128};
double startc,end;
int verbose,maxj;
void startsearch(int n)
{
int start,i,j,k;
if(n>STOP){
if(curlist[n-1]<mval || mval==-1){
mval = curlist[n-1];
memcpy(flist,curlist,n*sizeof(int));
if(verbose){
printf("%d",mval);
printf("Current time: %.2f seconds",(float)(clock()-startc)/CLK_TCK);
for(i=1;i<=STOP;i++)
printf("%d ",flist);
printf(""
}
}
return;
}
for(k=1;k<STOP;k++)
if(!subval[k])
break;
start=curlist[n-1]+k;
k--;
if(k>=maxj) // if too large
k=maxj-1; // use the ones we have
if(marray[STOP-n+1][k]==0) // if not calced
k=0; // use prevans
for(i=start;mval==-1 || i<mval-marray[STOP-n+1][k]+1;i++){
// if i is more than the maximum value to generate a better
// answer, no need to search anymore
curlist[n]=i;
// the application of 对偶性
if(n<STOP-1 && mval>0 && mval - curlist[2] + 1 < i + marray[STOP-n+1][k])
break;
for(j=1;j<n;j++)
if(subval[curlist[n]-curlist[j]])
break;
if(j<n)
continue;
if(verbose && n<=3)
printf("Place %d now searching: %d",n,i);
for(j=1;j<n;j++)
subval[curlist[n]-curlist[j]]++;
startsearch(n+1);
for(j=1;j<n;j++)
subval[curlist[n]-curlist[j]]=0;
if(n==STOP) // In the last step, it's no use to
break; // search for a further result
}
}
void main()
{
int i,j,k;
int rstop; // real stop
scanf("%d",&rstop);
memset(curlist,0,sizeof(curlist));
memset(marray,0,sizeof(marray));
if(prevans[rstop-2]==0) // we don't search too big numbers!
return;
curlist[1]=1; // of course, the first item is 1
startc = clock();
for(i=0;i<14;i++)
marray[i+1][0]=prevans;
verbose=0;
maxj = (prevans[rstop-2]+rstop*1.5)/3;
for(i=2;i<rstop/2+1;i++) // fill up marray
for(STOP=i,j=1;j<maxj;j++){
mval = -1;
memset(subval,0,sizeof(subval));
for(k=1;k<=j;k++)
subval[k]=1;
startsearch(2);
marray[j]=mval;
}
mval = -1;
memset(subval,0,sizeof(subval));
STOP = rstop;
verbose=1;
startsearch(2); // now real search
end = clock();
printf("%d",mval);
for(i=1;i<=STOP;i++)
printf("%d ",flist);
printf(""
printf("Time elapsed: %.2f seconds",(float)(end-startc)/CLK_TCK);
}
Top
回复人： Lawrence444(胖子) ( ) 信誉：100 2002-9-8 17:29:37 得分:0
扑，gofor，还是你的算法好。
我用你的算法加上我的动态规划和对偶思想，n=13只用了370.25秒。按照咱俩机器速度的比例10:3计算，在你那里估计也就用不到两分钟。
不好意思再贴程序了，这两天贴了太多程序。