二叉树常考算法（趣味数学与编程）

古印度有个叫锡塔的大臣，他聪明过人，发明了一种棋子，国王百玩不厌，于是决定重赏锡塔锡塔说：“陛下，我只要一点麦子请您让人将麦子放在我发明的棋盘的六十四个格子内，第一格放一粒，第二格放二粒，第三格放四粒，第四格放八粒，第五格放十六粒……照这样放下去，每格比前一格多放一倍麦粒，直到把六十四个棋格放满就行了”国王听了哈哈大笑，他觉得谷仓里的麦子多着呢，填完六十四个棋格实在是小意思哪知，管粮食的大臣计算了一下，急得满头大汗，因为需要的麦子太多了，我来为大家科普一下关于二叉树常考算法?以下内容希望对你有帮助!

二叉树常考算法

1 印度国王赐麦

古印度有个叫锡塔的大臣，他聪明过人，发明了一种棋子，国王百玩不厌，于是决定重赏锡塔。锡塔说：“陛下，我只要一点麦子。请您让人将麦子放在我发明的棋盘的六十四个格子内，第一格放一粒，第二格放二粒，第三格放四粒，第四格放八粒，第五格放十六粒……照这样放下去，每格比前一格多放一倍麦粒，直到把六十四个棋格放满就行了。”国王听了哈哈大笑，他觉得谷仓里的麦子多着呢，填完六十四个棋格实在是小意思。哪知，管粮食的大臣计算了一下，急得满头大汗，因为需要的麦子太多了。

事实上依格子顺序放的麦粒数是一个等比数列：

1 2 4 8 16 32 …… 2^63。

下面来推导等比数列前n项和S的公式。设第一项为a，公比为q，则等比数列可表示为：

如果按1立方米的麦子有1500万粒计算，国王应赏赐的麦子就约有12000亿立方米，就算把全世界2000年所产生的麦子全加在一起，也没有这个数目大呀！国王这才明白过来，这可怎么办呀？一个聪明的大臣对国王说：“陛下，就请锡塔自己去数麦子吧。”因为一秒钟能数两粒，一分钟能数120粒，一小时也只能数出7200粒，每天数上10小时，也只能拿到72000粒麦子。照这样的速度数上一年，也只有2000万粒——3000万粒，也就是1—2立方米的麦子。而要想把国王如数上次给他的麦子全部数清，就得要2000亿年呢！聪明的锡塔无法数完麦子只能放弃了赏赐。

2 电脑的位数与支持的内存

先从世界人口说起。据统计，现在世界人口约75亿，如果说给每人一个不重复的编号（只使用0和1两个符号），需要多少位数？

2^x = 7500000000

也就是求以2为底7500000000的log。

2^32 = 4294967296

2^33 = 8589934592

33个二进制位就够了。

32位电脑有32条地址线，支持的内存是2的32次方，也就是4GB内存（1GB ＝ 1024^3）。4GB也就是40多亿个Byte。

而64位电脑理论上的寻址空间为2的64次方，达18446744073709551616，也就是17179869184G。

64位的CPU需要64位的操作系统支持。当然64位的系统也支持32位的CPU。

如果主板有四条内存插槽为，单条内存最大的是16GB，四个内存插槽刚好可以插16x4=64GB内存。

如大部分X99/X399主板都支持8内存插槽，用单条16G的，就是128GB内存了。

3 两次递归调用，就是二叉树的遍历问题

如汉诺塔问题：

void han(int n,char a,char b,char c) { if(n==1) printf("%d %c→%c *\n",n,a,c); else { han(n-1,a,c,b); printf("%d %c→%c\n",n,a,c); han(n-1,b,a,c); } }

可图示如下：

两叉树的扩充就是一个翻倍的问题，1，2，4，8，……，2^n

移动的最少次数应等于2^n - 1

4 贪财的富翁

一个百万富翁遇到一个陌生人，陌生人找他谈一个换钱的计划，该计划如下：

第一天给我你十万元，而你第一天只需给我一分钱，

第二天我仍给你十万元，你给我两分钱，

第三天我仍给你十万元，你给我四分钱，....，

你每天给我的钱是前一天的两倍，直到满一个月（30天）。

百万富翁很高兴，欣然接受了这个契约。请编程序，通过计算说明，这个换钱计划对百万富翁是否是个划算的交易。

