Форум программистов, компьютерный форум CyberForum.ru

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.78
LeoDiz
0 / 0 / 0
Регистрация: 03.12.2011
Сообщений: 3
#1

Найти разные элементы масива - C++

03.12.2011, 19:19. Просмотров 1132. Ответов 24
Метки нет (Все метки)

Здравствуйте, есть задача дана целочисленная последовательность (одномерный массив целых чисел). Написать программу нахождения количества различных элементов этой последовательности, уже 2 недели думаю никак не могу сделать. Мое решение:
C++
1
2
3
4
5
6
7
8
9
10
11
int kolovo(int mas[], int n)
 {
     int k=0;
     for(int j=0; j<n; j++)
         for(int i=1; i<n; i++)
             if(mas[j]!=mas[i])
                 k=k+1;
        
 
     return k;
 }
Выводит вообще непонятное количество, пробивал посчитать на листочке но источник проблемы так и не нашел. Видел на этом же форуме решение задачи но только на C# там ничего не понимаю.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.12.2011, 19:19     Найти разные элементы масива
Посмотрите здесь:

Разные элементы. C++
Элементы масива C++
Вывести разные элементы матрицы C++
Расположить элементы масива по схеме C++
Для масива 7 на 7 найти строки з максимальным и минимальным елементом и поменять их местами C++
C++ Массив: Найти сумму элементов динамического масива действительных чисел
C++ Составить программу размещающая элементы масива в возврастающем порядке.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
n00b.vcxproj
Кодер
47 / 46 / 2
Регистрация: 10.10.2010
Сообщений: 229
03.12.2011, 19:31     Найти разные элементы масива #2
Цитата Сообщение от LeoDiz Посмотреть сообщение
int i=1
Счет индексов в массиве начинается с нуля. Возможно что то не досчитывает.
C++
1
int i=0;
и
Цитата Сообщение от LeoDiz Посмотреть сообщение
k=k+1;
на будующее, проще делать так
C++
1
k++;
явных ошибок вроде бы нет, если цель с учётом повторений, то необходимо добавить массив или вектор и в нем размещать уже просмотренные циклом числа, иначе (если такое число в цикле есть) следующий цикл.
go
Эксперт C++
3586 / 1366 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
03.12.2011, 19:33     Найти разные элементы масива #3
C
1
2
3
4
5
6
7
8
for ( i=0; i < size; i++)
{
         for ( j = 0; j<size;j++)
             if  (  (arr[i]==arr[j]) && (i!=j) )
                  break; 
         if ( j==size )
             printf ("%5d", arr[i]);
}
taras atavin
Ушёл с форума.
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
03.12.2011, 19:39     Найти разные элементы масива #4
{1, 2,3 ,4 ,5}. Элементов 5, все разные. Значит разных элементов 5. Теперь что делает твой код, если даже исправить диапазон:
k=0, i=0, j=0:
a[0]==a[0], нифига не делаем.
k=0, i=1, j=0:
a[0]!=a[1], k=k+1=1.
k=1, i=2, j=0:
a[0]!=a[2], k=k+1=2.
k=2, i=3, j=0:
a[0]!=a[3], k=k+1=3.
k=3, i=4, j=0:
a[0]!=a[4], k=k+1=4.
k=4, i=0, j=1:
a[1]!=a[0], k=k+1=5.
k=5, i=1, j=1:
a[1]==a[1], нифига не делаем.
k=5, i=2, j=1:
a[1]!=a[2], k=k+1=6.
k=6, i=3, j=1:
a[1]!=a[3], k=k+1=7.
k=7, i=4, j=1:
a[1]!=a[4], k=k+1=8.
k=8, i=0, j=2:
a[2]!=a[0], k=k+1=9.
k=9, i=1, j=2:
a[2]!=a[1], k=k+1=10.
k=10, i=2, j=2:
a[2]==a[2], нифига не делаем.
k=10, i=3, j=2:
a[2]!=a[3], k=k+1=11.
k=11, i=1, j=2:
a[2]!=a[4], k=k+1=12.
k=12, i=0, j=3:
a[3]!=a[0], k=k+1=13.
k=13, i=1, j=3:
a[3]!=a[1], k=k+1=14.
k=14, i=2, j=3:
a[3]!=a[2], k=k+1=15.
k=15, i=3, j=3:
a[3]==a[3], нифига не делаем.
k=15, i=4, j=3:
a[3]!=a[4], k=k+1=16.
k=16, i=0, j=4:
a[4]!=a[0], k=k+1=17.
k=17, i=1, j=4:
a[4]!=a[1], k=k+1=18.
k=18, i=2, j=4:
a[4]!=a[2], k=k+1=19.
k=19, i=3, j=4:
a[4]!=a[3], k=k+1=20.
k=20, i=4, j=4:
a[4]==a[4], нифига не делаем.
k=20. Для этого не нужен ни комп, ни бумага, я проанализировал всё в уме менее, чем за 100 миллсекунд, дольше записывал.

