Технический форум - Опять массивы

Технический форум (http://www.tehnari.ru/)

- Delphi, Kylix and Pascal (http://www.tehnari.ru/f43/)

- - Опять массивы (http://www.tehnari.ru/f43/t252812/)

Опять массивы

И снова здравствуйте! В этот раз я пришел не за кодом(в кои-то веки),
а за советом.
Итак, собственно, само задание :
Дан массив N из набора случайных чисел. Отсортировать массив в таком порядке -
Пример: 0 1 2 3 4 5 6 7 8 9 10 - 10 8 6 4 2 0 1 3 5 7 9 //массив после сортировки//
Ну, то есть большое влево - маленькое вправо и т.д.
Я уверен, решение у меня под носом, однако пока не додумался.
Мне нужна только подсказка, хотя бы в каком направлении думать,
не все же на шее висеть да код вымаливать.
Заранее спасибо всем тем, кто не пройдет мимо и поможет. Авось из меня что-нибудь и выйдет:ctivo:

И все же непонятно - почему в массиве после сортировки ( в Вашем примере ) идет дублирование чисел?
Случайные - это понятно. Но как 8-ку какую-то перекинуть влево или вправо?
Странное задание.
Так-то - все просто.
Отсортировать по убывающей.
Идти с нулевого индекса и раскидывать в два новых массива через раз, затем слить оба массива в новый искомый или старый.
P.S.
Есть особенности по четности/нечетности размерности массива.

Цитата:

Сообщение от Viewer (Сообщение 2471520)

И все же непонятно - почему в массиве после сортировки ( в Вашем примере ) идет дублирование чисел?

Не идёт. Это у него показаны старый - новый массивы.
А вообще - забавная такая задачка. По-всякому решать можно. Ну вот, например, с использованием множеств (Alexey123, Вы уж простите великодушно, что программа написана на ЯП Free Pascal, т.е. на языке времён, как выяснилось, нашествия Батыя):

Код:

Type

 Ar=Array[0..255] of Byte;



Var

 A,B:Ar;

 S:Set of Byte;

 i,j,Jmax,N:Byte;



Function Num_max(C:Ar):Byte;

var

 Mx,k,k1,Nm:Byte;

begin

 k1:=0;

 Repeat

  if k1 in S then Inc(k1);

 Until Not(k1 in S);

 Mx:=C[k1];

 Nm:=k1;

 for k:=k1+1 to N do

  if (C[k]>Mx) and Not(k in S) then

   begin

    Mx:=C[k];

    Nm:=k;

   end;

 Num_max:=Nm;

end;



Begin

 Randomize;

 Write(' N = ');

 Readln(N);

 Writeln('Initial array:');

 for i:=0 to N do

  begin

   A[i]:=Random(100);

   write(A[i]:4);

  end;

 writeln;

 writeln;

 if (N mod 2)=0 then Jmax:=(N div 2)-1 else Jmax:=(N div 2);

 S:=[];

 j:=0;

 Repeat

  i:=Num_Max(A);

  B[j]:=A[i];

  S:=S+[i];

  i:=Num_Max(A);

  B[N-j]:=A[i];

  S:=S+[i];

  Inc(j);

 Until j=Jmax+1;



 if (N mod 2)=0 then

  for i:=0 to N do

   if Not(i in S) then B[(N div 2)]:=A[i];



 Writeln('Ordered array:');

 for i:=0 to N do write(B[i]:4);

 Readln

End.

Ну или так, в соответствии с вышеизложенной мной идеей.
Из недостатков - расход памяти на доп. массивы, но зато высокоуровенный стиль и большая понятность для начинающих:

Код:

var

  arRnd, arOdd, arEven: array of integer;

const

  maxValue = 9; // Max value of rnd

  maxLen = 30; // arRnd.Length

begin

  SetLength(arRnd, maxLen);

  SetLength(arOdd, maxLen);

  SetLength(arEven, maxLen);

// Init

  for var i := Low(arRnd) to High(arRnd) do

    arRnd[i] := random(MaxValue + 1);

// Sort up   

  arRnd.Sort;

  write('len=', arRnd.Length,' ', arRnd);

  writeln();



// separate odd and even   

  var j: integer = 0;

  var k: integer = j;

  for var i := High(arRnd) downto Low(arRnd) do

    begin

      case Odd(arRnd[i]) of

        True: begin

                arOdd[j] := arRnd[i];

                Inc(j);

              end;

        False: begin

                arEven[k] := arRnd[i];

                Inc(k);

              end;

      end;  

    end;

// truncate

  SetLength(arOdd, j);  

  SetLength(arEven, k);

// sort up

  arEven.Sort;

// splice  

  for var i := Low(arOdd) to High(arOdd) do

    arRnd[i] := arOdd[i];

  for var i := Low(arEven) to High(arEven) do

    arRnd[j + i] := arEven[i];

// out 

  write('j=',j,' ',arOdd);

  writeln();

  write('k=',k,' ', arEven);

  writeln();

  write('j+k=',j+k,' ', arRnd);

  

end.

Код:

len=30 [0,1,1,1,2,2,2,3,3,3,3,4,5,5,5,6,6,6,7,7,7,7,7,7,7,8,8,8,9,9]

j=19 [9,9,7,7,7,7,7,7,7,5,5,5,3,3,3,3,1,1,1]

k=11 [0,2,2,2,4,6,6,6,8,8,8]

j+k=30 [9,9,7,7,7,7,7,7,7,5,5,5,3,3,3,3,1,1,1,0,2,2,2,4,6,6,6,8,8,8]

Еще один вариант, где исключена сортировка начального большого массива, но введены сортировки двух усеченных массивов. Это к вопросу о методике повышения скорости выполнения, т.к. один большой массив сортируется дольше, чем два массива половинной размерности. Чисто методическое решение.

Код:

var

  arRnd, arOdd, arEven: array of integer;

const

  maxValue = 50; // Max value of rnd

  maxLen = 30; // arRnd.Length

begin

  SetLength(arRnd, maxLen);

  SetLength(arOdd, maxLen);

  SetLength(arEven, maxLen);

// Init

  for var i := Low(arRnd) to High(arRnd) do

    arRnd[i] := random(MaxValue + 1);



  write('len=', arRnd.Length,' ', arRnd);

  writeln();



// separate odd and even   

  var j: integer = 0;

  var k: integer = j;

  for var i := Low(arRnd) to High(arRnd) do

    case Odd(arRnd[i]) of

      True: begin

              arOdd[j] := arRnd[i];

              Inc(j);

            end;

      False: begin

               arEven[k] := arRnd[i];

               Inc(k);

             end;

    end;

      

// truncate

  SetLength(arOdd, j);  

  SetLength(arEven, k);



// sort up

  arOdd.Sort;

// reverse

  Reverse(arOdd);

// sort up

  arEven.Sort;



// splice  

  for var i := Low(arOdd) to High(arOdd) do

    arRnd[i] := arOdd[i];

  for var i := Low(arEven) to High(arEven) do

    arRnd[arOdd.Length + i] := arEven[i];

// out 

  write('j=',j,'   ',arOdd);

  writeln();

  write('k=',k,'   ', arEven);

  writeln();

  write('j+k=',j+k,' ', arRnd);

  

end.

Ну и мои пять копеек:

Код:

uses  Crt;

const n=10;

var   a:array[1..n] of integer;

      i,t,ti,k,m:integer;

begin

  ClrScr;

   Randomize;

    for i:=1 to n do

      begin

        a[i]:=Random(99)+1;

        Write(a[i]:4);

      end; Writeln; Writeln;

   m:=1; k:=n;

    repeat

      t:=0;

      for i:=m to k do

       if a[i]>t then

         begin

           t:=a[i]; ti:=i;

         end;

      if (t mod 2)=0

       then

         begin

           for i:=ti downto m+1 do

            a[i]:=a[i-1];

           a[m]:=t;

           Inc(m);

         end

       else

         begin

           for i:=ti to k-1 do

            a[i]:=a[i+1];

           a[k]:=t;

           Dec(k);

         end;

    until (m=k);

     for i:=1 to n do

      Write(a[i]:4);

  Readkey;

end.

И еще один вариант, где case заменен на if else, поскольку это тоже повышает (в общем случае) быстродействие.
Также исключены комментарии, поскольку высокоуровенный код и так является самодокументируемым.

Код:

var

  arRnd, arOdd, arEven: array of integer;

  var j: integer = 0;

  var k: integer = j;

const

  maxValue = 50; // Max value of rnd

  maxLen = 30; // arRnd.Length

begin

  SetLength(arRnd, maxLen);

  SetLength(arOdd, maxLen);

  SetLength(arEven, maxLen);



  for var i := Low(arRnd) to High(arRnd) do

    arRnd[i] := random(MaxValue + 1);



// Основное тело вычислений



  for var i := Low(arRnd) to High(arRnd) do

    if Odd(arRnd[i]) then begin

      arOdd[j] := arRnd[i]; Inc(j);

    end else begin

      arEven[k] := arRnd[i]; Inc(k);

    end;

      

  SetLength(arOdd, j);  

  SetLength(arEven, k);

  arOdd.Sort;

  Reverse(arOdd);

  arEven.Sort;



  for var i := Low(arOdd) to High(arOdd) do

    arRnd[i] := arOdd[i];

  for var i := Low(arEven) to High(arEven) do

    arRnd[arOdd.Length + i] := arEven[i];

end.

P.S.
ЯП - PascalABC.Net.
Практически все это доступно на FreePascal и Delphi.

Спасибо! Спасибо всем! Такие добрые люди, душа радуется! Все понятно, все по полочкам, отблагодарил бы всех, да вот только исчерпал лимит "благодарностей" пользователю, такие дела. Я вам очень, очень признателен! Даже не знаю как поблагодарить :feel:

Так и мы рады, что "все понятно". :)

Немного "зацепила" эта задачка, потому продолжу. Не столько для ТС, сколько в порядке междусобойчика.
Начать с того, что ТС абсолютно невразумительно сформулировал задание.

Цитата:

Сообщение от Alexey123 (Сообщение 2471514)

Дан массив N из набора случайных чисел. Отсортировать массив в таком порядке -
Пример: 0 1 2 3 4 5 6 7 8 9 10 - 10 8 6 4 2 0 1 3 5 7 9 //массив после сортировки//
Ну, то есть большое влево - маленькое вправо и т.д.

Тут возможны две интерпретации.
1. Как поняли Viewer (жаль, не знаю имени) и Евгений:
В левой части нового массива должны расположиться все нечетные (по значению) элементы в порядке убывания. В правой - все четные в порядке возрастания.
2. Как понял Vladimir_S (то бишь я):
Максимальный элемент ставится в крайнюю левую позицию, следующий по значению - в крайнюю правую, следующий - во вторую слева, следующий - во вторую справа и т.д. Решение именно этой задачи я и предложил.

(Хотел бы я знать, что нашему ТС "понятно", если решались разные задачи, и кто прав - мне лично совсем непонятно).

Так вот, решение, предложенное мною (в моей интерпретации задания), далеко от оптимального (множества, лишний массив и т.п.), а потому пришло мне в голову другое - простое и изящное, вообще не требующее ни вспомогательных массивов, ни множеств. Да и четность длины массива отрабатывается автоматически. Вот так:

Код:

Type

 Ar=Array[1..255] of Byte;



Var

 A:Ar;

 k,N,i:Byte;



Procedure Exch(q:byte; var C:Ar);

Var

 Mx1,Mx2,D,m,p:byte;

begin

 p:=1+q;

 Mx1:=C[p];

 for m:=2+q to N-q  do

  if C[m]>Mx1 then

   begin

    p:=m;

    Mx1:=C[p];

   end;

 D:=C[1+q];

 C[1+q]:=C[p];

 C[p]:=D;

 p:=2+q;

 Mx2:=C[p];

 for m:=3+q to N-q do

  if C[m]>Mx2 then

   begin

    p:=m;

    Mx2:=C[p];

   end;

 D:=C[N-q];

 C[N-q]:=C[p];

 C[p]:=D;

end;



Begin

 Randomize;

 Write(' N = ');

 Readln(N);

 Writeln('Initial array:');

 for i:=1 to N do

  begin

   A[i]:=Random(100);

   write(A[i]:4);

  end;

 writeln;

 writeln;



 for k:=0 to (N div 2)-1 do Exch(k,A);



 Writeln('Ordered array:');

 for i:=1 to N do write(A[i]:4);



 Readln

End.

Подумаю, может быть и вашей интерпретации задания что-нибудь в этом роде придумаю. Хотя тут чуть сложнее.