程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> 杭電ACM1297——Children’s Queue~~大數相加的應用

杭電ACM1297——Children’s Queue~~大數相加的應用

編輯:關於C++

題目的意思很明確,不能單獨有一個女生站一起。

假設有N個人。

1.最後一個人是男生,則有F(N - 1)。

2.最後一個人是女生,則第N - 1也是女生,則有F(N - 1)。

但還有一種就是,第N - 2個是女生,(是男生的話,包含在F(N - 1)中),但是第N - 3 個是男生,則不包含在上面的情況中,但是也是符合的。也就是最後三個是女生,倒數第四個是男生。也就是還有F(N - 4)種。

 

所以有遞推公式:F(N) = F(N - 1) + F(N - 2) + F(N - 4)。

 

下面的是AC的代碼:

 

#include 
#include 
using namespace std;

char num[1001][300];

void add(int x, int y)         //大數相加函數
{
	int temp[300];
	int len1 = strlen(num[x]);
	int len2 = strlen(num[y]);
	int i, j, k = 0;
	for(i = len1 - 1, j = len2 - 1; i >= 0 && j >= 0; i--, j--)
	{
		temp[k++] = num[x][i] - '0' + num[y][j] - '0';
	}
	while(i >= 0)
	{
		temp[k++] = num[x][i--] - '0';
	}
	while(j >= 0)
	{
		temp[k++] = num[y][j--] - '0';
	}
	for(i = 0; i < k - 1; i++)
	{
		if(temp[i] >= 10)
		{
			temp[i + 1] += temp[i] / 10;
			temp[i] %= 10;
		}
	}
	if(temp[k - 1] >= 10)
	{
		temp[k] = temp[k - 1] / 10;
		temp[k - 1] %= 10;
		k++;
	}
	i = k - 1;
	j = 0;
	while(i >= 0)
	{
		num[x][j++] = temp[i--] + '0';
	}
	num[x][k] = '\0';
}

int main()
{
	int i;
	num[0][0] = '1'; num[0][1] = '\0';
	num[1][0] = '1'; num[1][1] = '\0';
	num[2][0] = '2'; num[2][1] = '\0';
	num[3][0] = '4'; num[3][1] = '\0';
	num[4][0] = '7'; num[4][1] = '\0';
	for(i = 5; i <= 1000; i++)
	{
		strcpy(num[i], num[i - 1]);
		add(i, i - 2);
		add(i, i - 4);
	}
	while(cin >> i)
	{
		cout << num[i] << endl;
	}
	return 0;
}


 

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