数字圆圈

gxqcn

请将 1～20 这 20 个数围成一个圆圈， 使得任意相邻的两个数字之和都是素数。

medie2005

给出一个满足条件的序数最小的排列： 1 2 3 4 7 6 5 8 9 10 13 16 15 14 17 20 11 12 19 18 全部解可以由下面这个程序得到：

1. #include <iostream>
2. #include <iterator>
3. #include <windows.h>
5. using namespace std;
7. int Prime[]={0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,
8. 0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,0};
10. void PrimeRing( int n ){
11. int *a=new int[n+1], *l=new int[n+1], *u=new int[n+1];
12. int k, p, q;
13. for( k=0; k<n; ++k ) l[k]=k+1;
14. l[n]=0;
15. k=1;
16. X2: p=0; q=l[0];
17. X3: a[k]=q;
18. if( a[1]>1 ) goto X7;
19. if( !( k==1 || Prime[a[k-1]+a[k]] ) )
20. goto X5;
21. else
22. if( k==n && Prime[a[1]+a[n]] ){
23. copy( a+1, a+n+1, ostream_iterator<int>(cout," ") ),cout<<endl;
24. goto X6;
25. }
26. u[k]=p; l[p]=l[q]; ++k; goto X2;
27. X5: p=q; q=l[p]; if( q!=0 ) goto X3;
28. X6: --k;
29. if( k==0 ) return;
30. p=u[k], q=a[k], l[p]=q;
31. goto X5;
32. X7: delete []a; delete []u; delete []l;
33. }
35. int main( )
36. {
37. PrimeRing( 20 );
38. system("PAUSE");
39. return EXIT_SUCCESS;
40. }

复制代码

zgg___

能证明当n为偶数时总存在解么？ 呵呵，貌似大概率猜想成立的。 验证了n小于200时总是有解的。

medie2005

对2-398之间的偶数都验证了,均有解.

zgg___

或许证明是非常困难的，找到一点儿对此问题的讨论： http://www.math.uiuc.edu/~west/openp/primegraph.html

silitex

呵，神速的程序，敬礼一个！

风云剑

证明太难，我曾经也是这样猜测的，验证了很多，没发现例外。

风云剑

还有个类似问题 素数阵问题：类似，1～N*N，这N*N个数填充在一个N*N的矩阵中，使得任意两个相邻数之和为素数。 问题：对于任意正整数N(N>=4)是否都可以找到解？ 这里顶和底不相连，左右也不连，因此还不太像楼主的题目。改成在轮胎面上填数就更像是楼主问题的扩展了。 再扩展就不好描述了，呵呵。 BTW，这论坛用的什么字体啊，怎么数字看起来那么奇怪，高低不齐、错落有致的。

无心人

方阵的填充 我觉得失败的概率要大大增加了

gxqcn

原帖由 风云剑 于 2008-10-9 08:54 发表 ... BTW，这论坛用的什么字体啊，怎么数字看起来那么奇怪，高低不齐、错落有致的。

用的是“Georgia”字体，现仅在“默认模板”界面风格中采用， 它对英文字母表现得比较好，略有不足的是数字“0”与小写字母“o”易混淆。