Объяснение:
Эта задача сводится к задаче поиска пути на графе пространства состояний.
Состояние - положение черепашки на поле - (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))
Объяснение:
program zadachiGAME;
uses crt;
var a:array [1..59] of array [1..59] of string{integer};
var n,x,y,x1,y1,x3,y3,spawn,x4,y4,x5,y5,Xx,Yy,Xb,Yb,delta1,delta2,deltaGAMER,live:integer; var j:char;label restart1;label otskok1;label otskok2;
begin
restart1:
window (1,1,80,50);
clrscr;
cursoroff;
x1:=35;
y1:=44;
delta1:=1;
delta2:=1;
cursoroff;
live:=10;
y:=50;
x:=25;
deltagamer:=1;
gotoxy(x,y);
x3:=24;
y3:=1;
x4:=6;
y4:=45;
write('press for begin!');
readkey;
gotoxy(X,Y);
write(' ');
n:=1;
spawn:=1;
y3:=1;
x3:=24;
TextColor(3);
for spawn:=1 to 50 do
begin
gotoxy(x3,y3);
writeln('| |');
x3:=24;
y3:=y3+1;
end;
TextColor(11);
gotoxy(40,12);
begin
for y5:=10 to 22 do
for x5:=36 to 44 do
begin
gotoxy(x5,y5);
a[x5,y5]:=('a');
gotoxy(x5,y5);
write ('a');
end;
end;
repeat
begin
delay(53);
x1:=x1+delta1;
y1:=y1+delta2;
gotoxy(x1,y1);
write ('*');
gotoxy(x1+delta1*(-1),y1+delta2*(-1));
write(' ');
if ((x1<>x5) and (y1<>y5)) then //место с присваванием,которое не работает по непонятным причинам
begin
Xx:=x1;
Yy:=y1;
end;
if (a[x1,y1]=('a')) then
begin //проверка для ркошета в разные стороны
if (((x1-Xx)=(-1)) and ((y1-Yy)=(-1)) and ((x1=x5) and (y1=y5)))
then
begin
a[x5,y5]:=('an');
delta1:=delta1*(-1);
end;
if (((x1-Xx)=1) and ((y1-Yy)=(-1)) and ((x1=x5) and (y1=y5)))
then
begin
a[x5,y5]:=('an');
delta2:=delta2*(-1);
end;
end;
TextColor(11);
gotoxy(x4,y4);
begin //отображение некоторых данных
writeln('live - ',live:1);
writeln('Xx ',Xx,'Yy ',Yy);
write ('X1 ',x1,'Y1 ',y1);
end;
TextColor(5);
if (x1=58) or (x1=25) then
delta1:=(-1)*(delta1);
if (y1=2) then
delta2:=delta2*(-1);
if ((y1=y-1) and (x1=x)) or ((y1=y-1) and (x1=x-1)) or ((y1=y-1) and (x1=x+1)) or ((y1=y-1) and (x1=x+2)) or ((y1=y-1) and (x1=x+3)) then
delta2:=delta2*(-1)
else
if ((y1=y) and (x1<>x)) or ((y1=y) and (x1<>x-1)) or ((y1=y) and (x1<>x+1)) or ((y1=y) and (x1<>x+2)) or ((y1=y) and (x1<>x+3)) then
begin
gotoxy(x1,y1);
write(' ');
delta2:=delta2*(-1);
y1:=y1+delta2-1;
live:=live-1;
end;
TextColor(13);
if keypressed then
begin
//if keypressed then
j:=readkey;
case j of
#77:deltaGAMER:=3;//вправо
#75:deltaGAMER:=(-3);//влево
#27:Exit;
else
deltagamer:=(0);
end;
if (x=25) or ((x>55) and (x<59)) then
deltagamer:=(-1)*(deltagamer);
if (x=25) and (j=#77) or (x=56) and (j=#75)then
deltagamer:=(-1)*(deltagamer);
x:=x+(1*deltaGamer);
if j<> #75 then
begin
gotoxy(x,y);
write ('---');
end;
if j<> #77 then
begin
gotoxy(x,y);
write ('---');
end
else
gotoxy(x+deltagamer*(-1),wherey);
write(' ');
gotoxy(x,y);
end;
end;
until live=0;
begin
clrscr;
gotoxy(37,25);
writeln (' Defith');
gotoxy(37,27);
writeln (' press "r" for restart');
j:=readkey;
case j of
#114:goto restart1;
#82:goto restart1;
#170:goto restart1;
#138:goto restart1;
#27:end;
end;
end.
Задание 1
Алгоритм – это последовательность действий в определённом порядке.
Значение переменной - атрибут физической или абстрактной системы, который может изменять своё (как правило, численное) значение.
Цикл – это разновидность управляющей конструкции в высокоуровневых языках программирования, предназначенная для организации многократного исполнения набора инструкций.
Ветвление – это оператор, конструкция языка программирования, обеспечивающая выполнение определённой команды (набора команд) только при условии истинности некоторого логического выражения.
Задание 2
Задание 3
Основные алгоритмические структуры
▪️ Структура следования. ▪️ Структура полное ветвление ▪️ структура не полное ветвление
▪️ Цикл с предусловием. ▪️ Цикл с под условием. ▪️ Цикл с параметром.
Фото это для Задания 2