Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Алгоритмы > Два наименьших и два наибольших элемента


Автор: Guest 7.7.2005, 13:56
Как найти два наименьших и два наибольших элемента из десяти данных элементов. smile

Автор: ~FoX~ 7.7.2005, 14:01
определяем 4-е переменных, при проходе заносим в них первые 4-е элемента, дальше проверям на большее/меньшее и переоопределям при надобности......

Автор: Akina 7.7.2005, 14:02
Отсортировать по величине, взять 2 первых и 2 последних... smile

Автор: SoWa 7.7.2005, 17:19
Ну да! Методом сортировки, выбора или полного перебора.

Автор: Guest 7.7.2005, 17:37
Цитата(SoWa @ 7.7.2005, 17:19)
Ну да! Методом сортировки, выбора или полного перебора.

Попробовал завести четыре переменных, всё равно че то не робит...
А можно пример на паскале smile Плиз...

Автор: Akina 7.7.2005, 17:51
Цитата(Guest @ 7.7.2005, 18:37)
А можно пример на паскале  Плиз...

можно... в разделе "Центр помощи".

PS. А заодно можно зарегистрироваться - это совершенно бесплатно и даже не больно...

Автор: vadims 7.7.2005, 18:42
Выложи код как бы бы искал одно максимальное/минимальное число в массиве - попробую подталкнуть в нужном напралении
Или сортировку массива

Автор: Guest 7.7.2005, 19:19
Цитата(vadims @ 7.7.2005, 18:42)
Выложи код как бы бы искал одно максимальное/минимальное число в массиве - попробую подталкнуть в нужном напралении
Или сортировку массива

Вообще то с массивом я знаю как-это просто, нужно без массива и использовать "однопроходной" алгоритм ....
Вот код:
Код

uses crt;
const count_d=10;
var d,i:Integer;
    min,max:Integer;
begin
     Clrscr;
     min:=maxint; max:=-maxint;
     Write('Введите 10 целочисленных элементов:');
     for i:=1 to count_d do begin
        Read(d);
        if (min>d) then   min:=d;  
        if (max<d) then  max:=d;  
     end;
     WriteLn('Min:',min);
     WriteLn('Max:',max);
     Readkey;
end.

Так находится наименьший и наибольший элементы min и max.

Автор: vadims 7.7.2005, 19:56
Если это можешь - в чем тогда проблема ???
Только паскаль подзабыл и могут быть синтаксические ошибки, например так (но можно конечно и красоту понаводить)

uses crt;
const count_d=10;
var d,i:Integer;
array min[0..1]:Integer; //тут не помню точно синтаксис
array max[0..1]:Integer; // но 2 массива по 2 числа типа int
begin
Clrscr;

Write('Введите 10 целочисленных элементов:');

Read(d);
min[0]:=d; min[1]:= d;
max[0]:=d; max[1]:=d;


for i:=2 to count_d do begin
Read(d);

if (d<min[0]) then begin
min[1]:=min[0];
min[0]:=d;
end;
else begin
if (d<min[1]) then min[1]:=d;
end;

if (d>max[0]) then begin
max[1]:=max[0];
max[0]:=d;
end;
else begin
if (d>max[1]) then max[1]:=d;
end;

end;
WriteLn('Min:',min[0]);
WriteLn('Min:',min[1]);
WriteLn('Max:',max[0]);
WriteLn('Max:',max[1]);
Readkey;
end.

Автор: Guest 8.7.2005, 07:59
vadims, на мысль ты меня натолкнул...
Только условия пришлось немного подправить, вот так будет правильно:
Код

uses crt;
const count_d=10;
var d,i:Integer;
     min:array [0..1]of Integer;
     max:array [0..1]of Integer;
begin
     Clrscr;
     Write('Ââåäèòå 10 öåëî÷èñëåííûõ ýëåìåíòîâ:');
     for i:=1 to 2 do begin
        Read(d);
        if i=1 then begin
          min[0]:=d;
          max[0]:=d;
        end;
        if i=2 then begin
          min[1]:= d;
          max[1]:=d;
        end;
     end;
     for i:=3 to count_d do begin
     Read(d);
     if (d<min[0]) then begin
       min[1]:=min[0];
       min[0]:=d;
     end
     else if (d<min[1]) and (d<>min[0]) then
         min[1]:=d;
     if (d>max[0]) then begin
       max[1]:=max[0];
       max[0]:=d;
     end
     else if (d>max[1]) and (d<>max[0]) then
         max[1]:=d;
     end;
     WriteLn('Min:',min[0]);
     WriteLn('Min:',min[1]);
     WriteLn('Max:',max[0]);
     WriteLn('Max:',max[1]);
     Readkey;
