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

Alexey123 · 20 Мар 2017

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

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

Viewer · 20 Мар 2017

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

Vladimir_S · 21 Мар 2017

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

Не идёт. Это у него показаны старый - новый массивы.
А вообще - забавная такая задачка. По-всякому решать можно. Ну вот, например, с использованием множеств (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.

Viewer · 21 Мар 2017

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

Код:

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]

Viewer · 21 Мар 2017

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

Код:

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.

Евгений · 21 Мар 2017

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

Код:

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.

Viewer · 21 Мар 2017

И еще один вариант, где 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.

Alexey123 · 21 Мар 2017

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

Viewer · 21 Мар 2017

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

Vladimir_S · 22 Мар 2017

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

Alexey123 написал(а):
Дан массив 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.

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

Vladimir_S · 22 Мар 2017

Ну вот, ваша интерпретация. Действительно, чуть сложнее, но тоже без вспомогательных массивов:

Код:

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

Var
 A:Ar;
 k,N,i:Byte;

Procedure Exch(q:byte; var C:Ar);
Var
 Mx1,Mx2:Integer;
 D,m,p:byte;
begin
 p:=1+q;
 Mx1:=-1;
 for m:=1+q to N do
  if (C[m]>Mx1) and ((C[m] mod 2)=1) then
   begin
    p:=m;
    Mx1:=C[p];
   end;
 if Mx1>-1 then
  begin
   D:=C[1+q];
   C[1+q]:=C[p];
   C[p]:=D;
  end;
 p:=1+q;
 Mx2:=-1;
 for m:=1+q to N-q do
  if (C[m]>Mx2) and ((C[m] mod 2)=0) then
   begin
    p:=m;
    Mx2:=C[p];
   end;
 if Mx2>-1 then
  begin
   D:=C[N-q];
   C[N-q]:=C[p];
   C[p]:=D;
  end;
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-1 do Exch(k,A);

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

 Readln
End.

Евгений · 22 Мар 2017

Да, вроде, и ничего сложного.

Код:

