Рубрики

Вычислить nCr% p | Комплект 1 (Введение и решение для динамического программирования)

Учитывая три числа n, r и p, вычислим значение n C r mod p.

Пример:

Input:  n = 10, r = 2, p = 13
Output: 6
Explanation: 10C2 is 45 and 45 % 13 is 6.

Мы настоятельно рекомендуем вам нажать здесь и попрактиковаться, прежде чем переходить к решению.

Простое решение состоит в том, чтобы сначала вычислить n C r , а затем вычислить n C r % p. Это решение прекрасно работает, когда значение n C r мало.

Что если значение n C r велико?
Значение n C r % p обычно требуется для больших значений n, когда n C r не может вписаться в переменную и вызывает переполнение. Таким образом, вычисление n C r и последующее использование модульного оператора не является хорошей идеей, поскольку будет переполнение даже при немного больших значениях n и r. Например, методы, обсуждаемые здесь и здесь, вызывают переполнение для n = 50 и r = 40.

Идея состоит в том, чтобы вычислить n C r по следующей формуле

   C(n, r) = C(n-1, r-1) + C(n-1, r)
   C(n, 0) = C(n, n) = 1

Работа над формулой и треугольником Паскаля:
Посмотрим, как работает приведенная выше формула для C (4,3)

1 ========== >> n = 0, C (0,0) = 1
1–1 ======== >> n = 1, C (1,0) = 1, C (1,1) = 1
1–2–1 ====== >> n = 2, C (2,0) = 1, C (2,1) = 2, C (2,2) = 1
1–3–3–1 ==== >> n = 3, C (3,0) = 1, C (3,1) = 3, C (3,2) = 3, C (3,3) = 1
1–4–6–4–1 == >> n = 4, C (4,0) = 1, C (4,1) = 4, C (4,2) = 6, C (4,3) = 4, С (4,4) = 1
Итак, здесь каждый цикл на i строит i-й ряд паскальского треугольника, используя (i-1) -й ряд

Расширение приведенной выше формулы для модульной арифметики:
Мы можем использовать свойство распределения оператора modulor, чтобы найти nCr% p по формуле выше.

   C(n, r)%p = [ C(n-1, r-1)%p + C(n-1, r)%p ] % p
   C(n, 0) = C(n, n) = 1

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

Решение динамического программирования на основе двумерного массива может быть дополнительно оптимизировано путем построения по одной строке за раз. Смотрите Space оптимизированную версию в посте ниже для деталей.

Биномиальный коэффициент с использованием динамического программирования

Ниже приведена реализация, основанная на оптимизированной для пространства версии, описанной в посте выше.

C ++

// Решение на основе динамического программирования для вычисления nCr% p
#include<bits/stdc++.h>

using namespace std;

  
// Возвращает nCr% p

int nCrModp(int n, int r, int p)

{

    // Массив C будет хранить последнюю строку

    // треугольник паскаль в конце. И последняя запись

    // последней строки nCr

    int C[r+1];

    memset(C, 0, sizeof(C));

  

    C[0] = 1; // Верхний ряд треугольника Паскаля

  

    // Один за другим строит оставшиеся строки Паскаля

    // Треугольник сверху вниз

    for (int i = 1; i <= n; i++)

    {

        // Заполняем записи текущей строки, используя предыдущие

        // значения строк

        for (int j = min(i, r); j > 0; j--)

  

            // nCj = (n-1) Cj + (n-1) C (j-1);

            C[j] = (C[j] + C[j-1])%p;

    }

    return C[r];

}

  
// Драйвер программы

int main()

{

    int n = 10, r = 2, p = 13;

    cout << "Value of nCr % p is " << nCrModp(n, r, p);

    return 0;

}

ДЖАВА

// Динамическое программирование на основе
// решение для вычисления nCr% p

import java.io.*;

import java.util.*;

import java.math.*;

  

class GFG {

      

    // Возвращает nCr% p

    static int nCrModp(int n, int r, int p)

    {

        // массив C будет хранить последний

        // строка паскальского треугольника в конце.

        // И последняя запись последней строки nCr

        int C[]=new int[r+1];

        Arrays.fill(C,0);

      

        C[0] = 1; // Верхний ряд треугольника Паскаля

      

        // Один за другим строит оставшиеся строки Паскаля

        // Треугольник сверху вниз

        for (int i = 1; i <= n; i++)

        {

            // Заполняем записи текущей строки, используя предыдущие

            // значения строк

            for (int j = Math.min(i, r); j > 0; j--)

      

                // nCj = (n-1) Cj + (n-1) C (j-1);

                C[j] = (C[j] + C[j-1])%p;

        }

        return C[r];

    }

      

