Question

一道c语言的题目。急求大神解答。

假设我们有 2n 张牌，它们以 1, 2, ..., n, n+1, ..., 2n 编号并在开始时保持着这种顺序。一次洗牌就是将牌原来的次序变为 n+1, 1, n+2, 2, ..., 2n, n，也就是将原来的前 n 张牌放到位置 2, 4, ..., 2n，并且将余下的 n 张牌按照他们原来的次序放到奇数位置 1, 3, ..., 2n-1。已经证明对于任何一个自然数 n，这 2n 张牌经过一定次数的洗牌就回到原来的次序。但我们不知道对于一个特定的 n，需要几次洗牌才能将牌洗回原来的次序。

输入：
牌张数的一半n，即初始情况下一共有2n张牌，n为int型整数

输出：
将牌洗回原来的次序所需要的洗牌次数
这是我的程序。为什么输入100以上的数就会无效内存引用呢？
#include<stdio.h>
int f(int n,int a[],int b[])
{
int j,i,c[2000];
for(i=0;i<2*n;i++) c[i]=a[i];
for(i=0,j=1;i<n;i++,j=j+2) a[j]=c[i];
for(j=0;i<2*n;i++,j=j+2) a[j]=c[i];
for(i=0;i<2*n;i++)
{
if(a[i]!=b[i]) return (1+f(n,a,b));
}
if(i==2*n) return 1;
}
int main()
{
int i,n,a[2000],b[2000];
scanf("%d",&n);
for(i=0;i<2*n;i++) a[i]=i;
for(i=0;i<2*n;i++) b[i]=i;
printf("%d\n",f(n,a,b));
return 0;
}

Answer 1

这是由于原来的程序采用了递归，而且递归程序中的局部变量有较大的数组。当递归层数太多时，就会造成系统栈溢出，而导致程序崩溃。

以下的程序改为非递归的，就不会再有此现象：

#include<stdio.h> 

void f(int n,int a[],int b[]) 

{ 

 int j,i,c[20000]; 

  for(i=0;i<2*n;i++) c[i]=a[i]; 

   for(i=0,j=1;i<n;i++,j=j+2) a[j]=c[i]; 

   for(j=0;i<2*n;i++,j=j+2) a[j]=c[i]; 

} 

int main() 

{ 

   int i,n,a[20000],b[20000],num=0;         //做到20000张牌也能正确出解

 scanf("%d",&n); 

    for(i=0;i<2*n;i++) a[i]=i; 

  for(i=0;i<2*n;i++) b[i]=i; 

  for(i=0;i<n+n;)

  {

    f(n,a,b);

num++;

for(i=0;i<2*n;i++)

 if(a[i]!=b[i])break;

}

printf("%d\n",num);  

   return 0; 

}

Answer 2

//采纳答案很对，但是函数可以少传入一个变量，for循环可以合并下
#include<stdio.h>
void f(int n,int a[])
{
int j,i,c[20000];
for(i=0; i<2*n; i++) c[i]=a[i];
for(i=0,j=1; i<n; i++,j=j+2) a[j]=c[i];
for(j=0; i<2*n; i++,j=j+2) a[j]=c[i];
}
int main()
{
int i,n,a[20000],b[20000],num=0,flag=1; //做到20000张牌也能正确出解
scanf("%d",&n);
for(i=0; i<2*n; i++)
{
a[i]=i;
b[i]=i;
}
for(i=0; i<n+n;)
{
f(n,a);
num++;
for(i=0; i<2*n; i++)
{
if(a[i]!=b[i]) break;
}
}
printf("%d\n",num);
return 0;
}