Модифицированные Ханойской башни

@Pasha0005 · Регистрация: 01.02.2018

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

1)Ограничение по времени работы программы: 1 секунда

На дорогах Ханоя было введено одностороннее круговое движение, поэтому теперь диск со стержня 1 можно перекладывать только на стержень 2, со стержня 2 на 3, а со стержня 3 на 1. Перекладывать диски в другом направлении нельзя.

Определите последовательность перемещений, необходимых для переноса башни из n

дисков со стержня номер 1 на стержень номер 3.
Входные данные

Программа получает на вход количество дисков в пирамидке n
(1⩽n⩽10).
Выходные данные

Программа должна вывести последовательность перемещений пирамидки из n
дисков со стержня номер 1 на стержень номер 3 в соответствии с правилами этой игры. Каждое перемещение состоит из трех чисел, записанных в одной строке через пробел: номер диска (число от 1 до n, самый маленький диск имеет номер 1, самый большой — номер n

), номер стержня, с которого снимается диск (1, 2 или 3), номер стержня, на который кладется диск (1, 2 или 3).

Вам не нужно находить минимальное решение, но количество совершенных перемещений не должно быть больше 200000, при условии, что количество дисков не превосходит 10

@Black Fregat · 09.02.2018, 18:10

Забавная задача. Раз не нужно искать оптимальное решение, пойдёт, например, так:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
allowed = {
  (1,2): True,
  (2,1): False,
  (2,3): True,
  (3,2): False,
  (3,1): True,
  (1,3): False,
}
 
def move(n, x, y):
  if n > 0:
    z = 6 - x - y
    if allowed[(x,y)]:
      move(n-1, x, z)
      print(n, x, y)
      move(n-1, z, y)
    else:
      move(n, x, z)
      move(n, z, y)
 
n = int(input())
move(n,1,3)

Добавлено через 3 минуты
Не пойдёт. Выходит за ограничение для 10, надо таки оптимизировать..

Добавлено через 27 минут
Пришлось расписать сложный ход явно, тогда находит оптиальное решение:

Python
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
allowed = {
  (1,2): True,
  (2,1): False,
  (2,3): True,
  (3,2): False,
  (3,1): True,
  (1,3): False,
}
 
def move(n, x, y):
  if n > 0:
    z = 6 - x - y
    if allowed[(x,y)]:
      move(n-1, x, z)
      print(n, x, y)
      move(n-1, z, y)
    else:
      move(n-1, x, y)
      print(n, x, z)
      move(n-1, y, x)
      print(n, z, y)
      move(n-1, x, y)
 
n = int(input())
move(n,1,3)

@Pasha0005 · 14.02.2018, 20:19 **[ТС]**

Black Fregat ты профи

Добавлено через 17 секунд
Спасибо

Новые блоги и статьи Все статьи Все блоги /
Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .	Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .	Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .
Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .	модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий anaschu 08.04.2026 https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI	Блокировка документа от изменений, если он открыт у другого пользователя Maks 08.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .	Система безопасности+живучести для сервера-слоя интернета (сети). Двойная привязка. Hrethgir 08.04.2026 Далее были размышления о системе безопасности. Сообщения с наклонным текстом - мои. А как нам будет можно проверить, что ссылка наша, а не подделана хулиганами, которая выбросит на другую ветку и. . .

@Pasha0005 0 / 0 / 0 Регистрация: 01.02.2018 Сообщений: 46

	Модифицированные Ханойской башни 09.02.2018, 15:11. Показов 13843. Ответов 2 Метки нет (Все метки) 1)Ограничение по времени работы программы: 1 секунда На дорогах Ханоя было введено одностороннее круговое движение, поэтому теперь диск со стержня 1 можно перекладывать только на стержень 2, со стержня 2 на 3, а со стержня 3 на 1. Перекладывать диски в другом направлении нельзя. Определите последовательность перемещений, необходимых для переноса башни из n дисков со стержня номер 1 на стержень номер 3. Входные данные Программа получает на вход количество дисков в пирамидке n (1⩽n⩽10). Выходные данные Программа должна вывести последовательность перемещений пирамидки из n дисков со стержня номер 1 на стержень номер 3 в соответствии с правилами этой игры. Каждое перемещение состоит из трех чисел, записанных в одной строке через пробел: номер диска (число от 1 до n, самый маленький диск имеет номер 1, самый большой — номер n ), номер стержня, с которого снимается диск (1, 2 или 3), номер стержня, на который кладется диск (1, 2 или 3). Вам не нужно находить минимальное решение, но количество совершенных перемещений не должно быть больше 200000, при условии, что количество дисков не превосходит 10 0

@Pasha0005 0 / 0 / 0 Регистрация: 01.02.2018 Сообщений: 46
	14.02.2018, 20:19 [ТС]
	Black Fregat ты профи Добавлено через 17 секунд Спасибо 0

Модифицированные Ханойской башни

Решение