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

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

30.09.2022, 19:31. Показов 680. Ответов 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
12860 / 6725 / 1808
Регистрация: 18.10.2014
Сообщений: 17,026
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
Ответ Создать тему

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