例49 序列變換
問題描述
下面探討由數字0和1構成的序列，初始時，序列中只有一個數字1，之后對序列進行變換，在每次變換時，同時將序列中的每個數字0轉換為10，將每個數字1轉換為01，因此，在第1次變換后，得到序列01；第2次變換后，得到序列1001；第3次變換后，得到序列01101001；…，依此類推，
在第n次變換后，序列中將出現多少對連續的零？
輸入
每個輸入行包含一個自然數n（0<n<=1000），
輸出
對于每個輸入的n，列印n次變換后將在序列中出現的連續零對的數量，
輸入樣例
2
3
輸出樣例
1
1
（1）編程思路，
先撰寫如下程式直接模擬看看10次變換的結果，并輸出每次變換后，序列中連續零對的數量，10次變換后，序列長度會達到1024，因此，直接模擬只能針對較小的n，之后通過較小的n的結果，找出規律，
#include <stdio.h>
#include <string.h>
int main()
{
char s[1050];
s[0]='1';
s[1]='\0';
int t,i,j,len=1;
for (t=1;t<=10;t++)
{
for (i=len-1,j=2*len-1;i>=0;i--,j-=2)
{
if (s[i]=='1')
{
s[j-1]='0';
s[j]='1';
}
else
{
s[j-1]='1';
s[j]='0';
}
}
len=2*len;
s[len]='\0';
printf("%s\n",s);
int cnt=0;
for (i=1;i<len;i++)
{
if (s[i-1]=='0' && s[i]=='0')
cnt++;
}
printf("count[%2d]=%d\n",t,cnt);
}
}
程式運行后，輸出如下：
count[ 1]=0
count[ 2]=1
count[ 3]=1
count[ 4]=3
count[ 5]=5
count[ 6]=11
count[ 7]=21
count[ 8]=43
count[ 9]=85
count[10]=171
設s[i]是變換i次后的序列中連續零對的數量，由上面的模擬程式運行結果，可以推出如下規律：
當i為奇數時，s[i]=2 * s[i-1]-1
當i為偶數時，s[i]=2 * s[i-1]+1
由于n較大，s[1000]超過了long long型整數的表數范圍，故采用高精度計算，由于計算時，主要是乘2，因此，一個陣列元素可以保留一個10進制整數的8位，具體高精度計算參看源程式，
（2）源程式，
#include <stdio.h>
#define MOD 100000000
#include <string.h>
int main()
{
int i,j;
int b[1001][50];
memset(b,0,sizeof(b));
b[1][0]=1;
b[1][1]=0;
int len=1;
for (i=2;i<=1000;i++)
{
for (j=1;j<=len;j++)
b[i][j]=b[i-1][j]*2;
if (i%2) b[i][1]--;
else b[i][1]++;
int cf;
for (j=1;j<=len;j++)
{
cf=b[i][j]/MOD;
b[i][j]=b[i][j]%MOD;
b[i][j+1]+=cf;
}
if (b[i][len+1]!=0)
{
len++;
}
b[i][0]=len;
}
int n;
while (scanf("%d",&n)!=EOF)
{
len=b[n][0];
printf("%d",b[n][len]);
for (i=len-1;i>=1;i--)
printf("%08d",b[n][i]);
printf("\n");
}
return 0;
}
習題49
49-1 污水處理
問題描述
為了對河流污染進行控制，河岸邊的n座城市聯合建設一套河岸污水處理系統，每個城市在河邊都建有自己的污水處理廠，污水處理廠用于在排入河流之前清理城市污水；還有一條管道通往上游的鄰近城市，還有一條管道通往沿河下游的下一個城市，這樣，可以讓污水處理廠以最大容量運行，讓較少使用的處理廠關閉一段時間，效率更高，
因此，每個城市的污水處理廠有三種選擇：
1）處理從鄰近城市接收的污水，連同其自身的污水，將凈化后的水排入河流；
2）將其自身的污水，加上其下游鄰近城市輸送過來的污水，輸送至上游鄰近城市的處理廠（前提是該城市尚未使用管道將其污水輸送至下游）；
3）將其自身的污水，加上其上游鄰近城市輸送過來的污水，輸送至下游鄰近城市的處理廠，
上述選擇確保：
每個城市都必須在某處和某處對其水進行處理；
至少有一個城市必須將清潔的水排入河流，
若將一個向河流中排放處理后凈水的城市表示為“V”（向下的水流），將水傳遞給它的鄰近城市表示為“>”（到它右邊的下一個城市）或“<”（到左邊的下一個城市），
例如，有A和B兩個城市（n=2），可以如下有3種污水處理方式：
VV：A和B兩座城市的污水處理廠處理各自城市產生的污水并排放；
>V：A市將其污水沿管道（右側）輸送至B市，由B市的污水處理廠進行處理和排放；
V<：B市將其污水沿管道（左側）輸送至A市，由A市的污水處理廠進行處理和排放，
不可能出現“><”，因為這意味著A將污水輸送到B，B將自己的污水輸送到A，兩者都使用相同的管道，這是不允許的，
撰寫一個程式，給定河岸中城市（或污水處理廠）的數量NC（NC<=100），確定可根據上述規則進行的污水處理的方案數目NS，
輸入
輸入由一系列值組成，每行一個，其中每個值表示城市的數量，
輸出
輸出應該是一系列值，每行一個，其中每個值表示在同一輸入行中讀取的相應城市數的可能污水處理方案數，
輸入樣例
2
3
20
輸出樣例
3
8
102334155
（1）編程思路，
設F[i]表示有i個城市時的污水處理方法數，第i個城市的污水處理方法有
1）自己只處理自己的污水并排放，此時與前i-1個城市的處理方法無關，有F[i-1]種方法；
2）“<”給左邊的城市去處理，此時也與前i-1個城市的處理方法無關，只需將自己的污水輸送給第i-1個城市就行了，有F[i-1]種方法；
3）“>”左邊有污水傳過來和自己的污水一起處理，這時第i-1個城市可以向右傳了（“>”），如果這種情況發生的話，那么第i-1個城市肯定不可能是向左傳的（“<”），但對前i-2個城市的處理方法沒有影響，所以第i-1個城市向左傳的方法有F[i-2]種，這樣第i-1個城市的污水處理方法數F[i-1]中，不會向左傳的方法數為F[i-1]-F[i-2]，
由此，F[i]=3*F[i-1]-F[i-2]
初始時，F[1]=1，F[2]=3，
例如，i=2時，有VV、>V、V<三種處理方法，
i=3時，若第3座城市自己只處理自己的污水，則有VVV、>VV、V<V 這3種處理方案；若“<”給左邊的城市去處理，則有VV<、>V<、V<< 這3種處理方案；若接收“>”左邊有污水傳過來和自己的污水一起處理，則i=2時的3種方案中向左傳的方案有1種（V<），不向左傳的方案有2種，這樣又有>>V和V>V這兩種處理方案；因此，i=3時，有3+3+2=8種處理方案，
由于n較大，F[100]超過了long long型整數的表數范圍，故采用高精度計算，由于計算時，主要是乘3，因此，一個陣列元素可以保留一個10進制整數的8位，具體高精度計算參看源程式，
（2）源程式，
#include <stdio.h>
#include <string.h>
#define MOD 100000000
int main()
{
int i,j;
int f[101][40];
memset(f,0,sizeof(f));
f[1][0]=1; // 保存陣列第2維元素個數
f[1][1]=1;
f[2][0]=1;
f[2][1]=3;
int len=1;
for (i=3;i<=100;i++)
{
for (j=1;j<=len;j++)
f[i][j]=f[i-1][j]*3;
for (j=1;j<=f[i-2][0];j++)
f[i][j]=f[i][j]-f[i-2][j];
for (j=1;j<len;j++)
if (f[i][j]<0)
{
f[i][j]+=MOD;
f[i][j+1]--;
}
int cf;
for (j=1;j<=len;j++)
{
cf=f[i][j]/MOD;
f[i][j]=f[i][j]%MOD;
f[i][j+1]+=cf;
}
if (f[i][len+1]!=0)
{
len++;
}
f[i][0]=len;
}
int n;
while (scanf("%d",&n)!=EOF)
{
len=f[n][0];
printf("%d",f[n][len]);
for (i=len-1;i>=1;i--)
printf("%08d",f[n][i]);
printf("\n");
}
return 0;
}
49-2 漢諾塔問題
本題選自洛谷題庫 （https://www.luogu.org/problem/P1760）
問題描述
在十九世紀，一種稱為漢諾塔的游戲在歐洲廣為流行，游戲的裝置是一塊銅板，上面有三根柱子，左柱自下而上、由大到小順序串有N個金盤，呈塔形（如圖1所示），游戲的目標是把左柱上的金盤全部移到右邊的柱子上，條件是，一次只能移動一個盤，被移動的盤子必須放在其中的一根柱子上，并且不允許大盤在小盤上面，
圖1 漢諾塔問題
撰寫一個程式，計算將n個金盤從第1根柱子移到第3根柱子的移動次數，
輸入格式
一個數n，表示有n個圓盤（n<=15000），
輸出格式
一個數s，表示需要s步，
輸入樣例
31
輸出樣例
2147483647
（1）編程思路，
設把n個盤子按規定由第1根柱子移到第3根柱子的移動次數記為F[i]，移動的方法是：
1）先把n–1個盤子由第1根柱子移到第2根柱子，移動次數為F[i-1]；
2）把第n個盤子由第1根柱子移到第3根柱子，移動1次；
3）把第2根柱子上的n-1個盤于移到第3根柱子，移動次數為F[i-1]，
所以，F[i]=2*F[i-1]+1，初始值F[1]=1，
由于n較大，F[15000]超過了long long型整數的表數范圍，故采用高精度計算，由于計算時，主要是乘2，因此，為加快運算速度，一個陣列元素可以保留一個10進制整數的9位，并且為了節省存盤空間，采用滾動陣列，具體高精度計算參看源程式，
（2）源程式，
#include <stdio.h>
#define MOD 1000000000
#include <string.h>
int main()
{
int i,j;
int f[2][510]={0};
f[0][0]=1;
f[0][1]=0;
int len=1;
int n;
scanf("%d",&n);
for (i=1;i<=n;i++)
{
for (j=1;j<=len;j++)
f[i%2][j]=f[(i-1)%2][j]*2;
f[i%2][1]++;
int cf;
for (j=1;j<=len;j++)
{
cf=f[i%2][j]/MOD;
f[i%2][j]=f[i%2][j]%MOD;
f[i%2][j+1]+=cf;
}
if (f[i%2][len+1]!=0)
{
len++;
}
f[i%2][0]=len;
}
len=f[n%2][0];
printf("%d",f[n%2][len]);
for (i=len-1;i>=1;i--)
printf("%09d",f[n%2][i]);
printf("\n");
return 0;
}
49-3 平鋪地板
問題描述
有2×1和2×2兩種規格的地板，現要用這個兩種規格的地板平鋪2×n形狀的走道，共有多少種平鋪方法？（下圖為n=17的一種平鋪法），
輸入
輸入包括多行，每行包含一個整數n（0<=n<=250），
輸出
對于每行輸入，在單獨的行中輸出一個整數，給出2xn走道的平鋪方法數，
輸入樣例
2
8
12
100
200
輸出樣例
3
171
2731
845100400152152934331135470251
1071292029505993517027974728227441735014801995855195223534251 2
（1）編程思路，
設F[i]表示平鋪2×i走道的方法數，平鋪地板的方法如下：
1）若已經鋪好了2×（i-1）的走道，則要鋪到2×i，則只能用2×1的地板鋪在最后；
2）若已經鋪好了2×（i-2）的情形，則要鋪到2×i，則可以選擇1塊2×2的地板或兩塊2×1的地板，可能有如下三種鋪法：
其中第3種鋪法與鋪好2×（i-1）的情況重復，故舍去，
由此，可以得到遞推式為 ： F[i]=2*F[i-2]+F[i-1] ，初始時，F[0]=F[1]=1，
由于n較大，F[250]超過了long long型整數的表數范圍，故采用高精度計算，由于計算時，主要是乘2，因此，一個陣列元素可以保留一個10進制整數的8位，具體高精度計算參看源程式，
（2）源程式，
#include <stdio.h>
#include <string.h>
#define MOD 100000000
int main()
{
int i,j;
int f[255][15];
memset(f,0,sizeof(f));
f[0][0]=1; // 保存陣列第2維元素個數
f[0][1]=1;
f[1][0]=1;
f[1][1]=1;
int len=1;
for (i=2;i<=250;i++)
{
for (j=1;j<=len;j++)
f[i][j]=f[i-2][j]*2;
for (j=1;j<=len;j++)
f[i][j]=f[i][j]+f[i-1][j];
int cf;
for (j=1;j<=len;j++)
{
cf=f[i][j]/MOD;
f[i][j]=f[i][j]%MOD;
f[i][j+1]+=cf;
}
if (f[i][len+1]!=0)
{
len++;
}
f[i][0]=len;
}
int n;
while (scanf("%d",&n)!=EOF)
{
len=f[n][0];
printf("%d",f[n][len]);
for (i=len-1;i>=1;i--)
printf("%08d",f[n][i]);
printf("\n");
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/412844.html
標籤：C