易语言做网站登陆,seo网页优化培训,wordpress 可以做什么,最受欢迎的建站平台在说起全排列前#xff0c;先说一下昨天碰到的一个题目#xff08;答案不是我做出来的#xff0c;但是我感觉有好多个亮点#xff0c;贴出来方便日后的学习#xff09;#xff1a; 素数环 时间限制#xff1a;1000 ms | 内存限制#xff1a;65535 KB难度#xff1a;…在说起全排列前先说一下昨天碰到的一个题目答案不是我做出来的但是我感觉有好多个亮点贴出来方便日后的学习 素数环 时间限制1000 ms | 内存限制65535 KB 难度2 描述 有一个整数n把从1到n的数字无重复的排列成环且使每相邻两个数包括首尾的和都为素数称为素数环。 为了简便起见我们规定每个素数环都从1开始。例如下图就是6的一个素数环。 输入有多组测试数据每组输入一个n(0n20)n0表示输入结束。输出每组第一行输出对应的Case序号从1开始。如果存在满足题意叙述的素数环从小到大输出。否则输出No Answer。样例输入 6
8
3
0 样例输出 Case 1:
1 4 3 2 5 6
1 6 5 2 3 4
Case 2:
1 2 3 8 5 6 7 4
1 2 5 8 3 4 7 6
1 4 7 6 5 8 3 2
1 6 7 4 3 8 5 2
Case 3:
No Answer这个题的解法我考虑了很久怎么说呢感觉上并不是一道难度很大的题实际操作起来却又无从下手。我说一下我的思考过程首先这牵扯到寻找素数但是呢不是简单的找素数而是两个数的和在[1,n]之间的两个数mn的和 有多组测试数据每组输入一个n(0n20)n0表示输入结束。这句话可以看出输入的n最大也就20.那么即使在跑程序的时候当真输入为20最大的的一个和值也就是202040,那么我完全可以把[1,40]间的素数全部找出来并建立一个数组s[40]然后在[1,n]间查看看哪两个数的和是素数通过在数组s[40]里查找是否符合若符合将符合的值存放在一个数组里而后输出。 #include stdio.h
#includestring.h
int count,sa[40]; // coount 用于控制输出流 sa[]是一个用来显示区间[2,42]内每个数是否为素数的数组若为素数其对应的sa[j]1/*** found 函数的定义据作者说是由全排列改编过来的 ***/ void found(int n,int cur,int a[],int flag[]){ // 传入的 n 为 in[]数组中的元素即输入值 cur 初始值为1 是用于控制a[]的下标 a[]是一个a[0]1的用于存放可满足数的数组 // flag[]是一个初始值全部置0的数组 用于储存在判定检查过程中的数是否为要用的值后的布尔值if(curnsa[a[0]a[cur-1]]) // 这里用cur 与 输入值 n 进行比较判断 也就是说 a数组里存放的个数最多 n个最多把[1,n]之间的值全部放进去,或者说数组a里的最大值肯定不能大于n
{ { for(int i0;in;i) printf(%d ,a[i]); // 那么当a数组检查n是否可以存放时这次遍历也就到此结束了也就是该输出数组a了putchar(\n); count0; }
}
/***** 在cur!n时需要进一步的检查时利用递归在区间[2,n]以此将满足的数存放在a[]中 *****/else //for(int i2;in;i) //if(!flag[i]sa[ia[cur-1]]) // { //a[cur]i; //flag[i]1; //found(n,cur1,a,flag); //flag[i]0; //} //
} //
/*********************************************************************************/
int main(void)
{int i0,a[20],in[100],flag[20]; // in[20] 用于存放输入 memset(sa,0,sizeof(sa)); memset(flag,0,sizeof(flag));
/***********************************************************/ for(int ok1,k2,j2;j40;j,ok1) //{ //for(int i2;ij/2;i) // 在区间[2,40]里进行是否为素数的判定 用j控制数组sa的下标同时j还是一个数列【2,40】 { //if(j%i0) ok0; // 若为素数sa[j]1,否则不对sa[j]处理即为0 } //if(ok) sa[j]1; //} //
/**************************************************/ /**************************************/do // 我很喜欢这段控制输入的代码{ // scanf(%d,in[i]); // 很简单 但是很巧妙 }while(in[i-1]); //
/********************************/// 大方 优雅 a[0]1; for(int j1;ji;j) {count1; printf(Case %d:\n,j); // j 显示输入的数据的个数 if(!(in[j-1]%2)||in[j-1]1) found(in[j-1],1,a,flag); // if里判定 in[]数组里的元素是否为奇数 或者是为1 两种情况均调用函数 if(count) printf(No Answer\n); } return 0;
} 先简单简单注释一下可能在匆忙之中有一些错误哪位有发现多谢指出 转载于:https://www.cnblogs.com/zhangzimu/p/6187187.html
