Форум программистов, компьютерный форум, киберфорум
Pascal (Паскаль)
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.60/5: Рейтинг темы: голосов - 5, средняя оценка - 4.60
0 / 0 / 0
Регистрация: 29.11.2016
Сообщений: 1

Олимпиадная задача

30.11.2016, 01:17. Показов 913. Ответов 2

Студворк — интернет-сервис помощи студентам
На вход в файле 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


Собственно говоря, каким образом можно решить эту задачу?Самому отсортировать несложно, но как это описать алгоритмом?

Добавлено через 3 часа 3 минуты
Вообщем, кому интересно.На stackoverflow подсказали, что
на каждом шаге надо находить минимальный том, стоящий не на своем месте, и ставить его в конец."на своем месте" - то есть в порядке возрастания. для второго примера при первом шаге стоят в порядке возрастания 1 2 5 . 3 - минимальное, которое стоит не в порядке возрастания.соответственно 3 и ставим в конец.вот таким образом я смог решить задачу:
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
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.
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
30.11.2016, 01:17
Ответы с готовыми решениями:

Олимпиадная задача
Условие: http://i.imm.io/1m1cH.jpeg Примеры вывода: http://i.imm.io/1m1cL.png 2 часа писал программу.. она даже работала! Но загрузив...

Выборы. Олимпиадная задача
На выборах в Государственную думу в избирательные бюллетени внесено N партий. Электронный сканер для считывания информации с бюллетеней...

Олимпиадная задача с кубиками
Не могли бы вы мне помочь? Юный математике Матвей интересуется теорией вероятностей, и по этой причине у него всегда есть с собой...

2
Модератор
10422 / 5710 / 3401
Регистрация: 17.08.2012
Сообщений: 17,367
03.12.2016, 05:30
А что, в задании просят отсортировать массив? В задании просят найти минимальное количество перестановок, а не сами перестановки. А для этого достаточно найти количество томов, которые уже упорядочены так, как нужно (то есть, сначала том 1, затем том 2 итак далее). Оставшееся количество томов и будет искомым количеством перестановок.

Пример 1: 2 1 3 4 5 -> 4
Пример 2: 1 3 4 2 5 -> 3
Пример 3: 1 5 2 4 3 -> 2


Так что, всё гораздо проще, вот так, например:
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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.
3
Модератор
10422 / 5710 / 3401
Регистрация: 17.08.2012
Сообщений: 17,367
11.12.2016, 03:08
Вредно по ночам не спать... Ещё замечание. Массив не нужен. Хватит и переменной типа integer
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
11.12.2016, 03:08
Помогаю со студенческими работами здесь

Олимпиадная задача Pascal
Пришел недавно с олимпиады . Все решил , последняя задача никак не дается . Кто нибудь может знает как решит ? Сегодня Али в местном...

Олимпиадная задача, бред, но красиво
Кролик открыл в лесу кафе, в котором Сова выпекает пирожные. Осел решил угостить друзей и заказал множество пирожных разных видов в разных...

Олимпиадная задача про конфеты
У Пети Костылькова день рождения и он принес конфеты, чтобы угостить одноклассников и, конечно же, свою любимую учительницу Снежану...

задача на двумерные массивы (олимпиадная)
«Умножение методом решетки». В IX веке нашей эры арабский математик Мухаммед ибн Мусса ал-Хорезми придумал способ умножения натуральных...

Олимпиадная задача. Лестница из кубиков.
1) Мальчик Петя строит из кубиков лестницу. Лестница представляет собой несколько стоящихся рядом башенок из кубиков, каждая из которых...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Новые блоги и статьи
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве
8Observer8 02.02.2026
Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .
Философия технологии
iceja 01.02.2026
На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .
SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf
8Observer8 01.02.2026
Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .
SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли
8Observer8 30.01.2026
Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm
8Observer8 30.01.2026
Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .
SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 29.01.2026
Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .
Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT
bedvit 28.01.2026
Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .
SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 28.01.2026
Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru