{炒冷饭}“母牛数量算法”一年后我的总结。

leeon868

这里面有几个称呼，请注意，我称作使用面向对象的人是，“面向对象玩家”，只是玩笑，不是贬低。
题记：
很简单的题目，1+2+3+...+100，你是写个循环扔给计算机呢？还是学高斯那样想一想呢？
以前在ChinaUnix遇到过一个母牛生小牛的问题。题目很简单：
若一头小母牛，从出生起第四个年头开始每年生一头母牛，按此规律，第n年有多少头母牛？
原地址：http://bbs.chinaunix.net/viewthread.php?tid=130156
如果大家有耐心的话，可以看看这个非常长的帖子。里面有非常多各自实现的代码。
拿到题目了，我们是直接解题？还是思考一下再解题？
或许很多人就直接上手求解了。让我们看一段自认为很NB的c++代码，
呵呵，这个是ChinaUnix活跃用户flw的代码，比较典型：
# include <stdio.h>
class cow
{
public:
        static cow *head;
        static cow *tail;
        static unsigned long cowCount;
        int age;
        cow *next;
        cow()
        {
                age = 0;
                next = ( cow * ) NULL;
        }
        void grow(void)
        {
                age++;                // 年龄长了一岁。
                if ( age >= 4 )
                {                        // 第四个年头起，下崽。
                        cow *child = new cow;
                        tail->next = child;
                        tail = child;
                        cowCount++;
                }
        }
};
unsigned long cow::cowCount = 0;
cow *cow::head = NULL;
cow *cow::tail = NULL;
int main( void )
{
        int years = 30;
        cow *cows = new cow;
        cow::head = cows;
        cow::tail = cows;
        cow::cowCount = 1;
        for( int i=0; i<years; i++ )
                // 一年过去了，每牛（注意：不能叫“每人”）给我长一岁。
                for( cow *ptr = cow::head; ptr != NULL; ptr = ptr->next )  
                        ptr->grow();
        printf( "result: [%ld]\n", cow::cowCount );
        ptr = cow::head;
        while( ptr != NULL )
        {
                cow *temp = ptr;
                ptr = ptr->next;
                delete temp;
        }
        return 1;
}   
嗯，非常NB，不但面向对象，还用上了链表。此君估计是狂热的面向对象玩家外加数据结构爱好者。是个好员工啊。
如果按照大O标记复杂度，相信有些算法基础的都会感觉很恐怖。当然，这个是可以求解的。
当我看到这个，我第一就感叹，flw的高中数学算是白学了。

仔细想一想。4年生一头牛。其实就是Fibonacci斐波那契数列的小扩展，
原始的的数列递进间隔是3。f(n) = f(n-1) + f(n-2)
而这个题目是4，也就是：f(n) = f(n-1) + f(n-3)
因此我们也可以总结一个公式，第step年生产小母牛就是：n(i)=n(i-1)+n(i-step+1)

我们可以用递归去求解。这就是高级语言的特性。
#include <iostream>
typedef unsigned int qty_type;
int i = 0;
qty_type cow( qty_type _year )
{
qty_type c = ( _year < 4 ) ? 1 : cow( _year - 1 ) + cow( _year - 3 );
cout << "No." << ++i
           << "|year:"<< _year
           << "|quantity: "<< c
           << endl;
return c;
}

int main()
{
    cow(10);
    return 0;
}

Oh，这个虽然比较好了，我们其实不用“先进”的面向对象也能做到。
但，这个不行，这个一样会折磨我们的电脑，我们小小编译一下，小小输出一下就知道了。
不要输入太大，10就够了。
No.1|year:3|quantity: 1
No.2|year:1|quantity: 1
No.3|year:4|quantity: 2
No.4|year:2|quantity: 1
No.5|year:5|quantity: 3
No.6|year:3|quantity: 1
No.7|year:6|quantity: 4
No.8|year:3|quantity: 1
No.9|year:1|quantity: 1
No.10|year:4|quantity: 2
No.11|year:7|quantity: 6
No.12|year:3|quantity: 1
No.13|year:1|quantity: 1
No.14|year:4|quantity: 2
No.15|year:2|quantity: 1
No.16|year:5|quantity: 3
No.17|year:8|quantity: 9
No.18|year:3|quantity: 1
No.19|year:1|quantity: 1
No.20|year:4|quantity: 2
No.21|year:2|quantity: 1
No.22|year:5|quantity: 3
No.23|year:3|quantity: 1
No.24|year:6|quantity: 4
No.25|year:9|quantity: 13
No.26|year:3|quantity: 1
No.27|year:1|quantity: 1
No.28|year:4|quantity: 2
No.29|year:2|quantity: 1
No.30|year:5|quantity: 3
No.31|year:3|quantity: 1
No.32|year:6|quantity: 4
No.33|year:3|quantity: 1
No.34|year:1|quantity: 1
No.35|year:4|quantity: 2
No.36|year:7|quantity: 6
No.37|year:10|quantity: 19
OH，卖糕的，37次，只是算了10年而已，虽然我们得出了19就这个正确的数字，但是代价惨重，
并不是臆想的那样，我们算10次就够了，是远远超过的37次。如果是16年将增长到恐怖的377步。50年达到恐怖的166632769次。
我试图计算100年计算多少次，嗯，在写到这里的时候，这个简单的代码还没有计算出。真的急死人了。
竟然比“面向对象玩家”代价要大！
难道比“面向对象玩家”要凄惨就放弃这个简单的算法吗？一下否定了？
算法也是需要分析的。
来，看看输出的结果，我们可以看到这一组数据：
No.1|year:3|quantity: 1
No.2|year:1|quantity: 1
No.3|year:4|quantity: 2
No.4|year:2|quantity: 1
1、类似这样3、1、4、2年的计算重复了很多次，而且随着后面的计算次数增加，会越来越多。问题就出在这些3、1、4、2上。每次都持续累加计算这些最初的年份的值。这个其实在最初早已经计算好了啊。我们需要把这个计算后的值保存下来。
2、第4年才有数据的增加，此前的3年都没有数据。而随着4年4年的增加，中间间隔的2年的数据是需要逐渐保存下来的。要不然，中间这些数据就需要重新再计算一遍。
3、显而易见，我们已经知道前4年的情况了，何必要计算前四年的情况呢？
经过这三点分析，可以写出如下伪码：
function(总值, 计算间隔2年的和, 保留的间隔和1, 保留的间隔和2, 年数)

