VPF::[C++] Определить, есть ли в массиве элементы

frenchman

Дата 3.1.2007, 21:09 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 23
Регистрация: 3.1.2007

Репутация: нет
Всего: нет

Допустим, есть массив.Надо определить, есть ли в нем элементы с одинаковым значением.
Код писать не надо, поделитесь мыслями, алгоритмом.
Надо сортировать? Можно без сортировки как-то обойтись?
Опять же, прошу без кода, только мысли, алгоритм максимум и все.

jonie

Дата 3.1.2007, 21:14 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 5613
Регистрация: 21.8.2005
Где: Владимир

Репутация: нет
Всего: 118

два вложенных for ? smile

сортировка ничего тольком не даст... накладные расходы слишком большие.
на пальцах это имхо должно выголядеть как

берем элмент 0 ... пробегаем массив от 1-ого до конца, попутно сравнивая
берем элемент1 ... пробегаем от 2-ого до конца сравнивая
...............
до конца перебора)

--------------------

Что-то не поняли? -> Напейтесь до зеленых человечков... эта сверхцивилизация Вам поможет...

frenchman

Дата 3.1.2007, 21:20 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 23
Регистрация: 3.1.2007

Репутация: нет
Всего: нет

Не слишком большое время выполнения получится?
Ну, понятно, если в массиве 5 чисел... а если мы миллиончик в массиве имеем... )) перебирать будем 999 999 чисел?

и циклов for получится (КОЛ_ВО_чисел_в_массиве - 1 ) ???

Это сообщение отредактировал(а) frenchman - 3.1.2007, 21:22

jonie

Дата 3.1.2007, 21:22 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 5613
Регистрация: 21.8.2005
Где: Владимир

Репутация: нет
Всего: 118

Цитата

Не слишком большое время выполнения получится?
Ну, понятно, если в массиве 5 чисел... а если мы миллиончик в массиве имеем... ))

а есть еще методы?) или память или скорость.

Цитата

и циклов for получится (КОЛ_ВО_чисел_в_массиве - 1 ) ???

цикла ДВА. один внешний другой в него вложенный (вложенный пробегает от N до конца массива), внешний сдвигает N вперед.

Это сообщение отредактировал(а) jonie - 3.1.2007, 21:24

--------------------

Что-то не поняли? -> Напейтесь до зеленых человечков... эта сверхцивилизация Вам поможет...

frenchman

Дата 3.1.2007, 21:25 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 23
Регистрация: 3.1.2007

Репутация: нет
Всего: нет

ok. а если жертвовать не скоростью, апамятью? тогда как?

MAKCim

Дата 3.1.2007, 21:26 (ссылка)

(нет голосов)

Загрузка ...

Воін дZэна

Профиль
Группа: Экс. модератор
Сообщений: 5644
Регистрация: 10.12.2005
Где: Менск, РБ

Репутация: 6
Всего: 207

если известен диапозон чисел в массиве
то сортировка подсчетом

--------------------

Ах, у елі, ах, у ёлкі, ах, у елі злыя волкі ©

Daevaorn

Дата 3.1.2007, 21:29 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2155
Регистрация: 29.11.2004
Где: Москва

Репутация: нет
Всего: 70

Цитата(frenchman @ 3.1.2007, 22:25

)

ok. а если жертвовать не скоростью, апамятью? тогда как?

А можно я с кодом всё-таки? smile

Код


#include <vector>
#include <map>
#include <iostream>
#include <cstdlib>

inline int random( int range_min, int range_max )
{
    return ( (double)rand() / (RAND_MAX + 1) * (range_max - range_min) + range_min );
}

int main()
{
    typedef std::vector< int > ArrayType;
    ArrayType input_array;
    input_array.reserve( 1000 );
    for( int i = 0; i < 1000; ++i )
        input_array.push_back( random( 0, 100 ) );


    typedef std::map< int, std::vector< ArrayType::size_type > > WorkMapType;
    WorkMapType work_map;

    for( int i = 0; i < input_array.size(); ++i )// для наглядности
    {
        int val = input_array[ i ];
        work_map[ val ].push_back( i );
    }

    for( WorkMapType::const_iterator iter = work_map.begin(); iter != work_map.end(); ++iter )
    {
        std::cout << "Value <" << iter->first << "> in positions:\n\t";
        for( int i = 0; i < iter->second.size(); ++i )
            std::cout << iter->second[ i ] << ' ';
        std::cout << std::endl;
    }
    return 0;    
}

frenchman

Дата 3.1.2007, 21:31 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 23
Регистрация: 3.1.2007

Репутация: нет
Всего: нет

если задаем массив с клавы?

frenchman

Дата 3.1.2007, 21:53 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 23
Регистрация: 3.1.2007

Репутация: нет
Всего: нет

если не использовать эти библиотеки :

#include <vector>
#include <map>

я их не знаЮ))) только можно сказать, взялся за с++ )))

KelTron

Дата 3.1.2007, 21:56 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 745
Регистрация: 8.10.2006
Где: Красноярск

Репутация: нет
Всего: 38

А можно еще и так : Задаем массив, создаем множество set на основе этого массива, если размер множества меньше размера массива - значит есть повторяющиеся элементы.

Не знаю, может это бредовое решение, но все таки.

P.S. Ну если без библиотек то надо еще мозги напрягать

