母牛数量算法

kuaizaifeng

强阿
好算法

jovent

年数N

2的(N/4)次方

每次生3头母牛的，就是3的(N/4)次方。

jovent

只有在N/4＝整数的时候母牛才会生小牛，题目没有给出母牛早产或难产

czx1124

用数学等比数列算，我的答案year=100,cow=33554432
#include<iostream.h>
int js(int);
int main()
{int cow,year;
cout<<"Input  year:";
cin>>year;
if (year>3&&year<12
{year=year-year%4;   //4年生一次，超过4年N倍按4年N倍算
cow=js(year);
cout<<"cow="<<cow;
return 0;
}
else if(year<1)
        cout<<"input is wrong";
else if(year<4&&year>0)
        cout<<"cow is:1";
else cout<<"input year is too big";
}
int js(int n)   //计算生的牛
{int i,b,c;
b=(n/4)+1;
c=1;   
/*这是等比数列吧，1，2，4，8…………用公式a(n)=a(0)*q的（n-1)次方  q:公比 ，a（0）:首项  */
for(i=1;i<b;++i) //算q的N-1次方
    { c=2*c;
      }
return c;
}

[ 本帖最后由 czx1124 于 2006-6-24 21:41 编辑 ]

jovent

原帖由 czx1124 于 2006-6-24 21:35 发表
用数学等比数列算，我的答案year=100,cow=33554432
#include<iostream.h>
int js(int);
int main()
{int cow,year;
cout<<"Input  year:";
cin>>year;
if (year>3&&am ...

我用计算器计算的结果也是33554432，不会写程序啊，HOHO~

feeling

不需要那么麻烦吧，就是一个简单的命题：
每4年，母牛数量翻番，计算n年后有多少母牛。

1. 
   
2. // 就是计算 2^(n/4)
   

复制代码

plxlj

int _calc(n)
{
        int a[4]={1,0,0,0};
        int i,sum=0,tmp;
        for(i=1; i<n; i++){
                a[3]=a[2]+a[3];
                tmp=a[0];
                a[0]=a[3];
                a[2]=a[1];
                a[1]=tmp;
               
        }
        sum=a[0]+a[1]+a[2]+a[3];
        return sum;
}

int main()
{
        int n=30;
        printf("%d\n",_calc(n));
        return 0;
}

stephen412

贴一个我的答案阿：
呵呵！应该比较节省资源哦！
我没有用递归的方法，我是针对这组数据的特点进行计算的。
#include<stdio.h>
   int fun(int n)
       {
         int i,sum,tmp;     / sum 最后的结果 ， i , tmp  中间量
         sum=n-3;           /  第一只牛第四年才可以每年生小牛
         tmp=0;         
         if(n<=3)             / 如果计算的年限小于等于3年
            sum+=0;
         else                   / 计算的年限大于3年
         {
         for(i=1;i<=sum-3;i++)       /所有的奶牛都要第四年生小牛， 所以sum-3 。
                                 /不同年头出生的牛，他们依次生出的牛的数目递减 如10年，4 ，3 ， 2 ， 1
            {
               tmp+=i;
             }
          }
         sum+=tmp;                     /计算最后的总结果
         return sum;

       }

   int main()
       {
          int n;
          printf("Please Input the n:\n");    / 提示输入计算的年数
          scanf("%d",&n);
          printf("The Result Is :%d\n",fun(n));

        }
是不是资源消耗很小阿！

dzbjet

o的递归的，估计用ULONG，也会溢出。

1. 
   
2. typedef unsigned long ULONG;
   
3. 
   
4. ULONG get_cow_num(int year);
   
5. ULONG f(int year);
   
6. 
   
7. void main()
   
8. {
   
9.         cout << get_cow_num(100) << endl;
   
10. }
    
11. 
    
12. ULONG get_cow_num(int year)
    
13. {
    
14.         ULONG sum = 0;
    
15.         for( int i = 1; i <= year; ++i )
    
16.                 sum += f(i);
    
17. 
    
18.         return sum;
    
19. }
    
20. 
    
21. ULONG f(int year)
    
22. {
    
23.         ULONG ret = 0;
    
24. 
    
25.         switch(year)
    
26.         {
    
27.         case 1:
    
28.                 ret = 1;
    
29.                 break;
    
30.         case 2:
    
31.         case 3:
    
32.                                 ret = 0;
    
33.                                 break;
    
34.         case 4:
    
35.                 ret = 1;
    
36.                 break;
    
37.         default:
    
38.                 for( int k = 1; k <= year - 4; ++k )
    
39.                 {
    
40.                         ret += f(k);
    
41.                 }
    
42.         }
    
43. 
    
44.         return ret;
    
45. }
    

复制代码

[ 本帖最后由 dzbjet 于 2006-9-7 16:35 编辑 ]

dzbjet

改善后的：用了一个全局数组，存储计算过的f[year]，消除递归。
不知道对不对，大家指正：

1. 
   
2. #include <iostream>
   
3. #include <vector>
   
4. #include <algorithm>
   
5. #include <functional>
   
6. #include <string>
   
7. #include <iterator>
   
8. #include <map>
   
9. #include <vector>
   
10. 
    
11. #include <time.h>
    
12. 
    
13. using namespace std;
    
14. 
    
15. typedef double ULONG;
    
16. 
    
17. ULONG get_cow_num(int year);
    
18. ULONG f(int year);
    
19. 
    
20. ULONG ff[101] = { 0 };
    
21. 
    
22. void main()
    
23. {
    
24.         memset(ff, 0, sizeof(ff));
    
25.        
    
26.         printf("%.f\n", get_cow_num(100));// << endl;
    
27. 
    
28. }
    
29. 
    
30. ULONG get_cow_num(int year)
    
31. {
    
32.         ULONG sum = 0;
    
33.         for( int i = 1; i <= year; ++i )
    
34.         {
    
35.                 ULONG temp = f(i);
    
36.                 sum += temp;
    
37.                 printf("f(%d) = %.f, finished!   sum[%d] = %.f\n", i, temp, i, sum);
    
38.         }
    
39. 
    
40.         return sum;
    
41. }
    
42. 
    
43. ULONG f(int year)
    
44. {
    
45.         if( ff[year] ) return ff[year];
    
46. 
    
47.         ULONG ret = 0;
    
48. 
    
49.         ULONG temp = 0;
    
50. 
    
51.         switch(year)
    
52.         {
    
53.         case 1:
    
54.                 ret = 1;
    
55.                 break;
    
56.         case 2:
    
57.         case 3:
    
58.                 ret = 0;
    
59.                 break;
    
60.         case 4:
    
61.                 ret = 1;
    
62.                 break;
    
63.         default:
    
64.                 for( int k = 1; k <= year - 3; ++k )
    
65.                 {
    
66.                         // ret += f(k), 不需要了
    
67.                         ret += ff[k];
    
68.                 }
    
69.         }
    
70. 
    
71.         ff[year] = ret;
    
72. 
    
73.         return ret;
    
74. }
    

复制代码

输出：

1. 
   
2. f(1) = 1, finished!   sum[1] = 1
   
3. f(2) = 0, finished!   sum[2] = 1
   
4. f(3) = 0, finished!   sum[3] = 1
   
5. f(4) = 1, finished!   sum[4] = 2
   
6. f(5) = 1, finished!   sum[5] = 3
   
7. f(6) = 1, finished!   sum[6] = 4
   
8. f(7) = 2, finished!   sum[7] = 6
   
9. f(8) = 3, finished!   sum[8] = 9
   
10. f(9) = 4, finished!   sum[9] = 13
    
11. f(10) = 6, finished!   sum[10] = 19
    
12. f(11) = 9, finished!   sum[11] = 28
    
13. f(12) = 13, finished!   sum[12] = 41
    
14. f(13) = 19, finished!   sum[13] = 60
    
15. f(14) = 28, finished!   sum[14] = 88
    
16. f(15) = 41, finished!   sum[15] = 129
    
17. f(16) = 60, finished!   sum[16] = 189
    
18. f(17) = 88, finished!   sum[17] = 277
    
19. f(18) = 129, finished!   sum[18] = 406
    
20. f(19) = 189, finished!   sum[19] = 595
    
21. f(20) = 277, finished!   sum[20] = 872
    
22. f(21) = 406, finished!   sum[21] = 1278
    
23. f(22) = 595, finished!   sum[22] = 1873
    
24. f(23) = 872, finished!   sum[23] = 2745
    
25. f(24) = 1278, finished!   sum[24] = 4023
    
26. f(25) = 1873, finished!   sum[25] = 5896
    
27. f(26) = 2745, finished!   sum[26] = 8641
    
28. f(27) = 4023, finished!   sum[27] = 12664
    
29. f(28) = 5896, finished!   sum[28] = 18560
    
30. f(29) = 8641, finished!   sum[29] = 27201
    
31. f(30) = 12664, finished!   sum[30] = 39865
    
32. f(31) = 18560, finished!   sum[31] = 58425
    
33. f(32) = 27201, finished!   sum[32] = 85626
    
34. f(33) = 39865, finished!   sum[33] = 125491
    
35. f(34) = 58425, finished!   sum[34] = 183916
    
36. f(35) = 85626, finished!   sum[35] = 269542
    
37. f(36) = 125491, finished!   sum[36] = 395033
    
38. f(37) = 183916, finished!   sum[37] = 578949
    
39. f(38) = 269542, finished!   sum[38] = 848491
    
40. f(39) = 395033, finished!   sum[39] = 1243524
    
41. f(40) = 578949, finished!   sum[40] = 1822473
    
42. f(41) = 848491, finished!   sum[41] = 2670964
    
43. f(42) = 1243524, finished!   sum[42] = 3914488
    
44. f(43) = 1822473, finished!   sum[43] = 5736961
    
45. f(44) = 2670964, finished!   sum[44] = 8407925
    
46. f(45) = 3914488, finished!   sum[45] = 12322413
    
47. f(46) = 5736961, finished!   sum[46] = 18059374
    
48. f(47) = 8407925, finished!   sum[47] = 26467299
    
49. f(48) = 12322413, finished!   sum[48] = 38789712
    
50. f(49) = 18059374, finished!   sum[49] = 56849086
    
51. f(50) = 26467299, finished!   sum[50] = 83316385
    
52. f(51) = 38789712, finished!   sum[51] = 122106097
    
53. f(52) = 56849086, finished!   sum[52] = 178955183
    
54. f(53) = 83316385, finished!   sum[53] = 262271568
    
55. f(54) = 122106097, finished!   sum[54] = 384377665
    
56. f(55) = 178955183, finished!   sum[55] = 563332848
    
57. f(56) = 262271568, finished!   sum[56] = 825604416
    
58. f(57) = 384377665, finished!   sum[57] = 1209982081
    
59. f(58) = 563332848, finished!   sum[58] = 1773314929
    
60. f(59) = 825604416, finished!   sum[59] = 2598919345
    
61. f(60) = 1209982081, finished!   sum[60] = 3808901426
    
62. f(61) = 1773314929, finished!   sum[61] = 5582216355
    
63. f(62) = 2598919345, finished!   sum[62] = 8181135700
    
64. f(63) = 3808901426, finished!   sum[63] = 11990037126
    
65. f(64) = 5582216355, finished!   sum[64] = 17572253481
    
66. f(65) = 8181135700, finished!   sum[65] = 25753389181
    
67. f(66) = 11990037126, finished!   sum[66] = 37743426307
    
68. f(67) = 17572253481, finished!   sum[67] = 55315679788
    
69. f(68) = 25753389181, finished!   sum[68] = 81069068969
    
70. f(69) = 37743426307, finished!   sum[69] = 118812495276
    
71. f(70) = 55315679788, finished!   sum[70] = 174128175064
    
72. f(71) = 81069068969, finished!   sum[71] = 255197244033
    
73. f(72) = 118812495276, finished!   sum[72] = 374009739309
    
74. f(73) = 174128175064, finished!   sum[73] = 548137914373
    
75. f(74) = 255197244033, finished!   sum[74] = 803335158406
    
76. f(75) = 374009739309, finished!   sum[75] = 1177344897715
    
77. f(76) = 548137914373, finished!   sum[76] = 1725482812088
    
78. f(77) = 803335158406, finished!   sum[77] = 2528817970494
    
79. f(78) = 1177344897715, finished!   sum[78] = 3706162868209
    
80. f(79) = 1725482812088, finished!   sum[79] = 5431645680297
    
81. f(80) = 2528817970494, finished!   sum[80] = 7960463650791
    
82. f(81) = 3706162868209, finished!   sum[81] = 11666626519000
    
83. f(82) = 5431645680297, finished!   sum[82] = 17098272199297
    
84. f(83) = 7960463650791, finished!   sum[83] = 25058735850088
    
85. f(84) = 11666626519000, finished!   sum[84] = 36725362369088
    
86. f(85) = 17098272199297, finished!   sum[85] = 53823634568385
    
87. f(86) = 25058735850088, finished!   sum[86] = 78882370418473
    
88. f(87) = 36725362369088, finished!   sum[87] = 115607732787561
    
89. f(88) = 53823634568385, finished!   sum[88] = 169431367355946
    
90. f(89) = 78882370418473, finished!   sum[89] = 248313737774419
    
91. f(90) = 115607732787561, finished!   sum[90] = 363921470561980
    
92. f(91) = 169431367355946, finished!   sum[91] = 533352837917926
    
93. f(92) = 248313737774419, finished!   sum[92] = 781666575692345
    
94. f(93) = 363921470561980, finished!   sum[93] = 1145588046254325
    
95. f(94) = 533352837917926, finished!   sum[94] = 1678940884172251
    
96. f(95) = 781666575692345, finished!   sum[95] = 2460607459864596
    
97. f(96) = 1145588046254325, finished!   sum[96] = 3606195506118921
    
98. f(97) = 1678940884172251, finished!   sum[97] = 5285136390291172
    
99. f(98) = 2460607459864596, finished!   sum[98] = 7745743850155768
    
100. f(99) = 3606195506118921, finished!   sum[99] = 11351939356274688
     
101. f(100) = 5285136390291172, finished!   sum[100] = 16637075746565860
     
102. 16637075746565860
     
103. Press any key to continue
     

复制代码

[ 本帖最后由 dzbjet 于 2006-9-7 17:16 编辑 ]