巧排数字 C语言将1、2、...、20这20个数排成一排,使得相邻的两个数之和为一个素数,且首尾两数字之和也为一个素数.编程打印出所有的排法.只有源码的不给分,要思路,怎么递归为什么这
来源:学生作业帮助网 编辑:作业帮 时间:2024/07/08 04:04:30
![巧排数字 C语言将1、2、...、20这20个数排成一排,使得相邻的两个数之和为一个素数,且首尾两数字之和也为一个素数.编程打印出所有的排法.只有源码的不给分,要思路,怎么递归为什么这](/uploads/image/z/10425475-19-5.jpg?t=%E5%B7%A7%E6%8E%92%E6%95%B0%E5%AD%97+C%E8%AF%AD%E8%A8%80%E5%B0%861%E3%80%812%E3%80%81%EF%BC%8E%EF%BC%8E%EF%BC%8E%E3%80%8120%E8%BF%9920%E4%B8%AA%E6%95%B0%E6%8E%92%E6%88%90%E4%B8%80%E6%8E%92%2C%E4%BD%BF%E5%BE%97%E7%9B%B8%E9%82%BB%E7%9A%84%E4%B8%A4%E4%B8%AA%E6%95%B0%E4%B9%8B%E5%92%8C%E4%B8%BA%E4%B8%80%E4%B8%AA%E7%B4%A0%E6%95%B0%2C%E4%B8%94%E9%A6%96%E5%B0%BE%E4%B8%A4%E6%95%B0%E5%AD%97%E4%B9%8B%E5%92%8C%E4%B9%9F%E4%B8%BA%E4%B8%80%E4%B8%AA%E7%B4%A0%E6%95%B0.%E7%BC%96%E7%A8%8B%E6%89%93%E5%8D%B0%E5%87%BA%E6%89%80%E6%9C%89%E7%9A%84%E6%8E%92%E6%B3%95.%E5%8F%AA%E6%9C%89%E6%BA%90%E7%A0%81%E7%9A%84%E4%B8%8D%E7%BB%99%E5%88%86%2C%E8%A6%81%E6%80%9D%E8%B7%AF%2C%E6%80%8E%E4%B9%88%E9%80%92%E5%BD%92%E4%B8%BA%E4%BB%80%E4%B9%88%E8%BF%99)
巧排数字 C语言将1、2、...、20这20个数排成一排,使得相邻的两个数之和为一个素数,且首尾两数字之和也为一个素数.编程打印出所有的排法.只有源码的不给分,要思路,怎么递归为什么这
巧排数字 C语言
将1、2、...、20这20个数排成一排,使得相邻的两个数之和为一个素数,且首尾两数字之和也为一个素数.编程打印出所有的排法.
只有源码的不给分,要思路,怎么递归为什么这么递归,分解成了什么样的小问题,让我懂
巧排数字 C语言将1、2、...、20这20个数排成一排,使得相邻的两个数之和为一个素数,且首尾两数字之和也为一个素数.编程打印出所有的排法.只有源码的不给分,要思路,怎么递归为什么这
哈,你也魔兽世界啊!
这里提供了三种方法:
(注意:为了让程序更快,根据排列的特点,每种方法都固定了最后一个元素,这样输出只是满足条件中的一部分,但是你可以修改每种方法中的输出,所有元素通过移动一个位置来输出, 如123,第一次输出123,第2次231,第3次312,这样就可以得到所有的解.)
下面只对其中的暴力方法做简单的说明.
暴力方法思想:对1-n做出所有的排列,然后依次检查每个排列看是否满足条件,满足的输出.
其中的递归只是做出排列.排列递归的思想就是,任选1到n中的一个放到最后位置,(递归)任选剩余的数中的一个放到次后位置,*** ,按照这样循环下去.
顺便提一下,这种方法很慢,做完所有排列要进行递归几十亿亿次,你要等很久(可能久到几个小时,哈哈)才能看到结果. 但是,你可以把我注释的for语句代替其下的for可以快一点看到结果.
具体看代码中的解释.
看懂暴力方法,就能看懂方法三了.一就不用看了,可能你也看不懂.虽然它的速度是这三个比较快的一个,但理解也更难.
如果这样你都看不懂,那么是你的问题了,可能你根本不知道什么是排列,也可能你根本不知道什么是递归,一切都是白说.(那样你应该找本书看,而不是光问.)
#include
#include
#include
#include
#include
bool IsPrimeNumber(int n)
{ /*判断素数*/
int i;
int sqrootN;
if ( n == 2 ) {
return true;
} else if ( n%2 == 0 || n==1 ) {
return false;
}
sqrootN = (int)( sqrt(n)+0.1 )+1;
i = 3;
while ( i < sqrootN ) {
if (n%i == 0) {
return false;
}
i += 2;
}
return true;
}
void Swap(int *a, int *b)
{ /*交换两数*/
int tmp;
tmp = *a;
*a = *b;
*b = tmp;
}
bool IsOk(int *arr, int arrsize)
{ /*判断是否满足条件*/
if ( !IsPrimeNumber(arr[arrsize-1]+arr[0]) ) {
return false;
}
while( --arrsize > 0 ) {
if ( !IsPrimeNumber(arr[arrsize]+arr[arrsize-1]) ) {
return false;
}
}
return true;
}
////////////////////////////////////////////////////////
// 方法一:
bool Adjust_Pair(int *arr, int arrsize, int depth)
{
static int total=0;
bool ret = false;
int i;
if ( depth==2 ) {
if ( IsPrimeNumber(arr[0]+arr[arrsize-1]) ) {
total++;
printf("\n%03d: ",total);
for( i=0; i1; i-=2) {
if ( IsPrimeNumber(arr[i-1]+arr[depth-2]) ) {
Swap(arr+depth-3, arr+i-1);
Swap(arr+depth-4, arr+i-2);
if ( Adjust_Pair(arr, arrsize, depth-2) ) {
ret = true;
}
Swap(arr+depth-3, arr+i-1);
Swap(arr+depth-4, arr+i-2);
}
}
return ret;
}
bool Make_Pair(int *arr, int arrsize, int depth)
{
bool ret = false;
int i;
static int total1=0;
static int total2=0;
if ( depth==0 ) {
return Adjust_Pair(arr, arrsize, arrsize);
}
for( i=0; i