Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C++ Builder > Повторение числа в масиве

Автор: max07 18.11.2005, 13:34

Добрый день,

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

Код


  int k = 0;
  int A[7] = {2,1,1,1,2,1,2};
  for(int i = 0; i < 7; i++) {
   for(int j = i; j < 7; j++) {
    if(A[i] == A[j])
      k++;
   }
  }
  Label1->Caption = k;

Как можно реализовать эту проверку?
Спасибо.

Автор: _hunter 18.11.2005, 13:45

обнуляй k после первого цикла

Автор: max07 18.11.2005, 14:31

Так к будет тогда 0 равен... Или я не так понял? Первый это с i или j?

Автор: _hunter 18.11.2005, 14:41

Цитата

Так к будет тогда 0 равен... Или я не так понял?

дык для этого k++ есть

Цитата

Первый это с i или j?

упс... согласен -- протупил...
после нулевого перед первым.

Автор: max07 18.11.2005, 16:50

Код


  int k;
  int A[7] = {2,1,1,1,2,1,2};
  for(int i = 0; i < 7; i++) {
   k = 0;
   for(int j = i; j < 7; j++) {
    if(A[i] == A[j])
      k++;
   }
  }

так чтоли? тогда резултат 1, а должно быть 4... Может по другому както?

Автор: _hunter 18.11.2005, 17:27

само-собой 1: у тебя последних двоек сколько? правильно, одна.
ты уже пройденные элементы обнуляй.
+ такой алгоритм у тебя запомнит только последнюю проверку => добавь еще одну переменную для сверки

Автор: max07 20.11.2005, 20:19

Так вот меня и интересует куда именно её добавить и какая проверка?

Автор: AntonChik 21.11.2005, 06:06

по-моему лучше сделать так:

Код


  int max,maxi;
  int A[7] = {2,1,1,1,2,1,2};
  int b[7];// неплохо бы еще сразу же обнулить этот массив
  for(int i = 0; i < 7; i++) b[A[i]]++;
  max=b[0];
  for( i = 1; i < 7; i++) if(  b[i]>max ){max=b[i];maxi=i;}
  Label1->Caption = A[maxi];

сам не компилял, но думаю мысль понятна...

Автор: Neitron 21.11.2005, 12:59

Я сам хотел предложить этот способ. Но он не эффективен.

Автор: Mayk 21.11.2005, 13:31

Цитата(Neitron @ 21.11.2005, 16:59)

Я сам хотел предложить этот способ. Но он не эффективен.

Почему же? Получается 2n [3n, если пообнулять], что гораздо меньше n(n+1)/2.
Короче говоря o(n) < o(n*n)

Правда если числа идут в разброс (типа {435,23243223,-2321}), то можно map юзать.
Так найдем максимум лишь за логарифмическое время.Но оно опять же лучеше чем n*n.

Автор: AntonChik 23.11.2005, 07:07

Цитата(Neitron @ 21.11.2005, 12:59)

Я сам хотел предложить этот способ. Но он не эффективен.

ладно, уговорил. делаем в один проход

Код


  int max,maxi;
  int A[7] = {2,1,1,1,2,1,2};
  int b[7];// неплохо бы еще сразу же обнулить этот массив
  max=0;
  for(int i = 0; i < 7; i++) 
 {
 b[A[i]]++;
 if(b[A[i]]>max ){max=b[A[i]];maxi=A[i];} 
 }
 Label1->Caption = maxi;

опять же сам не компилял, но должно поехать...

Автор: Exekutor 26.11.2005, 11:23

Код