20.03.2017, 21:51 | #1 (permalink) |
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, 21:51 | |
Helpmaster
Member
Регистрация: 08.03.2016
Сообщений: 0
|
Решение этой проблемы можно ускорить, прочитав похожие темы Опять массивы вирус про бонус, опять не пускают ВКонтакте, так глупо опять попалась при распаковке Массивы, C |
20.03.2017, 22:06 | #2 (permalink) |
Banned
Регистрация: 06.03.2017
Сообщений: 788
Сказал(а) спасибо: 0
Поблагодарили 18 раз(а) в 4 сообщениях
Репутация: 5680
|
И все же непонятно - почему в массиве после сортировки ( в Вашем примере ) идет дублирование чисел?
Случайные - это понятно. Но как 8-ку какую-то перекинуть влево или вправо? Странное задание. Так-то - все просто. Отсортировать по убывающей. Идти с нулевого индекса и раскидывать в два новых массива через раз, затем слить оба массива в новый искомый или старый. P.S. Есть особенности по четности/нечетности размерности массива. Последний раз редактировалось Viewer; 20.03.2017 в 22:14 |
21.03.2017, 11:59 | #3 (permalink) | |
Специалист
Регистрация: 27.08.2008
Адрес: Санкт-Петербург
Сообщений: 27,807
Сказал(а) спасибо: 340
Поблагодарили 583 раз(а) в 208 сообщениях
Репутация: 113184
|
Цитата:
А вообще - забавная такая задачка. По-всякому решать можно. Ну вот, например, с использованием множеств (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. |
|
21.03.2017, 18:13 | #4 (permalink) |
Banned
Регистрация: 06.03.2017
Сообщений: 788
Сказал(а) спасибо: 0
Поблагодарили 18 раз(а) в 4 сообщениях
Репутация: 5680
|
Ну или так, в соответствии с вышеизложенной мной идеей.
Из недостатков - расход памяти на доп. массивы, но зато высокоуровенный стиль и большая понятность для начинающих: Код:
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] |
21.03.2017, 19:34 | #5 (permalink) |
Banned
Регистрация: 06.03.2017
Сообщений: 788
Сказал(а) спасибо: 0
Поблагодарили 18 раз(а) в 4 сообщениях
Репутация: 5680
|
Еще один вариант, где исключена сортировка начального большого массива, но введены сортировки двух усеченных массивов. Это к вопросу о методике повышения скорости выполнения, т.к. один большой массив сортируется дольше, чем два массива половинной размерности. Чисто методическое решение.
Код:
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. |
Ads | |
Member
Регистрация: 31.10.2006
Сообщений: 40200
Записей в дневнике: 0
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 55070
|
21.03.2017, 20:07 | #6 (permalink) |
Member
Регистрация: 31.03.2010
Адрес: Тульская область
Сообщений: 1,309
Сказал(а) спасибо: 11
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 13090
|
Ну и мои пять копеек:
Код:
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. |
21.03.2017, 20:07 | #7 (permalink) |
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. ЯП - PascalABC.Net. Практически все это доступно на FreePascal и Delphi. Последний раз редактировалось Viewer; 21.03.2017 в 20:17 |
21.03.2017, 23:12 | #8 (permalink) |
Member
Регистрация: 11.12.2016
Сообщений: 26
Сказал(а) спасибо: 1
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 10
|
Спасибо! Спасибо всем! Такие добрые люди, душа радуется! Все понятно, все по полочкам, отблагодарил бы всех, да вот только исчерпал лимит "благодарностей" пользователю, такие дела. Я вам очень, очень признателен! Даже не знаю как поблагодарить
|
22.03.2017, 15:01 | #10 (permalink) | |
Специалист
Регистрация: 27.08.2008
Адрес: Санкт-Петербург
Сообщений: 27,807
Сказал(а) спасибо: 340
Поблагодарили 583 раз(а) в 208 сообщениях
Репутация: 113184
|
Немного "зацепила" эта задачка, потому продолжу. Не столько для ТС, сколько в порядке междусобойчика.
Начать с того, что ТС абсолютно невразумительно сформулировал задание. Цитата:
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. |
|
Ads | |
Member
Регистрация: 31.10.2006
Сообщений: 40200
Записей в дневнике: 0
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 55070
|
Опции темы | |
Опции просмотра | |
|
|