1.Открыть правой рукой хлебницу; __2.Взять булку хлеба правой рукой; __3.Положить хлеб на разделочную доску; (предположим, что доска уже лежала на столе) __4.Открыть правой рукой верхний ящик стола; __5.Найти блестящий нож, длиной 20 см, с черной ручкой; __6.Взять нож в правую руку; __7.Поднести нож к хлебу; __8.Зафиксировать хлеб левой рукой, взявшись за левый край булки; __9.Расположить нож строго над правым ребром булки хлеба; __10.Повторять следующие действия 5 раз: 10.1.Отступить влево на сантиметр; 10.2.Повторять следующие действия, пока лезвие ножа не не коснется доски: 10.2.1.Прижать нож к хлебу; 10.2.2.Совершить ножом возвратно поступательное движение вперед-назад; 10.3.Поднять нож вверх; __11.Положить нож в ящик; __12.Отпустить левой рукой хлеб.
Объяснение:
Запускаем программу и смотрим, как она работает: Ой... вместе с пятым куском и палец отрезал... чёрт! остановить программу! Я же не написал как именно нужно зафиксировать хлеб левой рукой, схватился как попало и большой палец торчал в сторону... Возвращаемся к строчке "Зафиксировать хлеб левой рукой, взявшись за левый край булки;" После нее пишем: "Поджать большой палец левой руки влево, к ладони;" Запускаем программу Ой... на строчке "Положить нож в ящик;" нож упал на пол... Проклятье! оказывается, стол стоит немного под наклоном и ящик сам закрылся... Возвращаемся к коду и перед строчкой "Положить нож в ящик;" пишем "Открыть правой рукой верхний ящик стола;" Заметили ошибку? Нет?! Как мы можем открыть ящик правой рукой, если в этой руке нож? Значит, сначала нужно положить нож на стол, потом открыть ящик, снова взять нож и т.д. И делаем мы это до тех пор, пока хлеб не будет нарезан как следует, без повреждения мебели и пальцев. Вот, примерно так происходит отладка С опытом начинаешь писать программы, которые работают с первого раза, допуская минимум ошибок, а проверка "открыт ли ящик", перед складыванием в него чего-то, входит в привычку. Когда какие-то операции совершаются постоянно, такие как нарезка хлеба, мойка посуды и т.д., то программисты их описывают в виде процедур. Процедура - набор определенных действий, спрятанный под одной командой. Таким образом, текст программы, который я приводил выше, можно поместить в процедуру под названием НарезатьХлеба(параметр), где в качестве параметра будем указывать количество кусков
Объяснение:
Эта задача сводится к задаче поиска пути на графе пространства состояний.
Состояние - положение черепашки на поле - (x, y).
Граф пространства состояний состоит из таких вершин-состояний, их количество N * M.
Переходов между вершинами всего два: R и D.
Здесь можно заметить, что прийти к одним и тем же вершинам мы можем разными путями. Например, путь из (0,0) в (1,1) можно расписать и как RD ((0,0) -> (0,1) -> (1,1)), и как DR ((0,0) -> (1,0) -> (1,1)), но это два разных маршрута.
Однако при неизменном ценовом листе максимальная стоимость и оный маршрут в любой клетке поля значение строго определённое и неизменное во времени.
Это значит, что нам не нужно рассчитывать результат для одинаковых состояний больше одного раза, так как они будут совпадать.
Итак, для каждого состояния у нас есть два правила перехода. Рассчитывая максимальную стоимость маршрута для состояния (x,y) мы следуем алгоритму:
Если можем идти вправо, рассчитываем параметры для этого маршрутаЕсли можем идти вниз, рассчитываем параметры для этого маршрутаВыбираем между путями, если можем идти, или стоим, если уже не можемК выбранному варианту добавляем параметры текущего состоянияЕсли такой алгоритм применить к состоянию (0,0), то дойдем до (N, M) и получим максимальную цену и маршрут.
Код:
import re
from typing import List
cache = {}
def calculate_max_way_price(x: int, y: int, prices: List[List[int]], m:int, n:int):
if (x, y) in cache:
return cache[(x, y)]
direction = ''
cost = prices[y][x]
x_cost, y_cost = -1, -1
x_way, y_way = '', ''
if x < m - 1:
x_cost, x_way = calculate_max_way_price(x + 1, y, prices, m, n)
if y < n - 1:
y_cost, y_way = calculate_max_way_price(x, y + 1, prices, m, n)
if not (x_cost < 0 and y_cost < 0):
if x_cost > y_cost:
cost += x_cost
direction = 'R' + x_way
else:
cost += y_cost
direction = 'D' + y_way
cache[(x, y)] = (cost, direction)
return cost, direction
MNtext = input('Enter N M: ')
MN = [int(x) for x in re.findall(r'\d+', MNtext)]
if len(MN) != 2:
print("Input data error! It is not M and N")
exit(-1)
N, M = MN[0], MN[1]
MAX_STEP_PRICE = 100
data = input('Enter all numbers separated by spaces. You must type ' + str(M*N) + ' elements:')
data = [int(x) for x in re.findall(r'\d+', data)]
if len(data) != N * M:
print("Input data error! Too few/many numbers")
exit(-2)
prices = []
for j in range(N):
prices.append(data[M*j:M*(j+1)])
print(calculate_max_way_price(0, 0, prices, M, N))