Это сообщение отредактировал(а) KelTron - 3.1.2007, 21:57

--------------------

Тысячами незримых нитей обвивает тебя Закон. Разрубишь одну - преступник. Десять - смертник. Все - Бог.
Эвенгар Салладорский, основатель Школы Тьмы.

sergejzr

Дата 3.1.2007, 22:30 (ссылка)

(нет голосов)

Загрузка ...

Un salsero
Group Icon

Профиль
Группа: Админ
Сообщений: 13285
Регистрация: 10.2.2004
Где: Германия г .Ганновер

Репутация: 11
Всего: 360

Есть замечательная штука - хэш. Это как раз и реализовывает <map>.

Смысл таков:

Создаёшь массив "BIG" на много элементов (сколько памяти не жалко). Скажем, массив у нас длиной N.
Обнуляешь все элементы в "BIG".

Проходишь по своему массиву "INPUT" чисел. И вырешиваешь индекс в "BIG" по формуле: число%N. То есть:

Код


//cnt - количество йелементов в INPUT
for(i=0;i<cnt;i++)
{
if(BIG[INPUT[i]%N]==1) printf("duplikat! %i",INPUT[i]);
else
BIG[INPUT[i]%N]=1;
}

Из за %N ты никогда не выйдешь за рамки массива. Но тут есть опасность, что два разные числа A и B дадут одинаковый результат. Т.е A%N==B%N. Таких совпадений тем больше, чрм меньше N. (Только случае, если N>=максимальному числу из INPUT, совпадений не будет).Исходное число ты уже никак не получишь. Поэтому их целесообразно сохранять в лист на индехкс в BIG и каждый раз по листу бежать проверять.

А кодом наверное полегче будет.

Код



struct leaf
{
int num;
leaf*next;
}

leaf* BIG[N];//массив с указателями на встречавшиеся номера.

for(i=0;i<cnt;i++){
int index=INPUT[i]%N;
if(!BIG[index]==NULL) 
{
leaf* start=BIG[index];
leaf* old=start;
while (start!=NULL) //Бежим по листу
{
if(start.num==INPUT[i]) {printf("duplikat"); return;} //Такой номер уже существует у нас, заканчиваем :)
old=start;
start=start.next;
}
old.next=new leaf;
leaf.num=INPUT[i]; //Запомним, что номер встречался
leaf.next=NULL;
}

Писал "от руки" на ошибки не проверял.

--------------------

Me.
FB.
LinkedIn.
ORCID.
YT.

frenchman

Дата 3.1.2007, 22:37 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 23
Регистрация: 3.1.2007

Репутация: нет
Всего: нет

Собственно я решил задачу так :

Код


#include<iostream>
#include<conio.h>

using namespace std;

int main()
{
    const int SIZE = 5;
    int arr[SIZE];
    for(int i = 0; i < SIZE; i++)
        cin >> arr[i];
    //for(int i = 0; i < SIZE; i++)
    //    cout << arr[i]; // test
    int el = arr[0];
    int p = 0;// el-tov net
    for(int i = 1; i < SIZE; i++)
        if(el == arr[i])
        {cout << "EST"; p++;getch();return 1;}

    el = arr[1];
    
    for(int i = 2; i < SIZE; i++)
        if(el == arr[i])
            {cout << "EST"; p++;getch();return 1;}
    
    el = arr[2];

    for(int i = 3; i < SIZE; i++)
        if(el == arr[i])
            {cout << "EST"; p++;getch();return 1;}

    el = arr[3];

        if(el == arr[4])
            {cout << "EST"; p++;}
    
    if(!p) cout <<"There are no same elements in array!";

    
    getch();
    return 1;

}

По умолчанию взяв кол-во эл-тов вмассиве равным 5ти, пересравнивал каждый элемент с последующим остатком массива...

sergejzr

Дата 3.1.2007, 22:46 (ссылка)

(нет голосов)

Загрузка ...

Un salsero
Group Icon

Профиль
Группа: Админ
Сообщений: 13285
Регистрация: 10.2.2004
Где: Германия г .Ганновер

Репутация: 11
Всего: 360

Собственно - это обыкновенный перебор, но не алгоритм.

Для простоты понимания обьясню идею хэша "на пальцах":

int BIG[N];

for(i=0;i<cnt;i++)
if(BIG[INPUT[i]]==1) printf("duplikat! %i" INPUT[i]);

Добавлено @ 22:49
да, кстати:
Модератор: Название темы должно отражать ее суть!

--------------------

Me.
FB.
LinkedIn.
ORCID.
YT.

sergejzr

Дата 3.1.2007, 22:49 (ссылка)

(нет голосов)

Загрузка ...

Un salsero
Group Icon

Профиль
Группа: Админ
Сообщений: 13285
Регистрация: 10.2.2004
Где: Германия г .Ганновер

Репутация: 11
Всего: 360

Для домашних заданий, курсовых, существует "Центр Помощи".

Тема перенесена!

--------------------

Me.
FB.
LinkedIn.
ORCID.
YT.

frenchman

Дата 3.1.2007, 23:05 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 23
Регистрация: 3.1.2007

Репутация: нет
Всего: нет

Кстати, это не домашнее задание! Я для себя ... хочу научиться, взял задачник и тренируюсь...

Добавлено @ 23:06
if(BIG[INPUT[i]]==1)

можешьэту строчку подробно обьяснить? что значит?

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »