100层楼2个鸡蛋C程序递归实现

/************************************************************************ * 输入：层数和鸡蛋数目 * 输出：保证鸡蛋不破的最高安全层的最少次数 * 如果有足够的鸡蛋数，其最少次数和损耗的鸡蛋数将都少于 二分法 即： 效率高于二分法!!! * * by gwang 2011-05-12 ------------------------- 推到过程： 一个蛋：1 1 1 1 1... 二个蛋：1 2 3 4 5... 3个蛋： 1 3 6 10 15... 4 : 1 4 10 15 30... 5 : 1 5 15 30 公式： f(1,1)=1, f(1,2)=1, f(1,3)=1,.... f(2,1)=1, f(2,2)=2, f(2,3)=3 f(3,1)=1, f(3,2)=3, f(3,3)=6 ... f(n,1)=1, f(n,2)=f(n-1,1)+f(n-1,2), ... f(n,m)=f(n-1,1)+...+f(n-1,m) f(n,m)=f(n-1,1)+...+f(n-1,m) -------------------------------- S为n个鸡蛋m次可以探测的层数： S=f(n,1)+f(n,2)+...+f(n,m) =================== 再分析： 仅仅是最坏情况下的最小次数，该方法的期望次数未必好于均分。简单计算下： (1) (2*1 + 3*2 + 4*3 + 5*4 + 6*5 + 7*6 + ... + 14*13)/100, 最大次数14，最小次数2, 期望次数=. (2) ()/100，最大次数19，最小次数2，期望次数=. ************************************************************************/ #include <stdio.h> //计算“egg个鸡蛋，第layer段”的层数 int f(int egg, int layer){ int s; int layer1,egg1; if(layer==1 || egg==1){ return 1; } s=0; egg1=egg; for(layer1=1;layer1<=layer;layer1++){ s=s+f(egg-1, layer1); } //printf("%d\n",s); return s; } //“layers层，eggs个鸡蛋”测最高安全层 // 返回所需的最小次数 int layer_eggs(int layers, int eggs){ int ss; int cishu; if(layers==0 || eggs ==0){ return -1; } ss=0; for(cishu=1;;){ ss+=f(eggs, cishu); /*最外层每段的层数*/ printf("%d\n",f(eggs, cishu)); if(ss>layers){ break; } cishu++; } printf("\n%d次 最多可以测到的层数: %d\n\n", cishu, ss); return cishu; } int main(int argc, char **argv){ int layers; int eggs; int test_times; /*参数可以任意改变*/ layers=100; eggs=2; printf("输入楼层数："); scanf("%d", &layers); printf("输入鸡蛋数："); scanf("%d", &eggs); test_times=layer_eggs(layers, eggs); printf("%d层 - %d 个鸡蛋: %d次\n\n", layers, eggs, test_times); system("pause"); return 0; }