素数环问题

章泽天 2010-01-03 08:34:52
把从1到20这20个数摆成一个环，要求相邻的两个数的和是一个素数。请问如何用回溯法排列树搜索的思想编写这个题目的具体算法？
用回溯法搜索排列树的算法框架可描述如下：
void backtrack(int t)
{
if(t>n)
output(x)
else
for(int i=t;i<=n;i++)
{
swap(x[t],x[i]);
if(constraint(t)&&bound(t)) backtrack(t+1);
swap(x[t],x[i]);
}
}
用回溯法搜索子集树，本人已经会了，具体算法如下：
main()
{ int a[20],k;
for(k=1;k<=20;k++)
a[k]=0;
a[1]=1;
try(2);
}
try(int i)
{
int k
for(k=2;k<=20;k++)
if(check1(k,i)==1 and check3(k,i)==1)//判断与前面的数不相同、与前面相邻的数据的和是一个素数；两个函数不打了
{
a[i]=k;
if(i=20)
output();//输出符合要求的素数环
else
{
try(i+1);
a[i]=0;
}
}

...全文
1378 20 打赏 收藏 转发到动态 举报
写回复
用AI写文章
20 条回复
切换为时间正序
请发表友善的回复…
发表回复
chuanye001 2010-04-19
  • 打赏
  • 举报
 回复
mark and up!
medie2005 2010-01-04
  • 打赏
  • 举报
 回复
总共有6309300个解。
如果全部打印输出的话，要很久。
章泽天 2010-01-04
  • 打赏
  • 举报
 回复
说明：上面12楼程序的是按回溯法排列树的搜索方法进行搜索的！ 运行起来好像无数解，大家看一下有无逻辑错误
章泽天 2010-01-04
  • 打赏
  • 举报
 回复
我把我的程序贴出来大家看一下:运行好像是无数解，所以怀疑自己算法有问题
// primeCircle_cTree.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"


#include<stdio.h>
#include<math.h>
int a[21];
int check1(int i)//检测当前摆放的数字与前面的数字有无重复
{
int k;
for(k=1;k<=i-1;k++)
if(a[k]==a[i])
return 0;
return 1;
}
int check2(int x)//检测x是否为素数
{
int k,n;
n=sqrt(double(x));
for(k=2;k<=n;k++)
if(x%k==0)
return 0;
return 1;
}
int check3(int i)//检测与前面相邻的数据的和是否是素数
{
if(i<20)
return(check2(a[i]+a[i-1]));
else
return(check2(a[i]+a[i-1])&&check2(a[i]+a[1]));//特别要注意第20个数还要和第一个数判断是否是素数
}

void output()
{
int j;
for(j=1;j<=20;j++)
printf("%d,",a[j]);
return;
}
void swap(int t1,int t2)//数据交换 排列树的精华吧
{
int t;
t=a[t1];
a[t1]=a[t2];
a[t2]=t;
return ;
}
void try(int t)
{
int j;
if(t>20)
output();
else
{
for(j=t;j<=20;j++)
{
swap(t,j);
if(check1(t)==1 && check3(t)==1)
{
try(t+1);

}
swap(t,j);
}
}
return ;

}
void main()
{
int k;
for(k=1;k<=20;k++)//定义素数环初始排列顺序，1，2，3...20
a[k]=k;
try(1);
return ;
}
章泽天 2010-01-04
  • 打赏
  • 举报
 回复
[Quote=引用 10 楼 pmars 的回复:]
lz到底要做什么啊？想要要断程序么？呵呵，8楼的不就是了么？

之后，楼主的程序，定义了20大小的数组（0~19（数组下标）），遍历的时候却是1~20，呵呵！

别的不说了！
[/Quote]
我写的是算法 忘了注明：下标从1开始
pmars 2010-01-04
  • 打赏
  • 举报
 回复
lz到底要做什么啊？想要要断程序么？呵呵，8楼的不就是了么？

之后，楼主的程序，定义了20大小的数组（0~19（数组下标）），遍历的时候却是1~20，呵呵！

别的不说了！
Dolphin_001 2010-01-04
  • 打赏
  • 举报
 回复
[Quote=引用 7 楼 leezjnu008 的回复:]
这道题目来自 清华大学出版社  吕国英主编的算法分析与设计一书，书中给出了用回溯法子集树的具体算法，然后让读者用回溯法排列树的思想把算法写出来，本人写了一个，可是运行出来有无数个解。不知道问题出在哪里，我把回溯法按排列树思想的编写的算法贴出来，大家帮忙看一下~~~
[/Quote]
解是很多个，可以看成是无数个。打印几百行来看看就知道。。。
medie2005 2010-01-04
  • 打赏
  • 举报
 回复 
#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[n+1], *l=new int[n+1], *u=new int[n+1];

     int k, p, q;

     for( k=0; k<n; ++k ) l[k]=k+1;

     l[n]=0;

     k=1;

X2:  p=0; q=l[0];

X3:  a[k]=q;

     if( a[1]>1 ) goto X7;

     if( !( k==1 || Prime[a[k-1]+a[k]] ) )

         goto X5;

     else

         if( k==n && Prime[a[1]+a[n]] ){

             copy( a+1, a+n+1, ostream_iterator<int>(cout," ") ),cout<<endl;

             goto X6;

         }

     u[k]=p; l[p]=l[q]; ++k; goto X2;

X5:  p=q; q=l[p]; if( q!=0 ) goto X3;

X6:  --k;

     if( k==0 ) return;

     p=u[k], q=a[k], l[p]=q;

     goto X5;

X7:  delete []a; delete []u; delete []l;

}



