二叉樹常考算法?古印度有個叫錫塔的大臣，他聰明過人，發明了一種棋子，國王百玩不厭，于是決定重賞錫塔錫塔說：“陛下，我隻要一點麥子請您讓人将麥子放在我發明的棋盤的六十四個格子内，第一格放一粒，第二格放二粒，第三格放四粒，第四格放八粒，第五格放十六粒……照這樣放下去，每格比前一格多放一倍麥粒，直到把六十四個棋格放滿就行了”國王聽了哈哈大笑，他覺得谷倉裡的麥子多着呢，填完六十四個棋格實在是小意思哪知，管糧食的大臣計算了一下，急得滿頭大汗，因為需要的麥子太多了，我來為大家科普一下關于二叉樹常考算法?以下内容希望對你有幫助!

二叉樹常考算法

古印度有個叫錫塔的大臣，他聰明過人，發明了一種棋子，國王百玩不厭，于是決定重賞錫塔。錫塔說：“陛下，我隻要一點麥子。請您讓人将麥子放在我發明的棋盤的六十四個格子内，第一格放一粒，第二格放二粒，第三格放四粒，第四格放八粒，第五格放十六粒……照這樣放下去，每格比前一格多放一倍麥粒，直到把六十四個棋格放滿就行了。”國王聽了哈哈大笑，他覺得谷倉裡的麥子多着呢，填完六十四個棋格實在是小意思。哪知，管糧食的大臣計算了一下，急得滿頭大汗，因為需要的麥子太多了。

事實上依格子順序放的麥粒數是一個等比數列：

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億年呢！聰明的錫塔無法數完麥子隻能放棄了賞賜。

先從世界人口說起。據統計，現在世界人口約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内存了。

如漢諾塔問題：

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

一個百萬富翁遇到一個陌生人，陌生人找他談一個換錢的計劃，該計劃如下：

第一天給我你十萬元，而你第一天隻需給我一分錢，

第二天我仍給你十萬元，你給我兩分錢，

第三天我仍給你十萬元，你給我四分錢，....，

你每天給我的錢是前一天的兩倍，直到滿一個月（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－