Застрял в алгоритме псевдокода поколения

Question

я не знаю, что делать дальше (и даже если мой подход является правильным) в следующей задаче:

Part 1 Part 2

Я просто понял, что возможный МНТ (для части a) - получить банку, проверить, если она сломается с высоты h, если да, тогда есть ответ, если нет, высота + 1 и продолжайте цикл.

Для части b приведено следующее. Поскольку мы знаем, что максимальная высота равна n, то мы начинаем с n (текущая высота = n). Поэтому мы идем сверху вниз, добавляя к нашему разбитому счету банки (они должны сломаться, если вы начинаете с вершины), пока банки не перестанут ломаться. Тогда число будет иметь текущую высоту + 1 (потому что нам нужно вернуться к одному индексу).

Для части с, я даже не знаю, каким будет мой подход, поскольку я предполагаю, что порядок алгоритма O (n^c), где c - дробь. Я также знаю, что O (n^c) быстрее, чем O (n).

Я также отметил, что есть проблема, подобная этой онлайн, но она говорит о ступеньках вместо роботизированной руки. Может быть, это похоже? Вот link

Есть ли у вас рекомендации/подсказки? Любая помощь будет оценена.

Благодарим вас за ваше время и помощь заранее.

Cheers!

Answer 1

Для части (a) вы можете использовать бинарный поиск по высоте. Псевдокод для этого же приведен ниже:

lo = 0 
hi = n 
while(lo<hi) { 
    mid = lo +(hi-lo)/2; 
    if(galss_breaks(mid)) { 
     hi = mid-1; 
    } else { 
     lo = mid; 
    } 
} 

«lo» будет содержать максимально возможную высоту в минимально возможных испытаниях. В худшем случае потребуется выполнить log (n) шагов, тогда как ваш подход может занять N шагов в худшем случае.

В части (б),

вы можете использовать свой подход а, начиная с минимальной высоты и увеличивать высоту на 1 до тех пор, стекло разбилось. Это позволит максимально разбить 1 стакан, чтобы определить требуемую высоту.

Answer 2

Ответ на часть (с). Идея заключается в том, чтобы найти некоторое число к и применим следующую схему: Бросьте банку с высоты к:

• Если ломается, падение другой из к-1 до 1, пока мы не найдем высоту, он ломается, не более, чем k попыток.
• Если он не сломался, опустите его снова с высоты k + (k-1). Опять же, если он сломает падение, то другой из (k + (k-1) -1) до k + 1, в противном случае продолжите (k + (k-1) + (k-2)).
• Продолжайте это до тех пор, пока не найдете высоту

(конечно, если в какой-то момент вы должны прыгать на высоту больше, чем п, вы просто перейти к п).

Эта схема гарантирует, что мы будем использовать не более k попыток. Итак, теперь вопрос заключается в том, как найти минимальное k (как функцию n), для которого схема будет работать.Так как на каждом шаге мы уменьшаем на 1 наш рост высоты, должно быть выполнено следующее уравнение:
k + (k-1) + (k-2) + ... + 1> = n
В противном случае будет выполняться из "шагов до достижения n. Мы хотим найти наименьшее k, для которого выполняется неравенство. Там есть формула суммы:

1 + 2 + ... + K = K (к + 1)/2

С помощью этого мы получим уравнение:

к (к + 1)/2 = п ===>к^2 + к - 2n = 0

Решая это (и если это не интеграл взять потолок его) даст нам к. Квадратичные уравнения могут иметь два решения, но не обращая внимания на негативный вы получите:

к = (-1 + SQRT (1 + 8n))/2

Глядя на сложности, мы можем игнорировать все, кроме n, который имеет показатель 1/2 (поскольку мы берем его квадратный корень). Это на самом деле лучше, чем запрошенная сложность n для мощности 2/3.