游游的排列统计

[编程题]游游的排列统计

热度指数：671 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

游游想知道，有多少个长度为 $n$ 的排列满足任意两个相邻元素之和都不是素数。你能帮帮她吗？

我们定义，长度为 $n$ 的排列值一个长度为 $n$ 的数组，其中1到 $n$ 每个元素恰好出现了一次。

输入描述:

一个正整数。

输出描述:

满足条件的排列数量。

示例1

输入

输出

说明

共有以下 4 种合法排列：
[1,3,5,4,2]
[3,1,5,4,2]
[2,4,5,1,3]
[2,4,5,3,1]

算法知识视频讲解

MoonHoplite

暴力枚举排列会超时，所以考虑回溯。当前选择的数字必须没有选择过，且与前一个数字的和不为素数（除非是第一个数）。

# Pypy3
prime = set([2, 3, 5, 7, 11, 13, 17, 19])
 
n = int(input())
 
ans = 0
path = [0] * n
on_path = [True] * (n + 1)
 
def dfs(i):
    if i == n:
        global ans
        ans += 1
        return
    for x in range(1, n + 1):
        if not i&nbs***bsp;(on_path[x] and x + path[i - 1] not in prime):
            on_path[x] = False
            path[i] = x
            dfs(i + 1)
            on_path[x] = True
dfs(0)
print(ans)

发表于 2025-02-07 16:48:00 回复(0)

来_offer来

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
void backtrack(vector<vector<int>>& damn,vector<int>& k,unordered_set<int> offer,unordered_set<int>& in,int index,int n)
{
if(k.size()==n)
{
damn.push_back(k);
return;
}
else {
for(int i=0;i<n;i++)
{
if(index==0)
{
k.push_back(i+1);
in.insert(i+1);
backtrack(damn,k,offer,in,index+1,n);
in.erase(i+1);
k.pop_back();
}
else {
if(offer.find(k[index-1]+i+1)!=offer.end()||in.find(i+1)!=in.end())
{

}
else {
k.push_back(i+1);
in.insert(i+1);
backtrack(damn,k,offer,in,index+1,n);
in.erase(i+1);
k.pop_back();
}
}
}
return;
}
}
int main() {
int n;
cin>>n;
vector<vector<int>> damn;
unordered_set<int> offer={1,3,5,7,11,13,17,19};
unordered_set<int> in;
vector<int> k;
int index;
backtrack(damn,k,offer,in,0,n);
int size=damn.size();
cout<<size<<endl;
// for(int i=0;i<size;i++)
// {
// int b=damn[i].size();
// for(int j=0;j<b;j++)
// {
// cout<<damn[i][j]<<" ";
// }
// cout<<endl;
// }
}

发表于 2025-03-24 16:40:45 回复(0)

OneNiP

#include <bits/stdc++.h>
using namespace std;
unordered_set<int> suShu = {2, 3, 5, 7, 11, 13, 17, 19};
int step = 0;
int pre = 0;
vector<int>used;
int res = 0;
int n;
void print(vector<int>v) {
for (int i = 0; i < v.size(); i++)cout << v[i] << ' ';
cout << endl;
}
void backtracking() {
if (step == n) {
res++;
return;
}
// print(path);
for (int i = 1; i <= n; i++) {
if (used[i])continue;
if (step && suShu.count(i + pre))continue;
int t = pre;
pre = i;
step++;
used[i] = 1;
backtracking( );
pre = t;
step--;
used[i] = 0;
}
}

int main() {
cin >> n;
used.resize(n + 1);
backtracking();
cout << res;
}
// 64 位输出请用 printf("%lld")

发表于 2024-06-25 11:25:24 回复(0)

RunnerQuan

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    private static int[] path;
    private static boolean[] visited; // visited[i]表示数字i是否被使用过
    private static int n;
    private static int ans;

    private static void dfs(int i) {
        if (i == n) {
            ans++;
            return;
        }

        for (int j = 1; j <= n; j++) {
            if (!visited[j]) {
                if (i > 0) {
                    if (!isPrime(path[i - 1] + j)) {
                        visited[j] = true;
                        path[i] = j;
                        dfs(i + 1);
                        visited[j] = false;
                    }
                } else {
                    visited[j] = true;
                    path[i] = j;
                    dfs(i + 1);
                    visited[j] = false;
                }
            }
        }
    }

    private static boolean isPrime(int num) {
        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            n = in.nextInt();
            path = new int[n];
            visited = new boolean[n + 1];
            dfs(0);
            System.out.println(ans);
        }
    }
}

发表于 2025-04-14 18:44:45 回复(0)

不会抓鱼的阿猫

回溯 + 剪枝

import java.util.*;
 
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static List<List<Integer>> res = new ArrayList<>();
    public static Deque<Integer> path = new LinkedList<>();
    public static boolean[] used;
 
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        used = new boolean[n + 1];
        for (List<Integer> list : res) {
            System.out.print(list.toString());
            System.out.println();
        }
 
        dfs(n);
        System.out.println(res.size());
    }
 
    public static void dfs(int n) {
        if (path.size() == n) {
            res.add(new ArrayList<>(path));
            return;
        }
 
        for (int i = 1; i <= n; i++) {
            if (used[i]) continue;
            if (!path.isEmpty() && isPrime(i + path.getLast())) continue;
            path.add(i);
            used[i] = true;
            dfs(n);
            used[i] = false;
            path.removeLast();
        }
    }
 
    public static boolean isPrime(int num) {
        if (num <= 1) return false;
        if (num <= 3) return true;
        if (num % 2 == 0 || num % 3 == 0) return false;
 
        for (int i = 5; i * i <= num; i += 6) {
            if (num % i == 0 || num % (i + 2) == 0) return false;
        }
        return true;
    }
}

发表于 2025-03-18 22:33:36 回复(0)