end. 

Огромное тебе спасибо, что навёл на мысль smile

Автор: vadims 8.7.2005, 08:57
Цитата(Guest @ 8.7.2005, 07:59)
);
    for i:=1 to 2 do begin
        Read(d);
        if i=1 then begin
          min[0]:=d;
          max[0]:=d;
        end;
        if i=2 then begin
          min[1]:= d;
          max[1]:=d;
        end;
   


Излишества на мой взгляд

Автор: Guest 8.7.2005, 09:41
Цитата(vadims @ 8.7.2005, 08:57)
Цитата(Guest @ 8.7.2005, 07:59)
);
     for i:=1 to 2 do begin
        Read(d);
        if i=1 then begin
          min[0]:=d;
          max[0]:=d;
        end;
        if i=2 then begin
          min[1]:= d;
          max[1]:=d;
        end;
    


Излишества на мой взгляд

А помоему нет, если написать так:
Код

  Read(d);
          min[0]:=d;
          max[0]:=d;
          min[1]:= d;
          max[1]:=d;

И задать последовательность:1 2 3 ... 7 8 9 10, то min[0] и min[1] будут равны 1.

И ещё, если оставить вот так:
Код

if (d<min[1]) then min[1]:=d;
end;

И задать последовательность:6 5 1 2 3 1 7 8 9 10, то min[0] и min[1], тоже будут равны 1.
Поэтому:
Код

if (d<min[1]) and (d<>min[0]) then min[1]:=d;
end;


Короче говоря проверил на все виды последовательностей, и попытался предусмотреть любую из них.

Автор: Akina 8.7.2005, 10:09
вообще коли integer, то начать бы с

Код

min[0]=-32768
min[1]=-32768
max[0]=32767
max[1]=32767


и потом только считывание и сравнение.

Цитата(vadims @ 8.7.2005, 09:57)
Излишества на мой взгляд

не излишество, а ошибка. Если второе введенное число будет самым большим (или самым маленьким) - сбойнет.

Автор: vadims 8.7.2005, 10:19
Согласен что мой выбор первых max/min значений некорректен, но и твой последний вариант как и сказал Akina тоже ошибка - проше всего вернуться к твоему изначальному
Цитата(Guest @ 7.7.2005, 19:19)
min:=maxint; max:=-maxint;

хотя возможны и другие варианты

Автор: Alex101 8.7.2005, 11:17
Может так?
Код

uses Crt;
var min1,min2,max1,max2: Integer;
a,i:Integer;
begin
readln(min1);
readln(min2);
readln(max1);
readln(max2);
{*Выстроим переменные в порядке возрастания так:
min1,min2,max2,max1*}
if min2<min1 then begin
 min2:=min1 xor min2;
 min1:=min1 xor min2;
 min2:=min1 xor min2
end;
if max2>max1 then begin
 max2:=max1 xor max2;
 max1:=max1 xor max2;
 max2:=max1 xor max2
end;
if (max2<min1)
then begin
 max2:=min1 xor max2;
 min1:=min1 xor max2;
 max2:=min1 xor max2
end;

if (min2>max1)
then begin
 max1:=min2 xor max1;
 min2:=min2 xor max1;
 max1:=min2 xor max1
end;

if (min2>max2)
then begin
 max2:=min2 xor max2;
 min2:=min2 xor max2;
 max2:=min2 xor max2
end;
for i:=5 to 10 do
begin
 readln(a);
 if a<min1 then begin
  min2:=min1;
  min1:=a;
 end
 else if a<min2 then min2:=a;

 if a>max1 then begin
  max2:=max1;
  max1:=a;
 end
 else if a>max2 then max2:=a;
end;
writeln(min1,' ',min2,' ',max2,' ',max1);
end.

Проверьте, у меня компилятора нет.

Автор: vadims 8.7.2005, 11:25
Alex101
А что означает конструкция min2:=min1 xor min2 - побитовое или логическое "исключающее или" или что-то другое ???

Автор: Alex101 8.7.2005, 11:28
vadims Побитовое "исключающее ИЛИ".
Надо все три строки смотреть - это обмен переменных значениями.

Автор: Guest 8.7.2005, 11:29
Цитата(Akina @ 8.7.2005, 10:09)
вообще коли integer, то начать бы с

Код

min[0]=-32768
min[1]=-32768
max[0]=32767
max[1]=32767


и потом только считывание и сравнение.

Цитата(vadims @ 8.7.2005, 09:57)
Излишества на мой взгляд

не излишество, а ошибка. Если второе введенное число будет самым большим (или самым маленьким) - сбойнет.

И вправду сбой дает...
Как ты сказал наверное самый лучший вариант:
Код

uses crt;
const count_d=10;
var d,i:Integer;
    min:array [0..1]of Integer;
    max:array [0..1]of Integer;
begin
     Clrscr;
     min[0]:=maxint; min[1]:=maxint;
     max[0]:=-maxint; max[1]:=-maxint;
     Write('Введите 10 целочисленных элементов:');
     for i:=1 to count_d do begin
         Read(d);
         if (d<min[0]) then begin
            min[1]:=min[0];
            min[0]:=d;
         end
         else if (d<min[1]) and (d<>min[0]) then
                min[1]:=d;
         if (d>max[0]) then begin
           max[1]:=max[0];
           max[0]:=d;
         end
         else if (d>max[1]) and (d<>max[0]) then
               max[1]:=d;
     end;
     WriteLn('Min:',min[0]);
     WriteLn('Min:',min[1]);
     WriteLn('Max:',max[0]);
     WriteLn('Max:',max[1]);
     Readkey;
end.


Всем кто помогал большущее спасибо smile

Автор: Alex101 8.7.2005, 11:41
Цитата
max[0]:=-maxint; max[1]:=-maxint

Лучше max[0]:=-maxint-1; max[1]:=-maxint-1;

Автор: vadims 8.7.2005, 11:47
Alex101 Обясни пожалуйста - никак не въеду

1. К чему эти операции ???
max1:=min2 xor max1;
min2:=min2 xor max1;
max1:=min2 xor max1

2. Чем лучше ???
max[0]:=-maxint-1; max[1]:=-maxint-1

Автор: Alex101 8.7.2005, 11:57
Цитата(vadims @ 8.7.2005, 11:47)
Чем лучше ???

maxint=32767, а maxnegativeint=-32768

Автор: vadims 8.7.2005, 12:01
Alex101
- Максимум это согласен.
Кстати, а компилятор не должен отсечь конструкцию -maxint ???

Взгляни на мой предыдущий пост - я его как раз редактировал когда ты отвечал

Автор: Akina 8.7.2005, 12:52
Цитата(vadims @ 8.7.2005, 13:01)
Кстати, а компилятор не должен отсечь конструкцию -maxint ???

Нет, это просто предопределенная Public Const. Но должно существовать и MinInt - это так, к слову...
Добавлено @ 12:54
Кстати. Если это в разделе "Алгоритмы" - почему циклимся на Паскалевом коде? А если нет - то в некоторых языках есть процедура SWAP...

Автор: Alex101 8.7.2005, 13:10
Цитата(vadims @ 8.7.2005, 11:47)
1. К чему эти операции ???
max1:=min2 xor max1;
min2:=min2 xor max1;
max1:=min2 xor max1

Меняются местами значения max1 и min2


Цитата(Akina @ 8.7.2005, 12:52)
в некоторых языках есть процедура SWAP...

Все равно мои три строчки будут работать быстрее smile

Автор: vadims 8.7.2005, 13:25
Цитата(Alex101 @ 8.7.2005, 13:10)
Меняются местами значения max1 и min2
А тоже самое и на ассемблере написать слабо ? smile
Еще ведь быстрее будет

Автор: Akina 8.7.2005, 13:43
Цитата(Alex101 @ 8.7.2005, 14:10)
Все равно мои три строчки будут работать быстрее

При чем тут скорость? мы об алгоритме говорим, значит реализация тривиальной функции (а SWAP - именно таковая) рассматриваться просто не должна, ибо оффтоп.

Автор: Alex101 8.7.2005, 14:14
Цитата(Akina @ 8.7.2005, 13:43)
а SWAP - именно таковая) рассматриваться просто не должна, ибо оффтоп.

Для данной ветки - безусловно, я просто старался оптимальный по скорости алгоритм предложить.

Sorry for offtop
Цитата(vadims @ 8.7.2005, 13:25)
А тоже самое и на ассемблере написать слабо ?

Не-а smile
Код

mov ax, min2
mov cx, max1
xchg ax,cx

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)