Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.92/13: Рейтинг темы: голосов - 13, средняя оценка - 4.92
0 / 0 / 0
Регистрация: 02.08.2014
Сообщений: 90
1

Задача "Ковровая дорожка"

04.10.2014, 14:32. Показов 2474. Ответов 5
Метки нет (Все метки)

Пытался решить задачи методами что знаю(ну логически решить),но для наведения хоть на какието мысли зашёл сюда.
Итак задача(скоратил чтоб не было павла ивановича и т.д):
Мы знаем что в ковровую дорожку входит кол-во ковров 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
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
04.10.2014, 14:32
Ответы с готовыми решениями:

Даны три слова - "мама", "мыла", "раму". Задача - напечатать всевозможные варианты построения слов
Я записал код, однако эту часть надо автоматизировать, поможете? КОД: } #include &lt;iostream&gt;...

Необработанное исключение в "0x76f015de" в "контрольная 1 задача 2.exe": 0xC0000005: Нарушение прав доступа при чтении "0x334e2c64"
доброго времени суток. Необработанное исключение в &quot;0x76f015de&quot; в &quot;контрольная 1 задача 2.exe&quot;:...

В зависимости от времени года "весна", "лето", "осень", "зима" определить погоду "тепло", "жарко", "холодно", "очень холодно"
В зависимости от времени года &quot;весна&quot;, &quot;лето&quot;, &quot;осень&quot;, &quot;зима&quot; определить погоду &quot;тепло&quot;,...

Для каждой строки найти слова, которые не имеют ни одного из букв: "l", "k", "r", "s" i "j"
Задано символьные строки. Строка состоит из нескольких слов (наборов символов), которые разделяются...

5
220 / 165 / 47
Регистрация: 17.07.2012
Сообщений: 587
04.10.2014, 14:58 2
первое что приходит в голову - то динамика.

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

ну и переход -перебираем какой тип допишем в конец.
0
0 / 0 / 0
Регистрация: 02.08.2014
Сообщений: 90
04.10.2014, 16:05  [ТС] 3
Понял не совсем но проблема в том что в одной дороге должны быть ВСЕ связи что указаны и НЕ ДОЛЖНО быть не одной что там нет.А так работал над схожим способом.
0
79 / 79 / 34
Регистрация: 26.10.2011
Сообщений: 220
04.10.2014, 22:11 4
К сожалению теоретические основы подвести я не смог, так, что буду объяснять решение задачи на примерах, и еще в связи с политической обстановкой переделал коврики на 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] - матрица совместимости):
C++
1
2
3
4
5
6
7
for(int i=0; i<3; i++) 
{ 
   int sum = 0;
   for(int j=0; j<3; j++) 
     sum+=carpet_M[j]*compatibility[i][j];
   carpet_M_plus_1[i] = sum;
}
Вот такое решение, попробуй потом расскажешь, что вышло.
0
193 / 173 / 30
Регистрация: 10.07.2012
Сообщений: 800
05.10.2014, 10:24 5
динамика 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
0 / 0 / 0
Регистрация: 02.08.2014
Сообщений: 90
05.10.2014, 21:45  [ТС] 6
Спасибо товарищи!Проверю ваши способы отпишусь.

Добавлено через 52 минуты
Но просто напомнить!Если например персидский совместим с персидским и азейбарджанским то
подойдёт на пример ппа или апп НО неподойдёт ппп или апа!Это важно и это основная проблема!
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
05.10.2014, 21:45
Помогаю со студенческими работами здесь

Реализовать классы "Воин", "Пехотинец", "Винтовка", "Матрос", "Кортик" (наследование)
Разработать программу с использованием наследования классов, реализующую классы: − воин;...

Задача "замочная скважина" и "ключ" ошибка в коде
Почему-то не работает программа реализующая следующую задачу: Даны мозаичные изображения...

Создать абстрактный класс "Издание" и производные классы "Книга", "Статья", "Электронный ресурс"
1. Создать абстрактный класс Издание с методами, позволяющими вывести на экран информацию об...

Создать класс "Книга" с полями "название книги", "количество страниц", "год издания"
Создать класс Книга поля: название книги,количество страниц,год издания методы: вычислить сколько...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru