Напишите программу, которая использует динамическое программирование для решения следующей проблемы. Найдите точку ближа ⇐ Python

[Anonymous]

Я пытался решить этот вопрос. Нужно это сделать в Python. Вот вопрос: < /p>
Напишите программу, которая использует динамическое программирование для решения следующей задачи. После каждой 3 -й итерации сделайте заданное количество шагов назад в направлениях X и Y. Приходите в точку (x, y), расстояние которого ближе всего к P (используя формулу расстояния). Начните с начала координат (0,0). < /P>
точечный класс
Точечный класс предоставляется для вас. В классе есть два члена данных: < /p>
x - The x-coordinate of a point
y - The y-coordinate of a point
< /code>
Основная программа < /p>
p также определено, и также прочитал координат в x и y координаты (целые числа) для точки P. /> вперед вдоль оси x-оси < /p>
вперед вдоль оси Y < /p>
обратно вдоль обеих оси каждые 3-ю итерацию < /p>
< /li>
определяет динамическое программирование, которое соответствует, и уносят необходимый номер, а также соответствует определяет, и это соответствует определяет, и это соответствует определяет, и это соответствует определяет, и это соответствует определяет, что соответствует определяет, и решает, что соответствует определениям, и решает, что соответствует определениям, и решает, что соответствует определениям, и решает, что соответствует определениям, и решает, что соответствует определениям. п. После каждой итерации вычислите расстояние между точкой P и текущим местоположением, используя функцию расстояния:
d = sqrt ((x_p - x_1)^2 + (y_p - y_1)^2)
Считайте количество итераций. Подсказка: отслеживайте предыдущее место. Точка P, 2-это количество шагов, которые нужно предпринять вдоль оси x, каждая итерация, 3-это количество шагов, которые нужно предпринять по оси Y, а 1-это количество шагов, которые нужно сделать обратно вдоль как оси x, так и y каждую 3-ю итерацию, выход < /p>
point p: (4,5)
gropty. /> Номер итераций: 2 < /p>
< /li>
< /ol>
*Примечание: Количество шагов, которые нужно сделать назад, никогда не превышает количество шагов, сделанных вперед.import math

# Point class
class Point:
def __init__(self):
self.x = 0
self.y = 0

# Main program
# Read in x and y for Point P
p = Point()
p.x = int(input())
p.y = int(input())

# Read in num of steps to be taken in X and Y directions
# Read in num of steps to be taken (backwards) every 3 steps
# Write dynamic programming algorithm
# Output
< /code>
Я пробовал так много вещей и в конечном итоге попытался сделать это, заканчивая его после 30 итераций, но обновляя все числа с наименьшим расстоянием от Point P. Не уверен, почему это неправильно, но это мой код: < /p>
import math

# Point class
class Point:
def __init__(self):
self.x = 0
self.y = 0

# Main program
# Read in x and y for Point P
p = Point()
p.x = int(input())
p.y = int(input())

# Read in num of steps to be taken in X and Y directions
num_x = int(input())
num_y = int(input())
# Read in num of steps to be taken (backwards) every 3 steps
num_back = int(input())
# Write dynamic programming algorithm
curr = Point()
previous = Point()

curr.x += num_x
curr.y += num_y
d1 = math.sqrt((p.x - previous.x)**2 + (p.y - previous.y)**2)
d2 = math.sqrt((p.x - curr.x)**2 + (p.y - curr.y)**2)
count = 1
num_steps = 0
final = Point()
while True:
if count == 30:
break
else:
count += 1
previous.x = curr.x
previous.y = curr.y
if count % 3 == 0:
curr.x -= num_back
curr.y -= num_back
else:
curr.x += num_x
curr.y += num_y
if d2 < d1:
d1 = d2
num_steps = count
final.x = curr.x
final.y = curr.y
d2 = math.sqrt((p.x - curr.x)**2 + (p.y - curr.y)**2)
# Output
print(f'Point P: ({p.x},{p.y})')
print(f"Arrival point: ({final.x},{final.y})")
print(f'Distance between P and arrival: {d1: 6f}')
print(f'Number of iterations: {num_steps}')
< /code>
дает As output: < /p>
4
5
2
3
1
Point P: (4,5)
Arrival point: (3,5)
Distance between P and arrival: 1.000000
Number of iterations: 3


Подробнее здесь: https://stackoverflow.com/questions/797 ... problem-fi