Помощь - Поиск - Пользователи - Календарь
Полная версия: Одномерный массив - вроде бы просто?
Форум «Всё о Паскале» > 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) ..
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.