gxqcn 发表于 2008-10-8 21:45:03

数字圆圈

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

medie2005 发表于 2008-10-8 22:16:48

给出一个满足条件的序数最小的排列：
1 2 3 4 7 6 5 8 9 10 13 16 15 14 17 20 11 12 19 18

全部解可以由下面这个程序得到：#include <iostream>
#include <iterator>
#include <windows.h>

using namespace std;

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,
             0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,0};

void PrimeRing( int n ){
   int *a=new int, *l=new int, *u=new int;
   int k, p, q;
   for( k=0; k<n; ++k ) l=k+1;
   l=0;
   k=1;
X2:p=0; q=l;
X3:a=q;
   if( a>1 ) goto X7;
   if( !( k==1 || Prime+a] ) )
         goto X5;
   else
         if( k==n && Prime+a] ){
             copy( a+1, a+n+1, ostream_iterator<int>(cout," ") ),cout<<endl;
             goto X6;
         }
   u=p; l=l; ++k; goto X2;
X5:p=q; q=l; if( q!=0 ) goto X3;
X6:--k;
   if( k==0 ) return;
   p=u, q=a, l=q;
   goto X5;
X7:delete []a; delete []u; delete []l;
}

int main( )
{
    PrimeRing( 20 );
    system("PAUSE");
    return EXIT_SUCCESS;
}

zgg___ 发表于 2008-10-8 22:53:17

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

medie2005 发表于 2008-10-8 23:52:58

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

zgg___ 发表于 2008-10-9 00:12:10

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

silitex 发表于 2008-10-9 08:16:45

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

风云剑 发表于 2008-10-9 08:45:10

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

风云剑 发表于 2008-10-9 08:54:51

还有个类似问题
素数阵问题：类似，1～N*N，这N*N个数填充在一个N*N的矩阵中，使得任意两个相邻数之和为素数。   
问题：对于任意正整数N(N>=4)是否都可以找到解？
这里顶和底不相连，左右也不连，因此还不太像楼主的题目。改成在轮胎面上填数就更像是楼主问题的扩展了。

再扩展就不好描述了，呵呵。

BTW，这论坛用的什么字体啊，怎么数字看起来那么奇怪，高低不齐、错落有致的。:Q:

无心人 发表于 2008-10-9 09:00:29

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

gxqcn 发表于 2008-10-9 19:18:23

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

用的是“Georgia”字体，现仅在“默认模板”界面风格中采用，
它对英文字母表现得比较好，略有不足的是数字“0”与小写字母“o”易混淆。
页: [1] 2
查看完整版本: 数字圆圈