Форум программистов, компьютерный форум, киберфорум
C для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 5.00/4: Рейтинг темы: голосов - 4, средняя оценка - 5.00
1 / 1 / 0
Регистрация: 21.07.2022
Сообщений: 25
1

Упорядочивание монет

30.09.2022, 19:31. Показов 688. Ответов 3
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
В древнем кладе было найдено n монет различного веса. Каждая из монет была обозначена строчной буквой латиницы. Все обозначения были различными. Монеты были попарно взвешены на чашечных весах. Протокол взвешиваний состоял из n(n−1)/2 строк, каждая строка содержала ровно три символа. Первый и третий символ содержали обозначения монет, а во втором был записан результат сравнения: знак <<< или знак >>>. Например, запись d>b означает, что монета d тяжелее монеты b.

Взвешивания очень утомили лаборанта, и он просит вас написать программу, которая упорядочит монеты по возрастанию веса.
Формат входных данных

На вход в первой строке подается одно натуральное число nnn — количество монет, 4≤n≤264. Далее в n(n−1)/2 строках записан протокол взвешиваний
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
30.09.2022, 19:31
Ответы с готовыми решениями:

Упорядочивание по убыванию
Помогите сделать вторую часть задачи. Проверить, все ли строки матрицы упорядочены по убыванию. Если нет, найти первую неупорядоченную...

Колокол - упорядочивание массива
Задча на тему массивы, файлы не нужны Вроде просто, но на Паскале/Делфи написать могу на Си хоть ты тресни! Может сказывается то что Си...

Подсчитать количество монет из сдачи
Си... Ребята, нужна помощь. Дана задача, подсчитать количество монет из сдачи (25 коп, 10, 5, 1) Результат выводить. К примеру 1.56...

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
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
12866 / 6731 / 1809
Регистрация: 18.10.2014
Сообщений: 17,035
01.10.2022, 22:44 3
Здесь ничего не нужно изобретать вообще. Задача совершенно тривиальная. Вам дана полная таблица результатов сравнений всех попарных комбинаций.

Берете любой алгоритм сортировки сравнениями и запускаете его на любом входном наборе монет. Всякий раз, когда алгоритм просит вам выполнить сравнение, просто смотрите в таблицу.

Готово.

Так можно сортировать произвольные наборы монет. Как я понял условие, отсортировать требуется все монеты. Ну значит берем набор из всех монет и подаем на вход алгоритму сортировки.

Цитата Сообщение от Foden Посмотреть сообщение
На вход в первой строке подается одно натуральное число nnn - количество монет
Не понял. Так "n" или "nnn"? Откуда вдруг взялось "nnn"?

Цитата Сообщение от Foden Посмотреть сообщение
Каждая из монет была обозначена строчной буквой латиницы. ... количество монет, 4≤n≤264.
Не понял. Каким образом 264 монеты можно обозначить "строчными буквами латиницы"?

Цитата Сообщение от Foden Посмотреть сообщение
знак <<< или знак >>>. Например, запись d>b
Но где в этой записи "<<<" или ">>>"?
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 буква ( латинская малая ) и знаки '>' и '<'

C Скопировано
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <stdio.h>
#include <stdlib.h>
 
void Swap( int* const values, const int left_index, const int right_index )
{
    int swap = values[ left_index ];
    values[ left_index ] = values[ right_index ];
    values[ right_index ] = swap;
}
 
#define CODE_A 97
 
int main( void )
{
    int n;
    int i;
    int* name_coins;
    int* weight_coins;
    int total_records;
    int current_record;
 
    scanf( "%d", &n );
    name_coins = ( int* )malloc( sizeof( int ) * n );
    weight_coins = ( int* )malloc( sizeof( int ) * n );
 
    for ( i = 0; i < n; i++ )
    {
        name_coins[ i ] = i;
        weight_coins[ i ] = i;
    }
 
    total_records = n * ( n - 1 ) / 2;
    for ( current_record = 0; current_record < total_records; current_record++ )
    {
#define GREATER '>'
#define LESS '<'
 
        char left, sign, right;
        int code_left, code_right;
 
        scanf( "%*c%c %c %c", &left, &sign, &right );
        code_left = left - CODE_A;
        code_right = right - CODE_A;
 
        if ( ( ( ( sign == GREATER ) && ( weight_coins[ code_left ]  < weight_coins[ code_right ] ) ) ) ||
            ( ( ( sign == LESS ) && ( weight_coins[ code_left ]  > weight_coins[ code_right ] ) ) ) )
        {
            Swap( weight_coins, code_left, code_right );
            name_coins[ weight_coins[ code_left ] ] = code_left;
            name_coins[ weight_coins[ code_right ] ] = code_right;
        }
    }
 
    printf( "\nSorted data: \n\t" );
    for ( i = 0; i < n; i++ )
    {
        printf( "%c\t", name_coins[ i ] + CODE_A );
    }
 
    free( name_coins );
    free( weight_coins );
 
    printf( "\n\n" );
    system( "pause" );
    return EXIT_SUCCESS;
}
основное преимущество - вся обработка на лету ( без доп. сортировки после считывания таблицы результатов сравнения )

очевидно, что при вводе данных не должно нарушаться свойство транзитивности, т е, например:
n = 3
a > b
b > c
a < c - error!

зы: на 100% не уверен, что здесь все гладко и нет каких-нибудь спец.случаев...
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
02.10.2022, 05:24
Помогаю со студенческими работами здесь

Найдите финальное расположение монет
Задача из http://acm.sgu.ru/olimp/index.php Прошу помочь с программой, а именно со скоростью выполнения. Задача оч простая -...

Вставка числа в матрицу и её упорядочивание
Доброго времени суток, ребята. Помогите с решением относительно простой (не для меня) задачи в Си по двумерному массиву (матрице). ...

Упорядочивание строк в алфавитном порядке
#include &lt;stdio.h&gt; #include &lt;string.h&gt; #define MAXLINES 5000 char *lineptr; #define MAXLEN 1000 int getline( char *s,...

Упорядочивание записей по датам дней рождения
Доброй ночи!:) К тем, кто не спит и может помочь обращаюсь) Требуется ввести с клавиатуры данные в массив,записи должны быть...

Упорядочивание массива по возрастанию (пузырьковая сортировка)
Подскажите пожалуйста как упорядочить элементы одномерного массива,состоящего из N вещественных элементов по возрастанию методом...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
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-приложений. Суть этого. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru
Выделить код Копировать код Сохранить код Нормальный размер Увеличенный размер