例50 向下的路徑
問題描述
有一個size=N的圖，如圖1所示，然后我們將找到一條從頂部節點到底部節點的向下路徑，
首先，我們選擇頂部節點作為開始，然后在任何節點，我們都可以沿著藍色邊緣水平或向下移動，到達下一個節點，當我們到達其中一個底部節點時，移動結束，然后，我們可以得到從頂部節點到底部節點的向下路徑，請注意，在移動程序中，每條藍邊最多走過1次，
例如，size=2時，圖2中的黃色路徑顯示了8條向下的路徑，
您的任務是計算存在多少向下的路徑，
輸入
第一行中有一個整數T（1<=T<=1000），表示總共有T個測驗用例，
對于每個測驗用例，只有一個整數N（1<=N<=10^18）表示圖形的大小，
輸出
對于每個測驗用例，在一行中輸出上述任務的正確答案，
因為答案可能非常大，只輸出它除以1000003的余數即可，
輸入樣例
2
1
2
輸出樣例
2
8
（1）編程思路，
設a[i]表示size=i時從頂部節點到底部節點的向下路徑的條數，
a[1]=2=1+1
a[2]=8=2*2*a[1]
a[3]=48=3*2*a[2]=3*2*8 （size=3時，可以先從頂部節點移動到最底行的上一行，此時方法數為a[2]，其結束點一定在上一行的3個節點之一，這3個節點，每個結點均有兩種方法向下移動到底行，故a[3]=3*2*a[2]）
......
a[n]= 2*n*a[n-1]
即：a[n]=2^n*n！
因為a[n]=2^n*n!，所以當n>1000003時，n！中有1000003這個因數，故ans=0，
（2）源程式，
#include <stdio.h>
#define MAXN 1000003
long long a[MAXN];
int main()
{
a[0]=0; a[1]=2;
int i;
for (i=2;i<MAXN;i++){
a[i]=(a[i-1]*2*i)%MAXN;
}
int t;
scanf("%d",&t);
while(t--){
long long n;
scanf("%lld",&n);
if (n<=MAXN) printf("%lld\n",a[n%MAXN]);
else printf("0\n");
}
return 0;
}
習題50
50-1 三角形計數
本題選自洛谷題庫 （https://www.luogu.org/problem/P2807）
題目描述
把大三角形的每條邊n等分，將對應的等分點連接起來（連接線分別平行于三條邊），這樣一共會有多少三角形呢？編程來解決這個問題，
輸入格式
第一行為整數t(≤100)，表示測驗資料組數；接下來t行，每行一個正整數n(≤500)，
輸出格式
對于每個n，輸出一個正整數，表示三角形個數，
輸入樣例
3
1
2
3
輸出樣例
1
5
13
（1）編程思路，
設a[i]表示邊長為i的三角形個數，
先用下圖所示的邊長為4的三角形來列舉邊長n<=4的三角形個數，
顯然，a[1]=1，
當i=2時，對應圖中上兩行，邊長為1的小三角形有4個，其中3個頂點向上（紅色三角形），1個頂點向下（白色三角形）；邊長為2的三角形有1個，所以，a[2]=5，
當i=3時，對應圖中上三行，可以看成是在上兩行（i=2）的基礎上增加第3行擴展而來，此時，增加了邊長為1的小三角形有5個，其中3個頂點向上（紅色三角形），2個頂點向下（白色三角形）；增加了邊長為2的三角形有2個，頂點均向上；增加了邊長為3的三角形1個，頂點向上，所以，a[3]=a[2]+5+2+1=13，
當i=4時，對應圖中全部四行，可以看成是在上面三行（i=3）的基礎上增加第4行擴展而來，此時，增加了邊長為1的小三角形有7個，其中4個頂點向上（紅色三角形），3個頂點向下（白色三角形）；增加了邊長為2的三角形有4個，其中3個頂點向上，1個頂點向下；增加了邊長為3的三角形2個，頂點均向上；增加了邊長為4的三角形1個，頂點向上，所以，a[4]=a[3]+7+4+2+1=27，
更一般地，i=n時，可以看成是在上n-1行（i=n-1）的基礎上增加第n行而來，此時，可分兩種情況討論：
1）增加的頂點向上的三角形中，邊長為1的，增加了n個，邊長為2的，增加了n-1個，…，邊長為n-1的，增加了2個，邊長為n的，增加了1個，共增加了n+(n-1)+…+2+1=(n+1)*n/2個，
2）增加的頂點向下的三角形中，又按n的奇偶不同分開討論，當n為偶數時，邊長為1的，增加了n-1個，邊長為2的，增加了n-3個，…，邊長為n/2-1的，增加了2個，邊長為n/2的，增加了1個，共增加了(n-1+1)*(n/2) / 2=n*n/4個；當n為奇數時，邊長為1的，增加了n-1個，邊長為2的，增加了n-3個，…，邊長為(n-1)/2的，增加了2個，邊長為(n+1)/2的，增加了0個，共增加了((n-1+2)*(n-1)/2) / 2=(n+1)*(n-1)/4個，
由此得到，若n為偶數，a[n]=a[n-1]+(n+1) * n / 2 + n * n /4
若n為奇數，a[n]=a[n-1] + (n + 1 ) * n / 2 + (n+1) * (n-1) / 4
（2）源程式，
#include <stdio.h>
int main()
{
int a[501]={0,1};
int i;
for (i=2;i<=500;i++)
{
if(i%2==0) a[i]=a[i-1]+(1+i)*i/2+i*i/4;
else a[i]=a[i-1]+(1+i)*(i-1)/4+(1+i)*i/2;
}
int t,n;
scanf("%d",&t);
for (i = 1;i <= t;i++)
{
scanf("%d",&n);
printf("%d\n",a[n]);
}
return 0;
}
50-2 1和1不相鄰
問題描述
給定一個正整數n，請求出n位二進制數中，確定不包含相鄰1的n位序列的個數，例如，對于n=3，答案為5（序列000、001、010、100、101符合要求，而011、110、111不符合要求），
輸入
第1行給出測驗用例的數量T，
對于每個測驗用例，在一行中給出一個小于45的正整數n，
輸出
每個測驗用例的輸出都以一行開頭，其中包含“Scenario #i:”，其中i是從1開始的用例編號，然后列印一行，其中包含沒有相鄰1的n位序列數，
輸入樣例
2
3
1
輸出樣例
Scenario #1:
5
Scenario #2:
2
（1）編程思路，
設a[i]表示不包含相鄰1的i位二進制數序列的個數，由于1不能連續，那么長度為n的二進制數，第1位是1，則第2位只能為0，情況總數等于a[n-2]，第1位是0，則情況總數等于a[n-1]，因此，a[n]=a[n-1]+a[n-2]，
（2）源程式，
#include <stdio.h>
int main()
{
long long a[50];
a[1] = 2;
a[2] = 3;
int i;
for (i=3; i<=45; i++)
{
a[i]=a[i-1]+a[i-2];
}
int t,n;
scanf("%d",&t);
for (i=1;i<=t;i++)
{
scanf("%d",&n);
printf("Scenario #%d:\n",i);
printf("%lld\n\n",a[n]);
}
return 0;
}
50-3 跳馬
問題描述
馬在一個n行m列棋盤的左下角（1,1）的位置，它想要走到終點右上角（n，m）的位置，而眾所周知，馬是要走日子格的，但現在這匹馬不想走回頭路——也就是說，它只會朝向上的方向跳，不會朝向下的方向跳，
這匹馬想從起點跳到終點，一共有多少種走法呢？
輸入格式
第一行兩個數n，m（n<=100,m<=100），表示一個n行m列的棋盤，馬最初是在左下角（1,1）的位置，終點在右上角（n，m）的位置，
輸出格式
輸出有一行，一個數表示走法數，由于答案可能很大，所以輸出答案除以1000000007所得的余數即可，
輸入樣例
4 4
輸出樣例
2
（1）編程思路，
設F[i] [j] 表示馬從左下角（1,1）跳到（i，j）的走法種數，
由于只能往上跳，即跳動程序中，行i只能增大，因此第1行中的各位置是怎么也跳不上去，即F[1][j]=0（1<=j<=m），又因為剛開始就在（1,1）這個位置上，從（1,1）往上只能跳兩個點（2,3）和（3,2），即F[2][3]=F[3][2]=1，.
由于位置（i，j），只能從（i-1，j-2），（i-2，j-1），（i-2，j+1），（i-1，j+2）這四個點跳過來，因此有
F[i][j]= F[i-1][j-2]+F[i-2][j-1]+F[i-2][j+1]+F[i-1][j+2]
需要注意的是，由于棋盤是有邊界的，因此在計算時，對每個點判斷一下，如果滿足條件就加上，否則不加，例如，若i-1>1 && j-2>=1，F[i-1][j-2]就可以加上；若i-1>1 && j+2<=m，F[i-1][j+2]就可以加上，
（2）源程式，
#include <stdio.h>
int main()
{
int f[105][105]={0};
int n,m;
scanf("%d%d",&n,&m);
f[2][3]=f[3][2]=1;
int i,j;
for (i=1; i<=n; i++)
{
for (j=1; j<=m; j++)
{
if (i==1) f[i][j] = 0;
if (i-2>1 && j+1<=m)
f[i][j] = (f[i][j]+f[i-2][j+1])%1000000007;
if (i-1>1 && j+2<=m)
f[i][j] = (f[i][j]+f[i-1][j+2])%1000000007;
if (i-1>1 && j-2>=1)
f[i][j] = (f[i][j]+f[i-1][j-2])%1000000007;
if (i-2>1 && j-1>=1)
f[i][j] = (f[i][j]+f[i-2][j-1])%1000000007;
}
}
printf("%d\n",f[n][m]);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/412901.html
標籤：其他