程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ 2506 Tiling 高精度

POJ 2506 Tiling 高精度

編輯:C++入門知識

POJ 2506 Tiling 高精度


題目大意:給出一個2*n的條形區域,問用2*1和2*2的方格一共有多少種擺放的方法。


思路:f[i] = f[i - 1] + f[i - 2] * 2

寫一個高精度加法就可以了。


CODE:

#include 
#include 
#include 
#include 
#include 
#define MAX 260
#define BASE 1000
using namespace std;

struct BigInt{
	int num[MAX],len;

	BigInt(int _ = 0) {
		memset(num,0,sizeof(num));
		if(_) {
			num[1] = _;
			len = 1;
		}
		else	len = 0;
	}
	BigInt operator +(const BigInt &a)const {
		BigInt re;
		re.len = max(len,a.len);
		int temp = 0;
		for(int i = 1; i <= re.len; ++i) {
			re.num[i] = num[i] + a.num[i] + temp;
			temp = re.num[i] / BASE;
			re.num[i] %= BASE;
		}
		if(temp)	re.num[++re.len] = temp;
		return re;
	}
}f[MAX];

ostream &operator <<(ostream &os,const BigInt &a) 
{
	os << a.num[a.len];
	for(int i = a.len - 1; i; --i)
		os << fixed << setfill('0') << setw(3) << a.num[i];
	return os;
}

int main()
{
	f[0] = BigInt(1);
	f[1] = BigInt(1);
	f[2] = BigInt(3);
	for(int i = 3; i <= 250; ++i)
		f[i] = f[i - 1] + f[i - 2] + f[i - 2];
	int x;
	while(scanf("%d",&x) != EOF)
		cout << f[x] << endl;
	return 0;
}


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved