例66 計算2的N次方
問題描述
任意給定一個正整數N(1<=N<=100)，計算2的n次方的值，
輸入
輸入一個正整數N，
輸出
輸出2的N次方的值，
輸入樣例
5
輸出樣例
32
（1）編程思路1，
當N=100時，2的N次方是一個很大的數，超出了一個長整數的表數范圍，因此，為了保存2的N次方，可以定義一個陣列int a[35];，每個陣列元素a[i]保存結果整數的1位數，例如，保存整數1024時，a[0]=4，a[1]=2，a[2]=0，a[3]=1，并記整數的位數len=4，
這樣一個整數乘以2，可以將每個陣列元素乘以2，同時進行進位處理即可，
（2）源程式1，
#include <stdio.h>
#include <string.h>
int main()
{
int n;
scanf("%d",&n);
int a[35];
memset(a,0,sizeof(a));
a[1]=1;
int i,j,len=1;
for(i=1;i<=n;i++)
{
int cf=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");
return 0;
}
（3）編程思路2，
一個陣列元素只保存整數的1位數字，這樣既浪費存盤空間，同時耗時，實際上，一個陣列元素可以保存9位數字都沒有問題，因為1個9位數乘以2，不會超過整數的表數范圍，
下面的程式采用1個陣列元素保存整數的6位數字，例如，整數1234567890，可以保存為a[0]=567890，a[1]=1234，并記整數的位數len=2，
（4）源程式2，
#include <stdio.h>
#include <string.h>
#define BASE 1000000
int main()
{
int n;
scanf("%d",&n);
int a[7];
memset(a,0,sizeof(a));
a[1]=1;
int i,j,len=1;
for(i=1;i<=n;i++)
{
int cf=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");
return 0;
}
習題66
66-1 求10000以內n的階乘
問題描述
求10000以內n的階乘，
輸入
只有一行輸入，整數n（0<=n<=10000），
輸出
一行，即n!的值，
樣例輸入
100
樣例輸出
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
（1）編程思路，
10000以內n的階乘是一個很大的數，超出了一個長整數的表數范圍，因此，為了保存n的階乘，可以定義一個陣列int a[2000];，每個陣列元素a[i]保存結果整數的4位數字，例如，保存整數1234567890時，a[0]=7890，a[1]=3456，a[2]=12，并記整數的位數len=3，
這樣一個整數乘以K（1,=k<=N），可以將每個陣列元素乘以K，同時進行進位處理即可，
（2）源程式，
#include <stdio.h>
#include <string.h>
#define BASE 10000
int main()
{
int n;
scanf("%d",&n);
int a[2000];
memset(a,0,sizeof(a));
a[1]=1;
int i,j,len=1;
for(i=2;i<=n;i++)
{
int cf=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");
return 0;
}
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]超過了一個長整數的表數范圍，所以用陣列保存一個整數的各位，
定義二維陣列int f[1005][301]，其中第1維f[i]表示吃i個巧克力的方案數，第2維用于保存各整數的各位數字，每個元素保存一個數字，其中f[i][0]保存吃i個巧克力的方案數x的位數，f[i][1]~f[i][f[i][0]]分別保存x從低位到高位的各位數字，
（2）源程式，
#include <stdio.h>
#include <string.h>
int main()
{
int n;
scanf("%d",&n);
int f[1005][301];
memset(f,0,sizeof(f));
f[1][0]=1;
f[1][1]=1;
f[2][0]=1;
f[2][1]=2;
int i,j;
for (i=3;i<=n;i++)
{
int len=f[i-1][0];
int cf=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");
return 0;
}
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)!，
定義一個陣列int a[410];來保存總方案數，每個陣列元素a[i]保存結果整數的1位數，
（2）源程式1，
#include <stdio.h>
#include <string.h>
int a[410];
void fact(int n) // 求階乘
{
memset(a,0,sizeof(a));
a[1]=2;
int i,j,len=1;
for(i=2;i<=n;i++)
{
int cf=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");
}
int main()
{
int n;
while(scanf("%d",&n) &&n!=-1)
{
printf("N=%d:\n",n);
fact(n-1);
}
return 0;
}
上面的程式采用一維陣列保存2*(n-)!，可以定義一個二維陣列int a[201][410];，將n=3~200的方案數全部保存下來，因為n!=n*(n-1)!，這樣無需每次求方案數時，都進行階乘的運算，按這樣的思路，撰寫如下的源程式，
（3）源程式2，
#include <stdio.h>
#include <string.h>
int a[201][410];
void init(void) // 求階乘
{
memset(a,0,sizeof(a));
a[1][0]=1;
a[1][1]=2;
int i,j,len=1;
for(i=2;i<=200;i++)
{
int cf=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;
}
}
int main()
{
int n,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");
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/428477.html
標籤：其他