М
Молодежь
К
Компьютеры-и-электроника
Д
Дом-и-сад
С
Стиль-и-уход-за-собой
П
Праздники-и-традиции
Т
Транспорт
П
Путешествия
С
Семейная-жизнь
Ф
Философия-и-религия
Б
Без категории
М
Мир-работы
Х
Хобби-и-рукоделие
И
Искусство-и-развлечения
В
Взаимоотношения
З
Здоровье
К
Кулинария-и-гостеприимство
Ф
Финансы-и-бизнес
П
Питомцы-и-животные
О
Образование
О
Образование-и-коммуникации
ZKRMT
ZKRMT
02.05.2023 02:30 •  Информатика

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

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

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

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

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

👇
Ответ:
muratov20011
muratov20011
02.05.2023

Описание алгоритма:

Будем наращивать длину последовательности от 0 знаков до N. Пусть после какого-то количества шагов у нас выписаны все последовательности длины А и мы хотим узнать количество подходящих последовательностей длины А+1. Распределим все последовательности на три группы(так как предыдущие символы нас не волнуют, то любые последовательности одной группы для нас равнозначны):

1) Заканчиваются на 0.

2) Ровно на одну единицу

3) Ровно на две единицы.

Из каждой последовательности группы 1 приписыванием нуля или единицы мы можем получить одну последовательность группы 1 и одну - группы 2. Неважно, какие именно, но они не перекрываются, т.к. предыдущие символы различны, хоть мы их и не учитываем. Точно так же из второй группы мы получаем одну последовательность группы 3 и одну группы 1, а из группы 3 - только группу 1. Таким образом, если количества последовательностей длины А по группам были (x, y, z), то для длины А+1 такое распределение будет (x+y+z, x, y). Если взять для длины 0 тройку (0, 0, 1) и просчитать тройки от 1 до N, получится искомое количество. Для N=1 и N=2 также работает правильно.

Программа на Pascal:

var num00,num01,num11,mem00:integer;

   n,i:byte;

begin

readln(n);

 num00:=1;

 for i:=1 to n do begin

   mem00:=num11;

   num11:=num01;

   num01:=num00;

   num00:=num01+num11+mem00;

 end;

writeln(num11+num01+num00);

end.

4,5(34 оценок)
Открыть все ответы
Ответ:
КурогаБич
КурогаБич
02.05.2023
1) 1024 байт =1024 байт
1024 байт > 1000 байт
800 байт < 1024 байт
400 бит = 400 бит
8192 байта < 1024 байта
2) 64 бита=64*8 байт=512 байт
3) 64=2^6?   i=6 бит
4) 40 байт
5)11 Кб=11*1024*8 бит
11*1024*8=11264*i     i=(11*1024*8)/11264=8 бит
N=2^8=256
6) 32=2^5? 
i=5
7) N=16   i=4     N=256   i=8     
8/4=2 (в 2 раза)
8) N=16   i=4   k=50   
I=50*4=200 бит
9) N=256   i=8   k=30*70*5   
I=30*70*5*8=84000 бит
10) 1 Мб=1024*1024*8 бит
1/512 Мб=(1024*1024*8)/512=1024*16 бит
1024*16=2048*i        i=(1024*16)/2048=8 бит
N=2^i     
2^8=256
11) N=256   i=8   k=160*192
I=160*192*8 бит
I=(160*192*8)/(1024*8)=30 Кб
4,5(87 оценок)
Ответ:
evaalmazova
evaalmazova
02.05.2023
1) 1024 байт =1024 байт
1024 байт > 1000 байт
800 байт < 1024 байт
400 бит = 400 бит
8192 байта < 1024 байта
2) 64 бита=64*8 байт=512 байт
3) 64=2^6?   i=6 бит
4) 40 байт
5)11 Кб=11*1024*8 бит
11*1024*8=11264*i     i=(11*1024*8)/11264=8 бит
N=2^8=256
6) 32=2^5? 
i=5
7) N=16   i=4     N=256   i=8     
8/4=2 (в 2 раза)
8) N=16   i=4   k=50   
I=50*4=200 бит
9) N=256   i=8   k=30*70*5   
I=30*70*5*8=84000 бит
10) 1 Мб=1024*1024*8 бит
1/512 Мб=(1024*1024*8)/512=1024*16 бит
1024*16=2048*i        i=(1024*16)/2048=8 бит
N=2^i     
2^8=256
11) N=256   i=8   k=160*192
I=160*192*8 бит
I=(160*192*8)/(1024*8)=30 Кб
4,7(84 оценок)
Новые ответы от MOGZ: Информатика
logo
Вход Регистрация
Что ты хочешь узнать?
Спроси Mozg
Открыть лучший ответ