Добавлено через 1 минуту
Цитата Сообщение от n00b.vcxproj Посмотреть сообщение
k++;
++k. И в заголовке тоже ++i, ++j.
n00b.vcxproj
Кодер
47 / 46 / 2
Регистрация: 10.10.2010
Сообщений: 229
03.12.2011, 19:43     Найти разные элементы масива #5
Цитата Сообщение от taras atavin Посмотреть сообщение
k++;
++k. И в заголовке тоже ++i, ++j.
разницы нет.
Thinker
Эксперт C++
4220 / 2194 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
03.12.2011, 19:43     Найти разные элементы масива #6
go, сложность вашего алгоритма примерно n^2, можно сделать n^2/2, а при определенных обстоятельствах и n)
taras atavin
Ушёл с форума.
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
03.12.2011, 19:46     Найти разные элементы масива #7
Цитата Сообщение от n00b.vcxproj Посмотреть сообщение
разницы нет.
Есть. k++ - намеренная пессимизация, тогда уж пиши k=k*1+1*k/k и удивляйся глюкам переполнения в середине диапазона.
n00b.vcxproj
Кодер
47 / 46 / 2
Регистрация: 10.10.2010
Сообщений: 229
03.12.2011, 19:47     Найти разные элементы масива #8
Цитата Сообщение от taras atavin Посмотреть сообщение
Есть. k++ - намеренная пессимизация, тогда уж пиши k=k*1+1*k/k и удивляйся глюкам переполнения в середине диапазона.
спасибо за инфу. но я делаю так всегда и никакого переполнения, как Вы сказали, не возникает.
taras atavin
Ушёл с форума.
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
03.12.2011, 19:49     Найти разные элементы масива #9
Нет, про переполнения я прогнал. Но тормозить будет при любом понижении автоматической оптимизации.
LeoDiz
0 / 0 / 0
Регистрация: 03.12.2011
Сообщений: 3
03.12.2011, 19:51  [ТС]     Найти разные элементы масива #10
Спасибо большое, очень выручили!
go
Эксперт C++
3586 / 1366 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
03.12.2011, 20:00     Найти разные элементы масива #11
Thinker, Вы всегда пишете про сложность, но редко вылаживаете алгоритмы
Напишите, интересно посмотреть
Thinker
Эксперт C++
4220 / 2194 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
03.12.2011, 20:04     Найти разные элементы масива #12
C++
1
2
3
4
5
6
7
for ( i = 0; i < size; ++i)
{
   for ( j = i + 1; j < size && a[i] != a[j]; ++j)
      ;
   if (j >= size)   
      printf ("%5d", a[i]);
}
taras atavin
Ушёл с форума.
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
03.12.2011, 20:05     Найти разные элементы масива #13
И никогда не объявляй переменные в теле циклов. В первом посте i объявлена в заголовке цикла по i, а он целиком находится в теле цикла по j.
go
Эксперт C++
3586 / 1366 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
03.12.2011, 20:14     Найти разные элементы масива #14
Thinker, ???
попробуйте
C
1
int a[]={1,2,2,3,4,5};
Thinker
Эксперт C++
4220 / 2194 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
03.12.2011, 20:17     Найти разные элементы масива #15
Цитата Сообщение от go Посмотреть сообщение
Thinker, ???
попробуйте
C
1
int a[]={1,2,2,3,4,5};
А что не так, что алгоритм выводит? если количество различных элементов, а не их значения, то так:

