Помощь - Поиск - Пользователи - Календарь
Полная версия: Одномерный массив - вроде бы просто?
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
Petruxa
Ребят помогите пожалуйста, второй день голову ломаю, что-то никак не выходит!
Найти три наименьших по значению элемента одномерного массива (равные не учитывать) целых чисел, введеных с клавы. Заменить их на соответствующие им индексы.
Спасибо
Lapp
Вот такой код, вроде, должен работать (не проверял).
M:=1;  { Общее число минимальных элементов }
for j:=1 to 3 do begin  { подготовка массивов минимальных элементов и номеров }
  Min[j]:=a[1];
  iMin[j]:=1
end;
for i:=2 to N do 
  for j:=1 to 3 do if a[i]<Min[j] then begin  { найден новый минимальный элемент }
    for k:=j to 2 do begin  { сдвигаем массив минимальных элементов вместе с индексами }
      Min[k+1]:=Min[k];
      iMin[k+1]:=iMin[k]
    end;
    Min[j]:=a[i];
    iMin[j]:=i;
    if (M=j) and (M<3) then Inc(M)  { увеличиваем число минимальных элементов }
    Break
  end;
for j:=1 to M do a[iMin[j]]:=iMin[j];  { замена минимальных элементов на их индексы }



Добавлено через 6 мин.
Однако, нет.. sad.gif
Уже нашел ошибку. В ситации 1, 2, 3, 4 - результат будет неверный.
Сейчас попробую исправить...
klem4
const
 n = 4;
type
  TArray = array [1..n] of Integer;
  TMinArray = array [1..3] of Integer;

const
  A: TArray = (5, 2, 1, 3);

var
  i, j, min: Integer;
  M: TMinArray;

begin

  for j := 1 to 3 do begin
    min := 1;
    for i := 2 to n do
     if (A[i] < A[min]) and ((j = 1) or (A[i] > A[M[j - 1]])) then
      min := i;
    M[j] := min;
  end;


  for i := 1 to 3 do A[M[i]] := M[i];
end. 
Lapp
Да, схема Klem4 лучше.. smile.gif
Свою я исправил (надо изначально заполнять массив минимумов максимальным элементом), но мусорить ей не хочу.

Но, Клем, у тебя все же есть ошибка.. yes2.gif Примерно такая же, как та, что я у себя исправлял. Нельзя на втором и третьем проходе брать первый номер в качестве начального.
Petruxa
'klem4' - огромное спасибо, всё работает!
Petruxa
а может лучше выложить Ваш код?
очень интересно...
Lapp
И еще одна: надо подсчитывать количество минимумов и распечатывать не все три элемента массива, а только найденные.

Все же я приведу тут свой исправленный вариант. Он отличается тем, что поиск производится за один проход.
(Не проверено!)
  Max:=a[1];
  iMax:=1;
  for i:=2 to N do if a[i]>Max then begin  { находим максимальный элемент }
    Max:=a[i];
    iMax:=i
  end;
  M:=1;  { Общее число минимальных элементов }
  for j:=1 to 3 do begin  { подготовка массивов минимальных элементов и номеров }
    Min[j]:=Max;
    iMin[j]:=iMax
  end;
  for i:=2 to N do 
    for j:=1 to 3 do if a[i]<Min[j] then begin  { найден новый минимальный элемент }
      for k:=j to 2 do begin  { сдвигаем массив минимальных элементов вместе с индексами }
        Min[k+1]:=Min[k];
        iMin[k+1]:=iMin[k]
      end;
      Min[j]:=a[i];
      iMin[j]:=i;
      if (M=j) and (M<3) then Inc(M)  { увеличиваем число минимальных элементов }
      Break
    end;
  for j:=1 to M do a[iMin[j]]:=iMin[j];  { замена минимальных элементов на их индексы }
Гость
помоему код klem4 проще и понятней, а особых изысков не нужно, думаю преподаватель не поймет smile.gif
Все равно ОГРОМНОЕ СПАСИБО !
Lapp
Цитата(Гость @ 14.03.2007 11:32) *

помоему код klem4 проще и понятней, а особых изысков не нужно, думаю преподаватель не поймет smile.gif
Все равно ОГРОМНОЕ СПАСИБО !

Согласен, я выше об этом уже сказал smile.gif. Правда, в моем тоже можно сделать упрощение: убрать массив минимумов, оставить только индексы (подсмотрено у Клема, сам почему-то не догадался smile.gif).
Вот так:
  Max:=1;
  for i:=2 to N do if a[i]>Max then Max:=i;  { находим максимальный элемент }
  M:=1;  { Общее число минимальных элементов }
  for j:=1 to 3 do Min[j]:=Max  { подготовка массива номеров минимальных элементов }
  for i:=2 to N do 
    for j:=1 to 3 do if a[i]<a[Min[j]] then begin  { найден новый минимальный элемент }
      for k:=j to 2 do Min[k+1]:=Min[k];
      Min[j]:=i;
      if (M=j) and (M<3) then Inc(M);  { увеличиваем число минимальных элементов }
      Break
    end;
  for j:=1 to M do a[Min[j]]:=Min[j];  { замена минимальных элементов на их индексы }

