2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 k-й элемент массива
Сообщение17.10.2013, 22:10 
Добрый вечер, участники форума!
И это снова я, если вы меня не забыли :D
На этот раз задача вывести k-ый по возрастанию элемент массива.
Сортировать нельзя, менять массив нельзя, заводить новый - правильно, нельзя. Нужно исхитриться.
Загвоздка в том, что, например,в массиве 1, 2, 1, 3 - второй по возрастанию элемент - 1. Т.е. нужен второй элемент не по значению, а по позиции в отсортированном массиве. (А сортировать нельзя).
Мой код разумеется очень плохой, ну хоть идея какая-то.
Написана функция:
код: [ скачать ] [ спрятать ]
  1. int k_item(int a[],int k) 
  2.     int item=0; 
  3.     int j=0; 
  4.     int i=0; 
  5.     int count=0; 
  6.     int min,max,prev_min; 
  7.     min=MIN(a); 
  8.      
  9.         while(count<k) 
  10.     { 
  11.         prev_min=min;   
  12.  
  13.             while(i<10) //Эта штука на случай повторения элементов 
  14.             { 
  15.                 if(a[i]==min) 
  16.                 { 
  17.                     count++; 
  18.  
  19.                     if(count>=k) 
  20.                     { 
  21.                         break; 
  22.                     } 
  23.                 } 
  24.                 i++; 
  25.             } 
  26.  
  27.             if(count>=k)     
  28.         { 
  29.             break; 
  30.         } 
  31.         min=MIN_next(a,prev_min);    
  32.         count++; 
  33.     } 
  34.      
  35.     return min; 


И две подфункции MIN - ищет минимум, и MIN_next ищет минимум строго больше некоторого числа.
На счет первой прошу не сомневаться :D А вот вторая:
MIN_next:
код: [ скачать ] [ спрятать ]
  1. int MIN_next(int a[],int E) 
  2.  
  3. int ind=0; 
  4. int min; 
  5.  
  6. while(a[ind]<=E)  
  7.     ind++; 
  8.  
  9. min=a[ind]; 
  10.  
  11. ind=0; 
  12.  
  13.  while(ind<10) 
  14.     { 
  15.         if((a[ind]<min)&&(a[ind]>E)) 
  16.         { 
  17.         min=a[ind]; 
  18.         } 
  19.          
  20.         ind++; 
  21.     } 
  22.  
  23.  return min; 

В связи с этим всем у меня два вопроса:
1)Как проще-то надо было сделать?
2)Что бы доработать в самой первой функции, а то она ж не работает такая этакая.

 
 
 
 Re: k-й элемент массива
Сообщение17.10.2013, 22:33 
А у меня к вам встречные два вопроса:
1) из каких соображений вы полностью игнорируете рекомендации, которые вам давали неоднократно?
2) вы хоть раз открывали букварь Керригана/Риччи?

 
 
 
 Re: k-й элемент массива
Сообщение18.10.2013, 01:39 
Аватара пользователя
Вам нужна "k-ая порядковая статистика". Посмотрите, что уже есть на эту тему в сети.

 
 
 
 Re: k-й элемент массива
Сообщение18.10.2013, 13:47 
Первый проход массива - считаем самые маленькие цифры массива, затем следующие и так далее до k. А чтобы при следующих сравнениях не считать те, что уже посчитаны - сравниваем не if(A < B), а if((A - B) == X)

 
 
 
 Re: k-й элемент массива
Сообщение18.10.2013, 15:16 
Alexu007 в сообщении #776799 писал(а):
if((A - B) == X)
Опять кошмар какой-то. :shock:

Можно сохранить индекс и значение текущего минимума, после этого можно легко перебрать все равные ему, дальше перебирать бо́льшие элементы и так до самого конца.

-- Пт окт 18, 2013 18:18:21 --

При этом никаких элементов отдельно от массива сохранять не нужно (значение минимума тоже можно не сохранять, но оно упрощает дело).

 
 
 
 Re: k-й элемент массива
Сообщение18.10.2013, 19:45 
arseniiv, спасибо, попробую!
_Ivana, конечно открывал, без паники :D
Alexu007, попробую вникнуть.

 
 
 
 Re: k-й элемент массива
Сообщение18.10.2013, 23:34 
В первом проходе по циклу считаешь только минимальные значения. Во втором проходе - следующие за минимальными. В третьем - следующие за следующими, игнорируешь всё что меньше, потому что их уже подсчитали. По-моему ничего сложного.

Задача учебная? Интуитивно проще отсортировать и тупо подсчитать. Но скорее всего сложность вычислений будет одинакова, независимо от алгоритма.

 
 
 
 Re: k-й элемент массива
Сообщение19.10.2013, 15:22 
Alexu007, у ТС прямым текстом написано:
shukshin в сообщении #776621 писал(а):
Сортировать нельзя, менять массив нельзя, заводить новый - правильно, нельзя.

С сортировкой, конечно, эффективнее будет.

 
 
 
 Re: k-й элемент массива
Сообщение19.10.2013, 16:20 
arseniiv зависит от ситуации. Массив может занимать почти всю имеющуюся память (все 128 байт :-) ) и при этом надо сохранить его без изменений.

 
 
 
 Re: k-й элемент массива
Сообщение19.10.2013, 18:27 
Ну, когда памяти мало и нужна упорядоченность, неотсортированные массивы не применяют с самого начала. :-)

 
 
 
 Re: k-й элемент массива
Сообщение19.10.2013, 19:05 
Код:
void __fastcall TForm1::Button1Click(TObject *Sender)
{

int X[20] = {9,2,3,5,6,7,9,3,1,2,7,5,0,6,1,1,3,2,9,1};

int m, n;

int min, next, Cx;

AnsiString str;


//массив на экран
for(int i = 0; i < 20; i++) str += IntToStr(X[i]) + ", ";

Label1->Caption = str;



str = "";



for(n = 0; n < 20; n++)
  {


  // находим минимальный член массива и количество
  m = 1;
  min = X[0];

  for(int i = 1; i < 20; i++)
    {
    if(X[i] < min) {min = X[i]; m = 1;}
    else if(X[i] == min) m++;
    }

  next = min;
  Cx = m;

  //ShowMessage(IntToStr(min) + "  " + IntToStr(Cx));


  //находим следующий член массива и количество
  while(Cx < n+1)
  {
  m = 1;
  next = X[0];

  for(int i = 1; i < 20; i++)
    {
    if(X[i] <= min) continue;
    if(X[i] < next) {next = X[i]; m = 1;}
    else if(X[i] == next) m++;
    }

  Cx += m;
  min = next;
  }


str += "X[" + IntToStr(n) + "] = " + IntToStr(next) + "\n";
}

Label2->Caption = str;



Изображение

 
 
 
 Re: k-й элемент массива
Сообщение19.10.2013, 19:31 
Зачем вы выложили полное решение? Алгоритм и так уже был описан.

Вдобавок, код можно было оформить лучше (не только использовав теги syntax), и не использовать формы и их скриншоты там, где они избыточны. Совершенно избыточны.

 
 
 
 Re: k-й элемент массива
Сообщение19.10.2013, 20:12 
Без решения вы не поверите, скажете, что пузырьком рассортировал. Скучно, в субботу вечером делать нечего... да и автор темы вроде потерял интерес...

Форма генерируется автоматически, програмировать её не надо. Не люблю я консоль.

 
 
 
 Re: k-й элемент массива
Сообщение19.10.2013, 22:38 
Alexu007 в сообщении #777312 писал(а):
Без решения вы не поверите
Во что?

Alexu007 в сообщении #777312 писал(а):
Форма генерируется автоматически, програмировать её не надо.
Спасибо, я знаю. Сам нередко рисую формочки в Visual C#. Но всему же своё место — тут форма совершенно лишняя.

Alexu007 в сообщении #777312 писал(а):
Не люблю я консоль.
Что там такого страшного? Содержимое вашего обработчика события нажатия кнопки на раз переписывается в содержимое main, присвоение к Label.Caption — в вывод.

 
 
 
 Re: k-й элемент массива
Сообщение20.10.2013, 00:36 
Аватара пользователя
 !  Alexu007, предупреждение за размещение на форуме полного решения учебной задачи.

 
 
 [ Сообщений: 15 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group