Ожерелье

@AtomJ2 · Регистрация: 11.05.2020

Студворк — интернет-сервис помощи студентам

В витрине ювелирного магазина стоит манекен, на шею которого надето ожерелье. Оно состоит из N колечек, нанизанных на замкнутую нить. Все колечки имеют разные размеры. В зависимости от размера колечки пронумерованы числами от 1 до N, начиная с самого маленького и до самого большого. Колечки можно передвигать вдоль нити и протаскивать одно через другое, но только в том случае, если номера этих колечек отличаются более чем на единицу.

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

Требуется написать программу, которая по заданному начальному расположению колечек находит последовательность протаскиваний колечек одно через другое, приводящую исходное расположение колечек в желаемое.

Формат входных данных
В первой строке входного файла записано число N (2<N<50). Во второй строке через пробел следуют N различных чисел от 1 до N – номера колечек, расположенных вдоль нити по часовой стрелке.

Формат выходных данных
Выходной файл должен содержать описание процесса упорядочения.

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

Если требуемого упорядочения колечек достичь не удается, в выходной файл нужно вывести строку impossible.

Пример входных данных
4
3 2 4 1
Пример выходных данных
1 3
2 4
1 4

@canadamoscow · 23.03.2021, 18:55

Для понимания алгоритма, вот тебе в помощь:
54321 //нужно развернуть и получить 12345, следим за тем, чтобы отсчет всегда начинался с 1 для удобства наблюдения ,тогда
0 0 15432 //нужно поставить 2 на позицию 2, перегоняя 5,4 и 3 влево за единицу, а значит в конец
-------------------------------------------
1 5 14325 //c 5 закончили теперь 4
1 4 13254 //c 4 закончили, теперь 3
1 3 12543 //готово, теперь 3 нужно установить на позицию 3, перегоняя 5 и 4 влево за еденицу
2 5 15243
1 5 12435 //c 5 закончили, теперь 4 влево и в конец
2 4 14235
1 4 12354 //готово, теперь 4 должна оказаться на позиции 4, переставляя 5 влево до конца и в конец
3 5 12534
2 5 15234
1 5 12345 //готово

Добавлено через 1 час 14 минут

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
begin
  var n := 4;
  var a := Lst(3, 2, 4, 1);
  a.Print; Print(' = ');
  a := a[a.IndexOf(1):] + a[:a.IndexOf(1)];
  Println(a);
  var i := 2; //в позиции i дожно быть число i
  var c := 0; //счетчик
  repeat
    while a[i - 1] <> i do
    begin
      var j := i;
      while j > 2 do
      begin
        var t := a[j-2]; a[j-2] := a[j-1]; a[j-1] := t; //swap
        Println(a[j-1], a[j-2], a);
        j -= 1;
        c += 1;
      end;
      a += a[1];
      a.RemoveAt(1);
      Println(1, a[n-1], a);
      c += 1;
    end; 
    i += 1;
  until i = n;
  Println('Шагов всего:',c);
end.

Работу с файлами оставляю на Вас

@canadamoscow · 25.03.2021, 09:42

Оптимизация

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
begin
  var n := 4;
  var a := Arr(3, 2, 4, 1); a.Println;
  a := a[a.IndexOf(1):] + a[:a.IndexOf(1)];
  for var i := 2 to n-1 do 
    while a[i-1] <> i do
      for var j := i downto 2 do begin
         swap(a[j-1], a[j-2]);
         Print(a[j-1], a[j-2]);
         if j = 2 then a := a[1:] + a[0:1];
         Println(a);
      end;
end.

@mr-Crocodile · 25.03.2021, 10:59

canadamoscow, а где же

Сообщение от AtomJ2

Если требуемого упорядочения колечек достичь не удается, в выходной файл нужно вывести строку impossible.

?

например,

Pascal
1
var a := Arr( 1,2,3,5,4);

Добавлено через 3 минуты

Сообщение от canadamoscow

