Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

Войти
Регистрация
Восстановить пароль
 
ForEveR
В астрале
Эксперт С++
7986 / 4745 / 321
Регистрация: 24.06.2010
Сообщений: 10,547
Завершенные тесты: 3
#1

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

02.10.2010, 03:12. Просмотров 798. Ответов 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;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.10.2010, 03:12
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Поиск медианы в отображении (C++):

Медианы треугольника, вывод названий - C++
Ребят помогите кто чем может! Срочно надо очень! Есть задания, их надо написать на С или С++ Задание №1 2D-решение треугольников...

Вычислить длину медианы(С код) - C++
Заданы вершины треугольника А(х1,у1),В(х2,у2),С(х3,у3).Вычислить длину медианы,проведенной из выбранной вершины треугольника.Выбор вершин...

Абсолютные медианы на неориентированном графе - C++
Сильно связный граф G=&lt;V,E&gt;, дугам(ребрам) и вершинам которого приписаны неотрицательные целые веса. Граф задан матрицей весов дуг A,u,v...

Иероглифы при отображении кириллицы в консоли - C++

Оптимизация программы нахождения медианы массива - C++
Всем доброй ночи. Мне надо было написать программку, которая выводит медиану массива - перелистал много тем, но так и не нашел нормального...

В массиве найти отклонение медианы от среднего арифметического - C++
По двум массивам построить третий, элементы которого являются частным от деления элементов первого на соответствующие элементы второго...

6
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];
0
ForEveR
В астрале
Эксперт С++
7986 / 4745 / 321
Регистрация: 24.06.2010
Сообщений: 10,547
Завершенные тесты: 3
02.10.2010, 10:55  [ТС] #3
alexzak, Как это может выглядеть в С++? Понять что-то не могу.
0
alexzak
84 / 57 / 1
Регистрация: 07.08.2010
Сообщений: 185
02.10.2010, 21:47 #4
Идея такая:
- есть map, из него получаем values (it->second) и засовываем их в вектор (на перле: values %seq),
- сортируем вектор,
- берём из него средний элемент (это и будет медиана),
(если количество элементов четное, то можно взять среднее между двумя элементами из середины).

А можно и полностью объекты копировать в вектор, а потом сортировать с предикатом, сравнивающим pair::second.
1
#pragma
Временно недоступен
954 / 225 / 6
Регистрация: 12.04.2009
Сообщений: 921
02.10.2010, 22:27 #5
А map разве нельзя сортировать по признаку?
Т.е. просто взять и сравнивать ->second ,по ходу изменяя его индекс в конейнере. Или это слишком трудоёмкая в плане ресурсов задача?
0
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. Но на практике, вектор сортировать будет быстрее, потому что алгоритм сортировки более эффективен, чем создание бинарного дерева.
0
#pragma
Временно недоступен
954 / 225 / 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 (или так сойдёт?).
Можно ведь вроде "насильно" менять индекс ключа.
0
03.10.2010, 23:11
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.10.2010, 23:11
Привет! Вот еще темы с ответами:

По введенным координатам вершин треугольника найти длину медианы - C++
Нужно найти длину медианы, вводятся координаты вершин треугольника

Даны длины треугольника ABC. Определить его медианы - C++
Даны длины сторон А,В,С треугольника. Определите его медианы. Длинна медианы проведенной на сторону А вычесляется по формуле...

Даны длины сторон А, В, С некоторого треугольника. Определить его медианы. - C++
Надо написать программу с функциями, перегрузку и шаблон к ней. вот задание: &quot;Даны длины сторон А, В, С некоторого треугольника....

Найти медианы на всех префиксах последовательности X длины n и вывести их сумму - C++
В этой задаче необходимо найти медианы на всех префиксах последовательности X длины n и вывести их сумму. Медианой последовательности...


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

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.