Рассчитать nCr при подсчете всех возможных путей задачи - PullRequest
Новая
       36

Рассчитать nCr при подсчете всех возможных путей задачи

0 голосов
/ 15 марта 2020

У меня есть сомнение в том, как автор достиг интуиции за формулой для вычисления (m + n -2) C n-1 в этой задаче - https://www.geeksforgeeks.org/count-possible-paths-top-left-bottom-right-nxm-matrix/

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

В частности, я не понимаю, как был разработан код ниже для того, что в основном представляет собой nCr 

 for (int i = n; i < (m + n - 1); i++) { 
        path *= i; 
        path /= (i - n + 1); 
    }

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

И это некоторые наблюдения, применяемые на практике. Даже если кто-то может указать мне на другую простую формулу для расчета того же самого, это будет здорово. В конце концов, это не так легко потреблять без наблюдения, которое могло бы занять время. Просто любопытно в то же время, почему это не решается стандартным способом решения nCr. Как здесь - https://www.geeksforgeeks.org/program-to-calculate-the-value-of-ncr-efficiently/

...