首页 > 试题广场 >

小红的排列构造①

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

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

$\hspace{15pt}$ 小红希望你构造一个长度为 $n$ 的排列 $\{a_1,a_2,\dots,a_n\}$ ，使得对所有 $1 \leqq i \leqq n$ ，都有 $a_i+i$ 不是质数。
$\hspace{15pt}$ 长度为 $n$ 的排列是由 $1 \sim n$ 这 $n$ 个正整数按任意顺序组成的数组，其中每个整数恰好出现一次。

$\hspace{15pt}$ 【名词解释】
$\hspace{23pt}\bullet\,$ 质数：大于 $1$ 的正整数，如果它除了 $1$ 和自身外不再有其他正整数因子，则称为质数。
$\hspace{23pt}\bullet\,$ 排列：长度为 $n$ 的排列是由 $1 \sim n$ 这 $n$ 个整数按任意顺序组成的数组，其中每个整数恰好出现一次。

输入描述:

在一行上输入一个整数 ，表示需要构造的排列长度。

输出描述:

如果不存在满足条件的排列，在一行上输出 ；否则，在一行上输出  个整数  表示一个符合要求的排列。当存在多种可行方案时，输出任意一种均可。

示例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 回复(1)

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

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)

KH7788

# a1+1=2外，其他数字自身相加（奇+奇，偶+偶）均为偶数➡合数，因此只需处理a1
length = int(input())
if length <= 2:
    print(-1)
else:
    nlist = [] 
    for i in range(1,length+1):
        nlist.append(i)
    # 交换a1，a3位置
    nlist[0],nlist[2] = nlist[2],nlist[0]
    for i in nlist:
        print(i, end=' ')

发表于 2025-01-21 11:12:50 回复(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年秋招蚂蚁编程题精选

难度：

6条回答 29收藏 3237浏览

通过挑战的用户

查看代码

云溪浮

2023-03-06 16:58:33