Рекурсия для реализации подсчета пути решетки - PullRequest
Новая
       23

Рекурсия для реализации подсчета пути решетки

0 голосов
/ 06 июня 2018

Я пытаюсь решить проблему нахождения количества путей в решетке (некоторой сетке) с помощью рекурсии.

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

Я не уверен, что это правильный способ использования рекурсии. Есть ли лучший способ решить эту проблему / использовать рекурсию для ее решения?

Спасибо

var array = [[0,0,0,0],[0,0,0,0],[0,0,0,0]];
var lastRowIndex=2;
var lastColIndex=3;
var count=0;
function pathCount(i,j){
    if(!(array[i-1]==undefined) || !(array[i][j-1]==undefined)){
        if(!(array[i-1]==undefined)){
            --i;
            pathCount(i,j);
            i++;
        }
        if(!(array[i][j-1]==undefined)){
            --j;
            pathCount(i,j); 
        }
    }else{
        ++count;
    }
    return count;
}
console.log(pathCount(lastRowIndex,lastColIndex));

1 Ответ

0 голосов
/ 06 июля 2018

Ваш код в порядке.в основном он делает то, что должен.

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

Поскольку любая проблема регрессии, давайте начнем с чего-то простого, индукционного базиса.

Первое замечание, в линейной сетке (размер 1xN или Nx1)есть только один действительный путь.Теперь, если вы находитесь в квадрате (i, j), у вас есть только 2 возможности перемещения, следовательно, общее количество путей является суммой двух элементов:

  1. Количество действительных путей изквадрат (i-1, j)
  2. Количество допустимых путей из квадрата (i, j-1)

(обратите внимание, что необходима проверка правильности этих аргументов, поскольку ониограничены возможными индексами сетки).

, поэтому возможная рекурсия: 

let size = 10;
let grid = {
  width: size,
  height: size
};
let currentPosition = {
  x: size,
  y: size
};

function validDecrement(value) {
  return (value - 1 >= 1 ? value - 1 : 1);
}

function countValidPaths(gridObject, startingLocation) {
  if (startingLocation.x === 1 || startingLocation.y === 1) {
    return 1;
  } else if (startingLocation.x > 1 && startingLocation.y > 1) {
    return countValidPaths(gridObject, {
      x: startingLocation.x,
      y: validDecrement(startingLocation.y)
    }) + countValidPaths(gridObject, {
      x: validDecrement(startingLocation.x),
      y: startingLocation.y
    });
  } else {
    console.log(`invalid input: grid: ${gridObject}, startingLocation: ${startingLocation}`);
  };
}

console.log(`Number of valid paths over a ${grid.height} by ${grid.width} grid is : ${countValidPaths(grid,currentPosition)}`);

Конечно, есть гораздо лучший подход к решению этого метода, чем рекурсия.число, которое вы ищете, является просто биномиальным коэффициентом C((grid.with-1)+(grid.height-1),(grid.width-1)) - решетки путей подсчета

...