Была дана перестановка, по ней построили таблицу инверсий. надо востановить перестановку. всего N целых чисел A1, A2, ..., AN, где число Ak (0 <= Ak < N) означает,
что ровно A k элементов, больших чем k, стоит до числа k в перестановке.
М | Заголовок темы должен быть информативным ! В следующий раз удалю ! klem4 |
gamordzhoba, пример входных данных приведи, и результат, который должен получиться при этих данных...
Из таблицы инверсий, например, 22010,
получаем исходную перестановку:
12345
35124
Если вторую строку перестановки представлять массивом В размера N , то код будет примерно такой
for i:=1 to N do B[i]:=0;
for i:=1 to N do
begin
k:=0;
j:=0;
while k<=A[i] do
begin
inc(j);
if B[j]=0 then inc(k);
end;
B[j]:=i;
end;
примерный
Ввод
4
2 0 1 0
Вывод
2 4 1 3
Помоги пожалуйста, а то я с другом поспорил,что мир не без добрых людей.
Ладно, напишу полную программу и завтра выложу, сегодня долго в инете не смогу сидеть.
gamardzhoba
Вот так вот:
const
{
n = 9;
}
n = 4;
type
arrType = array[1 .. n] of integer;
const
{
inver: arrType = (2, 3, 6, 4, 0, 2, 2, 1, 0);
}
inver: arrType = (2, 0, 1, 0);
var
i, j: integer;
perest: arrType;
begin
for i := n downto 1 do begin
move( perest[inver[i]+1], perest[inver[i]+2],
(n-(inver[i]+2)+1)*sizeof(integer) );
perest[inver[i]+1] := i;
{ Печатаем промежуточные результаты }
for j := 1 to n do
write(perest[j]:4);
writeln;
end;
{ Окончательный результат: }
for i := 1 to n do
write(perest[i]:4);
writeln;
end.
to gamardzhoba бери код, приведённый volvo, он эффективней, чем мой. Добавь ввод пользователем числа n, и используй динамические массивы (если что-то по ним непонятно, смотри FAQ раздела). Вывод промежуточных результатов можешь закомментировать.
Спасибо доьрые люди!!!!!!!!!!!