Зачем нужен следующий код? биномиальный коэффициент

Question

Я делаю проект эйлера, и я сейчас в проблеме 15, вот ссылка: https://projecteuler.net/problem=15. Я пытаюсь решить это с помощью биномиального коэффициента. Вот сайт, который его объясняет: http://www.mathblog.dk/project-euler-15/. Вы можете найти его внизу.

Мой вопрос: почему следующий код не так? Поскольку это следует за математическим алгоритмом, я думаю: n-k + i/i

 int grid = 20; 
     long paths = 1; 
     for (int i = 0; i < grid; i++) 
     { 
      paths *= (grid * 2) - (grid + i) 
      paths /= (i + 1); 
     } 
     Console.WriteLine(paths); 
     Console.ReadKey(); 

И почему этот код не так? Это точно так же, как и сайт mathblog, но в 1 строке.

 int grid = 20; 
     long paths = 1; 
     for (int i = 0; i < grid; i++) 
     { 
      paths *= ((grid * 2) - i)/(i + 1); 
     } 
     Console.WriteLine(paths); 
     Console.ReadKey(); 

Но почему именно этот код? Разве это не так, как предыдущий код? И это точно не соответствует математическому алгоритму? Потому что это n-k + i/i, и этот код делает n-i/i

 int grid = 20; 
     long paths = 1; 
     for (int i = 0; i < grid; i++) 
     { 
      paths *= ((grid * 2) - i); 
      paths /= (i + 1); 
     } 
     Console.WriteLine(paths); 
     Console.ReadKey(); 

Thnx guys!

Answer 1

Если вы хотите combain вычисления должно быть, как это

paths = (path *((grid * 2) - i))/(i + 1); 

Answer 2

По соглашению, во многих языках программирования, Int/INT дает ИНТ * не число с плавающей точкой. Ваш метод подразумевает, что «пути» должны принимать значения, которые не являются int. На самом деле ни один из трех методов не должен работать, но счастливым совпадением, последний работал: в основном потому, что все промежуточные значения «путей» также являются биномиальными коэффициентами.

Рекомендации по отладке: попросите вашу программу вывести промежуточные значения. Это очень помогает.

*: Как математик, мне почти никогда не нужна эта функция. Фактически другое соглашение (int/int -> double) сделало бы мою жизнь как программиста более простой в среднем.

---

Я просмотрел блог, который вы упомянули. Это делает ваше сообщение более понятным. В блоге упоминается формула: произведение для i от 1 до k (n-k + 1)/i. Так подражать его вам нужно будет написать

for (int i = 1; i <= grid; i++) // bounds! 
    { 
     paths *= (grid * 2) - (grid - i) // minus sign! 
     paths /= (i + 1); 
    } 

О том, что это работает с Интсами: это несчастный случай, из-за того, что в промежуточных значениях произведения (в конце каждого цикла) являются биномиальными коэффициентами по всему вычислению. Если вы будете вычислять продукты и деления в другом порядке, вы можете очень хорошо получить нецелые числа, чтобы вычисление завершилось с использованием целочисленного типа переменной для пути из-за соглашения int/int -> int. Блог не очень полезен, не говоря уже об этом.