    // Драйвер программы

    public static void main(String args[])

    {

        int n = 10, r = 2, p = 13;

        System.out.println("Value of nCr % p is "

                           + nCrModp(n, r, p));

          

    }

}

  

  
// Этот код предоставлен Никитой Тивари.

python3

# Решение на основе динамического программирования для вычисления nCr% p

  
# Возвращает nCr% p

def nCrModp(n, r, p):

  

    # Массив C будет хранить последнюю строку

    # Паскаль треугольник в конце. И последняя запись

    № последней строки nCr.

    C = [0 for i in range(r+1)]

  

    C[0] = 1 # Верхний ряд треугольника Паскаля

  

    # Один строит оставшиеся строки Паскаля

    # Треугольник сверху вниз

    for i in range(1, n+1):

  

        # Заполнить записи текущей строки

        # используя предыдущие значения строки

        for j in range(min(i, r), 0, -1):

  

            # nCj = (n - 1) Cj + (n - 1) C (j - 1)

            C[j] = (C[j] + C[j-1]) % p

  

    return C[r]

  
# Драйверная программа

n = 10

r = 2

p = 13

print('Value of nCr % p is', nCrModp(n, r, p))

  
# Этот код предоставлен Soumen Ghosh

C #

// Динамическое программирование на основе
// решение для вычисления nCr% p

using System;

  

class GFG {

      

    // Возвращает nCr% p

    static int nCrModp(int n, int r, int p)

    {

          

        // массив C будет хранить последний

        // строка паскальского треугольника в конце.

        // И последняя запись последней строки nCr

        int []C = new int[r + 1];

          

        for(int i = 0; i < r + 1; i++)

            C[i] = 0;

      

      

        C[0] = 1; // Верхний ряд треугольника Паскаля

      

        // Один строит оставшиеся строки

        // треугольника Паскаля сверху вниз

        for (int i = 1; i <= n; i++)

        {

              

            // Заполняем записи текущей строки, используя

            // значения предыдущей строки

            for (int j = Math.Min(i, r); j > 0; j--)

      

                // nCj = (n-1) Cj + (n-1) C (j-1);

                C[j] = (C[j] + C[j-1]) % p;

        }

          

        return C[r];

    }

      

    // Драйвер программы

    public static void Main()

    {

        int n = 10, r = 2, p = 13;

          

        Console.Write("Value of nCr % p is "

                            + nCrModp(n, r, p));

          

    }

}

  

  
// Этот код предоставлен нитин митталь.

[

PHP

<?php
// Динамическое программирование на основе
// решение для вычисления nCr% p

      
// Возвращает nCr% p

function nCrModp($n, $r, $p)

{

  
// собирается массив C
// сохранить последнюю строку
// треугольник паскаля в
// конец. И последняя запись
// последней строки nCr

$C = array();

  

for( $i = 0; $i < $r + 1; $i++)

    $C[$i] = 0;

  
// Верхний ряд Паскаля
// Треугольник

$C[0] = 1; 

  
// Один из оставшихся конструкций
// строки треугольника Паскаля из
// сверху донизу

for ($i = 1; $i <= $n; $i++)

{

      

    // Заполняем записи текущего

    // строка с использованием предыдущих значений строки

    for ($j = Min($i, $r); $j > 0; $j--)

  

        // nCj = (n-1) Cj + (n-1) C (j-1);

        $C[$j] = ($C[$j] + 

                  $C[$j - 1]) % $p;

}

  

return $C[$r];

}

  
// Код драйвера

$n = 10; $r = 2;$p = 13;

  

echo "Value of nCr % p is " ,

         nCrModp($n, $r, $p);

  
// Этот код добавлен
// от anuj_67.
?>


Выход:

Value of nCr % p is 6

Временная сложность вышеупомянутого решения составляет O (n * r) и требует O (n) пространства. Есть больше и лучшие решения вышеупомянутой проблемы.

Вычислить nCr% p | Набор 2 (теорема Лукаса)

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Вычислить nCr% p | Комплект 1 (Введение и решение для динамического программирования)

0.00 (0%) 0 votes