int main( )

{

    PrimeRing( 20 );

    system("PAUSE");

    return EXIT_SUCCESS;

}
章泽天 2010-01-04
  • 打赏
  • 举报
 回复
这道题目来自 清华大学出版社 吕国英主编的算法分析与设计一书，书中给出了用回溯法子集树的具体算法，然后让读者用回溯法排列树的思想把算法写出来，本人写了一个，可是运行出来有无数个解。不知道问题出在哪里，我把回溯法按排列树思想的编写的算法贴出来，大家帮忙看一下~~~
zwen1573 2010-01-04
  • 打赏
  • 举报
 回复
看来这题解题思路很多，Mark!
章泽天 2010-01-04
  • 打赏
  • 举报
 回复
15楼 你说的很好 谢谢 程序的确有点小问题~~
章泽天 2010-01-04
  • 打赏
  • 举报
 回复
经过大家的讨论和自己试验的结果 我得出了结论：我的程序应该是正确的，当然大家贴出来的程序也是正确的，不过算法思想可能和我要求的不一样 导致我质疑自己程序的原因是因为在可忍受的时间范围内，运行无法结束。
再次感谢大家的热心帮助，你们的解题思路，开阔了我的思维方式。
donkey301 2010-01-04
  • 打赏
  • 举报
 回复
没看出什么大问题。
1. 你的check3(int i)的时候：


if(i <20)

return(check2(a[i]+a[i-1]));

i=1的情况你没考虑，i=1应该直接返回1。
2. 没必要检测当前摆放的数字与前面的数字有无重复，不可能重复的。
3. 判断素数如果换成8楼的列表就快多了。
4. 如果8楼的程序的解是6309300个的话，你解的个数应该是6309300*20,譬如1,2,3,4四个数，你还会把2,3,4,1
3,4,1,2
4,1,2,3
打印出来。不过8楼的程序为什么没有循环打印我也没看出来。

[Quote=引用 12 楼 leezjnu008 的回复:]
我把我的程序贴出来大家看一下:运行好像是无数解，所以怀疑自己算法有问题
// primeCircle_cTree.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"


#include <stdio.h>
#include <math.h>
int a[21];
int check1(int i)//检测当前摆放的数字与前面的数字有无重复
{
int k;
for(k=1;k <=i-1;k++)
if(a[k]==a[i])
return 0;
return 1;
}
int check2(int x)//检测x是否为素数
{
int k,n;
n=sqrt(double(x));
for(k=2;k <=n;k++)
if(x%k==0)
return 0;
return 1;
}
int check3(int i)//检测与前面相邻的数据的和是否是素数
{
if(i <20)
return(check2(a[i]+a[i-1]));
else
return(check2(a[i]+a[i-1])&&check2(a[i]+a[1]));//特别要注意第20个数还要和第一个数判断是否是素数
}

void output()
{
int j;
for(j=1;j <=20;j++)
printf("%d,",a[j]);
return;
}
void swap(int t1,int t2)//数据交换 排列树的精华吧
{
int t;
t=a[t1];
a[t1]=a[t2];
a[t2]=t;
return ;
}
void try(int t)
{
int j;
if(t>20)
output();
else
{
for(j=t;j <=20;j++)
{
swap(t,j);
if(check1(t)==1 && check3(t)==1)
{
try(t+1);

}
swap(t,j);
}
}
return ;

}
void main()
{
int k;
for(k=1;k <=20;k++)//定义素数环初始排列顺序，1，2，3...20
a[k]=k;
try(1);
return ;
}
[/Quote]

Dolphin_001 2010-01-03
  • 打赏
  • 举报
 回复
直接写了个递归的算法，不知对不对，好像有无数个组合
#include <cmath>
#include<iostream>
using namespace std;

