Форум программистов, компьютерный форум, киберфорум
Алгоритмы
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.76/21: Рейтинг темы: голосов - 21, средняя оценка - 4.76
18 / 18 / 7
Регистрация: 20.03.2012
Сообщений: 585

Поиск медианы в двумерном массиве

01.02.2013, 10:56. Показов 4558. Ответов 13
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Объявляется конкурс на лучший алгоритм/функцию для нахождения значения медианы двумерного массива.
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
01.02.2013, 10:56
Ответы с готовыми решениями:

Поиск максимального элемента в двумерном массиве
Здравствуйте! Собственно вопрос - оптимальный алгоритм. Есть ли тут вообще алгоритм который находит быстрее чем перебором за O(mxn)

Поиск группы разных элементов в двумерном массиве
Есть задача - в двумером массиве размером, например, 100х100 найти координаты квадратов размером, например, 10х10, которые содержат, опять...

нахождение элементов в двумерном массиве
Собственно вопрос такой-как найти количество элементов между его максимальным и минимальным значениями,если я знаю их индексы в массиве.Уже...

13
Эксперт С++
 Аватар для Nameless One
5828 / 3479 / 358
Регистрация: 08.02.2010
Сообщений: 7,448
01.02.2013, 11:14
Призовой фонд какой?
0
01.02.2013, 11:21

Не по теме:

Цитата Сообщение от Nameless One Посмотреть сообщение
Призовой фонд какой?
клик на "спасибо" под постом победителя :)

0
Модератор
Эксперт PythonЭксперт JavaЭксперт CЭксперт С++
 Аватар для easybudda
12843 / 7592 / 1766
Регистрация: 25.07.2009
Сообщений: 13,973
01.02.2013, 11:29

Не по теме:


Цитата Сообщение от Nameless One Посмотреть сообщение
Призовой фонд какой?
- За каждый хороший поступок ты будешь получать одну спасибу.
- А что за них можно купить?
- За спасибы ничего нельзя купить, но ими можно гордиться!
(с)



ТС, другими словами "памагитесрочна"?
0
01.02.2013, 11:35

Не по теме:

Цитата Сообщение от Croessmah Посмотреть сообщение
клик на "спасибо" под постом победителя
Ну, это несерьезно :) Пусть озвучит цену, и мы, как положено, перенесем тему во фриланс.

0
 Аватар для SummerRain
328 / 327 / 92
Регистрация: 16.12.2012
Сообщений: 544
01.02.2013, 13:49
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
// Объявляется конкурс на лучший алгоритм/функцию для нахождения значения медианы двумерного массива.
 
// Функция findMedian возвращает медиану массива, если количество его элементов нечетно
//                               среднее арифметическое двух срединных значений, если количество четно
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <ctime>
#include <cstdlib>
 
#define N 5 // задайте размеры массива сами
#define M 10
 
int findMedian(int const mas[N][M])
{
    std::vector<int> vec;
    typedef std::vector<int>::size_type vec_size;
    for (int i = 0; i != N; ++i) {
        for (int j = 0; j != M; ++j) {
            vec.push_back(mas[i][j]);
        }
    }
    sort(vec.begin(), vec.end());       
    vec_size size = vec.size();
    vec_size mid = size/2;
    return size % 2 == 0 ? (vec[mid] + vec[mid + 1])/2 : vec[mid];
}
 
void show(int const mas[N][M])
{
    for (int i = 0; i != N; ++i) {
        for (int j = 0; j != M; ++j) {
            std::cout << std::setw(3) << mas[i][j] << " ";
        }
        std::cout << std::endl;
    }
}
 
int main()
{
    srand((unsigned)time(NULL));
    int mas[N][M];
    for (int i = 0; i != N; ++i) {
        for (int j = 0; j != M; ++j) {
            mas[i][j] = rand()%100;
        }
    }
    show(mas);
    int median = findMedian(mas);
    std::cout << std::endl << median << std::endl;
    system("pause");
    return 0;
}
0
18 / 18 / 7
Регистрация: 20.03.2012
Сообщений: 585
01.02.2013, 16:44  [ТС]
На сколько быстро работает алгоритм? В частности готовая функция sort? Есть же еще функция qsort, например. На сколько оправдано использование класса vector? (опять же вопрос скорости вычисления). Существуют ли, вообще, алгоритмы нахождения медианы без предварительной сортировки?

Цитата Сообщение от easybudda Посмотреть сообщение
"памагитесрочна"?
Не столько срочно, сколько качественно)
0
 Аватар для Venzo
