ねずみの繁殖問題

同級生の同級生がこんな質問をした.
1組のネズミがいて、生まれて1週間後に1対のネズミに成長して、2週間後にこのネズミは最初のネズミを産んで、3週間後に先週生まれたネズミはネズミになって、元のネズミはまた1対のネズミを産んでから死んで、4週間後に、最初のネズミ(この時すでにラットです)はまた1対のネズミを産んで、この時合計3対のネズミがいます.プログラミングして、N週間後に何組のネズミがあることを計算しますか?
 
まず、この問題はマウスが死ななければ、典型的なフィボナッチ数列である(実際にはフィボナッチ数列がウサギの繁殖を最初に記述している)
死を加えると、考え直す必要があります~
方法1:
自然はスーパー水と同时にとても役に立ちます---法则を探します.
周数0-----1-----2------3-----4------5-----6------7.....
鼠数1-----1-----2------3------4-----5------7.....
隣接する2つの和は、2週間と3週間の和が5週間、4週間と5週間の和が7週間であることが容易にわかります.
だから再帰する:

 1 #include <iostream>

 2 

 3 using namespace std;

 4 

 5 int mouse(int n)

 6 {

 7     if (0 == n)

 8     {

 9         return 1;

10     }

11     else if (1 == n)

12     {

13         return 1;

14     }

15     else if (2 == n)

16     {

17         return 2;

18     }

19     else

20     {

21         return mouse(n-2)+mouse(n-3);

22     }

23 }

24 

25 int main()

26 {

27     int n;

28 

29     while (cin >> n)

30     {

31         cout << mouse(n) << endl;

32     }

33 

34     return 0;

35 }

方法2:
再帰が遅すぎて、しかもこの問題に対して、明らかに再帰しか使えないほど複雑ではありません.
2つ目の方法は、繁殖過程全体を手動でシミュレートし、異なる年齢層のマウスを配列して保存することです.つまり、プッシュで作ることにします~

 1 #include <iostream>

 2  

 3  using namespace std;

 4  

 5  int num(int);

 6  

 7  int main()

 8  {

 9      int n;

10      while (cin >> n)

11      {

12          cout << "The answer is " << num(n) << endl;

13      }

14  

15  

16      return 0;

17  }

18  

19  int num(int n)

20  {

21      int a[3] = {1, 0, 0};

22      int t1, t2;

23  

24      for (int i=0; i<n; ++i)

25      {

26          t1 = a[1];

27          t2 = a[2];

28          a[1] = a[0];

29          a[2] = t1;

30          a[0] = t1 + t2;

31  

32          cout << i+1 << " has " << (a[0]+a[1]+a[2]) << " mice" << endl;

33      }

34      return (a[0]+a[1]+a[2]);

35  }

================================================================
また次の文があって、同級生の同級生の先生は大数でも処理できると言った.
追加:

 1 #include <iostream>

 2 #include <cstring>

 3 

 4 const int MAX = 100000;

 5 

 6 using namespace std;

 7 

 8 void add(char *str1, char *str2, char *str3);

 9 void num(int, char *);

10 

11 int main()

12 {

13     int n;

14     char s[MAX];

15     

16     while (cin >> n)

17     {

18         num(n, s);

19         cout << "The answer is " << s << endl;

20     }

21 

22 

23     return 0;

24 }

25 

26 void num(int n, char *s)

27 {

28     //Big Int

29     char a0[MAX]; 

30     char a1[MAX];

31     char a2[MAX];

32     char t1[MAX];

33     char t2[MAX]; 

34 

35     strcpy(a0, "1");

36     strcpy(a1, "0");

37     strcpy(a2, "0");

38     

39     for (int i=0; i<n; ++i)

40     {

41         strcpy(t1, a1);

42         strcpy(t2, a2);

43         strcpy(a1, a0);

44         strcpy(a2, t1);

45         add(t1, t2, a0);

46     }

47     char temp1[MAX];

48     char temp2[MAX];

49     char temp3[MAX];

50     strcpy(temp1, a0);

51     add(temp1, a1, temp2);

52     add(temp2, a2, temp3);

53     strcpy(s, temp3);

54 }

55 

56 void add(char *str1, char *str2, char *str3)

57 {

58     int i, j, i1, i2, tmp, carry;

59     int len1 = strlen(str1);

60     int len2 = strlen(str2);

61     char ch;

62 

63     i1 = len1 - 1;

64     i2 = len2 - 1;

65     j = carry = 0;

66 

67     for ( ; i1>=0 && i2>=0; ++j, --i1, --i2)

68     {

69         tmp = str1[i1] - '0' + str2[i2] - '0' + carry;

70         carry = tmp / 10;

71         str3[j] = tmp % 10 + '0';

72     }

73     while (i1 >= 0)

74     {

75         tmp = str1[i1--] - '0' + carry;

76         carry = tmp/10;

77         str3[j++] = tmp%10 + '0';

78     }

79     while (i2 >= 0)

80     {

81         tmp = str2[i2--] -'0' + carry;

82         carry = tmp/10;

83         str3[j++] = tmp%10 + '0';

84     }

85 

86     if (carry)

87     {

88         str3[j++] = carry + '0';

89     }

90     str3[j] = '\0';

91 

92     for (i=0, --j; i<j; ++i, --j)

93     {

94         ch = str3[i];

95         str3[i] = str3[j];

96         str3[j] = ch;

97     }

98 }