复工 复产 找 工作 ？先 来 看看 这道 面试题 ：双蛋 问题 |||||||||problème des deux œufs| resuming work|resuming production||||||this question|interview question (1)|Double Eggs| Wenn Sie wieder arbeiten und einen Job suchen, sollten Sie sich zuerst diese Frage im Vorstellungsgespräch ansehen: die Frage nach dem doppelten Ei Returning to work and looking for a job? First, let's take a look at this interview question: double egg question ¿De vuelta al trabajo y buscando empleo? Echa un vistazo primero a esta pregunta de entrevista: La pregunta del doble huevo Reprendre le travail et la production, à la recherche d'un emploi ? Regardez d'abord cette question d'entretien : le problème des œufs durs. 仕事に復帰して仕事を探していますか？まずこの面接の質問をチェックしてください：ダブルエッグの質問 De volta ao trabalho e à procura de emprego? Veja primeiro esta pergunta de entrevista: A pergunta do ovo duplo 复工复产找工作？先来看看这道面试题：双蛋问题

各位 同学 大家 好 我 是 李永乐 老师 ||||||Li Yongle| ||||||Li Yongle| Hello everyone, I'm Mr. Li! Bonjour à tous les élèves, je suis le professeur Li Yongle. 有 一个 小朋友 跟 我 说 ||a child||| A friend told me Un petit ami m'a dit 他 年底 的 时候 刚刚 把 工作 辞 了 |the end of the year||||||resigned| that he left his job at the end of last year Il vient juste de quitter son emploi à la fin de l'année. 准备 过 完年 找 工作 prepare||New Year|| and was planning to find a new job after the Chinese New Year Il se prépare à trouver un emploi après les fêtes. 结果 就 来 了 疫情 result|||| but the coronavirus stroke China at the beginning of 2020. Puis la pandémie est survenue. 那 现在 复工 复产 的 节奏 越来越近 了 Now, as the economy is recovering back to the normal state, Maintenant, le rythme de la reprise du travail et de la production est de plus en plus proche. 他 就 开始 着手 准备 找 工作 的 事 了 he is starting to prepare for job interviews. Il a donc commencé à se préparer à chercher un emploi. 他 最近 发现 了 一个 面试题 He recently found an interview question. Il a récemment découvert une question d'entretien. 据说 是 微软 还是 Google 的 一个 面试题 Allegedly, it's an interview question from Microsoft or Google. On dit que c'est une question d'entretien de Microsoft ou de Google 挺 有意思 的 想 让 我 讲 一 讲 It is very interesting, and he wanted me to explain it. C'est assez intéressant, je veux que je parle un peu 那 今天 咱们 就 一 起来 讨论一下 这个 面试题 ||||||discuter|| so today, let's talk about this interview question. Alors aujourd'hui, discutons ensemble de cette question d'entretien 我们 称之为 双蛋 问题 鸡蛋 的 蛋 It is called the Two Eggs Problem. Nous l'appelons le problème des œufs doubles. 双蛋 问题 实际上 是 一个 计算机 的 问题 Actually, this is a computer science problem. Le problème des œufs doubles est en fait un problème informatique. 这个 问题 是 这样 描述 的 Here is the question. Ce problème est décrit comme suit. 说 有 一个 大楼 There is a Skyscraper that has a total of 100 floors. Il y a un grand bâtiment 这个 大楼 非常 高 Ce bâtiment est très haut 这 大楼 一共 有 100 层 那么 高 Ce bâtiment a en tout 100 étages aussi hauts 这 100 层楼 These 100 floors, Ces 100 étages 1 2 3 4 ... 一直 到 100 层 1, 2, 3, 4 ... to floor 100. 1 2 3 4 ... jusqu'à 100 étages 然后 有 一个 鸡蛋 这个 鸡蛋 特别 神勇 |||||||courageux There is an egg being very strong. Puis il y a un œuf, cet œuf est particulièrement courageux 它 在 低 楼层 往下 扔 的 时候 |||étage|||| It won't break when falling from low floors. 到 地上 都 不会 碎 Sur le sol, ça ne se brisera pas 在 高 楼层 往下 扔 的 时候 到 地面 上 才 会 碎 It will only break when falling from high floors. Ce n'est qu'en le jetant d'un étage élevé que cela se brisera au sol 而 中间 有 一个 临界 的 楼层 ||||critique|| There is a boundary floor between the top and the bottom floors. Et il y a un étage critique au milieu 这个 临界 的 楼层 以下 Below this boundary floor, Ce niveau critique en dessous 不管 你 在 临近 楼层 以下 扔 多少次 no matter how many times you drop the egg, Peu importe combien de fois tu jettes en dessous du niveau critique 鸡蛋 都 是 不碎 的 the egg will not break. Les œufs ne se cassent jamais 然后 如果 你 超过 了 这个 临界 楼层 往下 扔 If you drop above the boundary floor Ensuite, si tu dépasses ce seuil, jette-le vers le bas. 这回 鸡蛋 才 碎 the egg will break immediately, Cette fois, l'œuf se brisera. 碎 了 之后 就 不能 再 反复 用 了 and it cannot be reused after broken. Une fois brisé, il ne peut plus être réutilisé. 现在 我 就 问 你 Now the question is 这个 人 如果 要是 一共 有 N 个 蛋 ||||||N|| Cette personne a au total N œufs 可以 用来 做 检测 qui peuvent être utilisés pour faire des tests 注意 如果 这个 蛋 没有 碎 就 还 可以 接着 扔 Notice that if an egg can be reused if not broken. Notez que si cet œuf n'est pas cassé, il peut encore être jeté 如果 这个 蛋碎 了 就 不能 再用 了 ||œuf||||| If it is broken, then you would have to use a new egg. Si cet œuf se casse, il ne peut plus être utilisé. 如果 有 N 个 蛋 的话 If there are N eggs, S'il y a N œufs, 那么 他 最少 要 扔 多少次 then what is the minimum number of drops, M, that is required to find the boundary floor? alors combien de fois doit-il au minimum les jeter ? 这个 次数 叫 M Ce nombre est appelé M 才能 找出 这个 临界 的 楼层 Il faut trouver cet étage critique 找出 这个 临界 的 楼层 Trouver cet étage critique 就是 这一 楼层 以上 就 都 会 碎 Above this floor, all eggs break C'est au-dessus de cet étage que tout se brise 这个 楼层 以下 就 都 不碎 Below this floor, no egg breaks En dessous de cet étage, rien ne se brise 这个 就是 扔 鸡蛋 的 问题 This is a question about dropping eggs, C'est précisément la question de jeter des œufs 那么 这个 扔 鸡蛋 的 问题 so the number of eggs that you have will affect the answer. Alors, ce problème de lancer des œufs 你 有 多少 个 鸡蛋 Combien d'œufs as-tu ? 会 影响 到 这个 问题 的 答案 对 吧 Cela affectera la réponse à ce problème, n'est-ce pas ? 首先 我们 先 来 分析 最 简单 的 情况 Firstly, let's look at the simplest case Tout d'abord, analysons la situation la plus simple. 如果 这个 人 他 只有 一个 蛋 如果 只有 一个 蛋 If the person has only one egg, Si cette personne n'a qu'un seul œuf, si elle n'a qu'un seul œuf 也 就是 N 等于 1 N=1, Alors N est égal à 1 那 我 就 问 I would ask: Alors je demande 你 最少 得 扔 多少次 才能 确定 出 临界 楼层 What is the minimum number of drops required to find the boundary floor? Combien de fois devez-vous jeter pour déterminer le niveau critique ? 大家 注意 这个 确定 出 临界 楼层 的 意思 是 Notice that this is the minimum number of tests required even in the worst-case scenario. Tout le monde, faites attention, cela signifie déterminer le niveau critique. 你 即使 是 最坏 的 情况 下 Même dans le pire des cas. 也 能够 通过 扔 这么 多次 鸡蛋 Je peux aussi déterminer ce niveau en lançant autant d'œufs. 就 确定 出 这个 楼层 对 吧 to find the boundary. Par exemple, si vous n'avez qu'un seul œuf. 比如说 你 只有 一个 鸡蛋 的话 For example, if you have only one egg, C'est vrai, n'est-ce pas ? 你 不 可能 上来 就 从 50 层 开始 扔 you cannot start it from the fifth floor. Vous ne pouvez pas commencer à lancer depuis le 50ème étage. 那 一旦 要是 碎 了 If it breaks, Si cela se brise une fois. 你 只能 知道 这个 临界 楼层 在 1 到 50 之间 then you only know the boundary floor is a floor between 1 and 50. Vous ne pouvez savoir que ce niveau critique se situe entre 1 et 50. 但是 你 却 不 知道 是 哪 一个 对 吧 Mais tu ne sais pas lequel c'est, n'est-ce pas ? 所以 如果 你 只有 一个 鸡蛋 的话 So, if you have only one egg, Donc, si vous n'avez qu'un seul œuf, 没有 别的 办法 你 只能 是 先 在 第一层 扔 and there is no other way, you could only drop it from the first floor Il n'y a pas d'autre moyen, vous devez d'abord le jeter du premier étage. 如果 碎 了 那 就是 一层 If it breaks, then the boundary is the first floor. S'il se casse, cela signifie que c'est un étage. 如果 不碎 就 从 第二层 扔 If it doesn't, then drop it again from the second floor. S'il ne se casse pas, alors on le jette de la deuxième couche. 第二层 碎 了 就是 二层 ||||deuxième étage If it breaks, then it is on the second floor. Si la deuxième couche se casse, alors c'est la deuxième couche. 不碎 他 就 再 从 第三层 扔 |||||troisième étage| if not, try the third floor. S'il ne se casse pas, alors on le jette de la troisième couche. 一个 一个 地往 上试 ||à|essayer Going up, floor-by-floor. Essayer un par un. 这样一来 你 没有 别的 好 方法 了 对 吧 Since you have no better way, you have to try each floor. Ainsi, tu n'as pas d'autre bonne méthode, n'est-ce pas ? 所以 一层 一层 去试 |||essayer Donc, essaie couche par couche. 最差 的 情况 是 到 100 层碎 了 |||||étages| The worst case is that it breaks when it reaches floor 100. Le pire des cas est que ça se casse à la 100e couche 或者 到 100 层 也 不碎 Or it doesn't break even from floor 100. Ou que ça n'éclate pas même à la 100e couche 因此 你 最差 的 情况 下要 扔 100 次 |||||devra|| Therefore, the worst case is 100 tests. Donc, dans le pire des cas, vous devez le jeter 100 fois 那 这个 就是 扔 的 次数 比较 多 了 This scenario has a very large number of tests because it has only one egg. Alors, cela signifie qu'il y a eu beaucoup de lancers. 因为 它 鸡蛋 太少 了 Parce qu'il a trop peu d'œufs. 他 只有 一个 蛋 Il n'a qu'un seul œuf. 好 了 那么 假如 说 这个 人 的 蛋 比较 多 Well, let's say that he has more eggs. D'accord, alors supposons que cette personne a beaucoup d'œufs. 他 有 无限 多个 蛋 他 有 无限 个 蛋 An unlimited number of eggs. Il a un nombre infini d'œufs. 那 这回 需要 扔 多少次 呢 This time, how many drops are required? Alors, combien de fois faut-il lancer cette fois ? 这时候 我们 就要 采用 Now we need to use an algorithm. À ce moment-là, nous devons adopter 计算机 里边 一种 常用 的 方法 了 une méthode couramment utilisée dans l'ordinateur 那 就是 二分法 是 吧 ||méthode de dichotomie|| Binary search, right? c'est-à-dire la méthode de la dichotomie, n'est-ce pas ? 二分法 也 是 牛顿 最早 提出 来 的 |||Newton|||| The binary search was first discovered by Newton. La méthode de dichotomie a également été proposée par Newton à l'origine. 但 当时 是 用来 去 找 一个 方程 的 根 的 |||||||équation||| At that time, however, it was used to find the roots of an equation. Mais à l'époque, elle était utilisée pour trouver une racine d'une équation. 这个 研究 起来 也 很 容易 It is easy to analyze. Cette recherche est également très facile. 就是说 我们 把 1 到 100 是 吧 We have 1 to 100. C'est-à-dire que nous prenons de 1 à 100, n'est-ce pas ? 1 到 100 层 我们 画 在 一个 数轴 上 ||||||axe des nombres| We draw them on a number line, Nous représentons les niveaux de 1 à 100 sur une droite numérique. 然后 我们 第一个 鸡蛋 and then, our first egg Puis, nous prenons le premier œuf. 我 在 50 层 的 地方 扔 will be dropped on floor 50. Je jette à un endroit au 50ème étage 如果 这个 鸡蛋 要是 碎 了 If this egg breaks, Si cet œuf se casse 那 就 说明 Alors cela signifie 临界 楼层 一定 是 在 1 到 50 之间 对 吧 then the boundary floor must be between 1 and 50, right? Le niveau critique doit être entre 1 et 50, n'est-ce pas? 如果 50 层 这个 鸡蛋 它 不碎 If it doesn't break on floor 50, Si l'œuf ne se brise pas à 50 étages, 那 就 说明 that the boundary must be between 50 and 100. cela signifie que 临界 楼层 应该 是 在 50 到 100 层 之间 Le niveau critique devrait se situer entre 50 et 100 étages. 这 就是 第一个 鸡蛋 的 扔 法 This is the way to drop the first egg. C'est donc la méthode de lancer le premier œuf. 那么 如果说 你 确定 了 它 在 1 到 50 之间 碎 了 Afterwards, if you find that it is between 1 and 50, Alors, si vous êtes certain qu'il s'est cassé entre 1 et 50. 那 于是 我们 可以 第二个 鸡蛋 在 25 层 的 地方 扔 we can drop the second egg on floor 25. Alors nous pouvons jeter le deuxième œuf à l'étage 25 如果 碎 了 说明 临界 楼层 在 这 If it breaks, then the boundary floor is here. S'il se casse, cela signifie que l'étage critique est ici 如果 不碎 说明 临界 楼层 在 这 If it doesn't then it is not here. S'il ne se casse pas, cela signifie que l'étage critique est ici 这样一来 我 每 扔 一个 鸡蛋 Every time I test, De cette façon, à chaque fois que je jette un œuf 都 可以 把 这个 间隔 除以 2 对 不 对 I can divide the possible range into two, right? je peux diviser cet intervalle par 2, n'est-ce pas ? 所以 叫 二分法 This method is called a binary search. C'est pourquoi cela s'appelle la méthode de la dichotomie. 那 我们 知道 你 除了 几次 2 之后 Afterwards, we know how many times you divided by 2. Alors nous savons que tu as fait quelques fois 2 après. 最后 如果 间隔 小于 1 了 |||inférieur à| If at the end, the range is smaller than 1 Enfin, si l'intervalle est inférieur à 1. 就 不用 再 去 试 了 对 不 对 you don't need to test it out by drop another egg. Alors il n'est plus nécessaire d'essayer, n'est-ce pas ? 因此 如果 我们 想 把 它 确定 出来 是 哪 一个 的话 Therefore, if we want to find out the right floor, Donc, si nous voulons déterminer de quel il s'agit 我们 就 需要 扔 的 次数 2ᴹ ||||||2 then the number of drops needs to be 2^M Nous avons besoin de lancer 2ᴹ fois 它 得 大于 等于 100 It must be larger than or equal to 100 (>=100) Il doit être supérieur ou égal à 100 最后 M 就 大于 等于 log₂¹⁰⁰ |||||log(1) so M is larger than or equal to log base 2 of 8 Enfin, M est supérieur ou égal à log₂¹⁰⁰ 我们 试一试 也 能 试出来 ||||réussir We could solve this by guessing Essayons, nous pouvons aussi le tester 这个 数 应该 是 6.64 This number should be 6.64 Ce nombre devrait être 6,64 6.64 我们 就 取 7 好 了 Round up 6.64, and we get 7 6.64 Nous allons donc prendre 7 所以 这个 时候 你 需要 扔 7 次 Therefore, in this case, you need to drop 7 times. Donc à ce moment-là, tu dois lancer 7 fois 在 最坏 的 情况 下 你 也 需要 扔 7 次 In the worst case, you need to drop it for 7 times. Dans le pire des cas, tu dois aussi lancer 7 fois 好 这是 这个 人有 无限 个 蛋 的 时候 是 这个 样子 的 Ok, so this is the case with an unlimited number of eggs. Bien, c'est comme ça quand cette personne a un nombre infini d'œufs. 那么 这个 面试题 一般 是 这么 问 的 Usually, this interview question asks Alors, cette question d'entretien est généralement posée comme ça. 如果 这个 人有 两个 蛋 的话 Si cette personne a deux œufs. 那么 他 要 扔 多少次 Alors, combien de fois doit-il lancer? 才能 保证 一定 把 这个 临界 楼层 找 出来 pour s'assurer de trouver ce niveau critique. 所以 就 叫 双蛋 问题 Hence, it is called the Two Eggs Problem. C'est donc ce qu'on appelle le problème des deux œufs. 所以 他 如果 有 两个 蛋 so if he has 2 eggs Donc, s'il a deux œufs 那么 这个 时候 怎么样 呢 what should he do this time? Alors, que se passe-t-il maintenant ? 叫 N 等于 2 Let N = 2. Appelons N égal à 2 我们 来看 一下 这个 情况 Let's look at this case Regardons cette situation 我们 先想 这样 一个 方法 |d'abord||| First, let's think about the followings: Nous allons d'abord envisager cette méthode 如果 第一个 蛋 某些 原因 下 它 碎 了 if the first egg breaks out of some reasons, Si le premier œuf se casse pour certaines raisons 那 我 就 只 剩下 一个 蛋 了 then I have 1 egg remaining. Alors il ne me reste qu'un œuf. 剩下 一个 蛋 之后 Since I have only 1 Après qu'il me reste un œuf. 我 只能 一个 层 一层 一层 一层 这样 往 上试 了 I can only test it floor-by-floor, all the way to 100. Je ne peux essayer qu'un niveau à la fois comme ça. 就 回到 第一种 情况 了 对 吧 We returned to the first case, isn't it? 所以 我 第一个 蛋 的 作用 The goal of my first egg Donc, je pense que le rôle du premier œuf 应该 是 用来 把 这个 范围 尽量 的 缩小 is to shorten the range of floors that I need to try. devrait être de réduire autant que possible cette portée 然后 用 第二个 蛋 一个 一个 的 去 试 Then I use the second egg for the remaining floors. puis d'utiliser le deuxième œuf pour essayer un par un. 只能 是 这样 吧 Let's also draw a diagram. Cela ne peut être que comme ça. 好 那 我们 还是 把 这个 图画 出来 D'accord, alors dessinons cette image. 说 有 这个 1 到 100 层 对 不 对 We have 1 to 100 floors, On dit qu'il y a cet étage de 1 à 100, n'est-ce pas ? 然后 我 有 两个 蛋 and then we have 2 eggs, Alors, j'ai deux œufs. A 和 B 我们 先 让 A 这个 鸡蛋 怎么 做 呢 A and B. What shall we do with egg A first? A et B, commençons par faire quelque chose avec cet œuf A. 我 先 让 A 这个 鸡蛋 I will drop A first. Je vais d'abord m'occuper de cet œuf A. 第一次 扔 I will drop it from floor 10. 我 让 它 在 10 层楼 往下 扔 Je le laisse tomber du 10ème étage. 它 如果 要是 碎 了 If it breaks, S'il se casse, 就 说明 临界 楼层 在 1 到 10 之间 对 吧 then that the boundary floor is between 1 and 10, isn't it? cela signifie que le niveau critique est entre 1 et 10, n'est-ce pas ? 如果 不碎 If not, Si ça ne se brise pas 我 就让 它 在 20 层 的 地方 扔 then I will drop it from floor 20. Je vais le laisser tomber au 20ème étage. 如果 碎 了 在 这 if it breaks then the boundary is there. S'il se brise ici. 如果 不碎 就 在 30 层 的 地方 扔 if not, drop it again from floor 30. S'il ne se brise pas, je le ferai tomber au 30ème étage. 也就是说 我 可以 让 A 这个 蛋 This means that I can drop egg A C'est-à-dire que je peux faire en sorte que l'œuf A 它 在 10 20 30 ... 一直 到 100 from floors 10, 20, 30... 100. Il va de 10 à 20, 30 ... jusqu'à 100 这些 个 楼层 扔 Ces étages sont jetés A 最多 可以 扔 10 次 对 吧 The maximum number of dropping A is 10, right? A peut jeter au maximum 10 fois, n'est-ce pas ? 好 如果 我 把 A 这个 确定 了 If A has a fixed number, D'accord, si je confirme A. 比如说 在 10 层 的 时候 没碎 |||||n'a pas cassé say, it didn't break from floor 10 Par exemple, il n'a pas cassé à 10 étages. 在 20 层 的 时候 碎 了 but it broke when dropping from floor 20. Il a cassé à 20 étages. 那 就 说明 临界 楼层 在 这 Then the boundary floor is there. Cela signifie donc que l'étage critique est ici 然后 我用 第二个 鸡蛋 再 去 试 Now I use my second egg, Ensuite, j'utilise le deuxième œuf pour essayer à nouveau 11 12 13 14 15 16 ... 一直 到 19 对 不 对 11, 12, 13,14,15,16 ... 19, isn't it? 11 12 13 14 15 16 ... jusqu'à 19, c'est bien ça ? 所以 B 这个 鸡蛋 The number of floors from which B will be dropped: Donc, l'œuf B 它 扔 的 楼层 就是 la hauteur de la chute est x1 x2 x3 ... 一直 到 x9 x1, x2, x3 ... x9. x1 x2 x3 ... jusqu'à x9 好 通过 这样 的 方法 This way, Bien, c'est une bonne méthode. 我 就 一定 能够 把 这个 楼层 给 试出来 对 吧 I will surely find the boundary, right? Je vais absolument pouvoir tester cet étage, n'est-ce pas ? 临界 楼层 给 试出来 Finding the boundary through tests. Tester l'étage critique 那 咱们 想一想 Now let's think Alors réfléchissons un peu 最多会 扔 多少次 呢 What is the maximum number of tests? Combien de fois pourra-t-on jeter au maximum ? 假如 说 A 在 第 10 层楼 的 地方 就 碎 了 Let's say that A breaks when dropping from floor 10. Si l'on dit que A se casse à l'endroit du 10ème étage. 那么 B 最多 是 9 次 Then B will be dropped a maximum of 9 times. Alors B au maximum est 9 fois. 总共 就是 扔 10 次 就 能 试出来 了 对 吧 This is a total of 10 tests. Au total, il faut seulement lancer 10 fois pour le découvrir, n'est-ce pas ? 好 如果 A 在 100 层 的 时候 才 碎 了 Ok, if A breaks when on floor 100 D'accord, si A se casse seulement au 100ème étage, 那么 A 扔 了 10 次 then A was dropped for 10 times Alors A a été lancé 10 fois. 然后 我 B 再 去 试 After, I try with B Puis je vais réessayer 结果 试到 最后 一个 才 碎 |essayer|||| It breaks on the last try Le résultat est que ça a cassé seulement au dernier essai 那 就 说明 你 在 99 层 或者 100 层碎 了 This means it broke when dropping from floor 99 or 100 Cela signifie que tu as cassé au 99ème ou au 100ème étage 此时 我们 就要 扔 19 次 对 不 对 This time we had to drop them for 19 times, isn't it? À ce moment-là, nous devons lancer 19 fois, vrai ou faux. 所以 最坏 的 情况 下 我们 需要 扔 19 次 In the worst case, we need to test 19 times. Donc, dans le pire des cas, nous devons lancer 19 fois. 好 扔 19 次 D'accord, lançons 19 fois. 咱们 思考 一下 Let's think about this a bit. Réfléchissons un peu 还有 没有 一种 方法 能够 比 这个 方法 更好 呢 Does there exist a better way? N'y a-t-il pas une méthode qui soit meilleure que cette méthode ? 这个 方法 它 有 的 时候 是 10 次 With this method, sometimes 10 times, Cette méthode peut parfois fonctionner 10 fois 有 的 时候 是 19 次 and at other times it is 19. Parfois, c'est 19 fois 在 10~19 之间 它 不 平均 It is not consistent. It fluctuates between 10 and 19. Entre 10 et 19, ce n'est pas uniforme 原因 是 什么 呢 What is the reason? Quelle en est la raison ? 原因 是因为 A 它 确定 的 间隔 是 等 间隔 的 The reason is that the intervals of possibilities that A eliminates are evenly spaced. La raison est que A détermine que l'intervalle est uniforme. 等 间隔 的 就 造成 B 这个 鸡蛋 去试 的 时候 L'uniformité des intervalles a causé que B, quand il essaie l'œuf, 每 一次 扔 的 次数 最多 都 是 一样 的 对 吧 A's maximum number of drops is always the same. le nombre de fois qu'il lance est toujours le même, n'est-ce pas ? 但是 如果 这个 临界 楼层 靠 后 的话 If the boundary is very high Mais si ce niveau critique est plus élevé, A 扔 的 次数 就 多 了 是不是 The number of tests would be very large. le nombre de lancers de A sera plus élevé, n'est-ce pas ? 所以 我们 在 思考 能 不能 让 这个 间隔 变得 不等 I'm thinking of whether we could make the intervals uneven. Donc, nous réfléchissons à la possibilité de rendre cet intervalle inégal. 我们 让 间隔 变得 不等 To make them uneven means that, Nous rendons l'intervalle inégal. 就是说 让 A 每多 扔 一次 |||de plus|| One additional test for A. C'est-à-dire que lorsque A lance encore une fois, B 的 这个 间隔 就 缩小 一点 Smaller intervals for B. l'intervalle de B se rétrécit un peu. A 扔 一次 B 就 间隔 缩小 一点 Drops A. Smaller B interval. A jette B une fois, l'intervalle se réduit un peu. 这样一来 让 它 总 次数 能够 平均 一下 This way, the total number would be smoothed out. De cette façon, cela permet de moyenniser le nombre total d'occasions. 也许 这种 情况 会 更好 对 不 对 Maybe this is better than the previous? Peut-être que cette situation sera meilleure, non ? 好 咱们 再 来看 一个 方法 Let's explore this further. D'accord, regardons une autre méthode 我们 换 一种 方法 Let's use a different explanation. Changeons de méthode 如果 我 让 这个 间隔 还是 1 到 100 是 吧 The total interval is still 1 to 100, Si je laisse cet intervalle toujours entre 1 et 100, n'est-ce pas? 但是 间隔 不 一样 but the smaller intervals are different. Mais les intervalles ne sont pas les mêmes 我 A 鸡蛋 第一次 扔 的 时候 呢 The interval created when I first dropped A is n floors. Quand j'ai lancé l'œuf A pour la première fois 我 让 它 的 间隔 是 n 层 Je fais en sorte que son intervalle soit n couches 然后 如果 它 不碎 If it doesn't break, Puis, s’il ne se casse pas 第二次 扔 的 时候 我 让 这个 间隔 是 n-1 层 then at the second test, let this interval be n-1 floors. Pour le deuxième lancer, je laisse cet intervalle être n-1 étages 第三次 扔 的 时候 我 让 这个 间隔 是 n-2 层 The third time, n-3 floors. Pour le troisième lancer, je laisse cet intervalle être n-2 étages 直到 最后 一次 扔 的 时候 呢 At the final test, n is 1 floor. Jusqu'à la dernière fois que je l'ai lancé 我 让 这个 间隔 是 1 层 Je fais en sorte que cet intervalle soit d'un étage 也 就是 A 每多 扔 一次 So every time I drop A C'est-à-dire qu'A lance une fois de plus 它 的 间隔 就 小 了 一点 B's interval of possible floors become smaller. Son intervalle est devenu un peu plus petit. 这样一来 B 所 需要 检验 的 次数 就会少 1 |||||||alors The number of B tests is always decreased by 1. Ainsi, le nombre de tests nécessaires pour B sera réduit de 1. A 多 扔 一次 B 就 少 扔 一次 More A, less B. A lance une fois de plus, donc B lance une fois de moins. 这样一来 总 次数 不 就 平均 了 一些 吗 then our total would be constant, right? De cette façon, le nombre total de fois ne sera-t-il pas un peu plus équilibré ? 也许 这种 方法 会 更好 Maybe this method is better? Peut-être que cette méthode serait mieux. 咱们 思考 一下 Assume that we are using this method. Réfléchissons un peu. 假如 按照 这种 方法 的话 我们 算一算 这个 n 应该 得 几 |faire le calcul||||| We calculate n. Calculons donc à combien devrait s'élever ce n. 这个 并 不难 This shoudn't be hard Ce n'est pas difficile. 就是 1+2+3+ ... 一直 加 加到 n It is 1+2+3... +n. C'est simplement 1 + 2 + 3 + ... jusqu'à n. 它 的 最后 我们 都 知道 用 高斯 公式 |||||||Gauss| We know how to use Gauss' formula. Nous savons tous que cela se termine par la formule de Gauss 它 应该 等于 n(n+1)/2 对 吧 It should be equal to n(n+1/2), right? Cela devrait être égal à n(n+1)/2, n'est-ce pas ? 那么 这个 结果 它 必须 要 大于 等于 100 and then the result must be greater or equal to 100. Donc ce résultat doit être supérieur ou égal à 100 所以 我们 可以 计算 出 这个 n 来 Calculate n. Donc, nous pouvons calculer ce n. 这个 n 要 大于 等于 13.65 n must be greater or equal to 13.65. Ce n doit être supérieur ou égal à 13.65. 于是 我们 就 取 n 等于 14 We will round up n. n=14 Alors nous prenons n égal à 14. n 等于 14 什么 意思 呢 What does this mean? que signifie n = 14 ? 就是说 我们 不 考虑 那种 加 1 减 1 的 临界 情况 了 This means that we no longer need to consider those +1 and -1's. C'est-à-dire que nous ne considérons pas ce genre de situation critique d'ajouter 1 ou soustraire 1. 就是说 A 鸡蛋 我们 这么 扔 I will drop A on floor 14. C'est-à-dire que nous jetons l'œuf A comme ça. 第一次 我 让 它 跨越 14 个 间隔 La première fois, je l'ai laissé traverser 14 intervalles. 也 就是 在 14 层楼 去 扔 C'est-à-dire que je l'ai jeté de 14 étages. 14 层楼 如果 碎 了 就 说明 在 1~14 层 之间 if it breaks, then the boundary is between 1 and 14. Si ça se casse à 14 étages, cela signifie que c'est entre le 1er et le 14e étage. 然后 我用 B 鸡蛋 试 1 2 3 4 ... 一直 到 13 对 吧 I will use egg B to try out 1,2,3,4,...,13, right? Ensuite, j'essaie avec l'œuf B 1, 2, 3, 4 ... jusqu'à 13, n'est-ce pas ? 如果 第一个 14 层 没碎 If it doesn't break from floor 14. Si les 14 premières couches ne se cassent pas, 我 就让 它加 13 层 要 减 1 对 吧 加 13 ||ajouter|||||| I will add 13 since it is deducted by 1. Alors je fais ajouter 13 couches, ça doit diminuer de 1, n'est-ce pas ? Ajouter 13. 14 加 13 27 层 14 plus 13 gives 27. 14 plus 13 égale 27 étages 如果 27 层不碎 |ne se casse pas If it doesn't break from floor 27, si 27 étages ne se brisent pas 我 就 再加 12 39 层 ||ajouter| I will add 12 more floors, so floor 39. je ajouterai encore 12 plus 39 étages 不碎 我 再加 11 是 50 层 ||ajouter|| Doesn't break. Add 11. Floor 50. Pas de bris, j'ajoute 11 pour atteindre 50 couches 不碎加 10 60 层 non cassant| Add 10 floors. Floor 60. Pas de bris, j'ajoute 10 pour atteindre 60 couches 不碎加 9 69 层 No break Add 9. Floor 69. Pas de bris, j'ajoute 9 pour atteindre 69 couches 然后 加 8 77 层 then add 8. Floor 77. Ensuite, ajoutez 8, 77 couches 加 7 84 层 Add 7 Floor 84 Ajoutez 7, 84 couches 然后 加 6 是 90 层 加 5 95 层 then adding 6 gives us floor 90 Adding 5 gives us floor 95 Ensuite, ajoutez 6, soit 90 couches, ajoutez 5, 95 couches 加 4 99 层 加 1 100 层 Add 4, floor 99. Add 1, floor 100. Ajouter 4 couches 99 ajouter 1 couche 100 最后 加不上 3 了 为什么 呢 |ajouter||| Finally, we can't add 3. Why? Enfin, je ne peux pas ajouter 3, pourquoi ? 因为 我 这个 实际上 是 13.65 Because n is 13.65 and we used 14. Parce que je suis en fait 13,65 你 取 了 个 14 Tu as pris un 14 自然而然 最后 它 就 会 差 了 一点点 Naturally, a little would be left at the end. Naturellement, à la fin, cela va être légèrement différent 好 那么 A 它 最 多 扔 多少次 Now, what is the maximum number for A? Bon, alors A, il peut jeter au maximum combien de fois 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12 A 最多 是 扔 12 次 A's maximum is 12 A peut être jeté au maximum 12 fois 那 如果 第一次 A 就 碎 了 If A got dropped the first time Alors, si A se casse dès la première fois 那 我 就 需要 用 B 鸡蛋 去 检验 1~13 层 then I would need B to test out floors 1 to 13. 再 加上 A 扔 的 一次 一共 是 扔 了 14 次 Adding the 1 time from A, the total is 14 times En ajoutant une fois de plus que A a lancé, cela fait un total de 14 lancés. 如果 A 扔 到 27 层 的 时候 碎 了 If A breaks when reaching floor 27 Si A a lancé au 27e étage et que cela a cassé, 那 我 B 就 需要 检验 15 层到 26 层 ||||||à| then B would test out floors 15 to 26 Alors je, B, devrai vérifier les étages 15 à 26. 再 加上 A 扔 的 那 两次 Adding the 2 times from A De plus, les deux fois où A a lancé. 最后 结果 还是 14 次 对 吧 the final number is still 14, right? Au final, le résultat est toujours de 14 fois, n'est-ce pas ? 那 当然 如果 A 扔 到 100 层碎 了 of course, if A breaks on floor 100 Bien sûr, si A lance et que ça casse à 100 étages. 或者 是 100 层 还 没碎 的话 or it doesn't break Ou si c'est 100 couches qui ne se sont pas encore brisées 那 你 就 不 需要 用 B 去 检验 了 then you don't need B anymore Alors tu n'as plus besoin de vérifier avec B. 那 最少 的 是 12 次 the minimum required number is 12 times Alors le minimum est de 12 fois. 于是 用 这种 方法 so with this method Alors on utilise cette méthode. 你 扔 鸡蛋 的 次数 是 在 12~14 之间 The number of egg drops is between 12 and 14 Le nombre de fois que vous jetez des œufs est entre 12 et 14. 最差 的 情况 下 是 14 次 the worst case is 14 Dans le pire des cas, c'est 14 fois. 所以 这样 一看 你 看 两个 鸡蛋 的 情况 下 looking this way, when you have 2 eggs Donc, en regardant cela, vous regardez la situation avec deux œufs. 这 M 不是 19 this M is not 19 Ce M n'est pas 19 最差 的 情况 下 in the worst case Dans le pire des cas 我 只 需要 扔 14 次 we only need to test 14 times Je n'ai besoin de lancer que 14 fois 就 能 保证 你 一定 能够 找到 那个 临界 的 楼层 了 对 吧 to guarantee that you can find the boundary floor Alors tu peux être sûr que tu vas trouver cet étage critique, n'est-ce pas ? 好 那 这个 面试题 其实 我们 就 说完 了 Ok, we have finished explaining this interview question Bien, donc cette question d'entretien, en réalité, nous en avons terminé. 不过 咱们 想 如果 仅仅 是 这样 一个 问题 的话 but if we think about this, if we only have such a question Cependant, on pense que si c'est juste une question comme ça... 其实 意义 并不大 its significance isn't much. En fait, ça n'a pas beaucoup de sens. 你 能够 保证 这种 方法 就是 最好 的 吗 Is this method guaranteed to be the best? Peux-tu garantir que cette méthode est la meilleure ? 也 不见得 吧 Not necessarily, Ce n'est pas forcément vrai. 而且 这个 人 一定 有 两个 蛋 since we have 2 eggs. Et cette personne doit avoir deux œufs. 不 一定 he could have 3 eggs, 4 eggs, 5 eggs, 6 eggs... Pas forcément. 他 可能 有 3 个 蛋 4 个 蛋 5 个 蛋 6 个 蛋 ... Il pourrait avoir 3 œufs, 4 œufs, 5 œufs, 6 œufs ... 那么 如果 我们 的 蛋 数量 不是 2 的话 if the number of eggs is smaller than 2 Alors, si notre nombre d'œufs n'est pas 2 这个 问题 又 该 如何 去 解决 呢 how shall we tackle it? Comment devrions-nous alors résoudre ce problème ? 所以 说 这道题 的 精髓 ||||essence Therefore, the main idea of this problem C'est donc l'essence de ce problème 其实 在于 其他 的 情况 下 is that under the other situations En fait, dans d'autres cas 我们 需要 使用 递归 的 思想 来 进行 求解 ||||||||résolution we need to use recursive thinking. Nous devons utiliser la pensée récursive pour résoudre 其实 递归 思想 我们 在 之前 讲 汉诺塔 |||||||Tour de Hanoï En fait, nous avons déjà parlé de la pensée récursive avec le problème de Hanoï 还有 拜占庭 将军 问题 的 时候 都 用到 过 |Byzance||||||| Il y a aussi la question des généraux byzantins qui a été utilisée. 但是 这个 递归 要 比 汉诺塔 那种 递归 but the one covered here is slighly more complicated than the one we used to solve the Tower of Hanoi Mais cette récursion est un peu plus complexe que celle du jeu de Hanoï. 稍微 复杂 一点 Un peu plus compliqué. 这个 思想 是 这样 的 The idea is this. 我们 把 这个 问题 普遍化 一点 ||||généraliser| Let's generalize this problem. Nous allons généraliser un peu cette question 就 假如 说 这 一层楼 它 有 T 层 ||||étage|||| Let's say this building has T floors. Disons que cet étage a T niveaux 这个 楼有 T 层 |étage|| This building has T floors, Cet immeuble a T niveaux 然后 我们 一共 有 N 个 蛋 and then we have N eggs in total. Alors, nous avons en tout N œufs. 这个 时候 我们 要 找到 在 最 不利 的 情况 下 now we need to find the minimum number of drop times for the worst-case scenario À ce moment-là, nous devons trouver dans les pires conditions 至少 要 扔 多少次 才能 一定 找到 这个 临界 楼层 au moins combien de fois nous devons les lancer pour pouvoir trouver ce seuil critique. 这个 次数 叫 M this number is M Ce nombre s'appelle M 那么 M 自然 是 T 和 N 的 一个 函数 |||||||||fonction naturally, M is a function of T and N Alors M est naturellement une fonction de T et N 我 就 问 这个 函数 值 到底 应该 是 多少 对 吧 What is this value of this function? Je me demande donc combien devrait être la valeur de cette fonction, n'est-ce pas ? 这个 问题 我们 首先 先 从 最 简单 的 情况 说起 To tackle this, we start from the most basic case Cette question, nous allons commencer par le cas le plus simple. 首先 我们 画 一个 表格 First, draw a table. Tout d'abord, nous allons dessiner un tableau. 这个 表格 呢 Ce tableau-là. 这个 表格 它 的 一列 表示 的 是 这个 楼层 数 T Its first row represents its floor number. Cette table a une colonne qui représente le nombre d'étages T. T 可以 是 1 2 3 或者 一直 到 100 是 吧 T can be 1,2,3,...,100. T peut être 1, 2, 3 ou aller jusqu'à 100, n'est-ce pas ? 然后 蛋 的 数目 The number of eggs Puis le nombre d'œufs. 也 可以 是 1 2 3 4 或者 是 更 多 的 蛋 对 吧 could also be 1,2,3,4 or even more, right? On peut aussi avoir 1, 2, 3, 4 ou même plus d'œufs, n'est-ce pas ? 好 的 现在 有 一些 情况 是 比较 好 填 的 Some spaces are relatively easy to fill. D'accord, il y a maintenant certaines situations qui sont relativement faciles à remplir. 比如说 吧 如果 你 只有 一个 鸡蛋 的话 For example, you only have 1 egg and 1 floor. Par exemple, si vous n'avez qu'un seul œuf. 你 有 一层楼 the minimum drop is 1, right? Tu as un étage 你 就 至少 得 扔 一次 对 不 对 Tu dois au moins jeter une fois, n'est-ce pas ? 你 有 两层楼 就 得 扔 两次 2 floors, 2 drops Tu as deux étages, tu dois jeter deux fois 有 三层楼 就 得 扔 三次 |trois étages|||| 3 floors, 3 drops Avec trois étages, il faut le jeter trois fois. 所以 这 一列 是 非常 好 填 的 so these are quite easy. Donc, cette colonne est très bien remplie. 那么 如果 是 只有 一层楼 呢 When there is only 1 floor, Alors, que se passe-t-il s'il n'y a qu'un seul étage ? 只有 一层楼 的话 S'il n'y a qu'un étage 不管 你 有 几个 鸡蛋 都 只 需要 扔 一次 No matter how many eggs you have, you only need 1 test, Peu importe combien d'œufs vous avez, vous n'avez besoin de les jeter qu'une seule fois 所以 这 一行 也 是 很 好 填 的 so this column is also very easy. Donc cette ligne est aussi très facile à remplir 也就是说 这 两个 边界 These 2 borders, C'est-à-dire que ces deux frontières 其实 都 是 非常 非常 好 填 的 are very easy to fill. sont en fait très, très faciles à remplir. 当然 后面 还有 我 就 没有 再往 下 写 ||||||encore|| There are more. Bien sûr, il y a encore la suite, je n'ai donc pas écrit plus bas. 这 两个 边界 很 好 填 These are easy to fill. Ces deux bordures sont très bien remplies. 关键 是 中间 这 一大堆 The harder part is these cells. La clé, c'est cette grande pile au milieu. 比如说 有 3 层楼 2 个 鸡蛋 For example, we have 3 floors and 2 eggs Par exemple, il y a 3 étages et 2 œufs. 你 至少 要 扔 几次 What is the minimum number of drops Tu dois jeter au moins plusieurs fois 100 层楼 2 个 鸡蛋 你 要 扔 几次 for floor 100, 2 eggs? Avec 100 étages et 2 œufs, combien de fois dois-tu jeter? 5000 层楼 3 个 鸡蛋 How about the 5000th floor and 3 eggs? Avec 5000 étages et 3 œufs 你 要 扔 几次 How many times? 所以 这个 问题 就 比较复杂 These are more complicated. Donc, ce problème est relativement complexe. 我们 怎么 去 研究 它 呢 How to tackle this? Comment allons-nous l'étudier ? 我们 就要 使用 递归 的 思想 了 We should use recursion. Nous allons devoir utiliser la pensée récursive. 这个 思想 是 这样 的 No matter how many eggs you have, Cette idée est comme ça 不管 你 有 多少 个 鸡蛋 Peu importe combien d'œufs vous avez 在 扔 的 时候 你 首先 必须 得选 一层 |||||||choisir| You must choose a floor Lorsque vous lancez, vous devez d'abord choisir un niveau 然后 扔 第一个 鸡蛋 对 不 对 to drop the first egg, isn't it? Alors, on jette le premier œuf, non ? 好 那么 第一个 鸡蛋 扔 在 哪 呢 Where should it be dropped? D'accord, alors où jette-t-on le premier œuf ? 我们 其实 也 并 不 清楚 扔 在 哪 I'm not clear either. En fait, nous ne savons pas vraiment où le jeter. 比如说 这个 楼层 是 1 到 T 这么 多层 |||||||étages Say that this building has 1 to T floors. Par exemple, cet étage est de 1 à T étages. 第一个 鸡蛋 你 随便 给 我 找个 地方 叫 第 k 层 for the first egg, you find a random floor, called k Le premier œuf, tu peux juste me trouver un endroit que l'on appellera le k-ième étage. 你 就 扔 吧 Tu peux simplement le jeter. 扔 完 了 之后 两种 结果 Dropping it results in 2 consequences: Après avoir jeté, il y a deux résultats 一种 是 碎 一种 是 不碎 Broken, or not. L'un est que ça se casse, l'autre est que ça ne se casse pas 如果 碎 就 说明 这个 临界 楼层 一定 在 前面 If it is broken, then the boundary floor is lower. S'il se casse, cela signifie que cet étage critique se trouve forcément devant 如果 不碎 就 说明 临界 楼层 一定 在 后面 对 不 对 If not broken, then the floor must be higher. Si ça ne se casse pas, cela signifie que l'étage critique doit être derrière, n'est-ce pas ? 好 那么 如果 碎 了 你 还 需要 扔 多少次 鸡蛋 If broken, then how many more trials are needed for these k floors? Bien, alors si ça se casse, combien de fois devras-tu encore jeter les œufs ? 才能 确定 这 k 个 楼层 里边 哪 一层 是 临界 楼层 呢 Pour déterminer quel étage parmi ces k étages est l'étage critique ? 我们 可以 说 这个 数 This number is actually Nous pouvons dire ce nombre 其实 就是 M 什么 呀 k 层楼 N-1 个 蛋 M(k, N-1). En fait, c'est M quoi, k étages, N-1 œufs 为什么 呢 因为 你 第一个 鸡蛋 已经 碎 了 Why? Because the first egg was broken, so you now have N-1 eggs. Pourquoi ? Parce que vous avez déjà cassé votre premier œuf 所以 你 的 蛋 只能 变成 N-1 个 了 Donc, ton œuf ne pourra devenir qu'un N-1 seulement. 而 楼层 原来 是 T 层 Originally you had T floors. Now you know that the boundary floor is lower, Et l'étage était à l'origine de T niveaux. 现在 你 已经 知道 不在 后面 只 在 前面 Maintenant, tu sais déjà que ce n'est pas derrière, mais seulement devant. 所以 楼层 变成 k 了 so T is replaced by k. Donc, l'étage est devenu k. 因此 你 会 有 这样 的 一个 数据 Therefore, you have M(k, N-1). Ainsi, vous aurez une telle donnée. 好 这 是 你 再 往后 还 需要 确定 多少次 Now, how many more times do we need to try? C'est bien, c'est ce que vous devez encore déterminer combien de fois. 再往 下 如果 它 不碎 的话 也 是 一样 的 In the previous case, if the egg doesn't break, the result is still be the same. Plus bas, si cela ne se brise pas, c'est pareil. 此时 楼层 就 变成 了 这么 多层 The number of floors is now T-k À ce moment-là, le nombre d'étages était devenu si élevé. 这个 层数 应该 是 T-k 层 |nombre de couches||||| Ce nombre d'étages devrait être T-k. 而 蛋 的 数目 还是 N 个 对 吧 The number of eggs is still N. Therefore, we still need M(T-k, N) tries. Et le nombre d'œufs est toujours N, n'est-ce pas ? 于是 我们 可能 还 需要 找 这么 多次 Alors nous devrions peut-être chercher autant de fois. 才能 确定 具体 是 在 哪 一层 Pour pouvoir déterminer exactement à quel niveau cela se trouve. 因为 我们 要 找 的 是 最 不利 的 情况 下 Since we are looking for the required trials in the worst case, Parce que ce que nous devons trouver, ce sont les pires scénarios. 需要 扔 多少 层 Combien de couches doivent être jetées. 所以 在 这 两种 可能 下 Donc, dans ces deux scénarios possibles. 我们 要 把 它 取 一个 最大值 ||||||maximum Nous devons lui donner une valeur maximale 这 两种 可能 中 比较 大 的 那个 值 we will take the larger value. C'est la valeur la plus grande parmi ces deux possibilités 就是 我 第一个 鸡蛋 扔 到 k 层 的 时候 This is the minimum number of trials required when we C'est lorsque j'ai lancé mon premier œuf à la couche k 我 需要 数 的 个数 对 吧 ||||nombre|| throw the first egg from floor k J'ai besoin du nombre de fois, n'est-ce pas ? 最少 需要 数 这么 多次 Il faut au moins le faire autant de fois 但是 同时 你 不要 忘 了 你 开始 还 扔 了 一层 对 不 对 but don't forget you have tested one floor earlier Mais en même temps, n'oublie pas que tu as commencé par en jeter une couche, n'est-ce pas ? 所以 你 还要 把 这个 数字 再 加上 一个 1 so we need to add 1 to it. Donc tu dois ajouter un 1 à ce chiffre. 就 这 两个 数中 较大 那个 数再加 1 ||||||numéro max{M(k, N-1), M(T-k, N)} + 1 Ajoute 1 au plus grand de ces deux chiffres. 它 就 等于 什么 呢 What is it equal to? Et cela équivaut à quoi ? 它 就 等于 当 你 第一个 鸡蛋 扔 到 第 k 层时 |||||||||||à l'étage It is equal to the number of trials when you have T floors and N eggs, with the first trial on floor k. Cela équivaut à lorsque vous jetez votre premier œuf au kème étage 如果 原来 你 有 T 层楼 和 N 个 鸡蛋 Si au départ vous avez T étages et N œufs 你 需要 扔 鸡蛋 的 个数 Le nombre d'œufs que vous devez jeter 但是 你 第一个 这个 k 你 怎么 确定 呢 对 不 对 Now, how do we determine k? Mais comment êtes-vous sûr que ce k est le premier ? Vrai ou faux. 我们 的 一个 方法 就是 枚举 One way is to list all k's from 1 to T. Une de nos méthodes est l'énumération 就是 把 k 等于 1 2 3 4 5 6 7... 一直 到 T C'est de faire en sorte que k soit égal à 1, 2, 3, 4, 5, 6, 7... jusqu'à T 我 全数 一遍 我 再 画 一个 表格 |toute la somme|||||| Let me draw another table. Je passe en revue tout ça et je dessine un tableau 这个 表格 是 我们 知道 你 这个 k 它 有 很 多种 可能 k can take any values. Ce tableau est celui que nous savons, ce k a beaucoup de possibilités. 你 第一个 鸡蛋 可以 扔 在 第一层 Your first try could be on floor 1. Votre premier œuf peut être lancé au premier étage. 你 也 可以 扔 到 第二层 可以 扔 第三层 It could also be floor 2 or 3. Vous pouvez aussi le lancer au deuxième étage, ou le lancer au troisième étage. 一直 到 你 可以 扔 到 最后 一层 就是 第 T 层 All the way to floor T. Jusqu'à ce que tu puisses jeter jusqu'à la dernière couche, c'est-à-dire la couche T. 那么 你 在 每 扔 一次 你 都 可以 做 这个 运算 You could calculate M every time you try a different starting floor k. Alors, à chaque fois que tu jettes, tu peux faire ce calcul. 对 不 对 C'est vrai, non ? 找到 那种 最 不利 的 情况 下 Find the number of tries, M, in the worst case. Trouver le cas le plus défavorable 你 需要 扔 鸡蛋 的 次数 Mᴋ 是 吧 ||||||Mᴋ(1)|| Le nombre de fois que vous devez jeter des œufs Mᴋ est ça 所以 如果 你 第一个 鸡蛋 扔 到 第一层 了 就是 M₁ First floor, M_1 Second, M_2 Third, M_3 Donc si vous jetez le premier œuf au premier étage, c'est M₁ 扔 到 第二层 就 M₂ Si vous jetez au deuxième étage, c'est M₂ 扔 到 第三层 就 M₃ Si vous jetez au troisième étage, c'est M₃ 一直 到 如果 第一个 鸡蛋 扔 到 T 层 了 那 就是 Mᴛ ||||||||||||Mᴛ(1) To M_T Il continue jusqu'à ce que si le premier œuf est jeté à l'étage T, alors c'est Mᴛ 对 不 对 Non, c'est faux 好 第一个 鸡蛋 你 是 可以 选 的 Bien, le premier œuf que tu peux choisir 你 可以 扔 在 任何 一层 Tu peux le lancer à n'importe quel étage 所以 我 需要 在 这 里面 所有 的 值 中 Since I could choose k, I will pick the one with the lowest tries. Donc, j'ai besoin de toutes les valeurs à l'intérieur de ça 我选 一个 最 什么 的 值 Je choisis une valeur la plus quoi que ce soit 最小 的 值 la plus petite valeur 所以 最终 的 结果 是 Therefore, Donc, le résultat final est M 在 T 层楼 N 个 鸡蛋 的 情况 下 它 等于 M(T, N) = min {M_1, M_2, ... , M_3} M œufs N au niveau T équivaut à 最小值 M₁ M₂ ... 一直 到 Mᴛ valeur minimale||||| valeur minimale M₁ M₂ ... jusqu'à Mᴛ 这样一来 我们 就 把 这个 数据 给 确定 了 Now we have a function that we can use for this problem. Ainsi, nous avons déterminé ces données 有人 说 那 这个 运算 这么 复杂 我 到底 怎么 算 You may say that this is too complicated to calculate. It is actually quite simple. Certains disent que ce calcul est si complexe. Comment dois-je le faire? 其实 很 简单 En fait, c'est très simple. 你 看 你 在 每 一次 计算 的 过程 中 At every drop, regardless of which floor, it is either T replaced by k, or T replaced by T-k. Regardez, vous êtes dans le processus de calcul à chaque étape. 不管 你 从 哪 一层楼 去 扔 Peu importe de quel étage vous jetez 你 都 要不然 是 把 这个 楼层 数给 减少 了 |||||||compter|| vous devez soit réduire le nombre d'étages T 变成 k 了 T est devenu k 或者 T 变成 T-k 了 Ou T est devenu T-k 要不然 就是 把 鸡蛋 的 个数 减少 了 It is either one less egg, Sinon, c'est que le nombre d'œufs a été réduit 或者 没有 减少 对 不 对 or that the number of eggs stays the same. Ou alors il n'y a pas eu de réduction, n'est-ce pas ? 所以 我们 已经 知道 了 Since we know what would happen Donc, nous savons déjà 楼层 少 和 鸡蛋 少 的 时候 的 情况 when we have 1 egg and N floor, or 1 floor and N eggs, la situation lorsque le nombre d'étages est faible et qu'il y a peu d'œufs 我们 就 可以 一点一点 算 出 we can use them to calculate the subsequent cases nous pouvons donc calculer peu à peu 楼层 多 和 鸡蛋 多 的 情况 for larger N and T. Des étages nombreux et des œufs nombreux. 也就是说 我们 可以 先算 两层楼 两个 鸡蛋 的 时候 |||d'abord||||| For example, we could first calculate T=2, N=2. C'est-à-dire que nous pouvons d'abord calculer le cas de deux étages avec deux œufs. 三层楼 两个 鸡蛋 的 时候 T=3, N=2. Le cas de trois étages avec deux œufs. 把 这 一列 都 算 完 Finish this second row, Calculer toute cette colonne 然后 利用 这个 数据 我 再 去 算 三个 鸡蛋 的 时候 and then use this data to calculate the next row N=3. Ensuite, en utilisant ces données, je vais calculer pour trois œufs 两层楼 如何 三层楼 如何 Comment faire un bâtiment de deux étages et trois étages 我 把 这 一列 也 算 完 J'ai aussi compté cette colonne 然后 我 再 算 四个 鸡蛋 的 时候 then we calculate the row for N=3. Puis je comptais à nouveau quatre œufs 这个 数 这个 数 分别 是 多 大 Cette somme, cette somme, quelle est leur taille respectivement 这样 一点一点 的 递归 We will fill in this table recursively, step-by-step. Ainsi, cette récursion petit à petit 就 把 这个 东西 给 弄出来 了 Alors, on a réussi à faire sortir ce truc. 所以 大家 看 这个 思想 其实 还是 挺 复杂 的 对 吧 After exploring this far, we see that this question is actually quite complicated. Donc, tout le monde voit que cette idée est en réalité assez complexe, n'est-ce pas ? 这是 一个 递归 的 这样 一个 思想 It is a recurrence relationship. C'est une idée de récurrence, ainsi, en quelque sorte. 那么 既然 说 到 面试题 了 Since we have been talking about an interview question, let me ask a relatively easier question, Alors, puisque nous parlons des questions d'entretien, 咱们 不妨 出 一个 简单 一点 的 面试题 Pourquoi ne pas proposer une question d'entretien un peu plus simple, 给 大家 想一想 for everyone to think about. pour que tout le monde puisse y réfléchir ? 假如 有 一个 圆形 的 小岛 Let's say there is an island that has a the shape of a circle Supposons qu'il y ait une petite île ronde 然后 有 一条 鳄鱼 在 圆形 小岛 周围 游弋 ||||||||navigue A crocodile is swimming around the island. Et puis il y a un crocodile qui nage autour de la petite île ronde 鳄鱼 的 速度 是 人 的 四倍 The speed of the crocodile is 4 times that of the human. La vitesse du crocodile est quatre fois celle d'un humain 而且 鳄鱼 总是 希望 找到 一个 离 人 最近 的 位置 It always finds a spot that is closest to the human. Et le crocodile espère toujours trouver un endroit le plus proche des gens 而 这个 人 最 开始 在 这个 小岛 的 正 中心 The human starts at the center of the island. Et cette personne se trouvait au tout début au centre de cette petite île 那么 我 问 这个 人该 如何 运动 ||||devrait|| How should he move to reach the edge of the island before the crocodile? Alors je demande à cette personne comment elle devrait s'exercer 才 能够 比 鳄鱼 先 到达 这个 岛 的 边缘 ne peut atteindre le bord de cette île avant le crocodile 从而 逃离 这个 岛 呢 et ainsi échapper à cette île 大家 如果 有 答案 的话 不妨 在 下方 留言 If you know the solution, do not hesitate to post a comment below. Si quelqu'un a une réponse, n'hésitez pas à laisser un commentaire ci-dessous 大家 如果 喜欢 我 的 视频 If you like this video, 可以 在 YouTube 账号 李永乐 老师 里 订阅 我 you could subscribe to my Youtube channel Liyongle (李永乐老师). 点击 小 铃铛 可以 第一 时间 获得 更新 信息 Click on the bell near the subscribe button to be notified of updates.