1 / 1 / 0
Регистрация: 21.07.2022
Сообщений: 25
|
|
1 | |
Упорядочивание монет30.09.2022, 19:31. Показов 680. Ответов 3
Метки нет Все метки)
(
В древнем кладе было найдено n монет различного веса. Каждая из монет была обозначена строчной буквой латиницы. Все обозначения были различными. Монеты были попарно взвешены на чашечных весах. Протокол взвешиваний состоял из n(n−1)/2 строк, каждая строка содержала ровно три символа. Первый и третий символ содержали обозначения монет, а во втором был записан результат сравнения: знак <<< или знак >>>. Например, запись d>b означает, что монета d тяжелее монеты b.
Взвешивания очень утомили лаборанта, и он просит вас написать программу, которая упорядочит монеты по возрастанию веса. Формат входных данных На вход в первой строке подается одно натуральное число nnn — количество монет, 4≤n≤264. Далее в n(n−1)/2 строках записан протокол взвешиваний
0
|
30.09.2022, 19:31 | |
Ответы с готовыми решениями:
3
Упорядочивание по убыванию Колокол - упорядочивание массива
|
383 / 280 / 112
Регистрация: 28.04.2015
Сообщений: 1,723
|
|
01.10.2022, 12:57 | 2 |
повезло, что каждая монета была взвешена с каждой другой
чем тяжелее монета, тем больше записей для нее будет иметь знак ">>>" ( это же справедливо и для самых легких монет, только в др.сторону "<<<" ) посчитать для каждой монеты частотность ">>>"/"<<<" и потом отсортировать по частотности какой-нибудь улучшенной сортировкой сложностью O( n * log( n ) ) например: n = 3 a >>> b b <<< c a >>> c [ 2 ][ 0 ][ 1 ] - a b c ( сумма всех значений будет именно n/2 * ( n - 1 ) ) --------------------------------- если бы не было все возможных сравнений, например n = 3 a >>> b b >>> c из этого следует, что a >>> c, то, имхо, все бы усложнилось ---------------------------------------- можно ли на лету отсортировать входные данные? вроде бы нет! Т е добиться сложности O( n ) нереал... была еще идея задействовать min( max )-heap ( пирамида, сорт.дерево ) и постараться получить сложность что-то типа (log(n))^2, но нет возможности установить однозначного соответствия между монетами, например a >>> b c <<< d на данный момент ничего нельзя судить о весах a ??? d, например зы: это навскидку, то, что бросается на глаз
0
|
Вездепух
![]() ![]() ![]() 12860 / 6725 / 1808
Регистрация: 18.10.2014
Сообщений: 17,026
|
|
01.10.2022, 22:44 | 3 |
Здесь ничего не нужно изобретать вообще. Задача совершенно тривиальная. Вам дана полная таблица результатов сравнений всех попарных комбинаций.
Берете любой алгоритм сортировки сравнениями и запускаете его на любом входном наборе монет. Всякий раз, когда алгоритм просит вам выполнить сравнение, просто смотрите в таблицу. Готово. Так можно сортировать произвольные наборы монет. Как я понял условие, отсортировать требуется все монеты. Ну значит берем набор из всех монет и подаем на вход алгоритму сортировки. Не понял. Так "n" или "nnn"? Откуда вдруг взялось "nnn"? Не понял. Каким образом 264 монеты можно обозначить "строчными буквами латиницы"? Но где в этой записи "<<<" или ">>>"?
0
|
383 / 280 / 112
Регистрация: 28.04.2015
Сообщений: 1,723
|
||||||
02.10.2022, 05:24 | 4 | |||||
а как насчет такого варианта
сортировка на лету за O ( K ), где K = n ( n - 1 ) / 2, то есть линейная сложность от количества строк входных данных т к будут все возможные сравнения, то можно расположить монеты в произвольном порядке, например a b c d e ... учитывая, что вес( а ) < вес ( b ) < вес ( c ) < ... в процессе получения очередной порции данных будет перетасовка пары монет ( при необходимости ) с запоминаем всей необходимой информации для упрощения названия монеты - 1 буква ( латинская малая ) и знаки '>' и '<'
очевидно, что при вводе данных не должно нарушаться свойство транзитивности, т е, например: n = 3 a > b b > c a < c - error! зы: на 100% не уверен, что здесь все гладко и нет каких-нибудь спец.случаев...
0
|
02.10.2022, 05:24 | ||||||
Помогаю со студенческими работами здесь
4
Найдите финальное расположение монет Вставка числа в матрицу и её упорядочивание Упорядочивание строк в алфавитном порядке
Упорядочивание массива по возрастанию (пузырьковая сортировка) Искать еще темы с ответами Или воспользуйтесь поиском по форуму:
|
|
![]() |
Новые блоги и статьи
![]() |
||||
Осваиваем Kubernetes: Подробная шпаргалка
Mr. Docker 15.03.2025
Kubernetes — это открытая платформа для автоматизации развертывания, масштабирования и управления контейнеризированными приложениями. Он был создан для решения проблем, с которыми сталкиваются. . .
|
Лучшие PHP REST API фреймворки
Jason-Webb 15.03.2025
Современные PHP REST API фреймворки предлагают большой набор функциональности: от автоматической валидации данных и управления маршрутизацией до генерации документации и интеграции с различными. . .
|
Многопоточность в Java с Project Loom: виртуальные или обычные потоки
Javaican 15.03.2025
Многопоточность всегда была одноим из основных элементов в разработке современного программного обеспечения. Она позволяет приложениям обрабатывать несколько задач одновременно, что критично для. . .
|
Что нового в Swift 6 и особенности миграции
mobDevWorks 15.03.2025
Swift 6 — это новый крупный релиз языка программирования от Apple, анонсированный на WWDC 2024. Если вы следили за эволюцией Swift, то наверняка заметили, что многие значимые возможности, которые. . .
|
Вопросы на собеседовании по Android
mobDevWorks 14.03.2025
По данным статистики, Android занимает более 70% мирового рынка мобильных операционных систем, что делает платформу привлекательной как для начинающих разработчиков, так и для опытных профессионалов. . . .
|
Лучшие игровые движки для Python
py-thonny 14.03.2025
Python обеспечивает разработчиков игр мощными движками и фреймворками, которые позволяют воплотить практически любую идею — от простой аркады до визуального романа с разветвленным сюжетом. Главное. . .
|
Бессерверный JavaScript: Разработка масштабируемых API с AWS Lambda
run.dev 14.03.2025
Но что такое бессерверные вычисления на самом деле? По сути, это модель облачных вычислений, где разработчик фокусируется исключительно на создании бизнес-логики, не тратя время на настройку. . .
|
Безопасность кода в C++26: Менеджеры ресурсов и висячие ссылки
NullReferenced 14.03.2025
C++ всегда был языком, предоставляющим разработчикам большие возможности и гибкость, но вместе с тем требующим ответственности. Одной из самых коварных проблем даже для опытных программистов остаются. . .
|
smart-agent proper interface settings (2025)
jigi33 14.03.2025
Smart-agent proper interface settings (mart 2025).
(see screenshots to look at "Etalon" ARM)
|
Продвинутые настройки JVM
Javaican 14.03.2025
Стандартные параметры запуска JVM хороши для повседневной разработки, но совершенно недостаточны для высоконагруженных систем. Представьте, что вы запускаете финансовую платформу, обрабатывающую. . .
|