Ханойская башня

@azazanchik · Регистрация: 24.01.2019

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

Уважаемые, киберфорумчане! Не знаю уже к кому идти, никак не решатся задачи. Весь гугл прочесан вдоль и поперек. Классическую интерпретацию решил сам, без всяких подсказок. А вот эти две что-то никак не идут, быть может это от того, что я уже 10 часов решаю задачи)))

Прошу расскажите логику, я больше не могу так жить)) Ну или приведите решение на любом языке, я пойму)

Условие:

Первоначально все диски лежат на стержне номер 1. Переместите диски с нечетными номерами на стержень номер 2, а с четными номерами - на стержень номер 3.

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

Входные данные
Вводится натуральное число - количество дисков.

Выходные данные
Выведите ответ на задачу.

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

@dondublon · 25.01.2019, 11:40

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

@azazanchik · 25.01.2019, 17:17 **[ТС]**

Это-то да, но вот куда перекладывать блины, которые были до четного или нечетного

Добавлено через 9 минут
С 12 года человек не может решить) Сортирующие башни

@azazanchik · 27.01.2019, 13:25 **[ТС]**

В общем сам пришел к такому алгоритму:

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
def f(n, x, y):
    if n > 0:
        f(n - 1, x, 6 - x - y)
        print(n, x, y)
        f(n - 1, 6 - x - y, y)
 
 
def sortF(n, x, y):
    if n > 0:
        f(n - 1, x, 6 - x - y)
        print(n, x, y)
        if n > 3:
            f(n - 3, 6 - x - y, x)
        if n > 2:
            print(n - 2, 6 - x - y, y)
        if n > 3:
            sortF(n - 3, x, 6 - x - y)
 
 
n = int(input())
if n % 2 == 0:
    sortF(n, 1, 3)
else:
    sortF(n, 1, 2)

Добавлено через 12 минут
И вторая:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
def f(n,x,y):
    if n > 0:
        if n == 1:
            print(n, x, y)
        else:
            f(n - 1, x, y)
            f(n - 2, y, 6 - x - y)
            print(0, x, y)
            f(n - 2, 6 - x - y, x)
            f(n - 1, x, y)
 
n = int(input())
f(n,1,3)

@dondublon · 28.01.2019, 12:08

@блблблблблблблб · 28.03.2021, 20:35

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

def f(n,x,y):
if n > 0:
if n == 1:
print(n, x, y)
else:
f(n - 1, x, y)
f(n - 2, y, 6 - x - y)
print(0, x, y)
f(n - 2, 6 - x - y, x)
f(n - 1, x, y)
n = int(input())
f(n,1,3)

Немного неправильно выдаёт, какой то 0 диск, хотя на его месте должен быть 2.
Можете помочь исправить

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

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
def f(n,x,y):
    if n > 0:
        if n == 1:
            print(n, x, y)
        else:
            f(n - 1, x, y)
            f(n-2 , y, 6 - x - y)
            print(2, x, y)
            f(n-2 , 6 - x - y, x)
            f(n - 1, x, y)
 
n = int(input())
f(n,1,3)

вот исправленный вариант 2 решения

@QuL1ux · 02.04.2023, 15:24

Решение первой

Python
1
2
3
4
5
6
7
8
9
def func(a, b, c):
    if a > 0:
        tmp = 6 - b - c
        func(a-1, b, tmp)
        print(a, b, c)
        func(a-1, tmp, c)
 
n = int(input())
func(n, 1, 3)

@SolomonRei · 02.04.2023, 15:53

1-я задача

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def hanoi(n, from_rod, to_rod, aux_rod):
    if n == 1:
        print(1, from_rod, to_rod)
        return
 
    hanoi(n - 1, from_rod, aux_rod, to_rod)
 
    print(n, from_rod, to_rod)
 
    hanoi(n - 1, aux_rod, to_rod, from_rod)
 
 
n = int(input())
for i in range(1, n+1):
    if i % 2 == 1:
        hanoi(i, 1, 2, 3)
    else:
        hanoi(i, 1, 3, 2)

2-я задача

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
26
def move_disk(start, end):
    global moves
    moves.append((1, start, end))
 
def exchange_disks(start, end, temp):
    global moves
    if len(start) > 0 and len(end) > 0 and start[-1] == end[-1] - 1:
        moves.append((0, start, end))
        end.append(start.pop())
    else:
        exchange_disks(start, temp, end)
        move_disk(start, end)
        exchange_disks(temp, end, start)
 
