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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 23, средняя оценка - 4.91
dron-k
1 / 1 / 0
Регистрация: 24.03.2009
Сообщений: 24
#1

решение массива - C++

26.07.2009, 14:47. Просмотров 2739. Ответов 16
Метки нет (Все метки)

Не сочтите за сложность помочь с такой задачей:

Найти минимальное из чисел, встречающихся в целочисленном
массиве X=(x1,x2,...,xn) ровно два раза.

Если можно то пришлите алгоритм решения, или сам код!!!

Заранее спасибо!!!

Программа нужна на C
Лучшие ответы (1)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Rififi
2336 / 1051 / 44
Регистрация: 03.05.2009
Сообщений: 2,656
26.07.2009, 15:19     решение массива #2
1. отсортировать массив
2. найти первое число, повторяющееся 2 раза.
crashc
23 / 23 / 4
Регистрация: 26.07.2009
Сообщений: 414
26.07.2009, 15:23     решение массива #3
сортировка массива может проводится с помощью стандартной функции sort вот например код программы сортирующей массив
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
#include <iostream.h>
#include <algorithm>
#include <vector>
 
//---------------------------------------------------------------------------
 
#pragma argsused
 
int main(int argc, char* argv[])
{int p;
 cout<<"vvedite kol-vo elementov"<<endl;
 cin>>p;
 float *r=new float[p];
 unsigned int r_size = p;
 for(int i=0;i<p;i++)
 {cout<<"["<<i<<"]= ";
  cin>>r[i];
  }
  cout<<"----------------------------"<<endl;
  cout<<"Ishodnii massiv"<<endl;
   for(unsigned int i = 0; i < r_size; i++ ) {
     cout << r[i] << " ";
   }
   cout << endl;
  sort(r,r+r_size);
  cout<<"----------------------------"<<endl;
  cout<<"Perepisannii massiv"<<endl;
  for(unsigned int i = 0; i < r_size; i++ )
  cout<<" "<<r[i]<<endl;;
 
        cin.get();
        cin.get();
        return 0;
}
odip
Эксперт С++
7155 / 3295 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
26.07.2009, 16:04     решение массива #4
Алгоритм без сортировки массива.
Сначала искомого числа нет.

Цикл по массиву.
Для каждого индекса берем соответствующее ему значение и считаем сколько раз в массиве он встречается.
Если не встречается ровно два раза, тогда переходим к следующему.
Если встречается ровно два раза, то =>
то смотрим какое из двух чисел меньше - найденное сейчас или найденное ранее.
И сохраняем как искомое то число, которое меньше.

На выходе из цикла возможен вариант, что искомое число не найдено.
zim22
depict1
276 / 141 / 2
Регистрация: 11.07.2009
Сообщений: 606
26.07.2009, 16:33     решение массива #5
Цитата Сообщение от odip Посмотреть сообщение
Для каждого индекса берем соответствующее ему значение
что будете делать, если значения отрицательные? или равны максимальному числу int? создавать массив такой же размерности?
Цитата Сообщение от odip Посмотреть сообщение
Если не встречается ровно два раза, тогда переходим к следующему.
я правильно понял: для каждого числа нужно будет все элементы массива просматривать? O(n*n) раз необходимо будет операцию сравнения сделать
***
вобщем, не нравится мне ваш вариант
odip
Эксперт С++
7155 / 3295 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
26.07.2009, 17:01     решение массива #6
что будете делать, если значения отрицательные? или равны максимальному числу int? создавать массив такой же размерности?
В языке C массивы идут от 0.
я правильно понял: для каждого числа нужно будет все элементы массива просматривать? O(n*n) раз необходимо будет операцию сравнения сделать
Правильно.
Но даже если массив у тебя сортированный, то простейший алгоритм, который ищет в нем число, которое встречается два раза тоже будет O(n*n).
Можно конечно использовать балансированные деревья или hash-и, но это сильно усложнит эту задачу, которая скорее всего для обучения.
Зато в моем алгоритме исходный массив не изменяется.

Добавлено через 55 секунд
вопервых это программа для постороения массива в порядке возрастания
То есть условие не полное ?
Ну тогда приведи полное условие.
dron-k
1 / 1 / 0
Регистрация: 24.03.2009
Сообщений: 24
26.07.2009, 17:59  [ТС]     решение массива #7
Это условие полное. Просто я только начал учить С, поэтому никакие сложности не нужны.
zim22
depict1
276 / 141 / 2
Регистрация: 11.07.2009
Сообщений: 606
26.07.2009, 18:01     решение массива #8
Цитата Сообщение от odip Посмотреть сообщение
В языке C массивы идут от 0.
не знал. спасибо.
Цитата Сообщение от odip Посмотреть сообщение
Для каждого индекса берем соответствующее ему значение и считаем сколько раз в массиве он встречается.
расшифруйте пожалуйста эту фразу, а именно: что собой представляют соответствующие значения?
***
кстати, моя программа неправильно работает.
алгоритм std::adjacent_find находит первую пару смежных элементов. и на этом возвращает результат поиска. т.е. повторяющихся элементов может быть больше двух.
вот исправленная версия проги:
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
#include <algorithm>
#include <iostream>
 
