找回密码
 欢迎注册
查看: 19698|回复: 12

[游戏] 数字圆圈

[复制链接]
发表于 2008-10-8 21:45:03 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
请将 1~20 这 20 个数围成一个圆圈,
使得任意相邻的两个数字之和都是素数。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 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

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

  4. using namespace std;

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

  7. void PrimeRing( int n ){
  8.      int *a=new int[n+1], *l=new int[n+1], *u=new int[n+1];
  9.      int k, p, q;
  10.      for( k=0; k<n; ++k ) l[k]=k+1;
  11.      l[n]=0;
  12.      k=1;
  13. X2:  p=0; q=l[0];
  14. X3:  a[k]=q;
  15.      if( a[1]>1 ) goto X7;
  16.      if( !( k==1 || Prime[a[k-1]+a[k]] ) )
  17.          goto X5;
  18.      else
  19.          if( k==n && Prime[a[1]+a[n]] ){
  20.              copy( a+1, a+n+1, ostream_iterator<int>(cout," ") ),cout<<endl;
  21.              goto X6;
  22.          }
  23.      u[k]=p; l[p]=l[q]; ++k; goto X2;
  24. X5:  p=q; q=l[p]; if( q!=0 ) goto X3;
  25. X6:  --k;
  26.      if( k==0 ) return;
  27.      p=u[k], q=a[k], l[p]=q;
  28.      goto X5;
  29. X7:  delete []a; delete []u; delete []l;
  30. }

  31. int main( )
  32. {
  33.     PrimeRing( 20 );
  34.     system("PAUSE");
  35.     return EXIT_SUCCESS;
  36. }
复制代码

评分

参与人数 1威望 +1 鲜花 +1 收起 理由
gxqcn + 1 + 1 不错!:)

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-8 22:53:17 | 显示全部楼层
能证明当n为偶数时总存在解么?
呵呵,貌似大概率猜想成立的。
验证了n小于200时总是有解的。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-8 23:52:58 | 显示全部楼层
对2-398之间的偶数都验证了,均有解.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-9 00:12:10 | 显示全部楼层
或许证明是非常困难的,找到一点儿对此问题的讨论:
http://www.math.uiuc.edu/~west/openp/primegraph.html
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-9 08:16:45 | 显示全部楼层
呵,神速的程序,敬礼一个!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-9 08:45:10 | 显示全部楼层
证明太难,我曾经也是这样猜测的,验证了很多,没发现例外。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-9 08:54:51 | 显示全部楼层
还有个类似问题
素数阵问题:类似,1~N*N,这N*N个数填充在一个N*N的矩阵中,使得任意两个相邻数之和为素数。   
  问题:对于任意正整数N(N>=4)是否都可以找到解?
这里顶和底不相连,左右也不连,因此还不太像楼主的题目。改成在轮胎面上填数就更像是楼主问题的扩展了。

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

BTW,这论坛用的什么字体啊,怎么数字看起来那么奇怪,高低不齐、错落有致的。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-9 09:00:29 | 显示全部楼层
方阵的填充
我觉得失败的概率要大大增加了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-10-9 19:18:23 | 显示全部楼层
原帖由 风云剑 于 2008-10-9 08:54 发表
...
BTW,这论坛用的什么字体啊,怎么数字看起来那么奇怪,高低不齐、错落有致的。  


用的是“Georgia”字体,现仅在“默认模板”界面风格中采用,
它对英文字母表现得比较好,略有不足的是数字“0”与小写字母“o”易混淆。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-3-29 20:02 , Processed in 0.050326 second(s), 17 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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