uses  Crt;
const n=10;
var   a:array[1..n] of integer;
      i,t,ti,k,m,p: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; p:=0;
    repeat  
      Inc(p);
      t:=0; 
      for i:=m to k do
       if a[i]>t then
         begin
           t:=a[i]; ti:=i;
         end;
      if (p 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.

Viewer · 22 Мар 2017

Вариантов решения задач - масса. Главное, чтобы они были понятны студентам.
Так-то вообще все решается в "одну строчку" ar.Sort(lambda);

Для студентов более понятен метод "разделяй и властвуй" и более высокоуровневый стиль.
Пример работы над массивом "на месте", но с разделением обработки четных и нечетных чисел. Процедуры сортировки могут быть объединены в одну, но это - снижение наглядности.

Код:

var
  arRnd: array of integer;
const
  maxValue = 60; // Max value of rnd
  maxLen = 31; // arRnd.Length

function Even_ahead(ar: array of integer): integer;
var k: integer = 0;
var x: integer;
begin
  for var i :=0 to ar.Length-1 do
    if not Odd(ar[i]) then
      begin
        x := ar[i];
        for var j := i downto k+1 do
          ar[j] := ar[j-1];
        ar[k] := x;
        Inc(k);
      end;
  Result := k;    
end;

procedure _Swap(ar: array of integer; i,j: integer);
var x: integer;
begin
  x := ar[i];
  ar[i]:=ar[j];
  ar[j]:=x;
end;

procedure Odd_Sort(ar: array of integer; k: integer);
var x: integer;
begin
  for var i := k to ar.Length-2 do
    for var j :=i to ar.Length-1 do
      if ar[i] > ar[j] then _Swap(ar,i,j);
end;

procedure Even_Sort(ar: array of integer; k: integer);
var x: integer;
begin
  for var i:=0 to k-2 do
    for var j :=i to k-1 do
      if ar[i] < ar[j] then _Swap(ar,i,j);
end;
  
begin
  SetLength(arRnd, maxLen);

  for var i := Low(arRnd) to High(arRnd) do
    arRnd[i] := random(MaxValue + 1);

  write('rnd=', arRnd.Length,' ', arRnd);
  writeln();
  
  var k: integer = 0;

// Тело основного цикла
  k := Even_Ahead(arRnd);
  Even_Sort(arRnd, k);
  Odd_Sort(arRnd, k);


  write('rnd=', arRnd.Length,' ', arRnd);
  writeln();

end.

Viewer · 23 Мар 2017

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

Код:

var
  ar: array of integer;
const
  maxValue = 60; // Max value of rnd
  maxLen = 19; // ar.Length

procedure _Swap(ar: array of integer; i,j: integer);
var x: integer;
begin
  x := ar[i];
  ar[i]:=ar[j];
  ar[j]:=x;
end;
  
begin
// Init  
  SetLength(ar, maxLen);
  for var i := Low(ar) to High(ar) do
    ar[i] := random(MaxValue + 1);

  write('rnd= ', ar.Length,' ', ar);
  writeln();

// Body  
  var k: integer = 0;
  var x: integer;
  
// Even to head
  for var i :=0 to ar.High do
    if not Odd(ar[i]) then begin
        x := ar[i];
        for var j := i downto k+1 do
          ar[j] := ar[j-1];
        ar[k] := x;
        Inc(k);
    end;
// Sort even
  for var i:=0 to k-2 do
    for var j :=i to k-1 do
      if ar[i] < ar[j] then _Swap(ar,i,j);
// Sort odd
  for var i := k to ar.High-1 do
    for var j :=i to ar.High do
      if ar[i] > ar[j] then _Swap(ar,i,j);

  write('sort=', ar.Length,' ', ar);
  writeln();
 
end.

Alexey123 · 24 Мар 2017

Вы все правильно поняли, это и подразумевалось. Понятно было ваше решение, он подходило под мой случай больше остальных. Сам как-то не задумывался что

Vladimir_S написал(а):
В левой части нового массива должны расположиться все нечетные (по значению) элементы в порядке убывания. В правой - все четные в порядке возрастания.

, поэтому им тоже благодарен, задачку нашел в интернете, решал для себя, про вторую интерпретацию не подумал, извините что-ли, из-за путаницыtehno015

Viewer · 29 Мар 2017

Не здесь, но зашел среди профи междусобойчик о самом кратком, но и понятном коде решения этой задачи, причем на разных языках.
Наверное, самый короткий, но и понятный для студентов вариант, получился на PascalABC.Net
( используются лямбда-функции и массив остается без изменений):

Код:

begin
  var ar := Seq(45,46,8,11,5,29,37,0,21,43,4,5,58,34,14,18,40,46,30);
  ar.Where(x -> x mod 2 = 0).SortedDescending.Print;
  Print('');
  ar.Where(x -> x mod 2 <> 0).Sorted.Print;
end.

Код:

58 46 46 40 34 30 18 14 8 4 0 5 5 11 21 29 37 43 45

Vladimir_S · 29 Мар 2017

Viewer написал(а):
Не здесь, но зашел среди профи междусобойчик о самом кратком, но и понятном коде решения этой задачи, причем на разных языках. Наверное, самый короткий, но и понятный для студентов вариант, получился на PascalABC.Net ( используются лямбда-функции и массив остается без изменений)

Но всё это, опять же замечу, если задачу интерпретировать, как разделение по четности. Между тем, если я правильно понял последний комментарий ТС, здесь подразумевается другой принцип разделения: если массив А упорядочен по убыванию, то в преобразованном массиве B элементы должны занять места так:
A[1] → B[1],
A[2] → B[n],
A[3] → B[2]
A[4] → B[n-1]...
У меня и эта задачка решена, вы же оба, дорогие коллеги, зациклились на четности.

Viewer · 29 Мар 2017

Постом #15 ТС подтвердил, что разделение на четные-нечетные - правильное понимание его задачи. Сделать так, как я понял в начале - не проблема, но, в данном случае, я всего лишь демонстрирую своим примером краткость и понятность кода, присущие высокоуровенному подходу.

Vladimir_S · 29 Мар 2017

Viewer написал(а):
Постом #15 ТС подтвердил, что разделение на четные-нечетные - правильное понимание его задачи.

А не факт! Пост #15 сформулирован довольно мутно, типа "как хочешь, так и понимай!"

Alexey123 написал(а):
Вы все правильно поняли, это и подразумевалось.

К кому относится это "Вы" - к вам? ко мне? А пёс разберёт!

Viewer · 29 Мар 2017

Vladimir_S написал(а):
А не факт! Пост #15 сформулирован довольно мутно, типа "как хочешь, так и понимай!" К кому относится это "Вы" - к вам? ко мне? А пёс разберёт!

Да и ладно, я не в претензии. Пусть Ваш вариант будет уникальным

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

Новые

Banned

Супермодераторы

Banned

Banned

Новые

Banned

Новые

Banned

Супермодераторы

Вложения

Супермодераторы

Вложения

Новые

Banned

Banned

Новые

Banned

Супермодераторы

Banned

Супермодераторы

Banned

Похожие темы