Magic Index举例分析

这篇文章主要讲解了“Magic Index举例分析”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“Magic Index举例分析”吧！

面试题：

给定一个数组A，其中有一个位置被称为Magic Index，含义是：如果i是Magic Index，则A[i] = i。假设A中的元素递增有序、且不重复，请给出方法，找到这个Magic Index。更进一步，当A中允许有重复的元素，该怎么办呢？

鸡蛋挺住体分析：

原题描述

两个软硬程度一样但未知的鸡蛋，它们有可能都在一楼就摔碎，也可能从一百层楼摔下来没事。有座100层的建筑，要你用这两个鸡蛋通过最少的次数确定哪一层是鸡蛋可以安全落下的***位置。可以摔碎两个鸡蛋

方法分析

看到这个题目，最保险的方法就是一层一层试验，但这样只需要一个鸡蛋就可以了。我们现在有两个鸡蛋，完全可以用有更快的方法。

进一步呢？可能试验的方法是二分查找，例如，***个鸡蛋再50层扔下，如果碎了，第二个鸡蛋从1-49逐层试验；如果没碎，***个鸡蛋在75层扔 下，如果碎了，第二个鸡蛋从51-74逐层试验…但是，这个方法，很容易悲剧，例如，当正好49层是可以安全落下的，需要尝试50次。比只有一个鸡蛋的情 况，效果还要差。

上面的分析都是从鸡蛋的角度出发的，想要得到最少的尝试次数，似乎比较难。那如果我们换个角度，从每个高度的楼层来看呢？如果，某个楼层是可以安全落下的，那么最少需要多少次尝试呢？看下面的分析

在我们编程解决问题的过程中，如果遇到***问题的时候，往往可以先尝试一下动态规划的方法。而动态规划的方法，首要的我们要找到构成这个***问题的 ***子问题。所以，下面的分析，我们首先尝试动态规划的方法，如何解决这个问题，这也是典型的程序员的思路；其次，在众多的问题当中，有不少可以直接归结 为数学方程式，如果我们能够写出数学方程式，那么，答案将是更加的简洁、美妙。所以，第二个方法，将尝试如果总结出数学方程式。

基于动态规划的方法

前面提到，若要采用动态规划的方法，最重要的是要找到子问题。做如下的分析，假设f{n}表示从第n层楼扔下鸡蛋，没有摔碎的最少尝试次数。***个鸡蛋，可能的落下位置(1,n),***个鸡蛋从第i层扔下，有两个情况：

1. 碎了，第二个鸡蛋，需要从***层开始试验，有i-1次机会

2. 没碎，两个鸡蛋，还有n-i层。这个就是子问题了f{n-i} 所以，当***个鸡蛋，由第i个位置落下的时候，要尝试的次数为1 +  max(i - 1, f{n - i})，那么对于每一个i，尝试次数最少的，就是f{n}的值。状态转移方程如下： f{n} = min(1 +  max(i - 1, f{n - 1}) ) 其中: i的范围为(1, n), f{1} = 1 完毕。

推广

动态规划的方法，可以推广为n层楼，m个鸡蛋。如下分析：  假设f{n,m}表示n层楼、m个鸡蛋时找到***楼层的最少尝试次数。当***个鸡蛋从第i层扔下，如果碎了，还剩m-1个鸡蛋，为确定下面楼层中的安全楼 层，还需要f{i-1,m-1}次，找到子问题；不碎的话，上面还有n-i层，还需要f[n-i,m]次，又一个子问题。 状态转移方程如下： f{n,  m} = min(1 + max(f{n - 1, m - 1}, f{n - i, m}) ) 其中： i为(1, n), f{i, 1} =  1

基于数学方程的方法

假设最少尝试次数为x，那么，***个鸡蛋必须要从第x层扔下，因为：如果碎了，前面还有x -  1层楼可以尝试，如果没碎，后面还有x-1次机会。如果没碎，***个鸡蛋，第二次就可以从x +（x - 1）层进行尝试，为什么是加上x -  1，因为，当此时，***个鸡蛋碎了，第二个鸡蛋还有可以从x+1 到 x + (x - 1) - 1层进行尝试，有x -  2次。如果还没碎，那***个鸡蛋，第三次从 x + (x - 1) + (x - 2)层尝试。碎或者没碎，都有x -  3次尝试机会，依次类推。那么，x次的最少尝试，可以确定的***的楼层是多少呢？ x + (x - 1) + (x - 2) + … + 1 =  x(x+1) / 2 那反过来问，当***楼层是100层，最少需要多少次呢？x(x+1)/2 >= 100,  得到x>=14，最少要尝试14次。

感谢各位的阅读，以上就是“Magic Index举例分析”的内容了，经过本文的学习后，相信大家对Magic Index举例分析这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是亿速云，小编将为大家推送更多相关知识点的文章，欢迎关注！