当前位置: 代码迷 >> 综合 >> 搜素与回溯 素数环:
  详细解决方案

搜素与回溯 素数环:

热度:94   发布时间:2024-01-15 08:39:47.0

素数环:

从1到20这20个数摆成一个环,要求相邻的两个数的和是一个素数。

书上算法分析:

【算法分析】

非常明显,这是一道回溯的题目。从1开始,每个空位有20种可能,只要填进去的数合法:与前面的数不相同;与左边相邻的数的和是一个素数。第20个数还要判断和第1个数的和是否素数。

【算法流程】

1、数据初始化;   2、递归填数:判断第i个数填入是否合法;

A、如果合法:填数;判断是否到达目标(20个已填完):是,打印结果;不是,递归填下一个;

B、如果不合法:选择下一种可能;

代码实现:(自己手打一遍,加上自己的理解)

 

#include<bits/stdc++.h>
using namespace std;
bool b[21]={0};
int total=0,a[21]={0};
int print();             //输出答案
bool pd(int x,int y);    //判断素数
int search(int x);       //回溯方案
int main()
{search(1);cout<<total<<endl;    //这是总方案数return 0;
}
int search(int x)
{int i;for(i=1;i<=20;i++)if(pd(a[x-1],i)&&!b[i])//和是否为素数  该数是否可用{a[x]=i;          b[i]=1;if(x==20){pd(a[20],a[1]);print();}else search(x+1);b[i]=0;              //可以选择不用这个数,保证每种方案}
}
bool pd(int x,int y)
{int i=x+y,j=2;while(j<=sqrt(i)&&i%j!=0)j++;if(j>sqrt(i))  return 1;else       return 0;
}
int print()
{total++;cout<<"<"<<total<<">";    //第几种方案for(int j=1;j<=20;j++)    //素数圈cout<<a[j]<<" ";cout<<endl;
}

  相关解决方案