Олимпиадная задача - Pascal (80318)

Формулировка задачи:

На вход в файле INPUT.TXT подаётся две строчки: N - количество томов(максимум 32) и (от 1 до N)порядок томов книг Нужно найти и вывести в файл OUTPUT.TXT

минимальное количество переставлений

, чтобы все тома были расположены в порядке

возрастания

, при условии, что только можно

брать любой том и ставить его последним

Пример:

INPUT.TXT

5 2 1 3 4 5

Output.txt

4 Сортировка происходит таким образом: 2 1 3 4 5 1. 1 3 4 5 2 2. 1 4 5 2 3 3. 1 5 2 3 4 4. 1 2 3 4 5

ещё пример

Input.txt

5 1 3 4 2 5

Output.txt

3 Так: 1.1 4 2 5 3 2.1 2 5 3 4 3.1 2 3 4 5 Собственно говоря, каким образом можно решить эту задачу?Самому отсортировать несложно, но как это описать алгоритмом?

Вообщем, кому интересно.На stackoverflow подсказали, что на каждом шаге надо находить минимальный том, стоящий не на своем месте, и ставить его в конец."на своем месте" - то есть в порядке возрастания. для второго примера при первом шаге стоят в порядке возрастания 1 2 5 . 3 - минимальное, которое стоит не в порядке возрастания.соответственно 3 и ставим в конец.вот таким образом я смог решить задачу:

var
n:integer;
a:array [1..33] of integer;
input:text;
output:text;
current_index:integer;
minimal:integer;
index:integer;
coint:integer;
nonFounded:boolean;
 
//процедура сдвига массива
procedure offset_massive(index_first:integer);
begin
for var i:=index_first to N do
a[i]:=a[i+1];
end;

procedure poisk();
begin
current_index:=0;
for var i:=1 to N do
begin
Nonfounded:=true;
minimal:=i;
 
for var j:=1+current_index to N do
begin
if i=a[j] then begin Nonfounded:=false;current_index:=j; break; end;
end;
 
if Nonfounded then break;
end;
 
if nonFounded then begin
for var l:=1 to N do if minimal=a[l] then begin index:=l; end;
a[n+1]:=minimal;
coint:=coint+1;
 
offset_massive(index);
 poisk();
end;
end;
begin
coint:=0;
assign(input,'INPUT.TXT');
reset(input);
Readln(input,N);
for var i:=1 to N do
begin
Read(input,a[i]);
end;
 
poisk();

assign(output,'OUTPUT.TXT');
Rewrite(output);
Writeln(output,coint);
close(input);
close(output);
end.

Решение задачи: «Олимпиадная задача»

Листинг программы

var i, k, n: integer;
    a: array[1..32] of integer;
    f: text;
begin
  assign(f, 'input.txt');
  reset(f);
  readln(f, n);
  k := 1;
  for i := 1 to n do
    begin
      read(f, a[i]);
      if a[i] = k then inc(k)
    end;
  close(f);
  assign(f, 'output.txt');
  rewrite(f);
  writeln(f, n - k + 1);
  close(f)
end.

Объяснение кода листинга программы

Объявляются переменные:
- i - целого типа, используется в цикле для индексации;
- k - целого типа, счетчик, инициализируется значением 1;
- n - целого типа, хранит количество элементов.
Объявляется массив:
- a - массив из 32 элементов целого типа.
Открывается файл input.txt.
Считывается значение переменной n из файла input.txt.
Устанавливается начальное значение счетчика k равное 1.
Выполняется цикл от 1 до n:
- Читается элемент массива a из файла input.txt и сохраняется в a[i].
- Если значение a[i] равно k, увеличивается значение k на 1.
Файл input.txt закрывается.
Открывается файл output.txt.
Выполняется перезапись файла output.txt.
В файл output.txt записывается результат вычисления выражения n - k + 1.
Файл output.txt закрывается. Код осуществляет чтение из файла input.txt, подсчет количества элементов массива, а затем запись результата в файл output.txt.