1 / 1 / 0
Регистрация: 21.07.2022
Сообщений: 25
|
|
1 | |
Упорядочивание монет30.09.2022, 19:31. Показов 688. Ответов 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
|
Вездепух
![]() ![]() ![]() 12866 / 6731 / 1809
Регистрация: 18.10.2014
Сообщений: 17,035
|
|
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
Найдите финальное расположение монет Вставка числа в матрицу и её упорядочивание Упорядочивание строк в алфавитном порядке
Упорядочивание массива по возрастанию (пузырьковая сортировка) Искать еще темы с ответами Или воспользуйтесь поиском по форуму:
|
|
Новые блоги и статьи
![]() |
||||
Циклы for в Python
py-thonny 17.03.2025
Существует множество ситуаций, когда нам нужно выполнить одно и то же действие несколько раз. Цикл for в Python — настоящий рабочий конь для большинства программистов. Если вам нужно пройтись по всем. . .
|
Предсказание ветвлений - путь к высокопроизводительному C++
NullReferenced 17.03.2025
В высокопроизводительном программировании на C++ каждый такт процессора на счету. Когда речь заходит о разработке систем с низкой задержкой — будь то высокочастотная торговля, обработка потоковых. . .
|
Паттерн CQRS в C#
UnmanagedCoder 17.03.2025
Создание сложных корпоративных приложений часто требует нестандартных подходов к архитектуре. Один из таких подходов — паттерн CQRS (Command Query Responsibility Segregation), предлагающий простую,. . .
|
Паттерн Цепочка ответственности в C#
UnmanagedCoder 17.03.2025
Цепочка ответственности — это поведенческий паттерн проектирования, который позволяет передавать запросы последовательно по цепочке потенциальных обработчиков, пока один из них не обработает запрос. . . .
|
Создаем микросервисы с NestJS, TCP и Typescript
run.dev 17.03.2025
NestJS — фреймворк, который значительно упрощает создание серверных приложений на Node. js. Его прелесть в том, что он комбинирует концепции ООП, функционального программирования и предлагает. . .
|
Гексагональная архитектура со Spring Boot
Javaican 17.03.2025
Если вы когда-нибудь сталкивались с ситуацией, когда внесение простых изменений в базу данных или пользовательский интерфейс заставляло вас переписывать весь код, то вы точно оцените элегантность. . .
|
Позиционирование Kafka Consumer и Seek-операции
Javaican 17.03.2025
Что же такое Consumer Seek в Kafka? По сути, это API-метод, который позволяет программно указать, с какой позиции (offset) Consumer должен начать или продолжить чтение данных из партиции. Без этого. . .
|
Python NumPy: Лучшие практики и примеры
py-thonny 17.03.2025
NumPy (Numerical Python) — одна из ключевых библиотек для научных вычислений в Python. Она превращает Python из просто удобного языка общего назначения в среду для проведения сложных математических. . .
|
Java Micronaut в Docker: контейнеризация с Maven и Jib
Javaican 16.03.2025
Когда речь заходит о микросервисной архитектуре на Java, фреймворк Micronaut выделяется среди конкурентов. Он создан с учётом особенностей облачных сред и контейнеров, что делает его идеальным. . .
|
Управление зависимостями в Java: Сравнение Spring, Guice и Dagger 2
Javaican 16.03.2025
Инъекция зависимостей (Dependency Injection, DI) — один из фундаментальных паттернов проектирования, который радикально меняет подход к созданию гибких и тестируемых Java-приложений. Суть этого. . .
|