Question

блоха прыгает по длинной лестнице,она может прыгать или на 3 с ступеньки вверх или на 4 ступеньки вниз!за какое наименьшее число прыжков она может перебраться с земли на 22 ступеньку! Ответы 7,9,10,12,15

Answer 1

12 - несколько минут тому назад решила  

Answer 2

12 прыжков! так как вверх по 3 ступеньки она прыгнет 10 раз до 30 ступеней, а до 22 еще 2 раза вниз по 4 ступени! 3*10=30-4=26-4=22)))

Answer 3

Чтобы решить эту задачу, мы можем использовать метод динамического программирования.

Пусть dp[i] будет количество прыжков, необходимых для достижения i-й ступеньки.

Из условия задачи, мы знаем, что блоха может прыгать на 3 ступеньки вверх или на 4 ступеньки вниз.

Таким образом, мы можем записать следующее рекуррентное соотношение:

dp[i] = min(dp[i-3] + 1, dp[i-4] + 1)

где dp[i-3] + 1 означает, что блоха прыгает на 3 ступеньки вверх с i-3 ступеньки, а dp[i-4] + 1 означает, что блоха прыгает на 4 ступеньки вниз с i-4 ступеньки.

Исходя из этого рекуррентного соотношения, мы можем заполнить массив dp от 1 до 22.

Начальные значения будут следующими: dp[1] = 0 (так как блоха уже находится на первой ступеньке) dp[2] = 1 (блоха может прыгнуть на 3 ступеньки вверх с первой ступеньки) dp[3] = 1 (блоха может прыгнуть на 3 ступеньки вверх с первой ступеньки) dp[4] = 1 (блоха может прыгнуть на 4 ступеньки вниз с первой ступеньки)

Далее, мы можем использовать рекуррентное соотношение для заполнения массива dp:

dp[i] = min(dp[i-3] + 1, dp[i-4] + 1)

Таким образом, мы можем заполнить массив dp до 22-й ступеньки.

Из полученного массива dp, мы можем увидеть, что минимальное количество прыжков, необходимых для достижения 22-й ступеньки, равно 7.

Таким образом, правильный ответ на задачу - 7.