Вопрос:
Я нашел следующий код для вычисления nCr, но не понимаю его логики. Почему этот код работает?
long long combi(int n,int k) { long long ans=1; k=k>n-k?n-k:k; int j=1; for(;j<=k;j++,n—) { if(n%j==0) { ans*=n/j; }else if(ans%j==0) { ans=ans/j*n; }else { ans=(ans*n)/j; } } return ans; } Лучший ответ:
что умный код!
В целом он рассчитан на следующую формулу:
ans = n! / (k!)(n-k)!
Он равен:
ans = n(n-1)(n-2) … (n-k)…1 / k(k-1)…1 * (n-k)(n-k-1) … 1
И после очевидной отмены:
ans = n(n-1)(n-2)..(n-k+1) / k!
Теперь обратите внимание, что номинатор и знаменатель имеют одинаковое количество элементов (элемент k)
Итак, вычисление ans будет выглядеть следующим образом:
ans = 1 // initially ans *= n/1 ans *= (n-1)/2 ans *= (n-2)/3 . . . ans *= (n-k+1)/k
взгляните еще раз на код, и вы заметите, что:
- ans умножается на n на каждой итерации
- n уменьшается на 1 на каждой итерации (n—)
- ans делится на j на каждой итерации
Это именно то, что делается по размещенному коду. Теперь посмотрим значения различных условий в цикле, с номинантом начиная с n и знаменателя от 1 до k, поэтому переменной j присваивается значение знаменатель правильно?
1) if(n%j==0)
на каждом шаге, если n/j (вычислимо). Поэтому мы сначала вычисляем его здесь, чем умножаем на все ans, эта практика сохраняет результат как можно меньше.
2) else if(ans%j==0)
на каждом шаге, если мы не смогли вычислить n/j, но на самом деле можем вычислить ans/j, чтобы неплохо было сказать:
ans /= j; //first we divide ans *= n; //then we multiply
Это всегда сохраняет наш общий результат как можно меньше, правильно?
3) last condition
на каждом шаге, если мы не смогли бы вычислить ни n/j, ни ans/j, в этом случае нам не удастся разделить сначала, а затем умножить (следовательно, сохранить небольшой результат). Но нам нужно продолжить, хотя у нас остается только один выбор, который
ans *= n; // multiply first ans /= j; // then divide
ET VOILA!
Пример
рассмотрим случай 3C7
мы знаем, что ответ 7!/3! * 4!
следовательно: ans = 7*6*5 / 1*2*3
посмотрим, что произойдет на каждой итерации:
//1 ans = 1 //2 n = 7 j = 1 ans = ans * n/j first compute 7/1 = 7 then multiply to ans ans = 1*7 ans = 7 //3 n = 6 j = 2 ans = ans* n/j evaluate n/j = 6/2 (can be divided) n/j = 3 ans = ans *(n/j) = 7 * 3 = 21 // 4 n = 5 j = 3 ans = ans * n/j evaluate n/j = 5/3 oppsss!! (first if) evaluate ans/j = 21/3 = 7 YES (second if) ans = (ans/j)*n = 7*5 = 35 // end iterations
Заметим, что в последней итерации, если мы вычисляем прямо, мы бы сказали:
ans = ans*n/j = 21 * 5 / 3 = 105 / 3 = 34
да, он находит правильный результат, но пока значение доходит до 105, прежде чем вернуться к 35. Теперь представьте себе вычисление реальных больших чисел?!
Заключение
Этот код тщательно вычисляет биномиальные коэффициенты, пытающиеся сохранить выход как можно меньше на каждом шаге вычисления, он делает это, проверяя, можно ли разделить (int), затем выполнить, следовательно, он способен вычислять некоторые большой kCn, что прямое кодирование не может обрабатываться (может произойти OverFlow)
Ответ №1
Чтобы частично ответить на этот вопрос, рассмотрим тот факт, что записи n choose k составляют Треугольник Паскаля. Поскольку треугольник Паскаля симметричен, достаточно переместить аргумент k в левую половину, что делается с помощью
k=k>n-k?n-k:k;
утверждение; см. определение условного оператора C.
Кроме того, результат ans инициализируется в начале, чтобы содержать 1, который является первым входом каждой строки в треугольнике Паскаля, что означает, что изначально ans на самом деле n choose j.
Ответ №2
Дело в том, что nCr для 1 <= k <= n/2 является таким же, как и в n/2 + 1 <= k <= n. Первое изменение в k, так что значение значения лежит в левой половине. Еще одна вещь nCk означает (n * (n-1)….. (nk))/(k * (k-1) *…. * 2 * 1), поэтому приведенный выше код применяется итеративно.
Ответ №3
да.
[N выбирает K] значительно уменьшает свои факториалы, потому что дивиденды и делители имеют много факторов, которые отменяют друг друга до x/x = 1 (при x > 0)
трюк заключается в том, чтобы не вычислять большие факториалы, поскольку эти большие факторы требуют слишком большого адресного пространства (слишком много бит)
первый трюк состоит в том, чтобы уменьшить долю до деления.
второй трюк состоит в том, чтобы сделать modulo в пределах условного, чтобы выбрать одну из трех операций для текущей итерации. это можно сделать по-другому, а целочисленный по модулю выбран как быстрый оператор, пропуская некоторые более медленные целые деления.
вы итерационно пересекаете треугольник паскалей.
с каждым путем, который вы принимаете, вы умножаете что-то.
Существует 3 возможных пути ветвления для каждого итерационного шага:
каждый из трех шагов умножает аккумулятор “ans” с другим значением, представляющим коэффициент между двумя “позициями” на треугольнике паскалей.
вы всегда делаете N умножений, где N – количество итераций и заканчивается значением биномиального коэффициента.
N – это столбец треугольника паскалей, который вы хотите знать, и вы накапливаете N, умноженное на что-то, уменьшая количество столбцов s (и строк) треугольника pascals на N = N-1 для каждой итерации.
= 1;
ANS = 0;
//внутри каждой итерации;
ans=ans*n; n=n-1; ans=ans/j; j=n+1;
целочисленное деление является медленным и может быть пропущено (или сделано быстрее, уменьшив делитель) не реже одного раза, а часто и много раз (потому что в треугольнике паскалей имеется много общих простых факторов), это делается по модульным условиям.
Треугольник pascals чрезвычайно симметричен (при суммировании его доменов), поэтому это работает.
разница между (частичными) суммами столбцов треугольника паскалей показывает симметрию, которая важна для умножений и делений здесь.
просто просмотрите несколько видеороликов YouTube на симметрии и идентичности треугольника паскалей.