k-й элемент массива

[shukshin]

Добрый вечер, участники форума!
И это снова я, если вы меня не забыли
На этот раз задача вывести k-ый по возрастанию элемент массива.
Сортировать нельзя, менять массив нельзя, заводить новый - правильно, нельзя. Нужно исхитриться.
Загвоздка в том, что, например,в массиве 1, 2, 1, 3 - второй по возрастанию элемент - 1. Т.е. нужен второй элемент не по значению, а по позиции в отсортированном массиве. (А сортировать нельзя).
Мой код разумеется очень плохой, ну хоть идея какая-то.
Написана функция:

1. int k_item(int a[],int k) 
2. { 
3.     int item=0; 
4.     int j=0; 
5.     int i=0; 
6.     int count=0; 
7.     int min,max,prev_min; 
8.     min=MIN(a); 
9.      
10.         while(count<k) 
11.     { 
12.         prev_min=min;   
13.  
14.             while(i<10) //Эта штука на случай повторения элементов 
15.             { 
16.                 if(a[i]==min) 
17.                 { 
18.                     count++; 
19.  
20.                     if(count>=k) 
21.                     { 
22.                         break; 
23.                     } 
24.                 } 
25.                 i++; 
26.             } 
27.  
28.             if(count>=k)     
29.         { 
30.             break; 
31.         } 
32.         min=MIN_next(a,prev_min);    
33.         count++; 
34.     } 
35.      
36.     return min; 
37. } 

И две подфункции MIN - ищет минимум, и MIN_next ищет минимум строго больше некоторого числа.
На счет первой прошу не сомневаться А вот вторая:
MIN_next:

1. int MIN_next(int a[],int E) 
2. { 
3.  
4. int ind=0; 
5. int min; 
6.  
7. while(a[ind]<=E)  
8. { 
9.     ind++; 
10. } 
11.  
12. min=a[ind]; 
13.  
14. ind=0; 
15.  
16.  while(ind<10) 
17.     { 
18.         if((a[ind]<min)&&(a[ind]>E)) 
19.         { 
20.         min=a[ind]; 
21.         } 
22.          
23.         ind++; 
24.     } 
25.  
26.  return min; 
27. } 

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

[_Ivana]

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

[Sphinx Pinastri]

Вам нужна "k-ая порядковая статистика". Посмотрите, что уже есть на эту тему в сети.

[Alexu007]

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

[arseniiv]

Alexu007 в сообщении #776799 писал(а):

if((A - B) == X)

Опять кошмар какой-то.

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

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

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

[shukshin]

arseniiv, спасибо, попробую!
_Ivana, конечно открывал, без паники
Alexu007, попробую вникнуть.

[Alexu007]

В первом проходе по циклу считаешь только минимальные значения. Во втором проходе - следующие за минимальными. В третьем - следующие за следующими, игнорируешь всё что меньше, потому что их уже подсчитали. По-моему ничего сложного.

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

[arseniiv]

Alexu007, у ТС прямым текстом написано:

shukshin в сообщении #776621 писал(а):

Сортировать нельзя, менять массив нельзя, заводить новый - правильно, нельзя.

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

[_Ivana]

arseniiv зависит от ситуации. Массив может занимать почти всю имеющуюся память (все 128 байт ) и при этом надо сохранить его без изменений.

[arseniiv]

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

[Alexu007]

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;

[arseniiv]

Зачем вы выложили полное решение? Алгоритм и так уже был описан.

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

[Alexu007]

Без решения вы не поверите, скажете, что пузырьком рассортировал. Скучно, в субботу вечером делать нечего... да и автор темы вроде потерял интерес...

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

[arseniiv]

Alexu007 в сообщении #777312 писал(а):

Без решения вы не поверите

Во что?

Alexu007 в сообщении #777312 писал(а):

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

Спасибо, я знаю. Сам нередко рисую формочки в Visual C#. Но всему же своё место — тут форма совершенно лишняя.

Alexu007 в сообщении #777312 писал(а):

Не люблю я консоль.

Что там такого страшного? Содержимое вашего обработчика события нажатия кнопки на раз переписывается в содержимое main, присвоение к Label.Caption — в вывод.

[Toucan]

Alexu007, предупреждение за размещение на форуме полного решения учебной задачи.