int main()
{
  int arr[] = {4, 4, 5};
  const int array_size = sizeof(arr) / sizeof(*arr);
 
  std::sort(arr, arr + array_size);
 
  int *it = arr;
  int *it_end = arr + array_size;
  
  while ((it = std::adjacent_find(it, it_end)) != it_end) {
    if ((it + 2 != it_end) && *(it + 2) != *it) {
      std::cout << "Found: " << *it << std::endl;
      return 0;
    } else {          
      it = std::upper_bound(it, it_end, *it);
    }
  }
  std::cout << "Not found" << std::endl;
  return 0;
}
odip
Эксперт С++
7155 / 3295 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
26.07.2009, 18:04     решение массива #9
Надо было сразу сказать, что на C нужно.
Тут на C++ решения выложили

Добавлено через 2 минуты 23 секунды
расшифруйте пожалуйста эту фразу, а именно: что собой представляют соответствующие значения?
Вообщем слово индекс можно выкинуть. Я просто хотел сказать, что цикл нужно делать по индексу массива.
Берем значение и считаем сколько раз оно в массиве встречается.
zim22
depict1
276 / 141 / 2
Регистрация: 11.07.2009
Сообщений: 606
26.07.2009, 19:14     решение массива #10
Цитата Сообщение от crashc Посмотреть сообщение
функция sort работает всегда без искомых чисел т.к. она работает за счет функции vector
за счёт функции вектор говорите? это в каком месте? хочу пример!
Skirmisher
44 / 44 / 0
Регистрация: 23.05.2009
Сообщений: 92
28.07.2009, 16:03     решение массива #11
Цитата Сообщение от odip Посмотреть сообщение

Например так: 3 5 5 10 11 12 13 14 15 16
Минимальное число, которое встречается ровно два раза - это 5.
А если в массиве не встречается одинаковых чисел что тогда?
M128K145
Эксперт C++
8280 / 3499 / 143
Регистрация: 03.07.2009
Сообщений: 10,707
28.07.2009, 16:05     решение массива #12
C++
1
std::cout<<"таких элементов нет";
odip
Эксперт С++
7155 / 3295 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
28.07.2009, 16:05     решение массива #13
А если в массиве не встречается одинаковых чисел что тогда?
Печатать текст: заданное число не найдено.
zim22
depict1
276 / 141 / 2
Регистрация: 11.07.2009
Сообщений: 606
28.07.2009, 16:25     решение массива #14
Цитата Сообщение от Skirmisher Посмотреть сообщение
adjacent_find тоже из STL, если не знал.
я знаю, что он из STL (как ни странно).
акцент в другом:
в первой версии вашей программы вы отказывались использовать STL, делая ударение на том, что программист должен всё писать сам. и предложили свою версию quick sort.
Хотя она уже реализована в C standard library
во-второй же версии вы тупо использовали sort.
так топик стартеру какой из ваших рекомендаций следовать: велосипеды мастерить или STL юзать?
Skirmisher
44 / 44 / 0
Регистрация: 23.05.2009
Сообщений: 92
28.07.2009, 16:45     решение массива #15
Цитата Сообщение от zim22 Посмотреть сообщение
я знаю, что он из STL (как ни странно).
акцент в другом:
в первой версии вашей программы вы отказывались использовать STL, делая ударение на том, что программист должен всё писать сам. и предложили свою версию quick sort.
Хотя она уже реализована в C standard library
во-второй же версии вы тупо использовали sort.
так топик стартеру какой из ваших рекомендаций следовать: велосипеды мастерить или STL юзать?
STL юзать)
firefox1913
27 / 27 / 2
Регистрация: 01.07.2009
Сообщений: 58
28.07.2009, 17:23     решение массива #16
Сообщение было отмечено автором темы, экспертом или модератором как ответ
вот держи
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
#include <iostream>
#include <algorithm>
using namespace std;
class f
{
public:
   f(int i) : m(i) { }
   bool operator() (int &a)
   {
      return m==a;
   }
private:
    int m;
};
int main()
{
   int mas[]={1,23,4,6,1},size,k;
   size=sizeof(mas) / sizeof(mas[0]);
   int min=*min_element(mas,mas+size);
   f b(min);
   k=count_if(mas,mas+size,b);
   if(k==2) cout<<"est "<< min <<endl;
   else cout<<"no "<<endl;
   return 0;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.07.2009, 21:14     решение массива
Еще ссылки по теме:

решение на c++ C++
Посчитать сумму элементов массива, при которых квадратное уравнение имеет решение C++
Решение в VC++ C++
C++ Решение в С++
Как найти медиану неотсортированного массива (без использования дополнительного массива) C++

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

Или воспользуйтесь поиском по форуму:
zim22
depict1
276 / 141 / 2
Регистрация: 11.07.2009
Сообщений: 606
28.07.2009, 21:14     решение массива #17
Цитата Сообщение от firefox1913 Посмотреть сообщение
вот держи
как было бы здорово, если бы вы прочитали тему и поняли что топик стартеру нужен вариант на Си, а не на Си++
Yandex
Объявления
28.07.2009, 21:14     решение массива
Ответ Создать тему
Опции темы

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