#define COUNT 20
int data[2*COUNT];
int num[COUNT + 1];
int Count = 0;
void InitPrimeNum()
{
int i, j;
memset(data, 0, 2*COUNT);
int iUpLimit = (int)sqrt(2.0*COUNT);
for(i = 2; i <= iUpLimit; i++)
if(!data[i])
for(j = i * 2; j <= 2*COUNT; j += i)
data[j] = 1;
}

bool inline IsPrimeNum(int iNum)
{
if (data[iNum] == 0)
{
return true;
}
else
{
return false;
}
}

bool inline IsDiffren(int iCurOrder, int iCurNum)
{
for(int i = 1; i < iCurOrder; i++ )
if (num[i] == iCurNum)
{
return false;
}
return true;
}

void Print()
{
for(int i = 1; i <= COUNT; i++)
cout<<num[i]<<" ";
cout<<endl;
}

void SumOfBorderUponIsPrimeNum(int iCurOrder)
{
if (iCurOrder == COUNT + 1)
{
if(IsPrimeNum(num[COUNT] + num[1]))
{
Print();
Count++;
}
return;
}

for(int i = 1; i <= COUNT; i++)
{
num[iCurOrder] = i;
if (iCurOrder == 1)
{
SumOfBorderUponIsPrimeNum(iCurOrder + 1);
}
else if(IsDiffren(iCurOrder, i) && IsPrimeNum(i + num[iCurOrder - 1]))
{
SumOfBorderUponIsPrimeNum(iCurOrder + 1);
}
}
}

void InitNum()
{
memset(num, 0 , COUNT + 1);
}

void main()
{
InitPrimeNum();
InitNum();
SumOfBorderUponIsPrimeNum(1);
cout<<Count<<endl;
getchar();
}
pw_Start 2010-01-03
  • 打赏
  • 举报
 回复
这个题感觉不用那么麻烦吧
解个方程就可以出来吧
设n个数一圈，而且设这n个数依次为a1,a2,...,an
相邻两个的和为质数，一共有n个，不妨设这n个素数分别为x1,x2,...,xn
那么依据题意，应该满足
a1 + a2 = x1
a2 + a3 = x2
:
:
an + a1 = xn
把这个方程变形为
RA=X，其中A=[a1,a2,...,an]T，X=[x1,x2,...,xn]T
R为系数矩阵，从上面的方程可以直接写出来（这里不好排版，我就不写了）
然后可得A=(R^-1)X
其中R已知，R^-1（R的逆矩阵）也容易求出来，只要找n个素数，构造一个X就行了，
这样就可以得到一个A
FancyMouse 2010-01-03
  • 打赏
  • 举报
 回复
v=20的hamilton回路wwww
arong1234 2010-01-03
  • 打赏
  • 举报
 回复
所谓的环，无非增加一个1＋20是不是素数的判断而已
其他相邻两个数，挨个求和并判断素数而已
最大19＋20＝39，最小3，总共也就20组数
our2848884 2010-01-03
  • 打赏
  • 举报
 回复
学习！
liuy052 2010-01-03
  • 打赏
  • 举报
 回复
UP
c/c++解决素数环问题
c/c++解决素数环问题，深度优先搜索算法，算法设计与分析
求解素数环问题
求解素数环问题 数据结构代码，初级学习人员使用
Python实战--内置数据结构深入视频精讲
本课程的Python环境为：Python3.7，Jupyter 4.4.0，CentOS 7.xPython爬虫语言是 目前最火的语言之一。本课程为Python教程的内置数据结构篇，通篇围绕Python的数据结构展开讲解，包括七大数据结构：字符串、列表、元组、集合、字典、bytes、bytearray，最后通过3个经典案例：素数求解，杨辉三角，矩阵转置来强化大家的学习成果。同时通过大量具像化的实际案例来告诉大家每种数据结构的应用场景，为什么需要这么来做。让同学们能够从学习中感受到知识的建立，不让每一个知识点变成孤岛，从而导致学完后还是一头雾水。学习完本课程后，同学们可以有效的理解数据结构内在机理，深入掌握每一种数据结构在实际应用中的典型案例。
java求解素数环问题
java求解素数环经典问题，很好的算法设计，看看就知道了
数据结构与算法

33,010

社区成员

35,328

社区内容

发帖
与我相关
我的任务
社区描述
数据结构与算法相关内容讨论专区
社区管理员
  • 数据结构与算法社区
加入社区
  • 近7日
  • 近30日
  • 至今

加载中

查看更多榜单
社区公告
暂无公告

试试用AI创作助手写篇文章吧

+ 用AI写文章