UVa 10334 Ray Through Glasses

本題連結

想法：
 　　觀察圖，能造成下次數量變多的折線，其最右邊"尖點"都位在上面那條線或下面那條線，例如a2=3，有'2'個"尖點"位在上面那條線，因此能使得a3比a2多出'2'條摺線(a3=a2+2=5)，在觀察a3，有'3'個尖點，因此能使a4比a3多出3個折線(a4=a3+3=8)。那麼尖點的產生方式在於前一個的折線數量，例如a2的尖點來自於a1的箭頭與上面那條線的交點，所以a2尖點的數量=a1，因此我們可得a3=a2+(a2尖點)=a2+a1。
　　簡而言之，本題為費伯那西數列，a(n)=a(n-1)+a(n-2)，而另外由於n可到1000，因此要自己寫大數加法。

	#include <cstdio>
	using namespace std;
	int fib[1001][501]={0};
	int main()
	{
	fib[0][0]=1;
	fib[1][0]=2;
	for (int i=2; i<=1000; i++){
	for (int j=0; j<500; j++){
	fib[i][j] += fib[i-2][j]+fib[i-1][j];
	if (fib[i][j]>9){
	fib[i][j] -= 10;
	fib[i][j+1]++;
	}
	}
	}
	int n;
	while (scanf("%d",&n)!=EOF) {
	int i = 500;
	while (fib[n][--i] == 0);
	for (; i>=0; i--)
	printf("%d",fib[n][i]);
	printf("\n");
	}
	return 0;
	}

view raw [UVa] 10334 Ray Through Glasses.cpp hosted with ❤ by GitHub