Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
ForEveR
Модератор
Эксперт С++
7958 / 4720 / 319
Регистрация: 24.06.2010
Сообщений: 10,525
Завершенные тесты: 3
#1

Поиск медианы в отображении - C++

02.10.2010, 03:12. Просмотров 758. Ответов 6
Метки нет (Все метки)

У Страуструпа такое задание. Решил сделать. Получилось каким-то кустарным методом, но работает. Проще возможно?
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
    
//
if(Map.size()!=0&&Map.size()%2!=0)
    {
        for (SIMap::iterator It=Map.begin(); It!=Map.end(); ++It)
        {
            int great=0;
            int less=0;
            int equal=0;
            for(SIMap::iterator Iter=Map.begin(); Iter!=Map.end(); ++Iter)
            {
                if(Iter->second==It->second)
                {
                    ++equal;
                    continue;
                }
                if(Iter->second<It->second)
                    less++;
                else if(Iter->second>It->second)
                    great++;
            }
            if(less==great)
                med=It->second;
            else if(equal>1)
            {
                std::cerr<<"Can`t be 2 or more equal elements\n";
                return 0;
            }
        }
    }
    else
    {
        std::cout<<"There is no median\n";
        return 0;
    }
    std::cout<<"Median is: "<< med <<'\n';
    return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.10.2010, 03:12     Поиск медианы в отображении
Посмотрите здесь:

Даны длины сторон А, В, С некоторого треугольника. Определить его медианы. C++
C++ Медианы треугольника, вывод названий
"Быстрая" сортировка с итерационным циклом вычисления медианы C++
C++ Вычислить длину медианы(С код)
Даны длины треугольника ABC. Определить его медианы C++
C++ Найти медианы на всех префиксах последовательности X длины n и вывести их сумму
C++ Оптимизация программы нахождения медианы массива
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
alexzak
84 / 57 / 1
Регистрация: 07.08.2010
Сообщений: 185
02.10.2010, 04:31     Поиск медианы в отображении #2
А что, по условию нельзя использовать дополнительную память? Грубо говоря,
Perl 6
1
2
%seq = (vasilii_ivanych => 5, petka => -1, yanka => 3);
$median = (sort values %seq)[%seq / 2];
ForEveR
Модератор
Эксперт С++
7958 / 4720 / 319
Регистрация: 24.06.2010
Сообщений: 10,525
Завершенные тесты: 3
02.10.2010, 10:55  [ТС]     Поиск медианы в отображении #3
alexzak, Как это может выглядеть в С++? Понять что-то не могу.
alexzak
84 / 57 / 1
Регистрация: 07.08.2010
Сообщений: 185
02.10.2010, 21:47     Поиск медианы в отображении #4
Идея такая:
- есть map, из него получаем values (it->second) и засовываем их в вектор (на перле: values %seq),
- сортируем вектор,
- берём из него средний элемент (это и будет медиана),
(если количество элементов четное, то можно взять среднее между двумя элементами из середины).

А можно и полностью объекты копировать в вектор, а потом сортировать с предикатом, сравнивающим pair::second.
#pragma
Временно недоступен
952 / 223 / 6
Регистрация: 12.04.2009
Сообщений: 921
02.10.2010, 22:27     Поиск медианы в отображении #5
А map разве нельзя сортировать по признаку?
Т.е. просто взять и сравнивать ->second ,по ходу изменяя его индекс в конейнере. Или это слишком трудоёмкая в плане ресурсов задача?
alexzak
84 / 57 / 1
Регистрация: 07.08.2010
Сообщений: 185
03.10.2010, 04:22     Поиск медианы в отображении #6
Цитата Сообщение от #pragma Посмотреть сообщение
А map разве нельзя сортировать по признаку?
map упорядочивает по ключу (key), поэтому если вдруг хочется по значению (value), то ничего не выйдет, кроме как создать новый map. Создание нового map'а будет N log N, заполнение и сортировка вектора тоже N log N. Но на практике, вектор сортировать будет быстрее, потому что алгоритм сортировки более эффективен, чем создание бинарного дерева.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.10.2010, 23:11     Поиск медианы в отображении
Еще ссылки по теме:

C++ В массиве найти отклонение медианы от среднего арифметического
По введенным координатам вершин треугольника найти длину медианы C++
Иероглифы при отображении кириллицы в консоли C++
Абсолютные медианы на неориентированном графе C++
Избыточный перенос на новую строку при отображении значения типа string C++

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

Или воспользуйтесь поиском по форуму:
#pragma
Временно недоступен
952 / 223 / 6
Регистрация: 12.04.2009
Сообщений: 921
03.10.2010, 23:11     Поиск медианы в отображении #7
А разве так нельзя делать?
C++
1
2
if ( iter->second > it->second  )
   mymap[it->second] = specific_index;
Ну или может там надо разыменовать итератор при подаче в map (или так сойдёт?).
Можно ведь вроде "насильно" менять индекс ключа.
Yandex
Объявления
03.10.2010, 23:11     Поиск медианы в отображении
Ответ Создать тему
Опции темы

Текущее время: 00:51. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru