Форум » Динамическое программирование » 23 задание № 136 » Ответить
23 задание № 136
cool.chastikov: Здравствуйте, решение, которое представлено в архиве (рекурсией) довольно понятно, но я хочу добить задачу своим методом, а именно создать массив чисел от нуля до 31 (включительно) и проходясь по всему массиву со второго элемента добавлять к нему сумму ходов из предыдущей ячейки и от ячейки, что на разряд меньше. Вот моя программа, выдаёт совсем не ответ 82, подскажите пожалуйста в чём может быть ошибка. [pre2] def count(n): counter = 0 while (n > 0): n //= 2 counter += 1 return counter a = [ 0 ] * 32 a[ 1 ] = 1 for i in range(2, 32): a[ i ] += a[ i - 1 ] a[ i ] += a[ i - 2**(count(i) - 1) ] print(a[ 31 ]) [/pre2] Заранее спасибо за ответ)
Ответов - 3
cool.chastikov: Я брал лищние команды, когда убирал 1 из разряда, вот пример: в число 1011 мы не сможем попасть, добавив еденицу слева. Так как число должно быть 011, но у нас оно преобразуется до 11и из него попасть в 1011 не получится, так как надо добавить ещё и 0. Следовательно нужно проверять второй разярд слева на то, чтобы он не был еденицей! Вот готовая программа, которая решает эту задачу: [pre2] def count(n): counter = 0 while n > 0: n //= 2 counter += 1 return counter def is_second_not_null(n): second_digit = -1 while n > 0: if n >= 2: second_digit = n % 2 n //= 2 if second_digit == 1: return True return False a = [ 0 ] * 32 a[ 1 ] = 1 for i in range(2, 32): a[ i ] += a[ i - 1 ] if is_second_not_null(i): a[ i ] += a[ i - 2 ** (count(i) - 1) ] print(a[ 31 ]) [/pre2]
dim18: cool.chastikov пишет: Здравствуйте, решение, которое представлено в архиве (рекурсией) довольно понятно Здравствуйте! Подскажите, пож., где в архиве находится решение этой задачи с пом. рекурсии?
Поляков: dim18 пишет: где в архиве находится решение этой задачи с пом. рекурсии? Здесь.
полная версия страницы