免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
› 论坛 › 程序设计 › C/C++ › 将20个连续的自然数排成一圈，使任意两个相邻的自然数之 ...
12下一页
最近访问板块 发新帖
查看: 7100 | 回复: 12
打印 上一主题 下一主题

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

kdhoe

论坛徽章:
0
跳转到指定楼层
1楼 [收藏(0)] [报告]
发表于 2011-02-14 16:28 |只看该作者 |倒序浏览
原题目：

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

论坛徽章:
3
2015年迎新春徽章 日期:2015-03-04 09:56:11数据库技术版块每日发帖之星 日期:2016-08-03 06:20:00数据库技术版块每日发帖之星 日期:2016-08-04 06:20:00
2楼 [报告]
发表于 2011-02-14 16:43 |只看该作者
找出所有和为质数的数对,找Hamiton环
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
yg

论坛徽章:
0
3楼 [报告]
发表于 2011-02-14 23:20 |只看该作者
  1. #include<stdio.h>

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

  8. char *N_prime;
  9. char *N_stat;
  10. int *result;
  11. int layer;
  12. int cur;
  13. int n;

  15. void get_prime()
  16. {
  17.     int i, j, maxfact;

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

  31. void prt_result()
  32. {
  33.     int i;

  35.     for( i = 1; i <= n; i++ )
  36.         printf( "%d ", result[i] );
  37.     printf( "\n" );
  38.     return;
  39. }

  41. int getfirst( int bp )
  42. {
  43.     int i;

  45.     for( i = bp+1; i <= n; i++ )
  46.         if( is_free(i) )
  47.             break;
  48.     return(i);
  49. }

  51. int main( int ac, char **av )
  52. {
  53.     while(1)
  54.     {
  55.         printf( "n=" );
  56.         scanf( "%d", &n );
  57.         if( n == 0 )
  58.             exit(0);
  59.         if( ( N_stat = (char *) calloc( n+1, sizeof(char) ) ) == (char *) NULL )
  60.         {
  61.             perror("calloc");
  62.             exit(1);
  63.         }
  64.         if( ( result = (int *) calloc( n+1, sizeof(int) ) ) == (int *) NULL )
  65.         {
  66.             perror("calloc");
  67.             exit(1);
  68.         }
  69.         if( ( N_prime = (char *) calloc( 2*n, sizeof(char) ) ) == (char *) NULL )
  70.         {
  71.             perror("calloc");
  72.             exit(1);
  73.         }
  74.         get_prime();
  75.         cur = 1;
  76.         layer = 1;
  77.         while(1)
  78.         {
  79.             if( cur > n )
  80.             {
  81.                 if( layer == 2 )
  82.                 {
  83.                     printf( "seach is over\n" );
  84.                     break;
  85.                 }
  86.                 else
  87.                 {
  88.                     cur = result[--layer];
  89.                     clr_stat(cur);
  90.                     cur = getfirst(cur);
  91.                 }
  92.             }
  93.             else
  94.             {
  95.                 if( layer == 1 || is_prime( cur+result[layer-1] ) )
  96.                 {
  97.                     result[layer] = cur;
  98.                     if( layer == n )
  99.                     {
  100.                         if( is_prime( result[1]+result[layer] ) )
  101.                             prt_result();
  102.                         cur = n+1;
  103.                     }
  104.                     else
  105.                     {
  106.                         set_stat(cur);
  107.                         layer++;
  108.                         cur = getfirst(0);
  109.                     }
  110.                 }
  111.                 else
  112.                     cur = getfirst(cur);
  113.             }
  114.         }
  115.         free( N_stat );
  116.         free( result );
  117.         free( result );
  118.         free( N_prime );
  119.     }
  120.     return( 0 );
  121. }
复制代码
其实也不是很复杂。用递归写实很小的。这时用很早以前写的一个程序该的，用的是回溯。注意终止条件，如果不是环，结果将要长的多。
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
cjaizss

论坛徽章:
3
2015年迎新春徽章 日期:2015-03-04 09:56:11数据库技术版块每日发帖之星 日期:2016-08-03 06:20:00数据库技术版块每日发帖之星 日期:2016-08-04 06:20:00
4楼 [报告]
发表于 2011-02-14 23:36 |只看该作者
Hamiton环是NPC,
看运气了，否则非常慢
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
mcemil

论坛徽章:
0
5楼 [报告]
发表于 2011-02-15 08:36 |只看该作者
Hamiton环是NPC,
看运气了，否则非常慢
cjaizss 发表于 2011-02-14 23:36


一个完全图找hamilton环不就是回朔搜索了
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
cjaizss

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



    完全图还找啥hamilton?随便一个排列都是啦
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
wb112200

论坛徽章:
0
7楼 [报告]
发表于 2011-02-15 10:23 |只看该作者
三楼的 算法稍微复杂了点儿...
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
ecjtubaowp

论坛徽章:
1
CU十二周年纪念徽章 日期:2013-10-24 15:41:34
8楼 [报告]
发表于 2011-02-15 14:13 |只看该作者
模拟吧，数据不大
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
mcemil

论坛徽章:
0
9楼 [报告]
发表于 2011-02-15 16:49 |只看该作者
完全图还找啥hamilton?随便一个排列都是啦
cjaizss 发表于 2011-02-15 08:48


对奥，联通的条件是和是素数，不是完全图。不过仍然是搜索
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
cjaizss

论坛徽章:
3
2015年迎新春徽章 日期:2015-03-04 09:56:11数据库技术版块每日发帖之星 日期:2016-08-03 06:20:00数据库技术版块每日发帖之星 日期:2016-08-04 06:20:00
10楼 [报告]
发表于 2011-02-15 16:56 |只看该作者
本帖最后由 cjaizss 于 2011-02-21 10:24 编辑
原题目：

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



    写了一个代码:

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

  5. int map[21][10];
  6. int degree[21];


  9. int cur_pos[21];
  10. int ham[20];
  11. int ham_len;
  12. int cur_use[21];

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

  33. void create_map(void)
  34. {
  35.         int a[20];
  36.         int len;
  37.         int i,j,k;
  38.         len=create_prime(a,40);
  39.         for(i=1;i<21;i++) {
  40.                 degree[i]=0;
  41.                 for(j=0;j<len;j++) {
  42.                         k=a[j]-i;
  43.                         if(k<=0)
  44.                                 continue;
  45.                         else if(k<=20)
  46.                                 map[i][degree[i]++]=k;
  47.                         else
  48.                                 break;
  49.                 }

  51.         }
  52. }

  54. int main()
  55. {
  56.         int i,j;
  57.         create_map();
  58.         ham[0]=1;
  59.         ham_len=1;
  60.         for(i=0;i<21;i++)
  61.                 cur_use[i]=0;
  62.         cur_use[1]=1;

  64.         cur_pos[0]=0;
  65.         j=1;
  66.         while(1) {
  67.                 while(cur_pos[j]<degree[j]) {
  68.                         if(cur_use[map[j][cur_pos[j]]]==0) {
  69.                                 cur_use[map[j][cur_pos[j]]]=1;
  70.                                 ham[ham_len++] = map[j][cur_pos[j]];
  71.                                 break;
  72.                         }
  73.                         cur_pos[j]++;
  74.                 }
  75.                 if(cur_pos[j]<degree[j]) {/*break;*/
  76.                         if(ham_len==20 && map[ham[19]][0]==1) {
  77.                                 for(i=0;i<20;i++)
  78.                                         printf("%d->",ham[i]);
  79.                                 printf("\n");
  80.                         } else {
  81.                                 j=ham[ham_len-1];
  82.                                 cur_pos[j]=0;
  83.                                 continue;
  84.                         }
  85.                 }
  86.                 if(--ham_len <= 0)
  87.                         break;
  88.                 cur_use[ham[ham_len]]=0;
  89.                 j=ham[ham_len-1];
  90.                 cur_pos[j]++;
  91.         }


  94.         return 0;
  95. }

  97.    
复制代码
运行

  2. $ ./a.out | less
  3. 1->2->3->4->7->6->5->8->9->10->13->16->15->14->17->20->11->12->19->18->
  4. 1->2->3->4->7->6->5->8->9->10->13->16->15->14->17->20->11->18->19->12->
  5. 1->2->3->4->7->6->5->8->9->10->13->18->19->12->11->20->17->14->15->16->
  6. 1->2->3->4->7->6->5->8->9->10->19->12->11->20->17->14->15->16->13->18->
  7. 1->2->3->4->7->6->5->8->9->10->19->18->13->16->15->14->17->20->11->12->
  8. 1->2->3->4->7->6->5->8->9->14->15->16->13->10->19->12->17->20->11->18->
  9. 1->2->3->4->7->6->5->8->9->14->15->16->13->10->19->18->11->20->17->12->
  10. 1->2->3->4->7->6->5->8->9->14->15->16->13->18->11->20->17->12->19->10->
  11. 1->2->3->4->7->6->5->8->9->20->11->12->17->14->15->16->13->10->19->18->
  12. 1->2->3->4->7->6->5->8->9->20->11->12->17->14->15->16->13->18->19->10->
  13. 1->2->3->4->7->6->5->8->9->20->11->18->13->10->19->12->17->14->15->16->
  14. 1->2->3->4->7->6->5->8->9->20->11->18->13->16->15->14->17->12->19->10->
  15. 1->2->3->4->7->6->5->8->9->20->11->18->19->10->13->16->15->14->17->12->
  16. 1->2->3->4->7->6->5->8->9->20->11->18->19->12->17->14->15->16->13->10->
  17. 1->2->3->4->7->6->5->8->9->20->17->14->15->16->13->10->19->12->11->18->
  18. 1->2->3->4->7->6->5->8->9->20->17->14->15->16->13->10->19->18->11->12->
  19. 1->2->3->4->7->6->5->8->9->20->17->14->15->16->13->18->11->12->19->10->
  20. 1->2->3->4->7->6->5->8->11->12->17->20->9->14->15->16->13->10->19->18->
  21. 1->2->3->4->7->6->5->8->11->12->17->20->9->14->15->16->13->18->19->10->
  22. 1->2->3->4->7->6->5->8->11->12->19->10->9->20->17->14->15->16->13->18->
  23. 1->2->3->4->7->6->5->8->11->12->19->18->13->10->9->20->17->14->15->16->
  24. 1->2->3->4->7->6->5->8->11->12->19->18->13->16->15->14->17->20->9->10->
  25. 1->2->3->4->7->6->5->8->11->18->13->10->19->12->17->20->9->14->15->16->
  26. 1->2->3->4->7->6->5->8->11->18->13->16->15->14->9->20->17->12->19->10->
  27. 1->2->3->4->7->6->5->8->11->18->13->16->15->14->17->20->9->10->19->12->
  28. 1->2->3->4->7->6->5->8->11->18->19->10->13->16->15->14->9->20->17->12->
  29. 1->2->3->4->7->6->5->8->11->18->19->12->17->20->9->14->15->16->13->10->
  30. 1->2->3->4->7->6->5->8->11->20->9->10->13->16->15->14->17->12->19->18->
  31. 1->2->3->4->7->6->5->8->11->20->9->10->13->18->19->12->17->14->15->16->
  32. 1->2->3->4->7->6->5->8->11->20->9->10->19->12->17->14->15->16->13->18->
  33. 1->2->3->4->7->6->5->8->11->20->9->10->19->18->13->16->15->14->17->12->
  34. 1->2->3->4->7->6->5->8->11->20->17->12->19->10->9->14->15->16->13->18->
  35. 1->2->3->4->7->6->5->8->11->20->17->12->19->18->13->10->9->14->15->16->
  36. 1->2->3->4->7->6->5->8->11->20->17->12->19->18->13->16->15->14->9->10->
  37. 1->2->3->4->7->6->5->8->15->14->9->10->19->12->17->20->11->18->13->16->
  38. 1->2->3->4->7->6->5->8->15->14->9->20->17->12->11->18->19->10->13->16->
  39. 1->2->3->4->7->6->5->8->15->14->17->12->11->20->9->10->19->18->13->16->
  40. 1->2->3->4->7->6->5->8->15->14->17->12->19->10->9->20->11->18->13->16->
  41. 1->2->3->4->7->6->5->8->15->14->17->12->19->18->11->20->9->10->13->16->
  42. 1->2->3->4->7->6->5->8->15->14->17->20->9->10->19->12->11->18->13->16->
  43. 1->2->3->4->7->6->5->8->15->16->13->10->9->14->17->20->11->12->19->18->
  44. 1->2->3->4->7->6->5->8->15->16->13->10->9->14->17->20->11->18->19->12->
  45. 1->2->3->4->7->6->5->8->15->16->13->10->19->12->17->14->9->20->11->18->
  46. 1->2->3->4->7->6->5->8->15->16->13->10->19->18->11->20->9->14->17->12->
  47. 1->2->3->4->7->6->5->8->15->16->13->18->11->20->9->14->17->12->19->10->
  48. 1->2->3->4->7->6->5->8->15->16->13->18->11->20->17->14->9->10->19->12->
  49. 1->2->3->4->7->6->5->8->15->16->13->18->19->10->9->14->17->20->11->12->
  50. 1->2->3->4->7->6->5->8->15->16->13->18->19->12->11->20->17->14->9->10->
  51. 1->2->3->4->7->6->5->12->11->8->9->20->17->14->15->16->13->10->19->18->
  52. 1->2->3->4->7->6->5->12->11->8->9->20->17->14->15->16->13->18->19->10->
  53. 1->2->3->4->7->6->5->12->11->8->15->14->17->20->9->10->19->18->13->16->
  54. 1->2->3->4->7->6->5->12->11->20->17->14->9->8->15->16->13->10->19->18->
  55. 1->2->3->4->7->6->5->12->11->20->17->14->9->8->15->16->13->18->19->10->
  56. 1->2->3->4->7->6->5->12->11->20->17->14->15->8->9->10->19->18->13->16->
  57. 1->2->3->4->7->6->5->12->17->14->9->20->11->8->15->16->13->10->19->18->
  58. 1->2->3->4->7->6->5->12->17->14->9->20->11->8->15->16->13->18->19->10->
  59. 1->2->3->4->7->6->5->12->17->14->15->8->9->20->11->18->19->10->13->16->
  60. 1->2->3->4->7->6->5->12->17->14->15->8->11->20->9->10->19->18->13->16->
  61. 1->2->3->4->7->6->5->12->17->20->9->14->15->8->11->18->19->10->13->16->
  62. 1->2->3->4->7->6->5->12->17->20->11->8->9->14->15->16->13->10->19->18->
  63. 1->2->3->4->7->6->5->12->17->20->11->8->9->14->15->16->13->18->19->10->
  64. ...
复制代码
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
12下一页
返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

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

清除 Cookies - ChinaUnix - Archiver - WAP - TOP