Вопрос :
Вы находитесь в шахте лифта 100-этажного дома.
Вы видите 21 провод с маркировкой 1 2 3 … 21.
Провода идут вверх на 100-й этаж, где концы обозначены A B C… U, но вы не знаете, как они соответствуют концам внизу.
У вас есть батарея, лампочка и много маленьких проводов.
Какое минимальное количество ходов требуется, чтобы найти пары между буквами и цифрами?
Обратите внимание, что соединение маленьких проводов в провод длиной 21 этаж не вариант.
Решение :
Обратите внимание, что ваша батарея, лампочка и небольшие провода — это, по сути, тестер соединения, а «подключение» — это отношение эквивалентности.
Внизу 1 оставляем несвязанным, 2 и 3 соединяем друг с другом, 4–6 соединяем друг с другом, 7–10 и т. д., так что имеем «классы эквивалентности» связности размеров 1, 2, 3, 4, 5 и 6.
Теперь совершите путешествие наверх и выясните, какие буквы не связаны ни с чем другим, с одной другой буквой, с двумя другими и т. д., пока не разберетесь с классами эквивалентности.
Теперь соедините первые буквы из каждого класса эквивалентности (их 6) в новый класс эквивалентности, вторые из каждого (из них 5) в другой и т. д. Идите в самый низ, уберите исходные связи и вычислите новые классы эквивалентности аналогичным образом.
Теперь мы знаем из первого набора классов, какие группы из n букв (для n = от 1 до 6) вверху соответствуют каким группам из n чисел внизу. Теперь из второго набора классов мы знаем, какие буквы и цифры были «первыми» в своих первоначальных классах, какие были «вторыми» и т. д., так что у нас есть полная пара.
Это решение хорошо работает для любого треугольного числа проводов, но его можно легко адаптировать для работы со всеми натуральными числами больше 2.
Спасибо за прочтение
Placewit воспитывает лучших инженеров, предоставляя интерактивные занятия в классе и помогая им развивать свои навыки и попадать в замечательные компании.
Узнайте больше на Placewit. Следите за нами в Instagram и Facebook для ежедневного обучения.
