例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;
}