Определить, сколько существует различных маршрутов, ведущих из левого верхнего в правый нижний угол - Free Pascal

  1. Дана прямоугольная доска N × M (N строк и M столбцов). В левом верхнем углу находится шахматный конь, которого необходимо переместить в правый нижний угол доски. При этом конь может ходить только так, как показано на рисунке: Необходимо определить, сколько существует различных маршрутов, ведущих из левого верхнего в правый нижний угол. Входные данные В первой строке входного файла находятся два натуральных числа N и M (1 ≤ N, M ≤ 15). Выходные данные В выходной файл выведите единственное число количество способов добраться конём до правого нижнего угла доски. Примеры входные данные 4 4 выходные данные 2 входные данные 7 15 выходные данные 13309 Пробовал решить так:


textual

Код к задаче: «Определить, сколько существует различных маршрутов, ведущих из левого верхнего в правый нижний угол - Free Pascal»

{$mode objfpc}
{$COPERATORS ON} //Чтобы можно было использовать +=
const MaxSize = 15;
var dp: array [1..MaxSize, 1..MaxSize] of int64;// Насколько я помню ответ там большой можем быть, потому лучше взять int64
    n, m: Integer;
    
function answer(i, j: Integer): int64;
begin
   if dp[i][j] >= 0 then Exit(dp[i][j]); 
   { Будем считать что если dp[i][j] = -1, то мы его еще не считали, а если мы уже считали это значение, тогда 
     возвращаем его и выходим из функции}
   dp[i][j] := 0;
   if i-2 >= 1 then begin // Проверяем границы чтоб не обратиться к элементу которого нет
      if j-1 >= 1 then dp[i][j] += answer(i-2, j-1); // прибавляем ответ
      if j+1 <= m then dp[i][j] += answer(i-2, j+1);
   end;
   if j-2 >= 1 then begin
      if i-1 >= 1 then dp[i][j] += answer(i-1, j-2);
      if i+1 <= n then dp[i][j] += answer(i+1, j-2);
   end;
   Result := dp[i][j];
end;
 
var i, j: Integer;
begin
   Readln(n, m);
   for i := 1 to n do
      for j := 1 to m do
         dp[i][j] := -1; // Изначально все пометим -1
   dp[1][1] := 1; // Кроме начального значения
   Write(answer(n, m));
end.

СДЕЛАЙТЕ РЕПОСТ

11   голосов, оценка 3.818 из 5



Похожие ответы
  1. Улитка ползёт по вертикальному шесту высотой h метров, поднимаясь за день на a метров, а за ночь спускаясь на b метров. На какой день улитка доползёт до вершины шеста? Программа получает на вход натуральные числа h, a, b и должна вывести одно натуральное число. Гарантируется, что a>b. При решении этой задачи нельзя пользоваться условной инструкцией if и циклами. ---------------------------- Как решить эту задачу без конструкции if? С ней легко, а без нее как? Не говорите мне, что это легкая задача. Дайте мне работающий код. В гугл не посылать, решения либо абсурдно легкие(h div (a-b), что, очевидно, неверно), либо слишком сложные, но в тоже время не выдающие правильные ответы.

  1. не могу понять как описать в паскале делятся без остатка на x,х-1,х+1. Одновременно? В цикле от 1 до 100 if (i mod x = 0) and ((i-1) mod x = 0) and ((i+1) mod x = 0) tnen n := n + 1; задание 51. Ввести x с клавиатуры и определить, сколько чисел в промежутке от 1 до 100 делятся без остатка на x, x-1 или x+1.

  1. Помогите решить. Даны четыре точки A1(x1, y1), A2(x2, y2), A3(x3, y3), A4(x4, y4). Определить, будут ли они вершинами параллелограмма.

  1. Даны три матрицы: a, b, c размером n m(n,m<=12). Определить в какой из них среднее арифметическое положительных элементов больше.

  1. : Написать программы с использованием - условного оператора, - логической переменной, определяющие расположение точки А(х,у) относительно заштрихованной области: принадлежит области или не принадлежит.

  1. В Волшебной стране используются монетки достоинством A1, A2,…, AM. Волшебный человечек пришел в магазин и обнаружил, что у него есть ровно по две монетки каждого достоинства. Ему нужно заплатить сумму N. Напишите программу, определяющую, сможет ли он расплатиться без сдачи. Входные данные В первой строке записано сначала число N (1 ≤ N≤ 10^9), затем число M (1 ≤ M≤ 16). Во второй строке записано M попарно различных чисел A1, A2,…, AM (1 ≤ Ai ≤ 107). Числа разделяются пробелами. Выходные данные Выведите наименьшее количество монет K, которое придется отдать Волшебному человечку, если он сможет заплатить указанную сумму без сдачи. Если без сдачи не обойтись, то выведите одно число 0. Если же у Волшебного человечка не хватит денег, чтобы заплатить указанную сумму, выведите одно число –1 (минус один). Вот мой код, но он крашится

  1. Определить, сколько раз во введенной строке с 5 по 15 позицию встречается символ ‘*’.

  1. Заданы два натуральных числа. Найти остаток от деления первого числа на второе и определить, расположены ли цифры в записи остатка в порядке возрастания или убывания слева направо.

  1. Создать стек со случайными целыми числами. Подсчитать, сколько его элементов имеют отрицательные значения.