weixin_43113933 2020-07-01 23:02 采纳率: 58.3%
浏览 190
已采纳

网络博客回溯法素数环问题疑惑?

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
using namespace std;
bool b[11]= {0};
int total=0,a[11]= {0};
int search(int);//回溯过程
int print();//输出方案
bool pd(int,int);//判断素数
int main()
{
    search(1);
    cout<<total<<endl;//输出总方案数
}
int search(int t)
{
    int i;
    for (i=1; i<=10; i++)//有20个数可选
        if (pd(a[t-1],i)&&(!b[i]))//判断与前一个数是否构成素数及该数是否可用
        {
            a[t]=i;
            b[i]=1;//跟着i标记
            if (t==10)
            {
                if (pd(a[10],a[1]))
                    print();
            }
            else
                search(t+1);
            b[i]=0;
        }
}
int print()
{
    total++;
    cout<<"<"<<total<<">";
    for (int j=1; j<=10; j++)
        cout<<a[j]<<" ";
    cout<<endl;
}
bool pd(int x,int y)
{
    int k=2,i=x+y;
    while (k<=sqrt(i)&&i%k!=0)//判断相邻数的和是否是素数
        k++;
    if (k>sqrt(i))
        return 1;
    else
        return 0;
}

以上是网上博客解决素数环的问题,我一直比较疑惑的点是最终的输出结果为什么只有1,2,3,5,7开头的,4,6,8,9,10开头的呢
当前结果6 1 10 7 4 9 2 3 8 5
当前结果6 1 10 7 4 9 8 3 2 5
当前结果6 1 10 9 2 5 8 3 4 7
当前结果6 1 10 9 8 5 2 3 4 7
比如以上也是满足的
另外一个穷举法

#include<iostream>
#include<algorithm>

using namespace std;

int A[100], isp[100], n;//isp是素数表,用于存放素数 

int is_prime(int x){
    for(int i = 2; i < x; i++){
        if(x % i == 0) return 0;
    }
    return 1;
}

void printPrime(){
    //生成第一个排列,顺序排列, A[1] = 1 A[2] = 2 
    for(int i = 1; i <= n; i++){
        A[i] = i;
    }
    do{
        bool ok = true;
        for(int i = 1; i < n; i++){
            int index = A[i]+A[i+1];
            if(!isp[index]){
                ok = false;
                break;
            }
        }
        //第一个和最后一个数的和 
        if(!isp[A[1] + A[n]]){
            ok = false;
        }
        if(ok){
            cout << "当前结果"; 
            for(int i = 1; i <= n; i++){
                cout << A[i] << " ";
            }
            cout << endl;
        }
    } while(next_permutation(A+2, A+n+1));//第一个一定为1不变,只更新第2个到最后1个的排列
}   //因为A[0]=0,A[1]=1

int main(){
    cin >> n;
    //记录1~n*2的值是否为素数 
    for(int i = 2; i <= n*2; i++){
        isp[i] = is_prime(i);
    }
    printPrime();
}

穷举法却可以有1到10开头的都有,我想不明白第一个程序为什么不能输出全部,实在想不明白,希望大佬指点一下,

  • 写回答

1条回答 默认 最新

  • 关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

    报告相同问题?

    问题事件

    • 已采纳回答 9月25日

    悬赏问题

    • ¥15 java为什么这个按钮监听事件不触发
    • ¥20 unity打光没有照亮物体
    • ¥25 powershell如何拷贝1周前的文件
    • ¥15 询问MYSQL查询SQLSERVER数据表并比较差异后,更新MYSQL的数据表
    • ¥15 关于#前端#的问题,请各位专家解答!
    • ¥15 最小生成树问题 Prim算法和Kruskal算法
    • ¥25 医院住院病人呼叫器设计
    • ¥15 不想和现在的团队合作了,怎么避免他们对程序动手脚
    • ¥20 C语言字符串不区分大小写字典排序相关问题
    • ¥15 关于#python#的问题:我希望通过逆向技术爬取1688搜索页下滑加载的数据