VPF::Что нужно подтянуть? - Форум программистов

Teleport

Дата 21.6.2011, 12:16 (ссылка)

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

Загрузка ...

Опытный

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

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

asmdzen, не знаю кто из нас прав smile

Твою логику понял.

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

ShadowC

Дата 3.10.2011, 00:38 (ссылка)

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

Загрузка ...

Шустрый

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

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

извеняюсь за некропостинг,но заинтерисовала задача,решил попробовать решить,вот что пришло на ум

Код


#include <iostream>

using namespace std;

int main()
{
       const int size = 10;
        int arr[size] = {10, 1, 1, 3, 1, 3, 1, 8, 9, 2};
        int count = 0;
        int g=0;

for(int i=0;i<size;i++){
g=0;
for(int j=i-1;0<=j;j--){
if(arr[i]==arr[j])
g=1;
}
if(g!=1)
count++;         
}
cout<<count;
        system("PAUSE");
        return 0;
}

что скажите по поводу такого алгаритма решения
алгоритм построен на том,что программа берет массив и проверяет все элементы массива предшествующие этому массива и если не находит такого-же то инкрементирует счетчик,наверное можно было решить более красиво с таким же алгаритмом,у меня вышло весьма неуклюже

Это сообщение отредактировал(а) ShadowC - 3.10.2011, 00:43

volatile

Дата 3.10.2011, 01:21 (ссылка)

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

Загрузка ...

Эксперт

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

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

Цитата(ShadowC @ 3.10.2011, 00:38

)

что скажите по поводу такого алгаритма решения

ShadowC, время выполнения вашего алгоритма N^2.
Чтобы почувствовать нужно взять большой массив.
Если в массиве миллион элементов, то понадобится порядка 10^12 итераций.

Другими словами программа будет работать целый день, тогда как можно все сделать за 1 минуту.

ShadowC

Дата 3.10.2011, 15:04 (ссылка)

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

Загрузка ...

Шустрый

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

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

Цитата(volatile @ 3.10.2011, 01:21)

Цитата(ShadowC @ 3.10.2011, 00:38

)

что скажите по поводу такого алгаритма решения

ну наверное можно даже с моими знаниями(8-ая глава книги дейтлов),но я сам обучаюсь без учителя,поэтому у меня сейчас не стоит вопрос об эффективности программ,а все силы направлены на то что бы решить задачу,думаю когда поднатаскаюсь до нормального уровня там можно будет и быстродействие подумать...

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

Это сообщение отредактировал(а) ShadowC - 3.10.2011, 15:07

bsa

Дата 3.10.2011, 15:33 (ссылка)

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

Загрузка ...

Эксперт

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

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

Цитата(ShadowC @ 3.10.2011, 16:04

)

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

Этот вариант был давно уже предложен. Правда, он тоже не особо оптимален из-за использования двусвязного списка.

Код

#include <iostream>
#include <iterator>
#include <algorithm>

int main()
{
    int data[] = {1, 2, 3, 3, 2, 1};
    std::sort(data, data + sizeof(data)/sizeof(*data));
    std::copy(data, std::unique(data, data + sizeof(data)/sizeof(*data)), std::ostream_iterator<int>(std::cout, " "));
    return 0;
}

Это сообщение отредактировал(а) bsa - 3.10.2011, 15:42

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

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

ShadowC

Дата 3.10.2011, 15:37 (ссылка)

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

Загрузка ...

Шустрый

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

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

Цитата(bsa @ 3.10.2011, 15:33)

Цитата(ShadowC @ 3.10.2011, 16:04

)

Этот вариант был давно уже предложен.

я пренципиально не читал тему и думал сам,а то так не интересно...
кстате bsa ты опытный в этом деле у меня к тебе вопрос ну и ко всем кто на него может ответить,какой самый быстрый алгоритм сортировки?

Это сообщение отредактировал(а) ShadowC - 3.10.2011, 15:52

SolRus

Дата 3.10.2011, 21:03 (ссылка)

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

Загрузка ...

Новичок

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

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

хоть вопрос не мне, все равно кой чего отпишу:

Цитата(ShadowC @ 3.10.2011, 15:37)

какой самый быстрый алгоритм сортировки?

если сильно интересует эта тема читай книгу "Искусство_программирования" Дональда Кнута, том3

если побыстрому то на вики есть кое-что

я точно незнаю какой, оно вроде зависит от того сколько элементов

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