免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
12下一页
最近访问板块 发新帖
查看: 7078 | 回复: 12

将20个连续的自然数排成一圈,使任意两个相邻的自然数之和均为素数 [复制链接]

论坛徽章:
0
发表于 2011-02-14 16:28 |显示全部楼层
原题目:

    将1,2,3,……,20这20个连续的自然数排成一圈,使任意两个相邻的自然数之和均为素数

论坛徽章:
3
2015年迎新春徽章
日期:2015-03-04 09:56:11数据库技术版块每日发帖之星
日期:2016-08-03 06:20:00数据库技术版块每日发帖之星
日期:2016-08-04 06:20:00
发表于 2011-02-14 16:43 |显示全部楼层
找出所有和为质数的数对,找Hamiton环

论坛徽章:
0
发表于 2011-02-14 23:20 |显示全部楼层
  1. #include<stdio.h>

  2. #define set_stat(x) N_stat[x]=1
  3. #define clr_stat(x) N_stat[x]='\0'
  4. #define is_free(x) (N_stat[x]=='\0')
  5. #define is_prime(x) (N_prime[x])

  6. char *N_prime;
  7. char *N_stat;
  8. int *result;
  9. int layer;
  10. int cur;
  11. int n;

  12. void get_prime()
  13. {
  14.     int i, j, maxfact;

  15.     memset( N_prime, 1, 2*n );
  16.     for( i = 2; i < n; i++ )
  17.     {
  18.         if( N_prime[i] == '\0' )
  19.               continue;
  20.         j = i;
  21.         while( ( j += i ) < 2*n )
  22.             N_prime[j] = '\0';
  23.     }
  24.     return;
  25. }

  26. void prt_result()
  27. {
  28.     int i;

  29.     for( i = 1; i <= n; i++ )
  30.         printf( "%d ", result[i] );
  31.     printf( "\n" );
  32.     return;
  33. }

  34. int getfirst( int bp )
  35. {
  36.     int i;

  37.     for( i = bp+1; i <= n; i++ )
  38.         if( is_free(i) )
  39.             break;
  40.     return(i);
  41. }

  42. int main( int ac, char **av )
  43. {
  44.     while(1)
  45.     {
  46.         printf( "n=" );
  47.         scanf( "%d", &n );
  48.         if( n == 0 )
  49.             exit(0);
  50.         if( ( N_stat = (char *) calloc( n+1, sizeof(char) ) ) == (char *) NULL )
  51.         {
  52.             perror("calloc");
  53.             exit(1);
  54.         }
  55.         if( ( result = (int *) calloc( n+1, sizeof(int) ) ) == (int *) NULL )
  56.         {
  57.             perror("calloc");
  58.             exit(1);
  59.         }
  60.         if( ( N_prime = (char *) calloc( 2*n, sizeof(char) ) ) == (char *) NULL )
  61.         {
  62.             perror("calloc");
  63.             exit(1);
  64.         }
  65.         get_prime();
  66.         cur = 1;
  67.         layer = 1;
  68.         while(1)
  69.         {
  70.             if( cur > n )
  71.             {
  72.                 if( layer == 2 )
  73.                 {
  74.                     printf( "seach is over\n" );
  75.                     break;
  76.                 }
  77.                 else
  78.                 {
  79.                     cur = result[--layer];
  80.                     clr_stat(cur);
  81.                     cur = getfirst(cur);
  82.                 }
  83.             }
  84.             else
  85.             {
  86.                 if( layer == 1 || is_prime( cur+result[layer-1] ) )
  87.                 {
  88.                     result[layer] = cur;
  89.                     if( layer == n )
  90.                     {
  91.                         if( is_prime( result[1]+result[layer] ) )
  92.                             prt_result();
  93.                         cur = n+1;
  94.                     }
  95.                     else
  96.                     {
  97.                         set_stat(cur);
  98.                         layer++;
  99.                         cur = getfirst(0);
  100.                     }
  101.                 }
  102.                 else
  103.                     cur = getfirst(cur);
  104.             }
  105.         }
  106.         free( N_stat );
  107.         free( result );
  108.         free( result );
  109.         free( N_prime );
  110.     }
  111.     return( 0 );
  112. }
复制代码
其实也不是很复杂。用递归写实很小的。这时用很早以前写的一个程序该的,用的是回溯。注意终止条件,如果不是环,结果将要长的多。

论坛徽章:
3
2015年迎新春徽章
日期:2015-03-04 09:56:11数据库技术版块每日发帖之星
日期:2016-08-03 06:20:00数据库技术版块每日发帖之星
日期:2016-08-04 06:20:00
发表于 2011-02-14 23:36 |显示全部楼层
Hamiton环是NPC,
看运气了,否则非常慢

论坛徽章:
0
发表于 2011-02-15 08:36 |显示全部楼层
Hamiton环是NPC,
看运气了,否则非常慢
cjaizss 发表于 2011-02-14 23:36


一个完全图找hamilton环不就是回朔搜索了

论坛徽章:
3
2015年迎新春徽章
日期:2015-03-04 09:56:11数据库技术版块每日发帖之星
日期:2016-08-03 06:20:00数据库技术版块每日发帖之星
日期:2016-08-04 06:20:00
发表于 2011-02-15 08:48 |显示全部楼层
一个完全图找hamilton环不就是回朔搜索了
mcemil 发表于 2011-02-15 08:36



    完全图还找啥hamilton?随便一个排列都是啦

论坛徽章:
0
发表于 2011-02-15 10:23 |显示全部楼层
三楼的 算法稍微复杂了点儿...

论坛徽章:
1
CU十二周年纪念徽章
日期:2013-10-24 15:41:34
发表于 2011-02-15 14:13 |显示全部楼层
模拟吧,数据不大

论坛徽章:
0
发表于 2011-02-15 16:49 |显示全部楼层
完全图还找啥hamilton?随便一个排列都是啦
cjaizss 发表于 2011-02-15 08:48


对奥,联通的条件是和是素数,不是完全图。不过仍然是搜索

论坛徽章:
3
2015年迎新春徽章
日期:2015-03-04 09:56:11数据库技术版块每日发帖之星
日期:2016-08-03 06:20:00数据库技术版块每日发帖之星
日期:2016-08-04 06:20:00
发表于 2011-02-15 16:56 |显示全部楼层
本帖最后由 cjaizss 于 2011-02-21 10:24 编辑
原题目:

    将1,2,3,……,20这20个连续的自然数排成一圈,使任意两个相邻的自然数之和均为素数
kdhoe 发表于 2011-02-14 16:28



    写了一个代码:

  1. #include <stdio.h>
  2. #include <stdlib.h>

  3. int map[21][10];
  4. int degree[21];


  5. int cur_pos[21];
  6. int ham[20];
  7. int ham_len;
  8. int cur_use[21];

  9. int create_prime(int*a,int max)
  10. {
  11.         int *x;
  12.         int i,j;
  13.         x=alloca(sizeof(int)*(max+1));
  14.         for(i=3;i<=max;i+=2)
  15.                 x[i]=1;
  16.         x[2]=1;
  17.         for(i=3;i<max/3;i+=2)
  18.                 for(j=i*3;j<=max;j+=i*2)
  19.                         x[j]=0;
  20.         j=0;
  21.         for(i=3;i<=max;i+=2)
  22.                 if(x[i]==1) {
  23.                         a[j++] = i;
  24.                 }
  25.         return j;
  26. }

  27. void create_map(void)
  28. {
  29.         int a[20];
  30.         int len;
  31.         int i,j,k;
  32.         len=create_prime(a,40);
  33.         for(i=1;i<21;i++) {
  34.                 degree[i]=0;
  35.                 for(j=0;j<len;j++) {
  36.                         k=a[j]-i;
  37.                         if(k<=0)
  38.                                 continue;
  39.                         else if(k<=20)
  40.                                 map[i][degree[i]++]=k;
  41.                         else
  42.                                 break;
  43.                 }

  44.         }
  45. }

  46. int main()
  47. {
  48.         int i,j;
  49.         create_map();
  50.         ham[0]=1;
  51.         ham_len=1;
  52.         for(i=0;i<21;i++)
  53.                 cur_use[i]=0;
  54.         cur_use[1]=1;

  55.         cur_pos[0]=0;
  56.         j=1;
  57.         while(1) {
  58.                 while(cur_pos[j]<degree[j]) {
  59.                         if(cur_use[map[j][cur_pos[j]]]==0) {
  60.                                 cur_use[map[j][cur_pos[j]]]=1;
  61.                                 ham[ham_len++] = map[j][cur_pos[j]];
  62.                                 break;
  63.                         }
  64.                         cur_pos[j]++;
  65.                 }
  66.                 if(cur_pos[j]<degree[j]) {/*break;*/
  67.                         if(ham_len==20 && map[ham[19]][0]==1) {
  68.                                 for(i=0;i<20;i++)
  69.                                         printf("%d->",ham[i]);
  70.                                 printf("\n");
  71.                         } else {
  72.                                 j=ham[ham_len-1];
  73.                                 cur_pos[j]=0;
  74.                                 continue;
  75.                         }
  76.                 }
  77.                 if(--ham_len <= 0)
  78.                         break;
  79.                 cur_use[ham[ham_len]]=0;
  80.                 j=ham[ham_len-1];
  81.                 cur_pos[j]++;
  82.         }


  83.         return 0;
  84. }

  85.    
复制代码
运行

  1. $ ./a.out | less
  2. 1->2->3->4->7->6->5->8->9->10->13->16->15->14->17->20->11->12->19->18->
  3. 1->2->3->4->7->6->5->8->9->10->13->16->15->14->17->20->11->18->19->12->
  4. 1->2->3->4->7->6->5->8->9->10->13->18->19->12->11->20->17->14->15->16->
  5. 1->2->3->4->7->6->5->8->9->10->19->12->11->20->17->14->15->16->13->18->
  6. 1->2->3->4->7->6->5->8->9->10->19->18->13->16->15->14->17->20->11->12->
  7. 1->2->3->4->7->6->5->8->9->14->15->16->13->10->19->12->17->20->11->18->
  8. 1->2->3->4->7->6->5->8->9->14->15->16->13->10->19->18->11->20->17->12->
  9. 1->2->3->4->7->6->5->8->9->14->15->16->13->18->11->20->17->12->19->10->
  10. 1->2->3->4->7->6->5->8->9->20->11->12->17->14->15->16->13->10->19->18->
  11. 1->2->3->4->7->6->5->8->9->20->11->12->17->14->15->16->13->18->19->10->
  12. 1->2->3->4->7->6->5->8->9->20->11->18->13->10->19->12->17->14->15->16->
  13. 1->2->3->4->7->6->5->8->9->20->11->18->13->16->15->14->17->12->19->10->
  14. 1->2->3->4->7->6->5->8->9->20->11->18->19->10->13->16->15->14->17->12->
  15. 1->2->3->4->7->6->5->8->9->20->11->18->19->12->17->14->15->16->13->10->
  16. 1->2->3->4->7->6->5->8->9->20->17->14->15->16->13->10->19->12->11->18->
  17. 1->2->3->4->7->6->5->8->9->20->17->14->15->16->13->10->19->18->11->12->
  18. 1->2->3->4->7->6->5->8->9->20->17->14->15->16->13->18->11->12->19->10->
  19. 1->2->3->4->7->6->5->8->11->12->17->20->9->14->15->16->13->10->19->18->
  20. 1->2->3->4->7->6->5->8->11->12->17->20->9->14->15->16->13->18->19->10->
  21. 1->2->3->4->7->6->5->8->11->12->19->10->9->20->17->14->15->16->13->18->
  22. 1->2->3->4->7->6->5->8->11->12->19->18->13->10->9->20->17->14->15->16->
  23. 1->2->3->4->7->6->5->8->11->12->19->18->13->16->15->14->17->20->9->10->
  24. 1->2->3->4->7->6->5->8->11->18->13->10->19->12->17->20->9->14->15->16->
  25. 1->2->3->4->7->6->5->8->11->18->13->16->15->14->9->20->17->12->19->10->
  26. 1->2->3->4->7->6->5->8->11->18->13->16->15->14->17->20->9->10->19->12->
  27. 1->2->3->4->7->6->5->8->11->18->19->10->13->16->15->14->9->20->17->12->
  28. 1->2->3->4->7->6->5->8->11->18->19->12->17->20->9->14->15->16->13->10->
  29. 1->2->3->4->7->6->5->8->11->20->9->10->13->16->15->14->17->12->19->18->
  30. 1->2->3->4->7->6->5->8->11->20->9->10->13->18->19->12->17->14->15->16->
  31. 1->2->3->4->7->6->5->8->11->20->9->10->19->12->17->14->15->16->13->18->
  32. 1->2->3->4->7->6->5->8->11->20->9->10->19->18->13->16->15->14->17->12->
  33. 1->2->3->4->7->6->5->8->11->20->17->12->19->10->9->14->15->16->13->18->
  34. 1->2->3->4->7->6->5->8->11->20->17->12->19->18->13->10->9->14->15->16->
  35. 1->2->3->4->7->6->5->8->11->20->17->12->19->18->13->16->15->14->9->10->
  36. 1->2->3->4->7->6->5->8->15->14->9->10->19->12->17->20->11->18->13->16->
  37. 1->2->3->4->7->6->5->8->15->14->9->20->17->12->11->18->19->10->13->16->
  38. 1->2->3->4->7->6->5->8->15->14->17->12->11->20->9->10->19->18->13->16->
  39. 1->2->3->4->7->6->5->8->15->14->17->12->19->10->9->20->11->18->13->16->
  40. 1->2->3->4->7->6->5->8->15->14->17->12->19->18->11->20->9->10->13->16->
  41. 1->2->3->4->7->6->5->8->15->14->17->20->9->10->19->12->11->18->13->16->
  42. 1->2->3->4->7->6->5->8->15->16->13->10->9->14->17->20->11->12->19->18->
  43. 1->2->3->4->7->6->5->8->15->16->13->10->9->14->17->20->11->18->19->12->
  44. 1->2->3->4->7->6->5->8->15->16->13->10->19->12->17->14->9->20->11->18->
  45. 1->2->3->4->7->6->5->8->15->16->13->10->19->18->11->20->9->14->17->12->
  46. 1->2->3->4->7->6->5->8->15->16->13->18->11->20->9->14->17->12->19->10->
  47. 1->2->3->4->7->6->5->8->15->16->13->18->11->20->17->14->9->10->19->12->
  48. 1->2->3->4->7->6->5->8->15->16->13->18->19->10->9->14->17->20->11->12->
  49. 1->2->3->4->7->6->5->8->15->16->13->18->19->12->11->20->17->14->9->10->
  50. 1->2->3->4->7->6->5->12->11->8->9->20->17->14->15->16->13->10->19->18->
  51. 1->2->3->4->7->6->5->12->11->8->9->20->17->14->15->16->13->18->19->10->
  52. 1->2->3->4->7->6->5->12->11->8->15->14->17->20->9->10->19->18->13->16->
  53. 1->2->3->4->7->6->5->12->11->20->17->14->9->8->15->16->13->10->19->18->
  54. 1->2->3->4->7->6->5->12->11->20->17->14->9->8->15->16->13->18->19->10->
  55. 1->2->3->4->7->6->5->12->11->20->17->14->15->8->9->10->19->18->13->16->
  56. 1->2->3->4->7->6->5->12->17->14->9->20->11->8->15->16->13->10->19->18->
  57. 1->2->3->4->7->6->5->12->17->14->9->20->11->8->15->16->13->18->19->10->
  58. 1->2->3->4->7->6->5->12->17->14->15->8->9->20->11->18->19->10->13->16->
  59. 1->2->3->4->7->6->5->12->17->14->15->8->11->20->9->10->19->18->13->16->
  60. 1->2->3->4->7->6->5->12->17->20->9->14->15->8->11->18->19->10->13->16->
  61. 1->2->3->4->7->6->5->12->17->20->11->8->9->14->15->16->13->10->19->18->
  62. 1->2->3->4->7->6->5->12->17->20->11->8->9->14->15->16->13->18->19->10->
  63. ...
复制代码
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP