Без трёх единиц

@fdgvds · Регистрация: 12.05.2021

Студворк — интернет-сервис помощи студентам

Определите количество последовательностей из нулей и единиц длины N (длина — это общее количество нулей и единиц), в которых никакие три единицы не стоят рядом.

Входные данные

Дано натуральное число N, не превосходящее 40.

Выходные данные

Выведите количество искомых последовательностей. Гарантируется, что ответ не превосходит 2³¹−1.

@КулХацкеръ · 12.05.2021, 09:10

На питоне, решение до N = 40 включительно.

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
            8646064
        15902591 4700770
    29249425      2555757
  53798080       1389537     2
 98950096       755476       4
181997601      410744        7
334745777      223317       13
615693474     121415        24
1132436852     66012       44
2082876103     35890       81
3831006429     19513      149
7046319384     10609      274
12960201916     5768     504
23837527729      3136  927
43844049029         1705
|         |
\         /
 \ d   b /
  \     /
   \___/

@iSmokeJC · 12.05.2021, 09:20

Не по теме:

КулХацкеръ, кросавчег!!

@Damenikx · 12.05.2021, 10:02

Не по теме:

КулХацкеръ, сохраню, пожалуй))

@fdgvds · 14.05.2021, 04:49 **[ТС]**

Python
1
2
3
4
5
6
7
8
9
10
n = int(input())
f = [0] * 40
f[1] = 2; f[2] = 4; f[3] = 7
 
i = 4
while i <= n:
  f[i] = (f[i-1] + f[i-2] + f[i-3])
  i+=1
 
print(f[n])

Вот правильный код, спасибо КулХацкеръ

@КулХацкеръ · 14.05.2021, 05:12

На здоровье! Ты большой молодец, что всё-таки сам написал программу.

@Ципихович Эндрю · 14.05.2021, 08:29

Сообщение от КулХацкеръ

Ты большой молодец, что всё-таки сам написал программу

ещё бы избавился от цикла вайл..........

@Kirqwerty · 21.06.2025, 17:38

Мой первый пост (не судите строго)

:
Решил через трехмерный массив сделать:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
n = int(input())
if n>2:
    dp = [[[0 for i in range(0,2)] for j in range(0,2)] for i in range(n+1)]
    dp[2][0][0]=1
    dp[2][1][0]=1
    dp[2][0][1]=1
    dp[2][1][1]=1
    for i in range(3,n+1):
        dp[i][0][0]=dp[i-1][0][0]+dp[i-1][1][0]
        dp[i][0][1]=dp[i-1][0][0]+dp[i-1][1][0]
        dp[i][1][0]=dp[i-1][0][1]+dp[i-1][1][1]
        dp[i][1][1]=dp[i-1][0][1]
    print(dp[n][0][0]+dp[n][0][1]+dp[n][1][0]+dp[n][1][1])
elif n==1:
    print(2)
else:
    print(4)

Новые блоги и статьи Все статьи Все блоги /
Загрузка PNG-файла с альфа-каналом с помощью библиотеки SDL3_image на Android 8Observer8 27.01.2026 Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .	влияние грибов на сукцессию anaschu 26.01.2026 Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .	Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .	Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .
Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .	Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly 8Observer8 24.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	моя боль iceja 24.01.2026 Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .	Модель сукцессии микоризы anaschu 24.01.2026 Решили писать научную статью с неким РОманом

@fdgvds 5 / 5 / 0 Регистрация: 12.05.2021 Сообщений: 4

	Без трёх единиц 12.05.2021, 07:38. Показов 55418. Ответов 7 Метки нет (Все метки) Определите количество последовательностей из нулей и единиц длины N (длина — это общее количество нулей и единиц), в которых никакие три единицы не стоят рядом. Входные данные Дано натуральное число N, не превосходящее 40. Выходные данные Выведите количество искомых последовательностей. Гарантируется, что ответ не превосходит 2³¹−1. Миниатюры 0

@iSmokeJC 19530 / 11067 / 2931 Регистрация: 21.10.2017 Сообщений: 23,294
	12.05.2021, 09:20
	Не по теме: КулХацкеръ, кросавчег!! 0

@Damenikx
	12.05.2021, 10:02
	Не по теме: КулХацкеръ, сохраню, пожалуй)) 0

@КулХацкеръ 710 / 356 / 104 Регистрация: 09.02.2018 Сообщений: 805
	14.05.2021, 05:12
	На здоровье! Ты большой молодец, что всё-таки сам написал программу. 1

Без трёх единиц

Решение