例47  车站

题目描述

火车从始发站（称为第 1 站）开出，在始发站上车的人数为 a，然后到达第 2 站，在第 2 站有人上、下车，但上、下车的人数相同，因此在第 2 站开出时（即在到达第 3 站之前）车上的人数保持为 a 人。从第 3 站起（包括第 3 站）上、下车的人数有一定规律：上车的人数都是前两站上车人数之和，而下车人数等于上一站上车人数，一直到终点站的前一站（第(n−1) 站），都满足此规律。现给出的条件是：共有n 个车站，始发站上车的人数为 a ，最后一站下车的人数是 m（全部下车）。试问x 站开出时车上的人数是多少？

输入格式

输入只有一行四个整数，分别表示始发站上车人数 a，车站数 n，终点站下车人数 m 和所求的站点编号 x。其中，1≤a≤20， 1≤x≤n≤20， 1≤m≤2×10⁴。

输出格式

输出一行一个整数表示答案：从 x 站开出时车上的人数。

输入样例

5 7 32 4

输出样例

13

         （1）编程思路。

        在编写程序之前，先找找规律：

        第1站：上车a 人；车上有 a 人；

        第2站：假设上车 b人，则下车 b人；车上仍然是a人；

        第3站：上车人数等于前两站上车人数之和：a+b人，下车人数等于上站上车人数 b人；净上车人数为 a 人；车上有 2a 人；

        第4站：上车人数a+2b，下车人数 a+b；净上车人数 b；车上有2a+b人；

        第5站：上车人数2a+3b，下车人数 a+2b，净上车人数 a+b；车上有 3a+2b人；

        第6站：上车人数3a+5b，下车 2a+3b，净上车人数a+2b；车上有 4a+4b人；

        第7站：上车人数5a+8b，下车 3a+5b，净上车人数2a+3b；车上有 6a+7b人；

……

可以看出，从第4站起，车上人数可以表示为 C1[i]*a+C2[i]*b

定义数组int C1[21]表示a的系数，int C1[21]表示b的系数。

由上面的列举可猜测

C1[i]=C1[i-1]+C1[i-2]-1

C2[i]=C2[i-1]+C2[i-2]+1

设C1[1]=1  C1[2]=1  C1[3]=2， C2[1]=0  C2[2]=0  C2[3]=0

上面列举的第4站到第7站均满足猜测的式子。

这样，第n-1站的车上人数为C1[n-1]*a+C2[n-1]*b，这个人数也是第n站下车的人数m。

即 C1[n-1]*a+C2[n-1]*b=m，由此可以计算出b。

于是，第x 站开出时车上的人数为a*C1[x]+b*C2[x]。

（2）源程序。

#include <stdio.h>

int main(void)

{

    int C1[21]={0,1,1,2},C2[21]={0,0,0,0};

    int a,n,m,x;

    scanf("%d%d%d%d",&a,&n,&m,&x);

    int i;

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

    {

        C1[i]=C1[i-2]+C1[i-1]-1;

        C2[i]=C2[i-2]+C2[i-1]+1;

    }

    int b=(m-a*C1[n-1])/C2[n-1];

    printf("%d",a*C1[x]+b*C2[x]);

    return 0;

}

习题47

47-1  基因序列

题目描述

一种病毒有101和111两种基因序列。任何含有这两种其中一种基因序列的人都会被感染。对于给定的L，表示有2^L个基因长度为L，且基因型互不相同的人（基因只由0和1构成）。问这2^L个人中有多少人不会感染得病。

输入格式

输入包含几个测试用例。对于每个测试用例，它包含一个正整数L（1<=L<=10^8）。输入结束由文件结束指示。

输出格式

对于每个测试用例，输出K mod 2005的值，这里K是不会感染得病的人数。

Sample Input

输入样例

4

输出样例

9

        （1）编程思路。

        设定义数组int a[2000]，其中数组元素a[i]表示基因长度为i的2ⁱ个人中不会感染得病的数量。先枚举L较小的值。显然，a[0]=1。

        若L=1，则基因序列为0或1，都不会感染，a[1]=2；

        若L=2，则基因序列为00、01、10或11，也都不会感染，a[2]=4；

        若L=3，则基因序列为000、001、010、011、100、110时，不会感染，而序列为101或111时会感染，因此a[3]=6；

        若L=4，则基因序列为0000、0001、0010、0011、0100、0110、1000、1001、1100时，不会感染，而序列为0101、0111、1010、1011、1101、1110、1111时会感染，因此a[4]=9；

        进一步列举，可知a[5]=15，a[6]=25，……。

        实际上，长度为L的不会染病的基因序列可以看成长度小于L的不会染病的基因序列扩展而来，当长度为L的基因序列最高位为0时，后面长度为L-1的不会染病的序列也不会染病，情况数为a[L-1]；当最高位为1时，次高位若为0，则第3位也必须为0，后面长度为L-3的不会染病的序列也不会染病，情况数为a[L-3]；次高位若为1，则之后第3位必须为0，且第4位也必须为0，即前缀必须为1100，后面长度为L-4的不会染病的序列也不会染病，情况数为a[L-4]。

        因此，a[L]=a[L-1]+a[L-3]+a[L-4]

        初始情况为：a[0]=1，a[1]=2， a[2]=4，a[3]=6，a[4]=9。

        由于该结果对于2005取模，故必然存在循环节，因此可循环求得循环节，并存储起来。由求得结果知，循环节为200。

      （2）源程序。

#include <stdio.h>

int main()

