Описание алгоритма:
Будем наращивать длину последовательности от 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, получится искомое количество. Для a=1 и b=2 также работает правильно.
Программа на Pascal:
var num00,num01,num11,mem00:integer;
a,i:byte;
begin
readln(b);
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.
Объяснение:
извени если ошебусь
:)
1) 255₁₀ = 11111111₂
2) 255₁₀ = 377₈
3) 255₁₀ = FF₁₆
4) 397₁₀ = 110001101₂
5) 397₁₀ = 615₈
6) 397₁₀ = 18D₁₆
Объяснение:
1) 255₁₀ = 11111111₂
255 / 2 = 127 + остаток 1
127 / 2 = 63 + остаток 1
63 / 2 = 31 + остаток 1
31 / 2 = 15 + остаток 1
15 / 2 = 7 + остаток 1
7 / 2 = 3 + остаток 1
3 / 2 = 1 + остаток 1
1 / 2 = 0 + остаток 1
записываем остатки снизу вверх
11111111₂ = 1 * 2⁰ + 1 * 2¹ + 1 * 2² + 1 * 2³ + 1 * 2⁴ + 1 * 2⁵ + 1 * 2⁶ + 1 * 2⁷ = 1 + 2 + 4 + 8 + 16 + 32 + 64 + 128 = 255₁₀
2) 255₁₀ = 377₈
255 / 8 = 31 + остаток 7
31 / 8 = 3 + остаток 7
3 / 8 = 0 + остаток 3
записываем остатки снизу вверх
377₈ = 7 * 8⁰ + 7 * 8¹ + 3 * 8² = 7 + 56 + 192 = 255₁₀
3) 255₁₀ = FF₁₆
255 / 16 = 15 + остаток 15
15 / 16 = 0 + остаток 15
записываем остатки снизу вверх
FF₁₆ = F * 16⁰ + F * 16¹ = 15 + 240 = 255₁₀
4) 397₁₀ = 110001101₂
397 / 2 = 198 + остаток 1
198 / 2 = 99 + остаток 0
99 / 2 = 49 + остаток 1
49 / 2 = 24 + остаток 1
24 / 2 = 12 + остаток 0
12 / 2 = 6 + остаток 0
6 / 2 = 3 + остаток 0
3 / 2 = 1 + остаток 1
1 / 2 = 0 + остаток 1
записываем остатки снизу вверх
110001101₂ = 1 * 2⁰ + 0 * 2¹ + 1 * 2² + 1 * 2³ + 0 * 2⁴ + 0 * 2⁵ + 0 * 2⁶ + 1 * 2⁷ + 1 * 2⁸ = 1 + 4 + 8 + 128 + 256 = 397₁₀
5) 397₁₀ = 615₈
397 / 8 = 49 + остаток 5
49 / 8 = 6 + остаток 1
6 / 8 = 0 + остаток 6
записываем остатки снизу вверх
615₈ = 5 * 8⁰ + 1 * 8¹ + 6 * 8² = 5 + 8 + 384 = 397₁₀
6) 397₁₀ = 18D₁₆
397 / 16 = 24 + остаток 13
24 / 16 = 1 + остаток 8
1 / 16 = 0 + остаток 1
записываем остатки снизу вверх
18D₁₆ = D * 16⁰ + 8 * 16¹ + 1 * 16² = 13 + 128 + 256 = 397₁₀