Для понимания алгоритма, вот тебе в помощь:
54321 //нужно развернуть и получить 12345,

кстати, ваш же пример ваш же код не обрабатывает:

Code
1
2
3
4
5
6
7
8
9
5 4 3 2 1 =  [1,5,4,3,2] 
1 2 [1,4,3,2,5] 
1 5 [1,3,2,5,4] 
1 4 [1,2,5,4,3] 
2 5 [1,5,2,4,3] 
1 3 [1,2,4,3,5] 
2 4 [1,4,2,3,5] 
1 5 [1,2,3,5,4] 
Шагов всего: 7

@eaa · 25.03.2021, 11:10

сортировка вставками или что?

@canadamoscow · 25.03.2021, 12:26

Сообщение от mr-Crocodile

Если требуемого упорядочения колечек достичь не удается

при n = 50, максимальное количество строк 19600

Сообщение от mr-Crocodile

var a := Arr( 1,2,3,5,4);

а кто будет делать n = 5 (в твоем примере явно n = 4)

@mr-Crocodile · 25.03.2021, 14:39

Сообщение от canadamoscow

а кто будет делать n = 5 (в твоем примере явно n = 4)

АААА! Ты прав. я фигню спорол. извини, пожалуйста!!

IGPIGP · 05.11.2023, 15:35

canadamoscow, а пузырёк не подойдёт? Только свопинг нужно сделать начиная с перемещения более мелкого элемента. Смотрите:

C++
1
2
3
4
5
if(a>b)//b можно протолкнуть внутрь a
int tmo;
b=tmp;
a=b;//b внутри a
b=tmp;//a на месте b

Должно ведь сработать?

А-а... Номера должны отличаться более чем на 1... Нужно подумать. Боюсь, что если все номера идут подряд в уже отсортированном виде, то задача не решаема. Но нужно подумать, может я и неправ.

@XzzzX · 06.11.2023, 18:13

Не по теме:

IGPIGP, вряд ли спустя 1.5 года автор до сих пор мучается и единственное что ему поможет это код на c++

Новые блоги и статьи Все статьи Все блоги /
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .	Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .

@AtomJ2 5 / 3 / 2 Регистрация: 11.05.2020 Сообщений: 47

	Ожерелье 23.03.2021, 11:48. Показов 4310. Ответов 8 Метки нет (Все метки) В витрине ювелирного магазина стоит манекен, на шею которого надето ожерелье. Оно состоит из N колечек, нанизанных на замкнутую нить. Все колечки имеют разные размеры. В зависимости от размера колечки пронумерованы числами от 1 до N, начиная с самого маленького и до самого большого. Колечки можно передвигать вдоль нити и протаскивать одно через другое, но только в том случае, если номера этих колечек отличаются более чем на единицу. Продавец хочет упорядочить колечки так, чтобы они располагались по возрастанию номеров вдоль нити по часовой стрелке. Снимать ожерелье с манекена нельзя. Требуется написать программу, которая по заданному начальному расположению колечек находит последовательность протаскиваний колечек одно через другое, приводящую исходное расположение колечек в желаемое. Формат входных данных В первой строке входного файла записано число N (2<N<50). Во второй строке через пробел следуют N различных чисел от 1 до N – номера колечек, расположенных вдоль нити по часовой стрелке. Формат выходных данных Выходной файл должен содержать описание процесса упорядочения. В каждой строке должны быть записаны через пробел два числа, указывающие номера колечек, протаскиваемых друг через друга. Количество строк выходного файла не должно превышать 50000. Если требуемого упорядочения колечек достичь не удается, в выходной файл нужно вывести строку impossible. Пример входных данных 4 3 2 4 1 Пример выходных данных 1 3 2 4 1 4 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	25.03.2021, 11:10
	сортировка вставками или что? 0

@XzzzX
	06.11.2023, 18:13
	Не по теме: IGPIGP, вряд ли спустя 1.5 года автор до сих пор мучается и единственное что ему поможет это код на c++ 0

Ожерелье

Решение