Найти, количество строк длины n, состоящих только из указанных символов и не содержащих заданную подстроку

@mercuriy71 · Регистрация: 18.02.2017

Найдите, сколько существует строк заданной длины n, состоящих только из символов 'a', 'b' и 'c', и не содержащих подстроки "ab".

C++

Входные данные #1
0
Выходные данные #1
1
Входные данные #2
3
Выходные данные #2
21
Входные данные #3
11
Выходные данные #3
46368

Байт · 18.02.2017, 11:21

mercuriy71, Самый лобовой путь - генерировать числа от 0 до 3ⁿ-1, переводить в троичную с/с и проверять на отсутствие комбинаций 01
Можно пойти от обратного. Считать только содержащие 01.

@DemolitionMan · 18.02.2017, 11:31

Сообщение от Байт

3n-1

- по-моему тут не 1 нужно отнимать, а другое число. Т.к. могут быть и такие варианты:
aba
abb
abc

Байт · 18.02.2017, 11:34

Сообщение от DemolitionMan

по-моему тут не 1 нужно отнимать, а другое число.

Да, извиняюсь. Отнимать вообще ничего не нужно.

@DemolitionMan · 18.02.2017, 12:05

Как не нужно? А 3 комбинации "ab", те что я написал? Их же нужно исключить.

Байт · 18.02.2017, 12:16

Сообщение от DemolitionMan

А 3 комбинации "ab", те что я написал? Их же нужно исключить.

Читайте внимательнее.

Сообщение от Байт

генерировать числа от 0 до 3ⁿ-1, переводить в троичную с/с и проверять на отсутствие комбинаций 01

PS. И все-таки от 0 до 3ⁿ-1. А всего их будет 3ⁿ

Байт Диссидент 27192 / 16949 / 3745 Регистрация: 24.12.2010 Сообщений: 38,132
	18.02.2017, 11:21	2
	mercuriy71, Самый лобовой путь - генерировать числа от 0 до 3ⁿ-1, переводить в троичную с/с и проверять на отсутствие комбинаций 01 Можно пойти от обратного. Считать только содержащие 01. 0

@DemolitionMan 132 / 158 / 87 Регистрация: 06.04.2016 Сообщений: 992
	18.02.2017, 11:31	3
	Сообщение от Байт 3n-1 - по-моему тут не 1 нужно отнимать, а другое число. Т.к. могут быть и такие варианты: aba abb abc 0

Байт Диссидент 27192 / 16949 / 3745 Регистрация: 24.12.2010 Сообщений: 38,132
	18.02.2017, 11:34	4
	Сообщение от DemolitionMan по-моему тут не 1 нужно отнимать, а другое число. Да, извиняюсь. Отнимать вообще ничего не нужно. 0

@DemolitionMan 132 / 158 / 87 Регистрация: 06.04.2016 Сообщений: 992
	18.02.2017, 12:05	5
	Как не нужно? А 3 комбинации "ab", те что я написал? Их же нужно исключить. 0

Байт Диссидент 27192 / 16949 / 3745 Регистрация: 24.12.2010 Сообщений: 38,132
	18.02.2017, 12:16	6
	Сообщение от DemolitionMan А 3 комбинации "ab", те что я написал? Их же нужно исключить. Читайте внимательнее. Сообщение от Байт генерировать числа от 0 до 3ⁿ-1, переводить в троичную с/с и проверять на отсутствие комбинаций 01 PS. И все-таки от 0 до 3ⁿ-1. А всего их будет 3ⁿ 0

Опции темы