例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×104，
輸出格式
輸出一行一個整數表示答案：從 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的2i個人中不會感染得病的數量，先列舉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]
由于該結果對于105取模，故必然存在回圈節，因此可回圈求得回圈節，并存盤起來，由求得結果知，回圈節為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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/412842.html
標籤：C