文科生的悲哀（使用递归发现规律）

解题思路:

由递归发现规律...

注意事项:单单用递归是会超时的！！！

参考代码:

#include <iostream>

using namespace std;

int sum = 0;

int N;

void step(int n, int course)//运用递归求解  很明显该方法效率不高  只能提供一个思路

{

if (n == N)//考试排满了则多一种排列方式

{

sum++;

}

else

{

switch (course)

{

case 1:step(n + 1, 3); break;//1 2 3 4分别代表政治 综合 历史 地理

case 2:step(n + 1, 4); break;

case 3:

{

step(n + 1, 1);

step(n + 1, 4);

break;

}

case 4:

{

step(n + 1, 2);

step(n + 1, 3);

break;

}

}

}

}

/*int main()

{

while (cin >> N)

{

sum = 0;

step(1, 1);//第一场考试是政治（政治是1）

cout <<"answer:"<< sum << endl;

}

}*/

int main()//由递归求解之后很明显能发现：M[i] = M[i - 1] + M[i - 2];

{

int M[10010] = { 0 };

int N;

while (cin >> N)

{

M[1] = M[2] = 1;

for (int i = 3; i <= N; i++)

{

M[i] = M[i - 1] + M[i - 2];

if (M[i] >= 7654321)M[i] %= 7654321;

}

cout << "answer:" << M[N] << endl;

}

}