c语言10的n次方

C语⾔程序设计100例之（66）：计算2的N次⽅

例66计算2的N次⽅

问题描述

任意给定⼀个正整数N(1<=N<=100)，计算2的n次⽅的值。

输⼊

输⼊⼀个正整数N。

输出

输出2的N次⽅的值。

输⼊样例

5

输出样例

32

（1）编程思路1。

当N=100时，2的N次⽅是⼀个很⼤的数，超出了⼀个长整数的表数范围。因此，为了保存2的N次⽅，可以定义⼀个数组inta[35];，每个数组元素a[i]保存结果整数的1位数，

例如，保存整数1024时，a[0]=4，a[1]=2，a[2]=0，a[3]=1，并记整数的位数len=4。

这样⼀个整数乘以2，可以将每个数组元素乘以2，同时进⾏进位处理即可。

（2）源程序1。

#include

#include

intmain()

{

intn;

scanf("%d",&n);

inta[35];

memt(a,0,sizeof(a));

a[1]=1;

inti,j,len=1;

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

{

intcf=0;

for(j=1;j<=len;j++)

{

a[j]=a[j]*2+cf;

cf=a[j]/10;

a[j]=a[j]%10;

}

while(cf!=0)

{

a[++len]=cf%10;

cf/=10;

}

}

for(i=len;i>=1;i--)

printf("%d",a[i]);

printf("n");

return0;

}

（3）编程思路2。

⼀个数组元素只保存整数的1位数字，这样既浪费存储空间，同时耗时。实际上，⼀个数组元素可以保存9位数字都没有问题，因为1个9位数乘以2，不会超过整数的表数范

围。

下⾯的程序采⽤1个数组元素保存整数的6位数字。例如，整数1234567890，可以保存为a[0]=567890，a[1]=1234，并记整数的位数len=2。

（4）源程序2。

#include

#include

#defineBASE1000000

intmain()

{

intn;

scanf("%d",&n);

inta[7];

memt(a,0,sizeof(a));

a[1]=1;

inti,j,len=1;

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

{

intcf=0;

for(j=1;j<=len;j++)

{

a[j]=a[j]*2+cf;

cf=a[j]/BASE;

a[j]=a[j]%BASE;

}

while(cf!=0)

{

a[++len]=cf%BASE;

cf/=BASE;

}

}

printf("%d",a[len]);

for(i=len-1;i>=1;i--)

printf("%06d",a[i]);

printf("n");

return0;

}

习题66

66-1求10000以内n的阶乘

问题描述

求10000以内n的阶乘。

输⼊

只有⼀⾏输⼊，整数n（0<=n<=10000）。

输出

⼀⾏，即n!的值。

样例输⼊

100

样例输出

9332626866764386389529253697920

（1）编程思路。

10000以内n的阶乘是⼀个很⼤的数，超出了⼀个长整数的表数范围。因此，为了保存n的阶乘，可以定义⼀个数组inta[2000];，每个数组元素a[i]保存结果整数的4位数字，

例如，保存整数1234567890时，a[0]=7890，a[1]=3456，a[2]=12，并记整数的位数len=3。

这样⼀个整数乘以K（1,=k<=N），可以将每个数组元素乘以K，同时进⾏进位处理即可。

（2）源程序。

#include

#include

#defineBASE10000

intmain()

{

intn;

scanf("%d",&n);

inta[2000];

memt(a,0,sizeof(a));

a[1]=1;

inti,j,len=1;

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

{

intcf=0;

for(j=1;j<=len;j++)

{

a[j]=a[j]*i+cf;

cf=a[j]/BASE;

a[j]=a[j]%BASE;

}

while(cf!=0)

{

a[++len]=cf%BASE;

cf/=BASE;

}

}

printf("%d",a[len]);

for(i=len-1;i>=1;i--)

printf("%04d",a[i]);

printf("n");

return0;

}

66-2吃巧克⼒

问题描述

⼩红的妈妈从外地出差回来，带了⼀盒好吃⼜精美的巧克⼒给⼩红（盒内共有N块巧克⼒，1000>N>0）。妈妈告诉⼩红每天可以吃⼀块或者两块巧克⼒。假设⼩红每天都吃

巧克⼒，问⼩红共有多少种不同的吃完巧克⼒的⽅案。例如：如果N=1，则⼩红第1天就吃掉它，共有1种⽅案；如果N=2，则⼩红可以第1天吃1块，第2天吃1块，也可以第1天

吃2块，共有2种⽅案；如果N=3，则⼩红第1天可以吃1块，第2天吃1块，第3天吃1块，也可以第1天吃1块，第2天吃2块，还可以第1天吃2块，第2天吃1块，所以⼩红共有3种⽅

案。现在给定N，请你写程序求出⼩红吃巧克⼒的⽅案数⽬。

输⼊

输⼊只有1⾏，即整数N。

输出

输出只有1⾏，即⼩红吃巧克⼒的⽅案数。

输⼊样例

3

输出样例

3

（1）编程思路。

设f[n]表⽰⼩红吃n个巧克⼒的⽅案数⽬。