n = int(input())
 
moves = []
start = list(range(n, 0, -1))
end = []
temp = []
 
exchange_disks(start, end, temp)
 
print(len(moves))
for move in moves:
    print(move[0], move[1], move[2])

Новые блоги и статьи Все статьи Все блоги /
Программная установка даты и запрет ее изменения Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: при создании документов установить период списания автоматически. . .	Вывод данных в справочнике через динамический список Maks 01.04.2026 Реализация из решения ниже выполнена на примере нетипового справочника "Спецтехника" разработанного в конфигурации КА2. Задача: вывести данные из ТЧ нетипового документа. . .	Функция заполнения текстового поля в реквизите формы документа Maks 01.04.2026 Алгоритм из решения ниже реализован на нетиповом документе "ВыдачаОборудованияНаСпецтехнику" разработанного в конфигурации КА2, в дополнении к предыдущему решению. На форме документа создается. . .	К слову об оптимизации kumehtar 01.04.2026 Вспоминаю начало 2000-х, университет, когда я писал на Delphi. Тогда среди программистов на форумах активно обсуждали аккуратную работу с памятью: нужно было следить за переменными, вовремя. . .
Идея фильтра интернета (сервер = слой+фильтр). Hrethgir 31.03.2026 Суть идеи заключается в том, чтобы запустить свой сервер, о чём я если честно мечтал давно и давно приобрёл книгу как это сделать. Но не было причин его запускать. Очумелые учёные напечатали на. . .	Модель здравосоХранения 6. ESG-повестка и устойчивое развитие; углублённый анализ кадрового бренда anaschu 31.03.2026 В прикрепленном документе раздумья о том, как можно поменять модель в будущем	10 пpимет, которые всегда сбываются Maks 31.03.2026 1. Чтобы, наконец, пришла маршрутка, надо закурить. Если сигарета последняя, маршрутка придет еще до второй затяжки даже вопреки расписанию. 2. Нaдоели зима и снег? Не надо переезжать. Достаточно. . .	Перемещение выделенных строк ТЧ из одного документа в другой Maks 31.03.2026 Реализация из решения ниже выполнена на примере нетипового документа "ВыдачаОборудованияНаСпецтехнику" с единственной табличной частью "ОборудованиеИКомплектующие" разработанного в конфигурации КА2. . . .

@azazanchik 1 / 1 / 0 Регистрация: 24.01.2019 Сообщений: 3

	Ханойская башня 24.01.2019, 22:48. Показов 33303. Ответов 7 Метки нет (Все метки) Уважаемые, киберфорумчане! Не знаю уже к кому идти, никак не решатся задачи. Весь гугл прочесан вдоль и поперек. Классическую интерпретацию решил сам, без всяких подсказок. А вот эти две что-то никак не идут, быть может это от того, что я уже 10 часов решаю задачи))) Прошу расскажите логику, я больше не могу так жить)) Ну или приведите решение на любом языке, я пойму) Условие: Первоначально все диски лежат на стержне номер 1. Переместите диски с нечетными номерами на стержень номер 2, а с четными номерами - на стержень номер 3. Вам не нужно находить минимальное решение, но количество совершенных перемещений не должно быть больше 200000, при условии, что количество дисков не превосходит 10. Входные данные Вводится натуральное число - количество дисков. Выходные данные Выведите ответ на задачу. Примеры входные данные 2 выходные данные 1 1 2 2 1 3 входные данные 3 выходные данные 1 1 2 2 1 3 1 2 3 3 1 2 1 3 2 0

@dondublon 4653 / 2073 / 366 Регистрация: 17.03.2012 Сообщений: 10,183 Записей в блоге: 6
	25.01.2019, 11:40
	Странно. Почитал первую задачу, вроде бы, она должна так же легко поддаваться рекурсии, как и классическая. 0

@azazanchik 1 / 1 / 0 Регистрация: 24.01.2019 Сообщений: 3
	25.01.2019, 17:17 [ТС]
	Это-то да, но вот куда перекладывать блины, которые были до четного или нечетного Добавлено через 9 минут С 12 года человек не может решить) Сортирующие башни 0

@dondublon 4653 / 2073 / 366 Регистрация: 17.03.2012 Сообщений: 10,183 Записей в блоге: 6
	28.01.2019, 12:08
	0