Строка Фибоначчи

@- NameError - · Регистрация: 04.12.2019

Студворк — интернет-сервис помощи студентам

Добрый день!

Сразу скажу, пытался неоднократно решить эту задачу, но проходит на 60 баллов постоянно.

Вот условие:

Строку Фибоначчи 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).

А вот моя попытка:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def fibo(n):
    f = ['A', 'B']
    for i in range(2, n + 1):
        f.append(f[i-1] + f[i-2])
    return(f)
  
thestring = int(input())
baran = input()
string = fibo(thestring)
pos_el = string[-1]
cou = pos_el.count(baran)
if thestring == 1 and baran == 'A':
    print(1)
elif thestring == 1 and baran == 'B':
    print(0)
else:
    print(cou)

Прошу помогите решить, хотя бы и с нуля, но на питоне.
Прошу не кидать сюда "типо" решенные темы на других языках, уже все их видел, это, внимание, ДРУГАЯ задача!
Всем кто прочел спасибо!

Рыжий Лис · 29.12.2019, 17:44

Пример входных и выходных данных покажи.

@udeep · 29.12.2019, 18:06

- NameError -,
Наверное, следует исходить из наличия в строке "fibo" периода Пизано.

@Catstail · 29.12.2019, 20:41

Вот так можно сгенерировать эту строку:

Python
1
2
3
4
5
6
7
8
9
10
def fib_string(n):
    c="B"
    p="A"
    r=""
    for i in range(1,n+1):
        r+=p+c
        c,p=c+p,c
    return r    
 
print(fib_string(10))

Строка при n=10

Кликните здесь для просмотра всего текста

ABBBABABABBABBABBABABBABABBABABBABBABABB ABBABABBABBABABBABABBABBABABBABABBABBABA BBABABBABBABABBABBABABBABABBABBABABBABBA BABBABABBABBABABBABBABABBABABBABBABABBAB ABBABBABABBABBABABBABABBABBABABBABABBABB ABABBABBABABBABABBABBABABBABABBABBABABBA BBABABBABABBABBABABBABBABABBABABBABBABAB BABABBABBABABBABBABABBABABBABBABABBABBAB ABBABABBABBABABBABABBABBABABBABBABABBABA BBABBABABBABBA

И сдается мне, что здесь нужно применить динамическое программирование - грубая сила не поможет.

@- NameError - · 29.12.2019, 21:26 **[ТС]**

Спасибо за совет!

Добавлено через 1 минуту
Да, конечно:

входные данные
1
A
выходные данные
1

входные данные
1
B
выходные данные
0

входные данные
1
BBABBABABBABABBABBABABBAB
выходные данные
0

Новые блоги и статьи Все статьи Все блоги /
Автозаполнение реквизита при выборе элемента справочника Maks 27.03.2026 Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .	Сумматор с применением элементов трёх состояний. Hrethgir 26.03.2026 Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .	Автозаполнение реквизитов при создании документа Maks 26.03.2026 Программный код из решения ниже размещается в модуле объекта документа, в процедуре "ПриСозданииНаСервере". Алгоритм проверки заполнения реализован для исключения перезаписи значения реквизита,. . .	Команды формы и диалоговое окно Maks 26.03.2026 1. Команда формы "ЗаполнитьЗапчасти". Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. В качестве источника данных. . .
Кому нужен AOT? DevAlt 26.03.2026 Решил сделать простой ланчер Написал заготовку: dotnet new console --aot -o UrlHandler var items = args. Split(":"); var tag = items; var id = items; var executable = args;. . .	Отправка уведомления на почту при создании или изменении элементов справочника Maks 24.03.2026 Программная отправка письма электронной почты на примере типового справочника "Склады" в конфигурации БП3. Перед реализацией необходимо выполнить настройку системной учетной записи электронной. . .	модель ЗдравоСохранения 5. Меньше увольнений- больше дохода! anaschu 24.03.2026 Теперь система здравосохранения уменьшает количество увольнений. 9TO2GP2bpX4 a42b81fb172ffc12ca589c7898261ccb/ https:/ / rutube. ru/ video/ a42b81fb172ffc12ca589c7898261ccb/ Слева синяя линия -. . .	Midnight Chicago Blues kumehtar 24.03.2026 Такой Midnight Chicago Blues, знаешь?. . Когда вечерние улицы становятся ночными, а ты не можешь уснуть. Ты идёшь в любимый старый бар, и бармен наливает тебе виски. Ты смотришь на пролетающие. . .

Рыжий Лис Просто Лис 5973 / 3735 / 1099 Регистрация: 17.05.2012 Сообщений: 10,791 Записей в блоге: 9
	29.12.2019, 17:44
	Пример входных и выходных данных покажи. 0

@udeep 55 / 40 / 18 Регистрация: 16.12.2019 Сообщений: 149
	29.12.2019, 18:06
	- NameError -, Наверное, следует исходить из наличия в строке "fibo" периода Пизано. 0

@- NameError - 0 / 0 / 0 Регистрация: 04.12.2019 Сообщений: 11
	29.12.2019, 21:26 [ТС]
	Спасибо за совет! Добавлено через 1 минуту Да, конечно: входные данные 1 A выходные данные 1 входные данные 1 B выходные данные 0 входные данные 1 BBABBABABBABABBABBABABBAB выходные данные 0 0

Опции темы

Строка Фибоначчи

Решение