两颗水晶球问题的O(sqrt(n))解决方案在所有情况下均不起作用。

huangapple
go评论98阅读模式
英文:

Two Crystal Ball Problem O(sqrt(n)) solution not working in all cases

问题

以下是您要翻译的部分：

"这是两个水晶球问题：假设有两个水晶球，如果从足够高的地方掉下来就会破碎，以最优化的方式确定它们会破碎的确切位置。解决方案：为了理解这个问题，让我们假设水晶球如果从高度为8米的地方掉下来就会破碎。所以，如果我们从真实的米数掉下来，球就不会破碎（false）。如果从2米高度掉下来，同样球也不会破碎（false）。我们一直这样做。当从8米高度掉下时，球会破碎（true）。如果我们将所有的false和true列成一个数组，它看起来像下面这样：
[false, false, false, false, false, false, false, false ,false, false, false, true, true, true, true] –

所以你应该找到第一个true。我尝试使用前端主课程中的方法来解决它，但我发现在某些情况下它不起作用，例如，它给我-1，但如果我添加新的false，它会给我true布尔值的第一个位置，即31。有没有办法改进这个算法，谢谢。"

英文:

GHere is the Two Crystal Ball problem: Given two crystal balls that will break if dropped from high enough distance, determine the exact spot in which it will break in the most optimized way. Solution: To understand the problem, let us assume the crystal ball will break if dropped from a height of 8 meters. So, if we drop from true meter, the ball will not break(false). If dropped from height of 2 meter, again the ball will not break(false). We keep on doing it. When dropped from 8 meters, the ball will break(true). If we list all falses and trues in an array, it will look like below:
[false, false, false, false, false, false, false, false ,false, false, false, true, true, true, true] –

so you should find the first true I tried to solve it using the methode from front end master course but I founded it doesn't work in all the cases in that case as an exemple it's give me -1 but if i add new false it give me the first place of true boolean which is 31 is there any way to improve that algorithm and thank you

<!-- begin snippet: js hide: false console: true babel: false -->

<!-- language: lang-js -->

  1. function two_crystal_balls(breaks) {
  2.   const jmpAmount = Math.floor(Math.sqrt(breaks.length));
  4.   let i = jmpAmount
  5.   for (i &lt; breaks.length; i += jmpAmount;) {
  6.     if (breaks[i]) {
  7.       break;
  8.     }
  9.   }
  10.   console.log(i, &quot;i&quot;)
  12.   i -= jmpAmount
  13.   console.log(i, &quot;i&quot;)
  15.   for (let j = 0; j &lt; jmpAmount &amp;&amp; i &lt; breaks.length; j++, i++) {
  16.     if (breaks[i]) {
  17.       console.log(j, &quot;i&quot;)
  18.       return i
  19.     }
  20.   }
  21.   return -1
  22. }
  24. console.log(two_crystal_balls([false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, true, true, true, true, true, true, true, true, true, true, true]))

<!-- end snippet -->

答案1

得分: 0

Here is the translated code without the comments and additional content:

  1. function two_crystal_balls(breaks) {
  2.   const jmpAmount = Math.floor(Math.sqrt(breaks.length));
  4.   let i = jmpAmount;
  5.   for (; i < breaks.length; i += jmpAmount) {
  6.     if (breaks[i]) {
  7.       break;
  8.     }
  9.   }
  11.   i -= jmpAmount;
  13.   for (let j = i; j < breaks.length; j++) {
  14.     if (breaks[j]) {
  15.       return j;
  16.     }
  17.   }
  18.   return -1;
  19. }
  20. console.log(two_crystal_balls([false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, true, true, true, true, true, true, true, true, true, true, true]))

Please note that I've translated the code as requested, and it should now be free of comments and additional content.

英文:

You have three problems in your code.

  1. The first loop is not correct. A for loop has the syntax

    1. for (initialization; condition; afterthought)

    The loop

    1. for (i &lt; breaks.length; i += jmpAmount;) {

    should be

    1. for (; i &lt; breaks.length; i += jmpAmount) {

  2. The loop

    1. for (let j = 0; j &lt; jmpAmount &amp;&amp; i &lt; breaks.length; j++, i++) {
    2.   if (breaks[i]) {
    3.     console.log(j, &quot;i&quot;)
    4.     return i
    5.   }
    6. }

    should be

    1. for (let j = i; j &lt; breaks.length; j++) {
    2.   if (breaks[j]) {
    3.     console.log(j, &quot;i&quot;);
    4.     return j;
    5.   }
    6. }

  3. j contains the solution, not i.

The fixed code:

<!-- begin snippet: js hide: false console: true babel: false -->

<!-- language: lang-js -->

  1. function two_crystal_balls(breaks) {
  2.   const jmpAmount = Math.floor(Math.sqrt(breaks.length));
  4.   let i = jmpAmount;
  5.   for (; i &lt; breaks.length; i += jmpAmount) {
  6.     if (breaks[i]) {
  7.       break;
  8.     }
  9.   }
  10.   console.log(i, &quot;i&quot;);
  12.   i -= jmpAmount;
  13.   console.log(i, &quot;i&quot;);
  15.   for (let j = i; j &lt; breaks.length; j++) {
  16.     if (breaks[j]) {
  17.       console.log(j, &quot;i&quot;);
  18.       return j;
  19.     }
  20.   }
  21.   return -1;
  22. }
  24. console.log(two_crystal_balls([false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, true, true, true, true, true, true, true, true, true, true, true]))

<!-- end snippet -->

huangapple
  • 本文由 发表于 2023年5月7日 06:40:48
  • 转载请务必保留本文链接：https://go.coder-hub.com/76191489.html
  • algorithm
  • javascript
  • typescript
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定