Сообщение Re[7]: Золотые слитки Гериона от 07.02.2016 23:21
Изменено 07.02.2016 23:24 Буравчик
Здравствуйте, Кодт, Вы писали:
К>А покажи свою программу, что ли.
Да мне не жалко. Но как всегда запутано все, сделано наспех. Добавил комментариев.
У нас даны взвешивания. Пытаемся найти такие веса слитков, которые проходят эти взвешивания и при этом слиток 1кг будет иметь другой вес. Проверяются все перестановки весов слитков (11! вариантов). Выводится "ок" или контрпример — как надо поменять веса.
К>А покажи свою программу, что ли.
Да мне не жалко. Но как всегда запутано все, сделано наспех. Добавил комментариев.
У нас даны взвешивания. Пытаемся найти такие веса слитков, которые проходят эти взвешивания и при этом слиток 1кг будет иметь другой вес. Проверяются все перестановки весов слитков (11! вариантов). Выводится "ок" или контрпример — как надо поменять веса.
import qualified Data.Map as Map
import Data.List
-- максимальный вес, который выдерживает мешок
bag_max_weight = 11
-- слитки
boxes = [1..11]
-- список взвешиваний
actions =
[ [1, 2, 3, 4]
, [1, 2, 3, 5]
, [1, 2, 6]
, [1, 3, 6]
, [1, 4, 6]
]
-- запускаем
main = case check_permutations actions boxes of
[] -> putStrLn "ok"
d:_ -> putStrLn $ "bad solve\n" ++ show d
-- проверка, что мешок не порвется
good_actions ws = all (<= bag_max_weight) $ map sum ws
-- перестановка слитков во взвешиваниях
convert_actions mapper actions = map (map (mapper Map.!)) actions
-- пытаемся поменять веса слитков так, чтобы слиток 1кг стал другого веса и при всех взвешиваниях мешок не порвался
-- если нашли такой вариант, то увы... взвешивания не указывают однозначно на слиток 1кг
check_permutations actions boxes =
[ mapper
| new_boxes <- permutations boxes -- список всех перестановок
, mapper <- [Map.fromList $ zip boxes new_boxes] -- dict (старый вес -> новый вес)
, mapper Map.! 1 /= 1 -- нужны только такие перестановки, которые меняют вес 1кг слитка
, actions_after_permutation <- [convert_actions mapper actions] -- веса слитков после перестановки
, good_actions actions_after_permutation -- мешок не порвался после перестановки
]
Два взвешивания | |
| |
Здравствуйте, Кодт, Вы писали:
К>А покажи свою программу, что ли.
Да мне не жалко. Но как всегда запутано все, сделано наспех. Добавил комментариев.
Это программа для проверки решения, а не для поиска решения.
У нас даны взвешивания. Для опровержения решения пытаемся найти контрпример — такие веса слитков, которые проходят эти взвешивания и при этом слиток 1кг будет иметь другой вес. Проверяются все перестановки весов слитков (11! вариантов). Выводится "ок" или контрпример — как надо поменять веса.
К>А покажи свою программу, что ли.
Да мне не жалко. Но как всегда запутано все, сделано наспех. Добавил комментариев.
Это программа для проверки решения, а не для поиска решения.
У нас даны взвешивания. Для опровержения решения пытаемся найти контрпример — такие веса слитков, которые проходят эти взвешивания и при этом слиток 1кг будет иметь другой вес. Проверяются все перестановки весов слитков (11! вариантов). Выводится "ок" или контрпример — как надо поменять веса.
import qualified Data.Map as Map
import Data.List
-- максимальный вес, который выдерживает мешок
bag_max_weight = 11
-- слитки
boxes = [1..11]
-- список взвешиваний
actions =
[ [1, 2, 3, 4]
, [1, 2, 3, 5]
, [1, 2, 6]
, [1, 3, 6]
, [1, 4, 6]
]
-- запускаем
main = case check_permutations actions boxes of
[] -> putStrLn "ok"
d:_ -> putStrLn $ "bad solve\n" ++ show d
-- проверка, что мешок не порвется
good_actions ws = all (<= bag_max_weight) $ map sum ws
-- перестановка слитков во взвешиваниях
convert_actions mapper actions = map (map (mapper Map.!)) actions
-- пытаемся поменять веса слитков так, чтобы слиток 1кг стал другого веса и при всех взвешиваниях мешок не порвался
-- если нашли такой вариант, то увы... взвешивания не указывают однозначно на слиток 1кг
check_permutations actions boxes =
[ mapper
| new_boxes <- permutations boxes -- список всех перестановок
, mapper <- [Map.fromList $ zip boxes new_boxes] -- dict (старый вес -> новый вес)
, mapper Map.! 1 /= 1 -- нужны только такие перестановки, которые меняют вес 1кг слитка
, actions_after_permutation <- [convert_actions mapper actions] -- веса слитков после перестановки
, good_actions actions_after_permutation -- мешок не порвался после перестановки
]
Два взвешивания | |
| |