Задача на проверку символьных цепочек, с использованием букв А и Б.

Эту задачу я нашёл в одной из школьных олимпиад на просторах Интернет. От детей 7-8 классов не требовалось составления компьютерной программы. Правильным ответом было определение количества число цепочек. Предлагаю своё, частное решение данной задачи на языке программирования Паскаль. Думаю, что будет несложно перевести её на другой ЯП, к примеру Питон.

Условие задачи

Для составления цепочек длины k разрешается использовать буквы А и Б, причём одна из букв (А или Б) должна стоять в цепочке три или более раз.
Сколько всего существует таких цепочек длины k=4? (Перечислять все такие цепочки не надо - только определить их количество).

Подготовка

Для начала проверим все возможные варианты, которые могут получиться в результате сочетания этих символов. Их не так много, потому что длина всей цепочки символов составляет 4 символа. Учитываем и те варианты, когда цепочка состоит из одного из приведённых символов. Начинаем заполнять с символа a, а последняя цепочка будет состоять только из символа b.

aaaa
aaab
aaba
aabb
abaa
abab
abba
abbb
baaa
baab
baba
babb
bbaa
bbab
bbba
bbbb

Итак, решением задачи являются следующие варианты:

aaaa
aaab
aaba
abaa
abbb
baaa
babb
bbab
bbba
bbbb

При нехитром подсчёте их количество равно 10. Это число и будем использовать в качестве проверки нашей программы.

Обратим внимание на условие проверки наших цепочек. Количество символов a или b должно быть равно или быть больше трёх.

В итоге программа будет состоять из двух процедур. Первая процедура заполняет массив из строк, представляющих собой цепочки символов. Вторая процедура будет заниматься проверкой

Готовый код программы

Program chains_ab;

const k=16;

var

i:integer; 

count_chains_ab:integer;

massiv:array[1..k] of string;

 

//Процедура заполнения массива

Procedure fulling(); 

  Var A,B,C,D:char;

  i:integer;

  begin

  Writeln(Варианты, из которых будем выбирать:);

  Writeln();

    i:=1;

      for A:=a to b do

        for B:=a to b do

         for C:=a to b do

          for D:=a to b do

            begin

               massiv[i]:=A+B+C+D;

               Writeln(massiv[i]);

               inc(i);

            end; 

  end; 

 

//Процедура подсчёта цепочек

Procedure podschet(); 

var j,count_a,count_b:integer;

str:string;

begin

for j:=1 to k do 

  begin    

    count_a:=0;   

    count_b:=0; 

    i:=length(massiv[j]);

    str:=massiv[j];

              while i>0 do 

                begin

                  if str[i] = a then count_a:=count_a+1;

                  if str[i] = b then count_b:=count_b+1;

                  i:=i-1;

                end;

      // проверяем количество цепочек

    if  (count_a>=3) or (count_b>=3) then inc(count_chains_ab);

  end;

end;

 

begin

  count_chains_ab:=0;

  fulling();

  Writeln();

  Writeln(--------------);

  podschet();

  writeln(Количество цепочек = , count_chains_ab);   

end.

Результат выполнения программы

Варианты, из которых будем выбирать:

aaaa
aaab
aaba
aabb
abaa
abab
abba
abbb
baaa
baab
baba
babb
bbaa
bbab
bbba
bbbb

--------------
Количество цепочек = 10

Ответ, который даёт программа на Паскале совпадает с тем, который был найден методом простого перебора. Задача решена.