首页 > 试题广场 >

小红的排列构造

[编程题]小红的排列构造

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

小红希望你构造一个排列，满足对于排列中的每一项 $a_i$ 都满足： $a_i+i$ 均不是质数（下标 $i$ 从1开始）。你能帮帮她吗？

长度为 $n$ 的排列是指：一个长度为 $n$ 的数组，其中1到 $n$ 每个正整数恰好出现1次。例如[2,1,3]是排列，而[1,3,4,3]不是排列。

输入描述:

一个正整数，代表待构造的排列长度。

输出描述:

如果无法构造，则输出-1。
否则输出一个长度为的满足要求的排列。有多解时输出任意即可。

示例1

输入

输出

-1

说明

长度为1的排列只有[1]，由于1+1=2是质数，不合法。所以不存在可以构造的排列。

示例2

输入

输出

9 4 6 2 1 8 3 10 7 5

说明

，不是质数。
，不是质数。
，不是质数。
以此类推，每个元素加上均不是质数。符合要求。

算法知识视频讲解

牛客276933196号

这个题是不是有问题

n=
1:无解
2:无解
3: 3 2 1
4: 3 2 1 4
5: 3 2 1 4 5
6: 3 2 1 4 5 6
n: 3 2 1 4 5 6 7 8 ....n

这不就是个解吗？

所以前面的我手动排一下，我后面的第i个位置上放i，和就是2i，肯定不是质数。

我没有理解错题意吧

除非再加个条件，第i个位置上不能放i

发表于 2023-06-20 16:59:53 回复(0)

说我这儿没问题啊的海豚很有力量

JAVA偶数放在偶数位奇数放在奇数位只需考虑位置0和1

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int a = in.nextInt();
int[] ans = new int[a];
if (a < 3) {
System.out.print(-1);
return;
}
for (int i = 0; i < a; i++) {
ans[i]= i+1;

}
if (a % 2 == 1) {

ans[0] = ans[a-1];
ans[a-1] = 1;
ans[1] = ans[a-2];
ans[a-2] =2;
}
if (a % 2 == 0) {
ans[0] = ans[a-2];
ans[a-2] = 1;
ans[1] = ans[a-1];
ans[a-1] = 2;
}
for (int i = 0; i < a; i++) {
System.out.print(ans[i]+" ");

}
}
}

发表于 2023-04-10 16:14:37 回复(0)

云溪浮

class xiaohong():
def __init__(self,n) -> None:
self.n = n
self.lis = []
self.list_xh()

def list_xh(self):
if n<=2:
return -1
elif n==3:
self.lis = [3,2,1]
return self.lis
else:
self.lis = [3,2,1] + [i for i in range(4,self.n+1)]
return self.lis

def print_func(self):
if self.n <= 2:
print(-1)
else:
print(' '.join(map(str,self.lis)))


n = int(input())

xiaohong(n).print_func()

如题，创建一个0到n的整数列表list，需要满足list【i】+ （i+1）的和不是质数（题意是下标从1开始，所以是i+1），所以只需要调整3、2、1这三个数的位置就可以，后面的 list【i】+（i+1）= 2*list【i】不会是质数；

发表于 2023-03-06 17:11:39 回复(0)

梅老板的粉

偶数在偶数位置上，奇数在奇数位置上。

#include <iostream>
#include <vector>
#include <climits>
#include <utility>
#include <cmath>
using namespace std;
int main() {
    int n;
    cin>>n;
    if (n < 3) {
        std::cout<<-1<<std::endl;
    }
    else {
        vector<int> v(n, 0);
        int oddIdx = 0, evenIdx = 1;
        while (n) {
            if (n%2 != 0) {
                v[oddIdx] = n;
                oddIdx += 2;
            }
            else {
                v[evenIdx] = n;
                evenIdx += 2;
            }
            --n;
        }
        for(auto&e: v) std::cout<<e<<" ";
        std::cout<<std::endl;
    }
    return 0;
}

发表于 2023-03-16 01:29:07 回复(0)

CodePanda

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    if(n<3){
        System.out.println(-1);
        return;
    }
    int[] ans = new int[n+1];
    //每个数加自身都是偶数，除了2以外的正偶数都是合数
    for(int i=1;i<=n;i++){
        ans[i] = i;
    }
    //因此只需要处理一下a1
    if(n%2==1){
        ans[1] = n;
        ans[n] = 1;
    }else{
        ans[1] = n-1;
        ans[n-1] = 1;
    }
    for(int i=1;i<=n;i++){
        System.out.print(ans[i]+" ");
    }
}

编辑于 2024-03-15 20:00:05 回复(0)

提交观点

问题信息

来自：22年秋招蚂蚁编程题精选

难度：

5条回答 19收藏 2712浏览

通过挑战的用户

查看代码

云溪浮

2023-03-06 16:58:33