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

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

Восстановить пароль Регистрация
 
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
02.10.2010, 03:12     Поиск медианы в отображении #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
    
//
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++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
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
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 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
Временно недоступен
 Аватар для #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++ Найти медианы на всех префиксах последовательности X длины n и вывести их сумму
C++ Оптимизация программы нахождения медианы массива
C++ В массиве найти отклонение медианы от среднего арифметического

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

Или воспользуйтесь поиском по форуму:
#pragma
Временно недоступен
 Аватар для #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     Поиск медианы в отображении
Ответ Создать тему
Опции темы

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