双蛋问题

双蛋问题

前几天看了李永乐老师的视频、忽然想写一下博客：

1，问题描述：

有i层楼，2个鸡蛋，鸡蛋是相同的，临界楼层是指从某个楼层之上抛下来，都会碎，但从这个楼层之下抛下来，都不会碎。没有碎的鸡蛋可以重复使用。试假设能找到这个临界楼层需要抛投的最少次数。

2、问题分析

2.1假设1：

假设楼层i为100
第一个鸡蛋直接从楼层的一半扔下去：
假设第一个鸡蛋没碎：
第二个鸡蛋最坏的情况为1+(i/2-1-1)
假设第一个鸡蛋碎了
第二个鸡蛋最坏的情况还是1+(i/2-1-1)
最坏的情况下是49次

2.2假设2：使用开平方法

假设100层楼
第一个鸡蛋从10层楼扔下去
最坏的情况为 (i/10-1)+10-1 = 19次

2.3假设3：使用高斯公式（2个鸡蛋使用这个次数最少）

文字表述：和=(首项 + 末项）x项数/2
数学表达：1+2+3+4+……+ n = (n+1)n /2

//使用循环求出次数
private static int layer;   //楼层数量private static int egg;    //鸡蛋数量private static int minNum; //最优解法：在layer层楼、egg个鸡蛋的时候，一定能找到临界楼层的最初抛投次数private static int maxInterval; //间隔的值之和：1、2、3、4的和小于楼层数量public static void main(String[] args) {layer = 200;  //楼层数量赋值egg = 2;    //鸡蛋数量赋值
//        getMin();}private static int getMin(){int num = 1;    //声明初始化间距为1minNum = recursionMin(num,layer);System.out.println(minNum);return minNum;}private static int  recursionMin(int num,int layer){if (maxInterval < layer && maxInterval + 1 != layer) {//num每次从一开始加    maxInterval为最大值：如果楼层为100最大值为1、2、3、4。。。14的和num = num + 1;maxInterval += num;return recursionMin(num,layer);} else {return num;}}

//解高斯方程求出次数
public static void main(String[] args) {layer = 100;  //楼层数量赋值egg = 2;    //鸡蛋数量赋值getEquation(layer);}public static int getEquation(int layer){double n;//补了一下小学数学--！套入公式(n+1)*n/2 = layer然后解方程/** (x-a)(x-a) = 0* x*x -ax -ax + a*a = 0* x*x - 2ax + a*a = 0* 解方程步骤：*   (n+1)*n = layer * 2*   n*n + n = layer *2*   n*n + 2*1/2*n + 1/2 * 1/2 = layer *2 + 1/2*1/2*   (n+1/2)*(n+1/2) = layer *2 + 1/4*   (n+1/2)*(n+1/2) = (layer * 2 * 4 + 1)/4*   n + 1/2 = Math.sqrt((layer * 2 * 4 + 1)/4)*   n = Math.sqrt((layer * 2 * 4 + 1)/4))  - 1/2* */int gen = layer*2+1/4;//1/2只会按整型运算,结果也是整形的所以==0 必须使用1.0/2.0n = il(Math.sqrt(gen) - 1.0/2.0);return 1;}

2.4多蛋情况下使用递归找出所有运算结果中次数最少的(运算的很慢很慢)

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;public class DuoDan {private static int layer;   //楼层数量private static int egg;    //鸡蛋数量private static int minNum; //最优解法：在layer层楼、egg个鸡蛋的时候，一定能找到临界楼层的最初抛投次数public static void main(String[] args) {layer = 30;  //楼层数量赋值egg = 3;    //鸡蛋数量赋值getMin();}private static int getMin() {recursionEgg(layer,egg);System.out.println(minNum);return minNum;}private static int recursionEgg(int layer,int egg){if(layer <= 0){//楼层数量小于0返回0return 0;}if(layer <= 1){//楼层数量小于1返回1return layer;}if(egg <= 1){//鸡蛋个数小于1返回剩余楼层数量return layer;}List<Integer> num = new ArrayList<Integer>();
//        int i = 5;//第一次求第一次重第几层往下扔for (int i = 1;i<layer;i++){//求出从1-n层楼往下扔鸡蛋的每次需要的最多次数num.add(recursionMax(layer,egg,i));}minNum = Collections.min(num);//取出一个最小值return minNum;}private static int  recursionMax(int layer,int egg,int k) {//k是当前从第几层楼开始扔if(k <= 0){//如果在第一层的话鸡蛋碎了会变成0  默认赋值1k = 1;}if(layer <= 0){//楼层数量小于0返回0return 0;}if(layer <= 1){//楼层数量小于1返回1return layer;}if(egg <= 1){//鸡蛋个数小于1返回剩余楼层数量return layer;}if (egg > 2) {//判断如果鸡蛋数量大于2的情况下循环递归调用//        没碎                                                    碎了return Math.max(recursionEgg(layer-k,egg),recursionEgg(k-1,egg-1))+1;}
//        //没碎                                                    碎了
//        //每扔一次数就加1、的出最坏情况下需要扔几次return Math.max(recursionMax(layer - k,egg,k-1),recursionMax(k-1,egg-1,k-1))+1;}}