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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 57, средняя оценка - 4.72
bubajiex
0 / 0 / 0
Регистрация: 03.10.2011
Сообщений: 7
#1

Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза - C++

03.10.2011, 20:00. Просмотров 7486. Ответов 46
Метки нет (Все метки)

Помогите пожалуйста
задачка вроде простенькая :
найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.10.2011, 20:00
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза (C++):

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

Двумерный массив. Найти: максимальное из чисел, встречающихся в заданной матрице более одного раза - C++
Найти: максимальное из чисел, встречающихся в заданной матрице более одного раза Матрица: 2 4 7 6 5 8 9 34 43 4 34 53 45 345 3 6 5 56...

Найти максимальное из чисел встречающихся в матрице более одного раза. Сделать используя указатели и классы - C++
Ребята..помогите,пожалуйста.Надо решить задачу,а никак не выходит(даже не знаю..прочитала в книге все про указатели и не пойму как...

Максимальное из чисел встречающихся в заданной матрице более одного раза - C++
Есть программа, она работает, но мне не понятен принцип, мог бы кто нибудь помочь? #include "stdafx.h" #include <iostream> ...

Максимальное из чисел, встречающихся в заданной матрице более одного раза - C++
//Дана целочисленная прямоугольная матрица. Определить: //1) количество строк, не содержащих ни одного нулевого элемента; ...

Определить максимальное из чисел, встречающихся в заданной матрице более одного раза - C++
Есть код. 1 задание, где определяет количество строк, не содержащих ни одного нулевого элемента уже сделано. Помогите дописать код, чтобы...

46
Deviaphan
Делаю внезапно и красиво
Эксперт С++
1306 / 1221 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
04.10.2011, 12:04 #31
Цитата Сообщение от Thinker Посмотреть сообщение
Разбить на целые и дробные части, а далее поразрядная сортировка.
Не факт, что 3,14 == 3,14. Или что 3,14 != 3,15. Но цифры другие, разумеется, это я для примера написал. Т.е. на "равно" же вещественные не сравниваются напрямую, поэтому при подсчёте количества те же проблемы могут возникнуть. С сортировкой эта проблема решается добавлением компаратора, а вот подсчётом...
0
Thinker
Эксперт С++
4228 / 2202 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
04.10.2011, 12:05 #32
Цитата Сообщение от fasked Посмотреть сообщение
Тоже неудобно, количество разрядов в дробной части может быть велико и одинаково почти для всех чисел. Если числа случайны, вероятность повышается.
Поэтому и говорил, что если у нас памяти ОЧЕНЬ много, то такой вариант, а иначе это не пройдет
0
romex
44 / 44 / 4
Регистрация: 11.04.2010
Сообщений: 223
04.10.2011, 12:05 #33
а далее поразрядная сортировка.
сложность которой NlogN, кстати...
0
Thinker
Эксперт С++
4228 / 2202 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
04.10.2011, 12:07 #34
Цитата Сообщение от Deviaphan Посмотреть сообщение
Не факт, что 3,14 == 3,14. Или что 3,14 != 3,15. Но цифры другие, разумеется, это я для примера написал. Т.е. на "равно" же вещественные не сравниваются напрямую, поэтому при подсчёте количества те же проблемы могут возникнуть. С сортировкой эта проблема решается добавлением компаратора, а вот подсчётом...
Сравнивать нужно отдельно целые и дробные части, поэтому поразрядная сортировка.

Добавлено через 24 секунды
Цитата Сообщение от romex Посмотреть сообщение
сложность которой NlogN, кстати...
она линейная на базе сортировки подсчетом.
0
odip
Эксперт С++
7159 / 3221 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
04.10.2011, 12:10 #35
поэтому поразрядная сортировка
В этой таблице n — это количество записей, которые необходимо упорядочить, а k — это количество уникальных ключей.
...
Поразрядная сортировка — Сложность алгоритма: O(n·k); требуется O(k) дополнительной памяти.
...
http://ru.wikipedia.org/wiki/Алгоритм_сортировки

Надеюсь вопрос о сложности поразрядной сортировки исчерпан ?
0
romex
44 / 44 / 4
Регистрация: 11.04.2010
Сообщений: 223
04.10.2011, 12:11 #36

Не по теме:

Тривиальнейшая задачка вылезла в такой ужас...



Добавлено через 1 минуту
k — это количество уникальных ключей.
тоесть два в данном случае? Только не бейте...
0
Thinker
Эксперт С++
4228 / 2202 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
04.10.2011, 12:12 #37
Цитата Сообщение от odip Посмотреть сообщение
Поразрядная сортировка — Сложность алгоритма: O(n·k); требуется O(k) дополнительной памяти.
Правильно, при фиксированном k - сложность линейная относительно n.
0
easybudda
Модератор
Эксперт CЭксперт С++
9695 / 5645 / 963
Регистрация: 25.07.2009
Сообщений: 10,850
04.10.2011, 14:59 #38
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
Не претендую на приз "Алгоритм года", сделал реализацию при условии, что массив нельзя изменять
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
#include <stdio.h>
#include <limits.h>
    
int * allmost_top(const int * arr, size_t size, int absTop){
    const int * ret;
    
    while ( *arr >= absTop && size > 0 ){
        ++arr;
        --size;
    }
    if ( ! size )
        return NULL;
    
    ret = arr;
    while ( --size )
        if ( *(++arr) < absTop && *ret < *arr )
            ret = arr;
    
    return (int*) ret;
}
 
int * find_same(const int * arr, size_t size, int value){
    while ( size-- ){
        if ( *arr == value )
            return (int*)arr;
        ++arr;
    }
    
    return NULL;
}
 
#define SIZE 10
int main(void){
    int arr[SIZE] = { 9, 8, 7, 2, 5, 3, 3, 4, 5, 1 };
    int * found;
    
    for ( found = allmost_top(arr, SIZE, INT_MAX); found; found = allmost_top(arr, SIZE, *found) )
        if ( find_same(found + 1, SIZE + arr - found - 1, *found) )
            break;
    
    if ( ! found )
        printf("No doubling elements in array!\n");
    else
        printf("The biggest element repeating in array have value of %d\n", *found);
    
    return 0;
}
Понятия не имею, что там со сложностью. Кстати, Thinker, буду признателен, если хорошую на ваш взгляд литературу подскажете...
Ну и очевидное ограничение - значения массива должны быть меньше INT_MAX, что, в прочем, можно исправить...
0
Deviaphan
Делаю внезапно и красиво
Эксперт С++
1306 / 1221 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
04.10.2011, 15:06 #39
Цитата Сообщение от easybudda Посмотреть сообщение
Понятия не имею, что там со сложностью
Не вдавался в размерности, но похоже, что для каждого элемента происходит два линейных поиска (find_some и allmost_top), так что сложность на кубическую похожа. Но я не сильно алгоритм смотрел, скорее всего квадратичная всё-таки.
0
easybudda
Модератор
Эксперт CЭксперт С++
9695 / 5645 / 963
Регистрация: 25.07.2009
Сообщений: 10,850
04.10.2011, 15:13 #40
Цитата Сообщение от Deviaphan Посмотреть сообщение
Но я не сильно алгоритм смотрел
Цитата Сообщение от easybudda Посмотреть сообщение
int * allmost_top(const int * arr, size_t size, int absTop)
Возвращает указатель на максимальный, но меньше, чем absTop элемент массива, или NULL, если все элементы больше или равны absTop.
Цитата Сообщение от easybudda Посмотреть сообщение
int * find_same(const int * arr, size_t size, int value)
ищет элемент со значением value в массиве после найденного "почти максимального"
В самом лучшем случае
9, 9, 8, 7, 6...
понадобится один проход по массиву и следующим же шагом всё закончится. Что, разумеется, не служит показателем "замечательности" алгоритма.
0
Merovingian
54 / 54 / 5
Регистрация: 24.09.2011
Сообщений: 149
04.10.2011, 15:57 #41
Цитата Сообщение от Deviaphan Посмотреть сообщение
Не вдавался в размерности, но похоже, что для каждого элемента происходит два линейных поиска (find_some и allmost_top), так что сложность на кубическую похожа. Но я не сильно алгоритм смотрел, скорее всего квадратичная всё-таки.
Конечно O(n*n) !
0
softmob
1248 / 698 / 155
Регистрация: 20.02.2010
Сообщений: 1,035
04.10.2011, 17:36 #42
посмотрите, а если так:
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
#include <iostream>
using namespace std;
 
int main(void)
{
    int n,max,k,f=0;
    cout << "vvedite n: "; cin >> n;
    int *a = new int[n];
    for (int i=0;i<n;i++)
    {
        cout << "vvedite a[" << i << "]: ";
        cin >> a[i];
    }
    for (int i=0;i<n;i++)
    {
        max=INT_MIN;
        for(int j=i;j<n;j++)
        {
            if (a[j]>max) { max=a[j];  k=j; }
        }
 
        swap(a[i],a[k]);
        if ((i) && (a[i]==a[i-1]))  { f=1;  break; }
    }
    delete [] a;
    if (f)
    {cout << max  << endl;}
    else    
    {cout << "takogo jelementa v massive net" << endl;}
    system ("pause");
}
0
Thinker
Эксперт С++
4228 / 2202 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
04.10.2011, 18:26 #43
Цитата Сообщение от easybudda Посмотреть сообщение
Кстати, Thinker, буду признателен, если хорошую на ваш взгляд литературу подскажете...
А на какую тему литературу? Эта:
http://www.cyberforum.ru/showthread.php?p=1950320

Добавлено через 1 минуту
Цитата Сообщение от fasked Посмотреть сообщение

Не по теме:

Thinker, теоретически, да. Есть же еще и распределенные вычисления

Смейтесь-смейтесь, об опытах с DES и миллионе долларах слышали, наверное.
0
easybudda
Модератор
Эксперт CЭксперт С++
9695 / 5645 / 963
Регистрация: 25.07.2009
Сообщений: 10,850
04.10.2011, 18:49 #44
Цитата Сообщение от Thinker Посмотреть сообщение
А на какую тему литературу?
Теория алгоритмов. Про информационную безопасность я мало-мальски в курсе - одмин всё-таки...
В прочем уже нашёл на эту тему увлекательную книжку: Колмогоров А. Н. Теория информации и теория алгоритмов. На википедии в списке литературы значится...
0
Thinker
Эксперт С++
4228 / 2202 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
04.10.2011, 18:59 #45
Цитата Сообщение от easybudda Посмотреть сообщение
Теория алгоритмов.
Макконелл. Основы современных алгоритмов.
Вирт. Алгоритмы и структуры данных.
Гасфилд. Строки, деревья и последовательности в алгоритмах.
Романовский. Дискретный анализ.

Возможно, что еще лучшие книги есть.
1
04.10.2011, 18:59
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.10.2011, 18:59
Привет! Вот еще темы с ответами:

Определить максимальное из чисел, встречающихся в заданной матрице более одного раза - C++
максимальное из чисел, встречающихся в заданной матрице более одного раза. Добрый вечер, есть программка, все компил., но после...

Определить максимальное из чисел, встречающихся в заданной матрице более одного раза - C++
Дана целочисленная прямоугольная матрица.Определить: Максимальное из чисел, встречающихся в заданной матрице более одного раза ...

Определить максимальное из чисел, встречающихся в заданной матрице более одного раза - C++
Здравствуйте!Помогите пожалуйста решить задачу. Дана целочисленная матрица. Определить максимальное из чисел, встречающихся в заданной...

Найти максимальное число из, встречающихся в матрице более одного раза - C++
Хей. Есть рабочая программа, но для её полной правильности в ней нужно использовать Функцию или процедуру. Задание: Найти максимальное...


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

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

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