Перебор

@BeHappy1456 · Регистрация: 16.03.2018

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

У Пети имеется игровое поле размером 3x3, заполненное числами от 1 до 9. В начале игры он может поставить фишку в любую клетку поля. На каждом шаге игры разрешается перемещать фишку в любую соседнюю по стороне клетку, но не разрешается посещать одну и ту же клетку дважды. Петя внимательно ведет протокол игры, записывая в него цифры в том порядке, в котором фишка посещала клетки. Пете стало интересно, какое максимальное число он может получить в протоколе. Помогите ему ответить на этот вопрос.

Формат входных данных

Входной файл содержит описание поля — 3 строки по 3 целых числа, разделенных пробелами. Гарантируется, что все девять чисел различны и лежат в диапазоне от 1 до 9.

Формат выходных данных

Выведите одно целое число — максимальное число, которое могло получиться в протоколе при игре на данном поле.
Ответ можно выводить не в виде числа, а в виде строки или в виде последовательности отдельных цифр (но не разделяя их пробелами).

Пример
стандартный ввод
1 2 3
4 5 6
7 8 9

стандартный вывод
987456321

@Catstail · 27.12.2020, 14:23

Как вариант:

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
27
28
29
graph=[(1,2),(1,4),(2,1),(2,3),(2,5),(3,2),(3,6), \
       (4,1),(4,5),(4,7),(5,2),(5,4),(5,6),(5,8), \
       (6,3),(6,5),(6,9),(7,4),(7,8),(8,5),(8,7), \
       (8,9),(9,6),(9,8)]
 
z=[]
       
def make_num(s):
    r=0
    for a in s:
        r=r*10+a
    return r    
       
def step(g,n,p): # n - текущая вершина, p - накопленный путь, g - граф
    global z
    for pair in g:
        if pair[0]==n and (pair[1] not in p):
            q=p+[pair[1]]
            step(g,pair[1],q)
    z.append(p)
    
def task():
    global z
    n=int(input("n="))
    z=[]
    step(graph,n,[n])
    print(max(map(make_num,z)))
    
task()

Хотя, возможно, жадный алгоритм был бы проще

Добавлено через 1 минуту
Опс... Не учел, что числа в табличке могут "тасоваться". Это несложно подправить.

@Miryz · 27.12.2020, 17:35

Catstail, решение не верно, например при n=2 программа выдает 8 чисел, когда можно было пройти матрицу получив 9 чисел, это нужно учесть.

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

@Catstail · 27.12.2020, 18:08

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

при n=2 программа выдает 8 чисел, когда можно было пройти матрицу получив 9 чисел

- боюсь, это не так. Попробуйте нарисовать путь, начинающийся в двойке длины 9.

Я чувствовал, что у меня есть ошибка. Кажется, удалось исправить:

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
27
28
29
30
31
32
33
graph=[(1,2),(1,4),(2,1),(2,3),(2,5),(3,2),(3,6), \
       (4,1),(4,5),(4,7),(5,2),(5,4),(5,6),(5,8), \
       (6,3),(6,5),(6,9),(7,4),(7,8),(8,5),(8,7), \
       (8,9),(9,6),(9,8)]
 
z=[]
       
def make_num(s):
    r=0
    for a in s:
        r=r*10+a
    return r    
       
def step(g,n,p): # n - текущая вершина, p - накопленный путь, g - граф
    global z
    k=0 # счетчик добавленных вершин
    for pair in g:
        if pair[0]==n and (pair[1] not in p):
            q=p+[pair[1]]
            k+=1
            step(g,pair[1],q)
    if k==0: # к текущему пути добавить ничего нельзя - конечный путь
        z.append(p)
    
def task():
    global z
    n=int(input("n="))
    z=[]
    step(graph,n,[n])
    #print(z) # можно распечатать варианты
    print(max(map(make_num,z)))
    
task()

@Miryz · 27.12.2020, 18:49

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

Попробуйте нарисовать путь, начинающийся в двойке длины 9.

тогда в алгоритме нужно выбирать среднее число или находящееся в углу

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

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

graph=[(1,2),(1,4),(2,1),(2,3),(2,5),(3,2),(3,6 ), \
(4,1),(4,5),(4,7),(5,2),(5,4),(5,6),(5,8 ), \
(6,3),(6,5),(6,9),(7,4),(7,8),(8,5),(8,7 ), \
(8,9),(9,6),(9,8)]

лучше преобразовать из матрицы, выглядит пугающе

@Catstail · 27.12.2020, 19:04

Miryz, В условии сказано: "На каждом шаге игры разрешается перемещать фишку в любую соседнюю по стороне клетку". Как я понимаю, по диагонали перемещать нельзя.

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

выглядит пугающе

- так ведь граф задается один раз. Менять его не нужно. Перечислить вершины явно - проще. Хотя можно и построить программно (это ничего не изменит)

Добавлено через 6 минут
Вот генерация графа. Кстати, она действительно будет нужна, если числа в матрице идут в другом порядке

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
matr=[[1,2,3],[4,5,6],[7,8,9]]
 
def make_graph(matr):
    res=[]
    n=len(matr)
    for i in range(n):
        for j in range(n):
            curr=matr[i][j]
            if i>=1:
                res.append((curr,matr[i-1][j]))
            if i<n-1:
                res.append((curr,matr[i+1][j]))                
            if j>=1:
                res.append((curr,matr[i][j-1]))
            if j<n-1:
                res.append((curr,matr[i][j+1]))                
    return res
    
print(make_graph(matr))

@Miryz · 27.12.2020, 19:05

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

Как я понимаю, по диагонали перемещать нельзя.

знаю. Я имел ввиду выбор начальной точки.

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

Перечислить вершины явно - проще. Хотя можно и построить программно

для личного решения может быть, для решения проверяемого тестирующей программой с матричным вводом нужно сделать программно. И как я понял, цифры можно не просто выстроить хаотично, а еще возможны одинаковые цифры в промежутке от 1 до 9, в таком случае решение с графами будет посложнее

@Catstail · 27.12.2020, 19:06

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

а еще возможны одинаковые цифры в промежутке от 1 до 9

Гарантируется, что все девять чисел различны и лежат в диапазоне от 1 до 9 - из условия

@Miryz · 27.12.2020, 19:08

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

Гарантируется, что все девять чисел различны и лежат в диапазоне от 1 до 9 - из условия

да, но почему это не могут быть одинаковые числа, не написано про именно последовательность чисел

@Catstail · 27.12.2020, 19:12

Окончательно:

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
matr=[[2,5,4],[3,9,8],[7,6,1]]  # другая раскладка
 
def make_graph(matr):
    res=[]
    n=len(matr)
    for i in range(n):
        for j in range(n):
            curr=matr[i][j]
            if i>=1:
                res.append((curr,matr[i-1][j]))
            if i<n-1:
                res.append((curr,matr[i+1][j]))                
            if j>=1:
                res.append((curr,matr[i][j-1]))
            if j<n-1:
                res.append((curr,matr[i][j+1]))                
    return res
    
#print(make_graph(matr))    
 
z=[]
       
def make_num(s):
    r=0
    for a in s:
        r=r*10+a
    return r    
       
def step(g,n,p): # n - текущая вершина, p - накопленный путь, g - граф
    global z
    k=0
    for pair in g:
        if pair[0]==n and (pair[1] not in p):
            q=p+[pair[1]]
            k+=1
            step(g,pair[1],q)
    if k==0:
        z.append(p)
    
def task():
    global z
    n=int(input("n="))
    z=[]
    graph=make_graph(matr)
    step(graph,n,[n])
    #print(z)
    print(max(map(make_num,z)))
    
task()

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

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

в таком случае решение с графами будет посложнее

- совсем ненамного

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

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

да, но почему это не могут быть одинаковые числа

- все 9 чисел различны...

Новые блоги и статьи Все статьи Все блоги /
Оттенки серого Argus19 18.03.2026 Оттенки серого Нашёл в интернете 3 прекрасных модуля: Модуль класса открытия диалога открытия/ сохранения файла на Win32 API; Модуль класса быстрого перекодирования цветного изображения в оттенки. . .	SDL3 для Desktop (MinGW): Рисуем цветные прямоугольники с помощью рисовальщика SDL3 на Си и C++ 8Observer8 17.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-rectangles-sdl3-c. zip finish-rectangles-sdl3-cpp. zip	Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая ссылка» (hard link),. . .	[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .
делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .

@BeHappy1456 25 / 2 / 0 Регистрация: 16.03.2018 Сообщений: 203

	Перебор 27.12.2020, 13:36. Показов 1462. Ответов 9 Метки нет (Все метки) У Пети имеется игровое поле размером 3x3, заполненное числами от 1 до 9. В начале игры он может поставить фишку в любую клетку поля. На каждом шаге игры разрешается перемещать фишку в любую соседнюю по стороне клетку, но не разрешается посещать одну и ту же клетку дважды. Петя внимательно ведет протокол игры, записывая в него цифры в том порядке, в котором фишка посещала клетки. Пете стало интересно, какое максимальное число он может получить в протоколе. Помогите ему ответить на этот вопрос. Формат входных данных Входной файл содержит описание поля — 3 строки по 3 целых числа, разделенных пробелами. Гарантируется, что все девять чисел различны и лежат в диапазоне от 1 до 9. Формат выходных данных Выведите одно целое число — максимальное число, которое могло получиться в протоколе при игре на данном поле. Ответ можно выводить не в виде числа, а в виде строки или в виде последовательности отдельных цифр (но не разделяя их пробелами). Пример стандартный ввод 1 2 3 4 5 6 7 8 9 стандартный вывод 987456321 0

@Miryz 291 / 131 / 58 Регистрация: 24.11.2019 Сообщений: 532
	27.12.2020, 17:35
	Catstail, решение не верно, например при n=2 программа выдает 8 чисел, когда можно было пройти матрицу получив 9 чисел, это нужно учесть. Добавлено через 15 минут Перед выходом на центр нужно проверять левый и правый столбец, чтобы путь по одному из них был пройден, это для выхода снизу или сверху, если справа или слева, то первую и последнюю строку. Если путь пройден только по одной стороне, то нужно допройти строку/столбец или опять путь будет не полон. 0