{

    int a[2005] = {1,2,4,6,9,15};

    int i;

    for (i=6;i<2000;++i)

    {

        a[i]=a[i-1]+a[i-3]+a[i-4];

        a[i]%=2005;

        if (a[i]==a[3] && a[i-1]==a[2] && a[i-2]==a[1] && a[i-3]==a[0]) break;

    }

    int len=i-4+1;       // 循环节长度

    int n;

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

    {

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

    }

    return 0;

}

47-2  Logs Stacking

        本题选自北大POJ题库 （http://poj.org/problem?id=2748）

Description

Daxinganling produces a lot of timber. Before loading onto trains, the timberjacks will place the logs to some place in the open air first. Looking from the sideway, the figure of a logs stack is as follows:

We have known that the number of logs in each layer is fewer than the lower layer for at least one log, and that in each layer the logs are connected in a line. In the figure above, there are 12 logs in the bottom layer of the stack. Now, given the number of logs in the bottom layer, the timberjacks want to know how many possible figures there may be.

Input

The first line of input contains the number of test cases T (1 <= T <= 1000000). Then T lines follow. Every line only contains a number n (1 <= n <= 2000000000) representing the number of logs in the bottom layer.

Output

For each test case in the input, you should output the corresponding number of possible figures. Because the number may be very large, just output the number mod 10^5.

Sample Input

4

1

2

3

5

Sample Output

1

2

5

34

        （1）编程思路。

        题目大意是：给出在最底层的木头的个数，问有多少种堆放木头的方式。要求木头必须互相挨着在一起。

        设a[i]表示最底层有i个木头的堆放木头的方式。显然，a[0]=1，a[1]=1，a[2]=2（一种情况为只有1层，该层放2个木头；另一种情况为堆放两层，最底层放2个木头，上一层放1个木头）。

        由于要求木头挨在一起，底层为i个木头，上层可放0~i-1个木头。当上层为1个时，相应有i-1个位置可放；上层为2个时，相应有i-2个位置可放，…，即：

        a[i]=a[0]+a[1]*(i-1)+a[2]*(i-2)+…+a[i-2]*2+a[i-1]                             （式1）

        同理，a[i-1]= a[0]+a[1]*(i-2)+a[2]*(i-3)+…+a[i-3]*2+a[i-2]              （式2）

        式1—式2可得： a[i]-a[i-1]=a[1]+a[2]+…+a[i-2]+a[i-1]                    （式3）

         同理，     a[i-1]-a[i-2]= a[1]+a[2]+…+a[i-2]                                    （式4）

         将式4代入到式3可得： a[i]-a[i-1]=a[i-1]-a[i-2]+a[i-1]

        即  a[i]=3*a[i-1]-a[i-2]

        由于该结果对于10⁵取模，故必然存在循环节，因此可循环求得循环节，并存储起来。由求得结果知，循环节为75000。

      （2）源程序。

#include <stdio.h>

#define MOD 100000

int main()

{

    int a[200005] = {1,1,2,5};

    int i;

    for (i=4;i<200000;i++)

    {

        a[i]=(3*a[i-1]-a[i-2]+MOD)%MOD;

        if (a[i]==a[1] && a[i-1]==a[0]) break;

    }

    int len=i-2+1;       // 循环节长度

    int t;

    scanf("%d",&t);

    while (t--)

    {

        int n;

        scanf("%d",&n);

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

    }

    return 0;

}

47-3 递归回文划分

问题描述

正整数N的一个划分是一个整数序列，其总和为N，通常在划分序列的各数之间用加号连接。例如，15 = 1+2+3+4+5 = 1+2+1+7+1+2+1。

如果一个划分从前往后读与从后往前读的内容相同，则该划分是回文的。上例中的第一个划分不是回文划分，而第二个划分是回文划分

如果一个划分是回文划分，且其左半部分是递归回文划分或空，则该划分是递归回文划分。上例中的第二个划分也是递归回文划分。

例如，整数7的递归回文划分有：

7，1+5+1，2+3+2，1+1+3+1+1，3+1+3，1+1+1+1+1+1+1

编写一个程序，求输入正整数N的递归回文划分的个数。

输入

输入的第一行包含一个整数N（1<=N<=1000），表示测试数据的个数。

每个测试数据由一行输入组成，其中包含一个正整数N。

输出

对于每个测试数据，输出为：测试数据的编号（从1开始计数）、一个空格和求得的递归回文分区的个数。

输入样例

3

4

7

20

输出样例

1 4

2 6

3 60

        （1）编程思路。

设F[i]表示正整数i的递归回文划分的个数。显然，F[0]=1，F[1]=1。

F[2]=F[0]+F[1]=2，分别是2，1+1；

F[3]=F[0]+F[1]=2，分别是3，1+1+1；

F[4]=F[0]+F[1]+F[2]=4，分别是4，1+2+1，2+2，1+1+1+1；

……

由于可推出，F[i]=F[0]+F[1]+F[2]+…+F[i/2-1]+F[i/2]

        这个式子也容易理解，对于正整数i，递归回文划分可表示为i（情况数为F[0]）、1+(i-2)+1（情况数为F[1]）、2+(i-4)+2（情况数为F[2]）、…、i/2+i/2（或i/2+1+i/2，根据i的奇偶而不同，但情况数均为F[i/2]），所以，F[i]=F[0]+F[1]+F[2]+…+F[i/2-1]+F[i/2]。

        （2）源程序。

#include <stdio.h>

int main()

{

    int f[1001];

    f[0]=1;

    f[1]=1;

    int i,j;

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

    {

       f[i] = 0;

       for (j=0; j<=i/2; j++)

          f[i]+=f[j];

    }

    int t;

    scanf("%d",&t);

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

    {

       int n;

       scanf("%d",&n);

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

    }

    return 0;

}