Оптимальный алгоритм переставления коробок, естественно.3DD писал(а): Ср июл 10, 2019 2:49 pmну если силы есть и оплата почасовая, то и таскайте их по одной, хоть бабл сортом переставляя, в чем вопрос?
Тогда нужно уточнение - наличие доп пространства куда коробки временно выносить, если сортировать, скажем, quick sort - выбираем pivot, сортируем, разделяем надвое, в каждой половине выбираем свой pivot и тдmikeG писал(а): Ср июл 10, 2019 2:52 pmОптимальный алгоритм переставления коробок, естественно.
Бабл сорт будет одну и ту же коробку много раз двигать.
Доп пространства нет.3DD писал(а): Ср июл 10, 2019 2:58 pm Тогда нужно уточнение - наличие доп пространства куда коробки временно выносить, если сортировать, скажем, quick sort - выбираем pivot, сортируем, разделяем надвое, в каждой половине выбираем свой pivot и тд
Ожидается, что кандидат начнет задавать уточняющие вопросы и в итоге выйдет на EEPROM!KVA писал(а): Ср июл 10, 2019 10:21 pm Про EEPROM/FLASH надо было бы сразу сказать, а то при заданных условиях (уточненных и некоторых недосказанных) задача вообще может не иметь решения на практике.
Места дополнительного нет. Носит человек. А коробки со стиральными машинами.
Но поговорить сойдет. :)
вы случаем не в амазоне работаетеmikeG писал(а): Вт июл 09, 2019 4:47 pm Вот задачка для иллюстрации смысла разных алгоритмов.
Нужно отсортировать коробки на складе. Коробки тяжелые, носить нужно по одной вручную.
Тут есть один маленький гиморрой: за один цикл коробки могут не переставиться.M. Ridcully писал(а): Ср июл 10, 2019 5:21 pm Прежде чем искать "оптимальное" решение нужно выяснить модель (ну или cost function, которую минимизуруем), по которой эта самая оптимальность считается. Одна возможная модель - минимизируется суммарное расстояние, на которое переносятся коробки. Тогда решением будет то, что предложила Lisa выше - сначала для каждой коробки определяется её правильное конечное место. Затем берётся любая (ближайшая?) коробка, сразу переносится на своё место. При этом берётся коробка, которая занимает это место и переносится на своё правильное место. Ну и т.д. Довольно очевидно, что для этой модели решение оптимальное - каждая коробка переноситмя кратчайшим путём на своё место.
Так он может за один проход все по одной взвесить (i.e. create Set), а за второй проход расставить по весу. O(n)ALV00 писал(а): Чт июл 11, 2019 10:07 amТут есть один маленький гиморрой: за один цикл коробки могут не переставиться.
А подробней, как расставлять? O(n) это понятно, только понадобится два прохода в худшем случае.