必威体育Betway必威体育官网
当前位置:首页 > IT技术

素数环

时间:2019-08-12 17:41:03来源:IT技术作者:seo实验室小编阅读:75次「手机版」
 

素数环

时限:1000ms 内存限制:10000K 总时限:3000ms

描述:

把1到20这重新排列,使得排列后的序列A满足:

a. 任意相邻两个数之和是素数

b. 不存在满足条件a的序列B使得:A和B的前k(0 <= k <= 19)项相同且B的第k+1项比A的第k+1项小。(即按字典序排列的第一项)

输入:

没有输入。

输出:

输出A,两个数字之间用一个空格隔开,第一个数字前面和最后一个数字后面没有空格。

code:

#include <iOStream>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
 
int a[21];
int cnt = 0;            //计数
bool isPrime(int n)
{
    int k = (int)sqrt(n*1.0);
    for(int i = 2; i <= k; i ++)
    {
        if(n%i == 0)
            return false;
    }
    return true;
}
 
void backtrack(int k)
{
 
    if(k > 20)
    {
        //判断环头和末是否满足
        if(!isPrime(a[1]+a[20]))
           return;
        cnt ++;
        if(isPrime(a[1]+a[20]) && cnt == 2)
        {
            cnt ++;
            for(int i = 1; i <= 20; i ++)
                printf("%d%c", a[i], i==20 ? '\n':' ');
            exit(0);                    //结束程序
        }
    }
    for(int i = k; i <= 20; i ++)
    {
        swap(a[k], a[i]);
        if(isPrime(a[k-1]+a[k]))
            Backtrack(k+1);
        swap(a[k], a[i]);               //回溯
    }
}
int main()
{
    for(int i = 1; i <= 20; i++)
        a[i] = i;
    Backtrack(2);
    return 0;
}

相关阅读

【openjudge】素数环

问题 A(2266): 【基础算法】素数环 时间限制: 5 Sec 内存限制: 128 MB 提交: 224 解决: 102 [提交][状态][我的提交] 题目描述

素数环

素数环NOJ1104回溯法应用,显然解空间是一个排列集,n最大为16,最大解空间为16!= 2*10^13(阶乘)。用next_permutation生成每排列,然后判断

分享到:

栏目导航

推荐阅读

热门阅读