@Ed_Os

Пытался решить задачи методами что знаю(ну логически решить),но для наведения хоть на какието мысли зашёл сюда.
Итак задача(скоратил чтоб не было павла ивановича и т.д):
Мы знаем что в ковровую дорожку входит кол-во ковров N и имеем таблицу совместимости ковров:
п-персидский т-турецкий а-азейбарджанский
(таблица пример)
п т а
п 1 1 1
т 1 0 1
а 1 1 0
Где если на пересечении ковров стоит 1 значит ковры встречаются в дорожке рядом а 0 нет.
(пример такой дорожки ппптаппапт)
Сколько кол-во дорожек состоящих из кол-ва ковров N и подходищих по таблице совместимости может быть?

Входные данные
число N(1<=N<=100)
потом 3 строки по 3 символа в каждой(эта таблица)

Выходные
число таких ковровых дорожек

2 примера:
1
Ввод вывод
10 __ 4596
111
101
110

2
Ввод вывод
3 __ 0
111
111
111

Надеюсь разьеснил понятно но если что надо я дораскажу.Прошу помочь наведением на способ,логическим решением,можно даже кодом на это необязательно.Всем помогавшим конечно спасибо и +)

__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь

0

@SlavaSSU

первое что приходит в голову - то динамика.

dp[i][mask][last] = количество дорожек длиной i, mask - множество уже полученных связей, last = тип последнего ковра.

ну и переход -перебираем какой тип допишем в конец.

0

@Ed_Os

Понял не совсем но проблема в том что в одной дороге должны быть ВСЕ связи что указаны и НЕ ДОЛЖНО быть не одной что там нет.А так работал над схожим способом.

0

@sergestus

К сожалению теоретические основы подвести я не смог, так, что буду объяснять решение задачи на примерах, и еще в связи с политической обстановкой переделал коврики на RUS - российские USA - американские CHN - китайские (ясно российские, что и американские не совместимы...) - так понятнее

Решение в общем: применим к задаче метод математической индукции, сведя ее к итеративному процессу - в нашем случае итерация M это количество дорожек состоящих из количества ковров M, соответственно следующая итерация M+1, вычисляется некоторым образом из итерации М и так далее до N.

Детальное решение: создать массив carpet размерность которого будет равна количеству типов ковриков (в нашем случае 3). В данном массиве хранятся количество дорожек, которые, оканчиваются ковриком данного типа на итерации M. Общее количество, тогда можно будет получить простой суммой на последней итерации.

Решение и пример:
Понятно, что на итерации 1 особых вариантов нет:
carpet[RUS] = 1;
carpet[USA] = 1;
carpet[CHN] = 1;
Их не надо вычислять просто зададим как начальные значения массива.
Переходим к итерации 2:
Российские коврики стыкуются с сами с собой и с китайскими, значит
carpet[RUS] = 2
Американские коврики стыкуются с сами с собой и с китайскими, значит
carpet[USA] = 2
Ну а хитрые китайцы стыкуются со всеми, значит
carpet[CHN] = 3
Ну а теперь попробуем посчитать итерацию M+1 (carpet_M и carpet_M_plus_1 - искомый массив на итерации М и М+1
соответственно, compatibility[3][3] - матрица совместимости):
Вот такое решение, попробуй потом расскажешь, что вышло.

0

@salam

динамика dp[len][carpet] - количество допустимых дорожек из len ковров, в которых последний ковер типа carpet.
переход dp[len+1][carpet] = dp[len][0] * A[carpet][0] + dp[len][1] * A[carpet][1] + dp[len][2] * A[carpet][2], где
A - матрица совместимости ковров.

0

@Ed_Os

Спасибо товарищи!Проверю ваши способы отпишусь.

Добавлено через 52 минуты
Но просто напомнить!Если например персидский совместим с персидским и азейбарджанским то
подойдёт на пример ппа или апп НО неподойдёт ппп или апа!Это важно и это основная проблема!

0