時間限制: 1000 ms 內存限制: 65535 K
問題描述
一只鼹鼠想要探索北方的一塊草地，這塊草地是一個無限大的方格矩陣，由於地鼠只會往前不會後退，所以他只會朝北或者東、西方向刨。由於刨過的地方已不是土地，所以不會再次進入這個方格。現在這只鼹鼠打算刨n步，它想要知道能有多少種刨的方案，你能幫他算算嗎？注：只要有任何的不同，就算是不同的刨法。
輸入
有多組輸入，每組是一個整形n，代表刨的步數，1<= n <= 100。
輸出
對於每組輸入，輸出總的方案數。
樣例輸入
1
2
樣例輸出
3
7
提示
無來源
小白菜
思路 ： 很明顯 他只能往3個方向走 假設 他只能往 前 和 上下走 我們用箭頭標注每一步從某處走到某處 假設上一步往前的個數為s3(下一步能走3個方向) 往上和往下的和為s2（下一步能走2個方向） 那麼對於下一次 每個往前的可以為s2增加2個 每個 往上和往下的可以產生一個往前的 由此 可知
s3[i]=s2[i-1]+s3[i-1];
s2[i]=s3[i-1]*2+s2[i-1];
ans[i]=s2[i]+s3[i];本題的坑在於 用 int 會爆掉 用 long long會爆掉 用unsigned long long 也會爆掉 用unsigned long long 千萬要注意 如果最大的數據看著不是負數並不代表不會爆掉 此時一定要多輸入幾個數 看看那些數是否爆掉 或者是否比最大數據對應的值更加大一些 做題一定要細心 所以只有用大數去做了 注意 用大數並不難 大數不是很復雜 不要怕大數 就是普普通通的模擬 不要被它的面具嚇到 看看拍出來後 多簡單啊 自己可一定要征服大數
[cpp]
#include<string.h> #include<stdio.h> int s2[111][100],s3[111][100],ans[111][100]; void solve( int str[],int ss[],int sss[]) { int i; for(i=0;i<100;i++) { str[i]+=(ss[i]+sss[i]); if(str[i]>=10) { str[i+1]=str[i]/10; str[i]=str[i]%10; } } } void solve2(int str[],int sss[],int ss[]) { int i; for(i=0;i<100;i++) sss[i]=sss[i]*2; for(i=0;i<100;i++) { str[i]+=(sss[i]+ss[i]); if(str[i]>=10) { str[i+1]=str[i]/10; str[i]=str[i]%10; } } } void print(int s[]) { int i; for(i=99;i>=0;i--) if(s[i]!=0) break; while(i>=0) { printf("%d",s[i]); i--; } printf("\n"); } int main() { int n,i; s2[1][0]=2; s3[1][0]=1; ans[1][0]=3; for(i=2;i<=100;i++) { solve(s3[i],s2[i-1],s3[i-1]); solve2(s2[i],s3[i-1],s2[i-1]); solve(ans[i],s2[i],s3[i]); /*a3[i]=a2[i-1]+a3[i-1]; a2[i]=a3[i-1]*2+a2[i-1]; ans[i]=a2[i]+a3[i];*/ } while(scanf("%d",&n)!=EOF) { print(ans[n]); } return 0; } #include<string.h>
#include<stdio.h>
int s2[111][100],s3[111][100],ans[111][100];
void solve( int str[],int ss[],int sss[])
{
int i;
for(i=0;i<100;i++)
{
str[i]+=(ss[i]+sss[i]);
if(str[i]>=10)
{
str[i+1]=str[i]/10;
str[i]=str[i]%10;
}
}
}
void solve2(int str[],int sss[],int ss[])
{
int i;
for(i=0;i<100;i++)
sss[i]=sss[i]*2;
for(i=0;i<100;i++)
{
str[i]+=(sss[i]+ss[i]);
if(str[i]>=10)
{
str[i+1]=str[i]/10;
str[i]=str[i]%10;
}
}
}
void print(int s[])
{
int i;
for(i=99;i>=0;i--)
if(s[i]!=0) break;
while(i>=0)
{
printf("%d",s[i]);
i--;
}
printf("\n");
}
int main()
{
int n,i;
s2[1][0]=2;
s3[1][0]=1;
ans[1][0]=3;
for(i=2;i<=100;i++)
{
solve(s3[i],s2[i-1],s3[i-1]);
solve2(s2[i],s3[i-1],s2[i-1]);
solve(ans[i],s2[i],s3[i]);
/*a3[i]=a2[i-1]+a3[i-1];
a2[i]=a3[i-1]*2+a2[i-1];
ans[i]=a2[i]+a3[i];*/
}
while(scanf("%d",&n)!=EOF)
{
print(ans[n]);
}
return 0;
}
