題目的意思很明確,不能單獨有一個女生站一起。
假設有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; }