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

Alexey123 · 20.03.2017, 21:51

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

Viewer · 20.03.2017, 22:06

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

Vladimir_S · 21.03.2017, 11:59

Цитата:

Сообщение от 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.03.2017, 18:13

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

Код:

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.03.2017, 19:34

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

Код:

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.03.2017, 20:07

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

Код:

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.03.2017, 20:07

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

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

Viewer · 21.03.2017, 23:16

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

Vladimir_S · 22.03.2017, 15:01

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

Цитата:

Сообщение от 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.

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

20.03.2017, 21:51	#1 (permalink)
Alexey123 Member Регистрация: 11.12.2016 Сообщений: 26 Сказал(а) спасибо: 1 Поблагодарили 0 раз(а) в 0 сообщениях Репутация: 10	Опять массивы И снова здравствуйте! В этот раз я пришел не за кодом(в кои-то веки), а за советом. Итак, собственно, само задание : Дан массив N из набора случайных чисел. Отсортировать массив в таком порядке - Пример: 0 1 2 3 4 5 6 7 8 9 10 - 10 8 6 4 2 0 1 3 5 7 9 //массив после сортировки// Ну, то есть большое влево - маленькое вправо и т.д. Я уверен, решение у меня под носом, однако пока не додумался. Мне нужна только подсказка, хотя бы в каком направлении думать, не все же на шее висеть да код вымаливать. Заранее спасибо всем тем, кто не пройдет мимо и поможет. Авось из меня что-нибудь и выйдет

20.03.2017, 22:06	#2 (permalink)
Viewer Banned Регистрация: 06.03.2017 Сообщений: 788 Сказал(а) спасибо: 0 Поблагодарили 18 раз(а) в 4 сообщениях Репутация: 5680	И все же непонятно - почему в массиве после сортировки ( в Вашем примере ) идет дублирование чисел? Случайные - это понятно. Но как 8-ку какую-то перекинуть влево или вправо? Странное задание. Так-то - все просто. Отсортировать по убывающей. Идти с нулевого индекса и раскидывать в два новых массива через раз, затем слить оба массива в новый искомый или старый. P.S. Есть особенности по четности/нечетности размерности массива. Последний раз редактировалось Viewer; 20.03.2017 в 22:14

21.03.2017, 20:07	#7 (permalink)
Viewer Banned Регистрация: 06.03.2017 Сообщений: 788 Сказал(а) спасибо: 0 Поблагодарили 18 раз(а) в 4 сообщениях Репутация: 5680	И еще один вариант, где 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. Последний раз редактировалось Viewer; 21.03.2017 в 20:17

20.03.2017, 21:51
Helpmaster Member Регистрация: 08.03.2016 Сообщений: 0	Решение этой проблемы можно ускорить, прочитав похожие темы Опять массивы вирус про бонус, опять не пускают ВКонтакте, так глупо опять попалась при распаковке Массивы, C

Ads
Яндекс Member Регистрация: 31.10.2006 Сообщений: 40200 Записей в дневнике: 0 Сказал(а) спасибо: 0 Поблагодарили 0 раз(а) в 0 сообщениях Репутация: 55070

21.03.2017, 23:12	#8 (permalink)
Alexey123 Member Регистрация: 11.12.2016 Сообщений: 26 Сказал(а) спасибо: 1 Поблагодарили 0 раз(а) в 0 сообщениях Репутация: 10	Спасибо! Спасибо всем! Такие добрые люди, душа радуется! Все понятно, все по полочкам, отблагодарил бы всех, да вот только исчерпал лимит "благодарностей" пользователю, такие дела. Я вам очень, очень признателен! Даже не знаю как поблагодарить

21.03.2017, 23:16	#9 (permalink)
Viewer Banned Регистрация: 06.03.2017 Сообщений: 788 Сказал(а) спасибо: 0 Поблагодарили 18 раз(а) в 4 сообщениях Репутация: 5680	Так и мы рады, что "все понятно".