由于⼩红每天可以吃⼀块或者两块巧克⼒，若最后⼀天⼩红吃1个巧克⼒，则有f[n-1]种⽅案；若最后⼀天⼩红吃2个巧克⼒，则有f[n-2]种⽅案；因此，f[n]=f[n-1]+f[n-2]。

由于n较⼤，f[n]超过了⼀个长整数的表数范围，所以⽤数组保存⼀个整数的各位。

定义⼆维数组intf[1005][301]，其中第1维f[i]表⽰吃i个巧克⼒的⽅案数。第2维⽤于保存各整数的各位数字，每个元素保存⼀个数字，其中f[i][0]保存吃i个巧克⼒的⽅案数x的

位数，f[i][1]~f[i][f[i][0]]分别保存x从低位到⾼位的各位数字。

（2）源程序。

#include

#include

intmain()

{

intn;

scanf("%d",&n);

intf[1005][301];

memt(f,0,sizeof(f));

f[1][0]=1;

f[1][1]=1;

f[2][0]=1;

f[2][1]=2;

inti,j;

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

{

intlen=f[i-1][0];

intcf=0;

for(j=1;j<=len;j++)

{

f[i][j]=f[i-1][j]+f[i-2][j]+cf;

cf=f[i][j]/10;

f[i][j]=f[i][j]%10;

}

if(cf!=0)

f[i][++len]=cf;

f[i][0]=len;

}

for(i=f[n][0];i>=1;i--)

printf("%d",f[n][i]);

printf("n");

return0;

}

66-3钥匙的放置

问题描述

设有n（3<=n<=200）个盒⼦，由A1、A2、…、An分别标识。每个盒⼦都配置了⼀个不同于其他盒⼦的锁。现在把n把钥匙锁进这n个盒⼦⾥，每个盒⼦只能装⼀把钥匙。锁好所

有盒⼦后，撬开A1、A2两个盒⼦，取出⾥⾯的钥匙，打开相应锁好的盒⼦。如果这两把钥匙可以打开某个盒⼦，取出盒⼦⾥的钥匙，再次解锁其他锁定的盒⼦。

问能够最终打开所有盒⼦的钥匙的放置⽅法有多少种。

输⼊

输⼊⽂件以-1结尾，包含多个数据，每个数据占⼀⾏。

输出

根据每个输⼊数据，计算最终打开所有盒⼦的钥匙的放置⽅法数。每个输出数据保留两⾏，第⼀⾏由输⼊数据保留，后⾯是冒号，冒号后⾯是等号，前⾯是N；第⼆个是放置的

⽅法数。

输⼊样例

6

8

-1

输出样例

N=6:

240

N=8:

10080

（1）编程思路。

钥匙的放置可以采⽤如下两种⽅案：

1）所有钥匙形成⼀个环，以⼀个钥匙（1或2）为起点可以到达所有钥匙，这样可以1或2中⼀个点为起始点依次打开所有盒⼦，所有钥匙环排列，⽅案数有(n-1)!种。

2）以1和2为起点分别形成两个环，两个环的⼤⼩就是⽅程x+y=n的正整数解，这个⽅程有n-1个解，剩下的n-2个钥匙可以全排列，作为各环上的顺序，有(n-1)*(n-2)!种⽅

案。

所以总⽅案数为2*(n-1)!。

定义⼀个数组inta[410];来保存总⽅案数，每个数组元素a[i]保存结果整数的1位数。

（2）源程序1。

#include

#include

inta[410];

voidfact(intn)//求阶乘

{

memt(a,0,sizeof(a));

a[1]=2;

inti,j,len=1;

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

{

intcf=0;

for(j=1;j<=len;j++)

{

a[j]=a[j]*i+cf;

cf=a[j]/10;

a[j]=a[j]%10;

}

while(cf!=0)

{

a[++len]=cf%10;

cf/=10;

}

}

for(i=len;i>=1;i--)

printf("%d",a[i]);

printf("n");

}

intmain()

{

intn;

while(scanf("%d",&n)&&n!=-1)

{

printf("N=%d:n",n);

fact(n-1);

}

return0;

}

上⾯的程序采⽤⼀维数组保存2*(n-)!。可以定义⼀个⼆维数组inta[201][410];，将n=3~200的⽅案数全部保存下来，因为n!=n*(n-1)!，这样⽆需每次求⽅案数时，都进⾏阶乘

的运算。按这样的思路，编写如下的源程序。

（3）源程序2。

#include

#include

inta[201][410];

voidinit(void)//求阶乘

{

memt(a,0,sizeof(a));

a[1][0]=1;

a[1][1]=2;

inti,j,len=1;

for(i=2;i<=200;i++)

{

intcf=0;

for(j=1;j<=len;j++)

{

a[i][j]=a[i-1][j]*i+cf;

cf=a[i][j]/10;

a[i][j]=a[i][j]%10;

}

while(cf!=0)//

{

a[i][++len]=cf%10;

cf/=10;

}

a[i][0]=len;

}

}

intmain()

{

intn,i;

init();

while(scanf("%d",&n)&&n!=-1)

{

printf("N=%d:n",n);

for(i=a[n-1][0];i>=1;i--)

printf("%d",a[n-1][i]);

printf("n");

}

return0;

}