Delphi (Lazarus). Определить количество всех возможных вариантов обувания 80 ног - Помощь студентам

Ovenvan · 09.06.2015, 20:01

Добрый день. Дана такая задача (текста задания нету, пересказываю словесно): у сороконожки 40 левых ножек и 40 правых ножек. В начале она может надеть тапочек только на первую левую ножку, затем либо на эту же правую ножку, либо на любую другую левую и т.д. (правая обувается, только если обута эта же левая). Нужно определить количество всех возможных вариантов обувания 80 ног.
Подкиньте, пожалуйста, хотя бы идейку решения. Что-то совсем не выходит.

Задача на динамическое программирование.

Ovenvan · 13.06.2015, 18:20

Накидал небольшую схему в Excel. Слева 2-ух ножка с пронумерованными ножками. Справа уже 3-х ножка. Ниже записал возможные последовательности обувания (в правой таблице последняя строка неправильная, нечаянно скопировал не то). Алгоритм понятнее что-то не стал.

Аватар · 13.06.2015, 19:13

Цитата:

либо на эту же правую ножку, либо на любую другую левую

Решение согласно условия 39!. Почему - выделил жирным строку условия, из которой следует - после обувания любой левой обязательно обувание этой же правой. Либо на другую левую не катит - тогда пропущенная правая ни когда не будет обута. Поскольку это сильно просто вопрос к ТС - В условии должно быть не на эту же правую ножку, а на любую необутую правую, соответствующая левая для которой уже обута

Ovenvan · 13.06.2015, 21:52

Не особо понял, почему именно 39! ? А если уменьшить задачу до 4 ног, то получится 3! ? Но 3! = 6, а всего 3 комбинации. Не могли бы вы поподробнее объяснить принцип решения?

Аватар · 13.06.2015, 22:08

1-ый ход - 1-ая левая
2-ой ход - 1-ая правая (по другому не моги согласно условия)
3-ий ход - одна из 3 оставшихся левых
4-ой ход - соответствующая правая (по другому не моги согласно условия)
5-ий ход - одна из 2 оставшихся левых
6-ой ход - соответствующая правая (по другому не моги согласно условия)
7-ий ход - последняя левая
8-ой ход - последняя правая

Итого вариантов 3*2=6=3!

Это для восьми ног

Для 4 - единственное решение - 1!

Ovenvan · 13.06.2015, 22:14

Либо я плохо передал смысл задачи, либо она некая классическая (и я всё равно не прав)? Так как на втором ходу мы можем обуть любую другую левую, не обязательно правую, но можем и правую.

Poma][a · 13.06.2015, 22:20

эм..
2^80, не?

Цитата:

а всего 3 комбинации

Откуда?

00 <- левые ноги (1 - обули, 0 - нет)
00 <- правые ноги

Теперь складываем все в одному строку
0000

Последний варинт
1111
Теперь кол-во чисел между 0 и 15? Таких 16. Где я наврал?

Аватар · 13.06.2015, 22:20

Цитата:

Так как на втором ходу мы можем обуть любую другую левую, не обязательно правую, но можем и правую.

Читай своё условие - если на втором обуем любую левую, то первую правую не обуем ни когда. Поскольку черными буквами на белом фоне написано - на эту же правую ножку. Убери эту фразу и вместо неё - на любую необутую правую, соответствующая левая для которой уже обута. Тогда для 4-х ножек и будет 3, а не 1

Цитата:

Где я наврал?

Л1П1Л2П2
Л1Л2П1П2
Л1Л2П2П1

Poma][a · 13.06.2015, 22:23

Куплю перечисление этих трех вариантов. Дорого

Цитата:

Л1П1Л2П2
Л1Л2П1П2
Л1Л2П2П1

О! Данке

Ovenvan · 13.06.2015, 22:33

Я чего-то запутался. По вашему решению сколько комбинаций обувания n-ножки с 2 левыми и 2 правыми ножками?

09.06.2015, 20:01	#1
Ovenvan Пользователь Регистрация: 09.06.2015 Сообщений: 21	Добрый день. Дана такая задача (текста задания нету, пересказываю словесно): у сороконожки 40 левых ножек и 40 правых ножек. В начале она может надеть тапочек только на первую левую ножку, затем либо на эту же правую ножку, либо на любую другую левую и т.д. (правая обувается, только если обута эта же левая). Нужно определить количество всех возможных вариантов обувания 80 ног. Подкиньте, пожалуйста, хотя бы идейку решения. Что-то совсем не выходит. Задача на динамическое программирование. Последний раз редактировалось Аватар; 10.06.2015 в 18:47.

13.06.2015, 21:52	#4
Ovenvan Пользователь Регистрация: 09.06.2015 Сообщений: 21	Не особо понял, почему именно 39! ? А если уменьшить задачу до 4 ног, то получится 3! ? Но 3! = 6, а всего 3 комбинации. Не могли бы вы поподробнее объяснить принцип решения? Последний раз редактировалось Ovenvan; 13.06.2015 в 21:56.

13.06.2015, 22:08	#5
Аватар Старожил Регистрация: 17.11.2010 Сообщений: 18,922	1-ый ход - 1-ая левая 2-ой ход - 1-ая правая (по другому не моги согласно условия) 3-ий ход - одна из 3 оставшихся левых 4-ой ход - соответствующая правая (по другому не моги согласно условия) 5-ий ход - одна из 2 оставшихся левых 6-ой ход - соответствующая правая (по другому не моги согласно условия) 7-ий ход - последняя левая 8-ой ход - последняя правая Итого вариантов 32=6=3! Это для восьми ног Для 4 - единственное решение - 1! Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию Последний раз редактировалось Аватар; 13.06.2015 в 22:12.*

Похожие темы
Тема	Автор	Раздел	Ответов	Последнее сообщение
Определить количество всех возможных способов укладки паркета	Cat_from_Napoli	Помощь студентам	0	16.04.2015 08:26
Перебор всех возможных вариантов заполнения матрицы 0 или 1 для дальнейшего использования.	Don Barochelli	Помощь студентам	0	16.12.2011 21:29
Генерация всех возможных вариантов	NanaTich	Помощь студентам	6	23.05.2011 07:00
Перебор всех возможных вариантов	phenix	Помощь студентам	3	03.12.2010 21:29
Перебор всех возможных вариантов	[MI_nor]	Общие вопросы C/C++	9	01.04.2009 21:17

13.06.2015, 22:14	#6
Ovenvan Пользователь Регистрация: 09.06.2015 Сообщений: 21	Либо я плохо передал смысл задачи, либо она некая классическая (и я всё равно не прав)? Так как на втором ходу мы можем обуть любую другую левую, не обязательно правую, но можем и правую.

13.06.2015, 22:33	#10
Ovenvan Пользователь Регистрация: 09.06.2015 Сообщений: 21	Я чего-то запутался. По вашему решению сколько комбинаций обувания n-ножки с 2 левыми и 2 правыми ножками?