А что касается сдачи кода с ошибками - твое дело.. Сам исправить не можешь?
volvo
Я бы сделал вот это (для общего случая, а не только для трех минимумов):
const
  n = 11;
  m =  3;

type
  arrType = array[1 .. n] of integer;
  minType = array[1 .. m] of integer;

const
  a: arrType = (1, 2, 3, 4, 3, 2, 7, 6, 3, 3, 1);

var
  found: boolean;
  mins: minType;
  i, j, k: integer;

begin
  for i := 1 to m do mins[i] := -1;

  for i := 1 to n do begin

    { Проверяем, было ли это значение уже обработано }
    found := false;
    for j := 1 to m do
      if (mins[j] <> -1) and (a[i] = a[mins[j]]) then found := true;

    { если было - берем следующее }
    if found then continue;

    { а тут, собственно, заполняем массив минимумов }
    j := 1;
    while (j <= m) and (mins[j] <> -1) and (a[mins[j]] < a[i]) do inc(j);
    if j <= m then begin
      for k := m downto j + 1 do mins[k] := mins[k - 1];
      mins[j] := i;
    end;

  end;

  { и меняем индексы }
  for i := 1 to m do
    if mins[i] <> -1 then a[mins[i]] := mins[i];

end.
Lapp
Пока смотрел код volvo, нашел еще одну ошибку у себя.. smile.gif
Ну и, заодно, переделал на случай поиска произвольного количества минимумов (L) smile.gif

  L:=3;
  Max:=1;
  for i:=2 to N do if a[i]>Max then Max:=i;  { находим максимальный элемент }
  M:=1;  { Общее число минимальных элементов }
  for j:=1 to L do Min[j]:=Max  { подготовка массива номеров минимальных элементов }
  for i:=2 to N do 
    for j:=1 to L do if a[i]<a[Min[j]] then begin  { найден новый минимальный элемент }
      for k:=L-1 downto j do Min[k+1]:=Min[k];
      Min[j]:=i;
      if (M=j) and (M<L) then Inc(M);  { увеличиваем число минимальных элементов }
      Break
    end;
  for j:=1 to M do a[Min[j]]:=Min[j];  { замена минимальных элементов на их индексы }
klem4
Цитата
Но, Клем, у тебя все же есть ошибка.. yes2.gif Примерно такая же, как та, что я у себя исправлял. Нельзя на втором и третьем проходе брать первый номер в качестве начального.


У меня то учитывается:

Цитата
if (A[i] < A[min]) and ((j = 1) or (A[i] > A[M[j - 1]])) then


Единственное можно еще опставить
{$B-}


Или о чем ты ? Поясни, в каком случае будет ошибка.
Lapp
Проверь на массиве 1, 2, 3, 4
Твоя прога выдает индексы: 1, 1, 1

Добавлено через 5 мин.
Посмотри - я тоже сначала засовывал в минимумы первый элемент.
А потом сделал так: сначала нахожу максимальный элемент, и его использую как начальный.
В твоем случае нужно примерно так:
  Max :=1;
  for i:=2 to n do if a[i]>a[Max] then Max:=i;
  for j := 1 to 3 do begin
    min := Max;

Или предложи другой выход..
klem4
Действительно, тогда вот что сочинил:

for j := 1 to 3 do begin

    i := 1; min := 1;

    if j > 1 then begin
      while (i <= n) and (A[i] <= A[M[j - 1]]) do inc(i);
      min := i;
      i := i + 1;
    end;

    while (i <= n) do begin
      if ((j = 1) and (A[i] < A[min])) OR (j > 1) and (A[i] < A[M[j - 1]]) then
       min := i;
      inc(i);
    end;

    M[j] := min;

  end;
Lapp
Цитата(klem4 @ 14.03.2007 13:09) *

Действительно, тогда вот что сочинил:

Можно и так smile.gif
Только исправь строчку:
      while (i < n) and (A[i] <= A[M[j - 1]]) do inc(i); { убрано равентсво }

- иначе вылетает за пределы массива, если все его элементы равны.

Но все же надо как-то считать, сколько минимумов найдено - иначе не разберешься в результатах (например, проверь на 1, 1, 1, 1).. Или, как volvo, по признаку (-1) ..
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.