Рубрики

Программа для эффективного расчета значения nCr

Даны два числа n, r (n> = r). Задача состоит в том, чтобы найти значение C (n, r) для большого значения n.

Примеры:

Input: n = 30, r = 15
Output: 155117520
C(30, 15) is 155117520 by  30!/((30-15)!*15!)


Input: n = 50, r = 25
Output: 126410606437752

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

 
C(n, r) = [n * (n-1) * .... * (n-r+1)] / [r * (r-1) * .... * 1]

Однако при больших значениях n, r продукты могут переполняться, поэтому на каждой итерации мы делим текущие переменные, содержащие значения продуктов, на их gcd.

Ниже приведена обязательная реализация:

C ++

// реализация C ++ для поиска nCr
#include <bits/stdc++.h>

using namespace std;

  
// Функция для поиска nCr

void printNcR(int n, int r)

{

  

    // p содержит значение n * (n-1) * (n-2) ...,

    // k содержит значение r * (r-1) ...

    long long p = 1, k = 1;

  

    // C (n, r) == C (n, nr),

    // выбираем меньшее значение

    if (n - r < r)

        r = n - r;

  

    if (r != 0) {

        while (r) {

            p *= n;

            k *= r;

  

            // gcd of p, k

            long long m = __gcd(p, k);

  

            // деление на gcd, чтобы упростить продукт

            // деление по их gcd сохраняет от переполнения

            p /= m;

            k /= m;

  

            n--;

            r--;

        }

  

        // k должно быть упрощено до 1

        // так как C (n, r) натуральное число

        // (знаменатель должен быть 1).

    }

  

    else

        p = 1;

  

    // если наш подход правильный p = ans и k = 1

    cout << p << endl;

}

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

int main()

{

    int n = 50, r = 25;

  

    printNcR(n, r);

  

    return 0;

}

Джава

// Java реализация для поиска nCr

  

class GFG {

  
// Функция для поиска nCr

    static void printNcR(int n, int r) {

  

        // p содержит значение n * (n-1) * (n-2) ...,

        // k содержит значение r * (r-1) ...

        long p = 1, k = 1;

  

        // C (n, r) == C (n, nr),

        // выбираем меньшее значение

        if (n - r < r) {

            r = n - r;

        }

  

        if (r != 0) {

            while (r > 0) {

                p *= n;

                k *= r;

  

                // gcd of p, k

                long m = __gcd(p, k);

  

                // деление на gcd, чтобы упростить продукт

                // деление по их gcd сохраняет от переполнения

                p /= m;

                k /= m;

  

                n--;

                r--;

            }

  

            // k должно быть упрощено до 1

            // так как C (n, r) натуральное число

            // (знаменатель должен быть 1).

        } else {

            p = 1;

        }

  

        // если наш подход правильный p = ans и k = 1

        System.out.println(p);

    }

  

    static long __gcd(long n1, long n2) {

        long gcd = 1;

  

        for (int i = 1; i <= n1 && i <= n2; ++i) {

            // Проверяет, является ли я фактором обоих целых

            if (n1 % i == 0 && n2 % i == 0) {

                gcd = i;

            }

        }

        return gcd;

    }

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

    public static void main(String[] args) {

        int n = 50, r = 25;

  

        printNcR(n, r);

  

    }

}

python3

# Реализация Python3 для поиска nCr

  

from math import *

  
# Функция для поиска nCr

def printNcR(n, r):

  

    # p содержит значение n * (n-1) * (n-2) ...,

    # k содержит значение r * (r-1) ...

    p = 1

    k = 1

  

    # C (n, r) == C (n, nr),

    # выбирая меньшее значение

    if (n - r < r):

        r = n - r

  

    if (r != 0): 

        while (r):

            p *= n

            k *= r

  

            # gcd of p, k

            m = gcd(p, k)

  

            # деление на gcd, чтобы упростить продукт

            # деление по их gcd сохраняет от переполнения

            p //= m

            k //= m

  

            n -= 1

            r -= 1

  

        # k должно быть упрощено до 1

        # как C (n, r) натуральное число

        # (знаменатель должен быть 1)

  

    else:

        p = 1

  

    # если наш подход правильный p = ans и k = 1

    print(p)

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

if __name__ == "__main__":

    n = 50

    r = 25

  

    printNcR(n, r)

      
# этот код предоставлен
# ChitraNayal

C #

// реализация C # для поиска nCr

  

using System;

  

public class GFG{

      
// Функция для поиска nCr

    static void printNcR(int n, int r) { 

  

        // p содержит значение n * (n-1) * (n-2) ...,

        // k содержит значение r * (r-1) ...

        long p = 1, k = 1; 

  

        // C (n, r) == C (n, nr),

        // выбираем меньшее значение

        if (n - r < r) { 

            r = n - r; 

        

  

        if (r != 0) { 

            while (r > 0) { 

                p *= n; 

                k *= r; 

  

                // gcd of p, k

                long m = __gcd(p, k); 

  

                // деление на gcd, чтобы упростить продукт

                // деление по их gcd сохраняет от переполнения

                p /= m; 

                k /= m; 

  

                n--; 

                r--; 

            

  

            // k должно быть упрощено до 1

            // так как C (n, r) натуральное число

            // (знаменатель должен быть 1).

        } else

            p = 1; 

        

  

        // если наш подход правильный p = ans и k = 1

        Console.WriteLine(p); 

    

  

    static long __gcd(long n1, long n2) { 

        long gcd = 1; 

  

        for (int i = 1; i <= n1 && i <= n2; ++i) { 

            // Проверяет, является ли я фактором обоих целых

            if (n1 % i == 0 && n2 % i == 0) { 

                gcd = i; 

            

        

        return gcd; 

    

  

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

        static public void Main (){

        int n = 50, r = 25; 

        printNcR(n, r); 

  

    }

// Этот код предоставлен ajit.
}

PHP

<?php
// Реализация PHP для поиска nCr

      
// Функция для поиска nCr

function printNcR($n, $r) { 

  

        // p содержит значение n * (n-1) * (n-2) ...,

        // k содержит значение r * (r-1) ...

        $p = 1;

        $k = 1; 

  

        // C (n, r) == C (n, nr),

        // выбираем меньшее значение

        if ($n - $r < $r) { 

            $r = $n - $r

        

  

        if ($r != 0) { 

            while ($r > 0) { 

                $p *= $n

                $k *= $r

  

                // gcd of p, k

                $m = __gcd($p, $k); 

  

                // деление на gcd, чтобы упростить продукт

                // деление по их gcd сохраняет от переполнения

                $p /= $m

                $k /= $m

  

                $n--; 

                $r--; 

            

  

            // k должно быть упрощено до 1

            // так как C (n, r) натуральное число

            // (знаменатель должен быть 1).

        } else

            $p = 1; 

        

  

        // если наш подход правильный p = ans и k = 1

        echo ($p); 

    

  

    function  __gcd($n1, $n2) { 

         $gcd = 1; 

  

        for ($i = 1; $i <= $n1 && $i <= $n2; ++$i) { 

            // Проверяет, является ли я фактором обоих целых

            if ($n1 % $i == 0 && $n2 % $i == 0) { 

                $gcd = $i

            

        

        return $gcd

    

  

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

        $n = 50;

        $r = 25; 

        printNcR($n, $r); 

  

  
// Этот код предоставлен Sachin.

  
?>

Выход:

126410606437752

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

Программа для эффективного расчета значения nCr

0.00 (0%) 0 votes