#include <iostream>
typedef unsigned int qty_type;
int i = 0;
qty_type cow( qty_type all_cow, qty_type a, qty_type b, qty_type c, qty_type year )
{
    cout << "No." << ++i
         << "|year: " << 100 - year
         << "|all_cow: " << all_cow
         << "\n";
    return !year ? all_cow : cow( all_cow + a, a + c, a, b, --year );
}
int main()
{
cow( 1, 1, 0, 0, 97 );
    return 0;
}
显而易见，其实我们是从第4年算起的，所以说，10年，其实我们算了7年而已。100年，但是我们仅仅算了97年而已。
不要太多，我们还是测试10次。
输出看看：
No.1|year: 3|all_cow: 1
No.2|year: 4|all_cow: 2
No.3|year: 5|all_cow: 3
No.4|year: 6|all_cow: 4
No.5|year: 7|all_cow: 6
No.6|year: 8|all_cow: 9
No.7|year: 9|all_cow: 13
No.8|year: 10|all_cow: 19
呵呵，结果是正确的。而且只计算了8次而已。
我们输入97，来看看结果。等等。怎么得到的越来越小了？在第60年的时候出现问题了：
……
No.58|year: 60|all_cow: 3808901426
No.59|year: 61|all_cow: 1287249059
No.60|year: 62|all_cow: 3886168404
No.61|year: 63|all_cow: 3400102534
……
原来是这里：
typedef unsigned int qty_type;
换一下
typedef unsigned long int qty_type;
得到的结果是一样的，原来现在的C++编译器早已经把int提升为和long一样的长度了。
不得已，我们只能
typedef unsigned long long int qty_type;
也就是int64类型来表示了，这样才得出了正确的结果：
year: 100|all_cow: 16637075746565861

在根据需求的时候，数字长度是否够长，这是一个大问题。还好我们的题目只是100年，如果int64得不出来，那就需要拓展考虑了。
如果涉及到大数字计算，问问自己，数够不够大呢？
总结：拿到需求，或者题目的时候，别看到题目如何就如何设计。

我前一段时间写代码，动不动就用class封装，但仔细反思一下，有必要封装嘛？真的有必要弄个类才可以嘛？
写了一个buffer类，很多操控都写进了这个类，其实，写个函数又如何？只不过多添加了个buffer的引用而已，其他没有多大区别。
大伯是建筑工程师，也是数学专家，上初中的时候，他曾经有过一句话：如果你能用算术方法直接解应用题，就别用方程式，虽然方程式解题会很简单。
现在才理解他当初的这句话。我现在的编程理念就是：能用functional就不用OO。

后记：在写完这个的时候，我的那个第一个递归，还没有结束，计算了将近3个小时。那个ChinaUnix的帖子，可能还有人在跟帖，把自己的想法写出来，但是没有看别人的回答。其实在那个帖子里的第一页就已经有人给出了非常好的答案了。没人看他的答案，那个人，2006年后就没有再上ChinaUnix……

朋友Yonsm曾经和我吃饭的时候的时候说过一句话：我们写程序的，就是不断修正自己本身的问题才能获得提高。

参考书目：《Structure and Interpretation of Computer Programs》
--------------
LeeoNix
2009-01-15

虎皮尖椒

这个世界上难道只有一个运行效率么？

帖子里面评论某斑竹的话灰常牛a.

leeon868

我并不是唯效率至上论。但有时候，效率就是一切。

我其实就想说，用脑子去想想，比不想就开始做要好。

看看别人的想法，也会有更好的答案的，但是很少人缺少耐心去看看。

那位叫：“灰色轨迹”的朋友，虽然现在已经不来CU了，但是他当初在当初7楼第一时间给出了最好的代码，但是没人看。

hellioncu

LZ，所谓“牛人”不是每个方面都牛的

leeon868

flw曾经很狂放的说，不符合他的就是错的。

我这里再回复一下，不要狂，狂没用。

如果他耐心看看前面的人的帖子。

DQP

真的很汗
估计flw是在搞怪吧。。。。
这道题是个很基本的问题 很明显就能看出和 Fibonacci很像
而应该把会重复用到的结果cache住 这也是很明显的事。。。 很多地方就用Fibonacci问题来作为用cache中间结果来提速的例子。
作为functional programming的版主不太可能不知道这个。。。

leeon868

具体见原帖，长达25页，估计除了我，不会有人耐心看完了。

win_hate

2003 年的帖子，现在是 2009 年，很多东西都变了。

fineamy

总结的很好。

cc520

菜鸟学习!!