C++
1
2
3
4
5
6
7
8
count = 0;
for ( i = 0; i < size; ++i)
{
   for ( j = i + 1; j < size && a[i] != a[j]; ++j)
      ;
   if (j >= size)
      ++count;   
}
go
Эксперт C++
3586 / 1366 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
03.12.2011, 20:20     Найти разные элементы масива #16
Код
1   2   3   4   5
двойка лишняя, и это не удивительно

Добавлено через 2 минуты
Цитата Сообщение от Thinker Посмотреть сообщение
count = 0;
А при чем здесь это?

мы то вот что делаем

Цитата Сообщение от LeoDiz Посмотреть сообщение
Найти разные элементы масива
Thinker
Эксперт C++
4220 / 2194 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
03.12.2011, 20:20     Найти разные элементы масива #17
Цитата Сообщение от go Посмотреть сообщение
Код
1   2   3   4   5
двойка лишняя, и это не удивительно
Ну так это учитано, алгоритм же вывел 1 2 3 4 5, так и должно быть)
go, ТС количество просил. Но это не важно, можно и так, и так)
go
Эксперт C++
3586 / 1366 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
03.12.2011, 20:24     Найти разные элементы масива #18
вот мой алгоритм Найти разные элементы масива, вы сказали сложный и предложили свой

Добавлено через 1 минуту
Thinker, мы должны вывести были только разные элементы, т.е. те, которые встречаются 1 раз!!!

Добавлено через 26 секунд
Цитата Сообщение от Thinker Посмотреть сообщение
Ну так это учитано, алгоритм же вывел 1 2 3 4 5, так и должно быть)
наверное, мы о разных вещах говорим

Добавлено через 47 секунд
http://codepad.org/ehWgyuXq

Добавлено через 54 секунды
Цитата Сообщение от Thinker Посмотреть сообщение
go, ТС количество просил. Но это не важно, можно и так, и так)
но я не количество вывожу, и я его не считаю даже

Цитата Сообщение от go Посмотреть сообщение
Thinker, мы должны вывести были только разные элементы, т.е. те, которые встречаются 1 раз!!!
Thinker
Эксперт C++
4220 / 2194 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
03.12.2011, 20:29     Найти разные элементы масива #19
go, но ведь задание
Цитата Сообщение от LeoDiz Посмотреть сообщение
Написать программу нахождения количества различных элементов
означает, что из 1 2 2 3 4 5 мы выбираем
1 2 3 4 5
А если, действительно, найти элементы, встречающиеся ровно один раз (тогда оно бы так и звучало), то ваш алгоритм без дополнительной информации о массиве можно оптимизировать лишь так:
применить сортировку qsort, а затем искать такие элементы. сложность будет O(nlog(n))
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.12.2011, 20:50     Найти разные элементы масива
Еще ссылки по теме:

Найти сумму элементов масива, которые находятся до максимального элемента C++
Отсортировать только положительные элементы масива по росту C++
Заполнение масива по формуле и нахождение наименьшего положительного элемента масива C++
C++ Найти шесть найменшых элементов масива, пользуясь функцией сортировки
C++ Как удалить элементы из масива?

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

Или воспользуйтесь поиском по форуму:
go
Эксперт C++
3586 / 1366 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
03.12.2011, 20:50     Найти разные элементы масива #20
Цитата Сообщение от Thinker Посмотреть сообщение
А что не так, что алгоритм выводит? если количество различных элементов, а не их значения, то так:
Выводит 5 , а надо то 4
http://codepad.org/MeYx8pI4
Yandex
Объявления
03.12.2011, 20:50     Найти разные элементы масива
Ответ Создать тему
Опции темы

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