2110：【例5.1】素数环
时间限制: 1000 ms 内存限制: 65536 KB提交数:221 通过数: 84
【题目描述】
输入正整数n𝑛，把整数11,22,…,n𝑛 组成一个环，使得相邻两个整数之和均为素数。
【输入】
输入正整数n𝑛。
【输出】
输出任意一个满足条件的环。
【输入样例】
6### 【输出样例】
4 3 2 5 6 1### 【提示】
数据满足：
4≤n≤30
#include<bits/stdc++.h>
using namespace std;
int a[40],n;// a数组用来储存素数环上的每一位数，a[1]代表第一位以此类推
bool b[40]; // b数组用来标记1-n个数有没有被使用，有没有加入素数环
int ss(int); // 定义一个搜索和回溯函数，参数为整数
bool pd(int,int); // 定义一个判断两个数之和是否为素数的函数
void print(); // 定义一个满足素数环的情况出现时，打印素数环
int main(){
cin>>n;
ss(1);// 1是实际参数，会真实的传递给函数
return 0;
}
int ss(int t){ // t是形式参数，是调用函数时才会生成的变量，用来接受实参
int i;
for( i=1;i<=n;i++){// 素数环的第1个数的所有可能性都要试一遍
if(t == 1){
a[t]=1; // i满足入素数环的条件，把i加入素数环
b[i]=1; // 标记i已经被使用
ss(t+1);
}else if(pd(a[t-1],i)&&(b[i]==0)){
a[t]=i; // i满足入素数环的条件，把i加入素数环
b[i]=1; // 标记i已经被使用
if(t==n){ // t代表此时素数环内有多少个元素，判断素数环是否满
if(pd(a[n],a[1])){
print();
//return 0;
}
}else{
ss(t+1);
}
b[i]=0;// 回溯，标记i重新变成未使用状态
}
}
return 0;
}
void print(){
for(int i=1;i<=n;i++){
cout<<a[i]<<" ";
}
cout<<endl;
return;
}
bool pd(int x,int y){
for(int i=2;i*i<=x+y;i++){
if((x+y)%i==0){
return 0;
}
}
return 1;
}
2 条评论
-
mrhowe SU @ 2024-6-2 20:34:351317：【例5.2】组合的输出
时间限制: 1000 ms 内存限制: 65536 KB提交数:55396 通过数: 27857
【题目描述】
排列与组合是常用的数学方法，其中组合就是从n个元素中抽出r个元素(不分顺序且r≤n)，我们可以简单地将n个元素理解为自然数1，2，…，n，从中任取r个数。
现要求你用递归的方法输出所有组合。
例如n＝5，r＝3，所有组合为：
1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5
【输入】
一行两个自然数n、r(1<n<21，1≤r≤n)。
【输出】
所有的组合，每一个组合占一行且其中的元素按由小到大的顺序排列，每个元素占三个字符的位置，所有的组合也按字典顺序。
【输入样例】
5 3### 【输出样例】
1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5#include<bits/stdc++.h> using namespace std; int a[40],n,r; bool b[40]; int ss(int); void print(); int main(){ cin>>n>>r; ss(1); return 0; } int ss(int t){ int i; for( i=1;i<=n;i++){ if((!b[i])&&(i>a[t-1])){ a[t]=i; b[i]=1; if(t==r){ print(); }else{ ss(t+1); } b[i]=0; } } return 0; } void print(){ for(int i=1;i<=r;i++){ printf("%3d",a[i]); } cout<<endl; return; } -
@ 2024-6-2 20:32:39
1318：【例5.3】自然数的拆分
时间限制: 1000 ms 内存限制: 65536 KB提交数:39816 通过数: 23292
【题目描述】
任何一个大于1的自然数n，总可以拆分成若干个小于n的自然数之和。
当n=7共14种拆分方法：
7=1+1+1+1+1+1+1 7=1+1+1+1+1+2 7=1+1+1+1+3 7=1+1+1+2+2 7=1+1+1+4 7=1+1+2+3 7=1+1+5 7=1+2+2+2 7=1+2+4 7=1+3+3 7=1+6 7=2+2+3 7=2+5 7=3+4 total=14【输入】
输入n。
【输出】
按字典序输出具体的方案。
【输入样例】
7### 【输出样例】
7=1+1+1+1+1+1+17=1+1+1+1+1+27=1+1+1+1+37=1+1+1+2+27=1+1+1+47=1+1+2+37=1+1+57=1+2+2+27=1+2+47=1+3+37=1+67=2+2+37=2+57=3+4
#include<iostream> #include<cstdio> #include<cstdlib> #include<iomanip> using namespace std; int a[10001]={1},n; int ss(int,int); void print(int); int main(){ cin>>n; ss(n,1); return 0; } int ss(int s,int t){ int i; for( i=a[t-1];i<=s;i++){ if(i<n){ a[t]=i; s-=i; if(s==0){ print(t); }else ss(s,t+1); s+=i; } } return 0; } void print(int t){ cout<<n<<"="; for(int i=1;i<=t-1;i++){ cout<<a[i]<<"+"; } cout<<a[t]; cout<<endl; return; }
- 1