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

@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)

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer 8Observer8 08.02.2026 Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .	SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств 8Observer8 07.02.2026 Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .	SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .
SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .

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

	Без трёх единиц 12.05.2021, 07:38. Показов 55524. Ответов 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

Опции темы

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

Решение