|
|
|
|
|
|
|
|
| |
|
|
|
|
|
|
|
| Я отношусь к Роджеру с большой симпатией и всегда рад его появлению. Тому что он пишет - не всегда :-) |
|
|
| номер сообщения: 8-484-145594 |
|
|
|
|
Доказывать я не мастак, а вот как именно я буду выбирать пирожные, могу рассказать.
Вот процедура, которую я буду повторять 20 раз:
1. Для каждого из ещё не выбранных сортов я посчитаю, по скольким ящикам он разложен.
2. Выберу тот сорт, который разложен по наименьшему количеству ящиков.
3. Возьму пирожное этого сорта из того ящика, в котором пирожных этого сорта больше всего. |
|
|
| номер сообщения: 8-484-145595 |
|
|
|
|
| Michael_S: Вот процедура, которую я буду повторять 20 раз ... |
Сьесть то он сьесть ... |
|
|
| номер сообщения: 8-484-145596 |
|
|
|
|
И действительно 
Не работают мои эвристики. И даже чуть более хитрые эвристики отказываются работать.
В то, что задача NP-complete верить пока не хочется. |
|
|
| номер сообщения: 8-484-145601 |
|
|
|
|
Слова Вы какие учёные знаете! Но задача то совсем простая, ну, для 5 класса максимум :-)
Решение проведём индукцией по числу к пирожных каждого сорта(одинаковое для всех сортов).
Для к = 2 решение просто. https://niktoinikak.livejournal.com/1573785.html Пусть теперь к > 2 и для всех меньших чем к утверждение доказано.
Возьмём какое-нибудь размещение, для которого утверждение верно, и вытащим соответствующую "нить" (т е по одному пирожному из каждого ящика при том все разных сортов). Тогда для получившегося после этого размещения верно предположение индукции, и, следовательно, можем вытащить ещё одну нить, после этого эщё одну - всего к нитей - при том больше 2-х.
Теперь поменяем местами 2 любых пирожных из разных ящиков. Поскольку при этом мы заденем 1 или 2 нити - останется нетронутая нить. Т е свойсво "можно вытянуть нить" при таком перемещении не нарушится.
Осталось осознать, что любое размещение м б такими перемещениями получено из любого другого.
Задача решена.
Да, получилось ровно 10 строчек - хотя я нисколько не экономил :-). |
|
|
| номер сообщения: 8-484-145602 |
|
|
|
|
Может, в 5-м классе я бы и понял. И даже на втором курсе. Но сейчас так быстро не соображаю.
А по поводу учёных слов, так я в этом момент решал другую задачу. То было не доказательство того, что решение существует, а попытка найти это существующее решение не перебирая 2432902008176640000 вариантов. |
|
|
| номер сообщения: 8-484-145605 |
|
|
|
|
Другое изложение:
1. Существует размещение пирожных по ящикам, при котором можно вытащить по одному пирожному из каждого ящика и все они разных сортов. Это очевидно. Такой выбор назовём "нитью".
2. Существует операция, изменяющая расположение пирожных в ящиках, при которой свойство "можно выбрать нить" сохраняется(описание операции - отдельно, тут это неважно).
3. Посредством нескольких таких операций можно получить из любого первоначально выбранного расположения любое другое. Т к на каждом шагу свойство "можно выбрать нить" сохраняется и существует раcпределение для которого оно выполняется - оно выполняется для любого другого.
4. Эта операция - переложение любых 2-х пирожных. Замечание: индукция используется только в п 2 - что данная операция сохраняет нужное свойство. |
|
|
| номер сообщения: 8-484-145606 |
|
|
|
|
| Пока понял только, что если удаётся доказать, что всегда существует одно решение, то из этого следует, что всегда существует не менее 10 различных решений. |
|
|
| номер сообщения: 8-484-145607 |
|
|
|
|
Вроде понял.
И вроде понял, как использовать это доказательство, чтобы построить алгоритм поиска решения, в котором задача поиска вида (20,10) сводится к примерно 200 поискам вида (20,2). |
|
|
| номер сообщения: 8-484-145608 |
|
|
|
|
Почитал в Вики об Абхазии.
История ... Обычная. Война всех против всех. Большинство абхазов(больше 60%) в конце 19 века переселилось в Турцию, и большинство населения стали грузины, в советское время - преобладающее большинство, так что Грузия правомерно рассматривала Абхазию как свою часть. Но видимо почти все грузины бежали, так что теперь это неверно.
О Господи. Никакие территории - кроме родного пятачка - не стоят ни одной жизни.
О люди, жалкий род, достойный слёз и смеха.
И с отвращением читая жизнь мою ... |
|
|
|
| номер сообщения: 8-484-145630 |
|
|
| |
|
|
|
|
|
|
|
| Copyright chesspro.ru 2004-2026 гг. |
|
|
|
