Прошу с алгоритмом к данной !

строку фибоначчи f(k) для натуральных чисел k определим так: f(1) = 'a', f(2) = 'b', f(k) = f(k - 1) + f(k - 2) при k > 2, где "+" означает конкатенацию строк. требуется найти количество вхождений строки s, состоящей из символов a и b, в строку фибоначчи f(n).

ограничения: длина s от 1 до 25, 1 < = n < = 45.

примечание. длина f(45) равна 1 134 903 170.


входные данные
в первой строке содержится число n, во второй - строка s.

выходные данные
выводится одно число - количество вхождений строки s в строку фибоначчи f(n).

Если х1,у1 - координаты одного конца 1-го отрезка, х2,у2 - координаты его второго конца, то уравнение прямой, на которой этот отрезок лежит, такое: у=у1+(у2-у1)(х-х1)/(х2-х1). для второго отрезка (х3,у3) и (х4,у4), прямая у=у3+(у4-у3)(х-х3)/(х4-х3). абсцисса точки пересечения (х,у) этих прямых находится из равенства у1+(у2-у1)(х-х1)/(х2-х1)=у3+(у4-у3)(х-х3)/(х4-х3). это х надо выразить в виде формулы до написания программы, чтобы х вычислялось в программе по этой формуле. схема программы: 1) проверка параллельности отрезков. если "да", то выход и ответ "не существует". 2) проверка выполнения двух двойных неравенств: x1 < = x < = x2, x2 < = x < = x4. если оба неравенства "истина", то ответ "существует", иначе "не существует" обратите внимание, что х1 должно быть меньше чем х2, и х3 меньше чем х4.

Там целая проще на калькуляторе, а если так то приравнивая к десятичной системе счисления, выбором остатков.. вычитание двоичных чисел. вычитать числа, будем также столбиком и общее правило тоже, что и для десятичных чисел, вычитание выполняется поразрядно и если в разряде не хватает единицы, то она занимается в старшем. решим следующий пример: 1101 - 110 = 111 первый разряд. 1 - 0 =1. записываем 1. второй разряд 0 -1. не хватает единицы. занимаем её в старшем разряде. единица из старшего разряда переходит в младший, как две единицы (потому что старший разряд представляется двойкой большей степени ) 2-1 =1. записываем 1. третий разряд. единицу этого разряда мы занимали, поэтому сейчас в разряде 0 и есть необходимость занять единицу старшего разряда. 2-1 =1. записываем 1. проверим результат в десятичной системе 1101 - 110 = 13 - 6 = 7 (111) верное равенство. еще один интересный способ выполнения вычитания связан с понятием дополнительного кода, который позволяет свести вычитание к сложению. получается число в дополнительном коде исключительно просто, берём число, заменяем нули на единицы, единицы наоборот заменяем на нули и к младшему разряду добавляем единицу. например, 10010, в дополнительном коде будет 011011. правило вычитания через дополнительный код утверждает, что вычитание можно заменить на сложение если вычитаемое заменить на число в дополнительном коде. пример: 34 - 22 = 12 запишем этот пример в двоичном виде. 100010 - 10110 = 1100 дополнительный код числа 10110 будет такой 01001 + 00001 = 01010. тогда исходный пример можно заменить сложением так 100010 + 01010 = 101100 далее необходимо отбросить одну единицу в старшем разряде. если это сделать то, получим 001100. отбросим незначащие нули и получим 1100, то есть пример решён правильно