#include <stdio.h> int main( ) { double m2f=1.0e5,f2m=0.01,m2fs=0,f2ms=0; int day=1;//一定要赋初值 for(day=1; day<=30; day ) { m2fs =m2f; f2ms =f2m; f2m*=2; //下面的输出不是必需，但可以使我们更加清楚地知道解题的过程，这可以是一个技巧 printf("第%d天,陌生人给富翁累计%.2f,富翁给陌生人累计%.2f,差额:%.2f\n", day, m2fs, f2ms, m2fs-f2ms); } printf("最终，陌生人给富翁：%.2f，富翁给陌生人：%.2f。 ", m2fs, f2ms); if(m2fs>f2ms) printf("陌生人自找"); else { if (m2fs<f2ms) printf("富翁傻帽了"); else printf("两人持平，没意思的交易"); } printf("\n"); while(1); return 0; }

输出：

第1天,陌生人给富翁累计100000.00,富翁给陌生人累计0.01,差额:99999.99

第2天,陌生人给富翁累计200000.00,富翁给陌生人累计0.03,差额:199999.97

第3天,陌生人给富翁累计300000.00,富翁给陌生人累计0.07,差额:299999.93

第4天,陌生人给富翁累计400000.00,富翁给陌生人累计0.15,差额:399999.85

第5天,陌生人给富翁累计500000.00,富翁给陌生人累计0.31,差额:499999.69

第6天,陌生人给富翁累计600000.00,富翁给陌生人累计0.63,差额:599999.37

第7天,陌生人给富翁累计700000.00,富翁给陌生人累计1.27,差额:699998.73

第8天,陌生人给富翁累计800000.00,富翁给陌生人累计2.55,差额:799997.45

第9天,陌生人给富翁累计900000.00,富翁给陌生人累计5.11,差额:899994.89

第10天,陌生人给富翁累计1000000.00,富翁给陌生人累计10.23,差额:999989.77

第11天,陌生人给富翁累计1100000.00,富翁给陌生人累计20.47,差额:1099979.53

第12天,陌生人给富翁累计1200000.00,富翁给陌生人累计40.95,差额:1199959.05

第13天,陌生人给富翁累计1300000.00,富翁给陌生人累计81.91,差额:1299918.09

第14天,陌生人给富翁累计1400000.00,富翁给陌生人累计163.83,差额:1399836.17

第15天,陌生人给富翁累计1500000.00,富翁给陌生人累计327.67,差额:1499672.33

第16天,陌生人给富翁累计1600000.00,富翁给陌生人累计655.35,差额:1599344.65

第17天,陌生人给富翁累计1700000.00,富翁给陌生人累计1310.71,差额:1698689.29

第18天,陌生人给富翁累计1800000.00,富翁给陌生人累计2621.43,差额:1797378.57

第19天,陌生人给富翁累计1900000.00,富翁给陌生人累计5242.87,差额:1894757.13

第20天,陌生人给富翁累计2000000.00,富翁给陌生人累计10485.75,差额:1989514.25

第21天,陌生人给富翁累计2100000.00,富翁给陌生人累计20971.51,差额:2079028.49

第22天,陌生人给富翁累计2200000.00,富翁给陌生人累计41943.03,差额:2158056.97

第23天,陌生人给富翁累计2300000.00,富翁给陌生人累计83886.07,差额:2216113.93

第24天,陌生人给富翁累计2400000.00,富翁给陌生人累计167772.15,差额:2232227.85

第25天,陌生人给富翁累计2500000.00,富翁给陌生人累计335544.31,差额:2164455.69

第26天,陌生人给富翁累计2600000.00,富翁给陌生人累计671088.63,差额:1928911.37

第27天,陌生人给富翁累计2700000.00,富翁给陌生人累计1342177.27,差额:1357822.73

第28天,陌生人给富翁累计2800000.00,富翁给陌生人累计2684354.55,差额:115645.45

第29天,陌生人给富翁累计2900000.00,富翁给陌生人累计5368709.11,差额:-2468709.11

第30天,陌生人给富翁累计3000000.00,富翁给陌生人累计10737418.23,差额:-7737418.23

最终，陌生人给富翁：3000000.00，富翁给陌生人：10737418.23。 富翁傻帽了

2^30 = 1073741824，也就是上面说的1G，10亿 。

－End－