127 / 125 / 16
Регистрация: 03.07.2011
Сообщений: 354
01.02.2013, 16:59
алгоритм Хоара. Принцип почти тот же, что и в быстрой сортировке
0
290 / 193 / 23
Регистрация: 03.08.2011
Сообщений: 2,824
Записей в блоге: 12
01.02.2013, 18:35
Цитата Сообщение от znseday Посмотреть сообщение
Объявляется конкурс на лучший алгоритм/функцию для нахождения значения медианы двумерного массива.
а может надо написать : спасите помогите, завтра зачёт - надо решить такую задачу
0
18 / 18 / 7
Регистрация: 20.03.2012
Сообщений: 585
02.02.2013, 10:15  [ТС]
Кажется я ошибся разделом... Интересует действительно самый оптимальный алгоритм. Или анализ ряда алгоритмов: плюсы и минусы. Т.к. поиск медианы нужен, в первую очередь, для анализа входящих изображений высокого разрешения; ну и для решения еще рада задач, где размеры массива не менее 1000*1000.
0
18 / 18 / 7
Регистрация: 20.03.2012
Сообщений: 585
06.02.2013, 21:29  [ТС]
Цитата Сообщение от SummerRain Посмотреть сообщение
std::vector
(Никогда раньше с ним не работал)
Он ведь при выходе из функции findMedian все свои данные сам удаляет?
0
 Аватар для SummerRain
328 / 327 / 92
Регистрация: 16.12.2012
Сообщений: 544
06.02.2013, 22:26
Цитата Сообщение от znseday Посмотреть сообщение
(Никогда раньше с ним не работал)
Он ведь при выходе из функции findMedian все свои данные сам удаляет?
это локальный объект, соответственно, сделав своё дело, перестаёт существовать.

Не по теме:

Ну как конкурс продолжается? есть победители?

0
18 / 18 / 7
Регистрация: 20.03.2012
Сообщений: 585
07.02.2013, 20:00  [ТС]
Цитата Сообщение от SummerRain Посмотреть сообщение
это локальный объект, соответственно, сделав своё дело, перестаёт существовать.
Это то понятно, но ведь не факт, что и свои динамические данные он удаляет. Вернее, я понимаю, что 99%, что удаляет, просто приступ паранойи)

Не по теме:

Пока победителем являетесь Вы, т.к. предложили хоть что-то. Идея работать с классом vector - хорошая, т.к. можно анализировать любые типы данных массивов любых размерностей, в том числе и не "прямоугольные". Но вопрос производительности - открытый, я пока ни с чем не сравнивал. Обработка массива 100 на 200 пока пока идет с приемлемой скоростью, но скоро размер массива будет увеличиваться на порядок



Добавлено через 1 минуту

Не по теме:

Кстати, я пока и анализирую не прямоугольные массивы, а массивы в виде окружностей

0
18 / 18 / 7
Регистрация: 20.03.2012
Сообщений: 585
09.02.2013, 16:28  [ТС]
Цитата Сообщение от SummerRain Посмотреть сообщение
// Функция findMedian возвращает медиану массива,
Протестировал на простых числах - результат выдает неверный (берет соседнее число(соседнюю сумму чисел) от медианы). Попробую разобраться и потом отпишусь..

Добавлено через 6 минут
Так смотрим вместе внимательно...:
Цитата Сообщение от SummerRain Посмотреть сообщение
return size % 2 == 0 ? (vec[mid] + vec[mid + 1])/2 : vec[mid];
Нужно изменить на
C++
1
return size % 2 == 0 ? (vec[mid] + vec[mid - 1])/2 : vec[mid];
Верно ведь? (на бумаге проверил)
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
09.02.2013, 16:28
Помогаю со студенческими работами здесь

Поиск числа в двумерном массиве (бинарный поиск)
Произвожу поиск элемента в массиве двумя способами: линейным(последовательным) поиском и бинарным(двоичным). Первый работает на ура. Второй...

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

Поиск в двумерном массиве
Здравствуйте ... помогите реализовать такую программу... прост в ассемблере я ваще не шарю ... вернее даже сказать переделать один код на...

Поиск в двумерном массиве
Помогите написать программу Условие следующее: Дано массив целых чисел А , который состоит из нулей и единиц. Для заданного значения К...

Поиск максимума в двумерном массиве
Рандомом задается двумерный целочисленный массив. Требуется: Найти максимальный элемент из тех, что отмечены крестиком. * * * х * * * ...


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

Или воспользуйтесь поиском по форуму:
14
Ответ Создать тему
Новые блоги и статьи
PhpStorm 2025.3: WSL Terminal всегда стартует в ~
and_y87 14.12.2025
PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .
Access
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha
Etyuhibosecyu 20.11.2025
Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
Мысли в слух
kumehtar 18.11.2025
Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .
Создание Single Page Application на фреймах
krapotkin 16.11.2025
Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru