Рубрики

Rencontres Number (Подсчет частичных неисправностей)

Учитывая два числа, n> = 0 и 0 <= k <= n, подсчитайте количество неисправностей с k фиксированными точками.

Примеры:

Input : n = 3, k = 0
Output : 2
Since k = 0, no point needs to be on its
original position. So derangements
are {3, 1, 2} and {2, 3, 1}

Input : n = 3, k = 1
Output : 3
Since k = 1, one point needs to be on its
original position. So partial derangements
are {1, 3, 2}, {3, 2, 1} and {2, 1, 3}

Input : n = 7, k = 2
Output : 924

В комбинаторной математике число rencontres <или D (n, k) представляет количество частичных нарушений.

Рекуррентное отношение для нахождения Rencontres Number D n, k :

D(0, 0) = 1
D(0, 1) = 0
D(n+2, 0) = (n+1) * (D(n+1, 0) + D(n, 0))
D(n, k) = nCk * D(n-k, 0))

Даны два положительных целых числа n и k . Задача состоит в том, чтобы найти rencontres номер D (n, k) для дающих n и k.

Ниже приведено рекурсивное решение этого подхода:

C ++

// Рекурсивная программа CPP для поиска n-го Rencontres
// Номер
#include <bits/stdc++.h>

using namespace std;

  
// Возвращает значение биномиального коэффициента C (n, k)

int binomialCoeff(int n, int k)

{

    // Базовые случаи

    if (k == 0 || k == n)

        return 1;

  

    // Рекуррентное отношение

    return binomialCoeff(n - 1, k - 1) +

           binomialCoeff(n - 1, k);

}

  
// Возвращаем Recontres number D (n, m)

int RencontresNumber(int n, int m)

{

    // базовое условие

    if (n == 0 && m == 0)

        return 1;

  

    // базовое условие

    if (n == 1 && m == 0)

        return 0;

  

    // базовое условие

    if (m == 0)

        return (n - 1) * (RencontresNumber(n - 1, 0) +

                          RencontresNumber(n - 2, 0));

  

    return binomialCoeff(n, m) * RencontresNumber(n - m, 0);

}

  
// Программа для водителя

int main()

{

    int n = 7, m = 2;

    cout << RencontresNumber(n, m) << endl;

    return 0;

}

Джава

// Рекурсивная Java-программа для поиска n-го Rencontres
// Номер

import java.io.*;

  

class GFG {

      

    // Возвращает значение биномиального коэффициента

    // C (n, k)

    static int binomialCoeff(int n, int k)

    {

          

        // Базовые случаи

        if (k == 0 || k == n)

            return 1;

  

        // Рекуррентное отношение

        return binomialCoeff(n - 1, k - 1) + 

                         binomialCoeff(n - 1, k);

    }

  

    // Возвращаем Recontres number D (n, m)

    static int RencontresNumber(int n, int m)

    {

          

        // базовое условие

        if (n == 0 && m == 0)

            return 1;

  

        // базовое условие

        if (n == 1 && m == 0)

            return 0;

  

        // базовое условие

        if (m == 0)

            return (n - 1) * (RencontresNumber(n - 1, 0

                          + RencontresNumber(n - 2, 0));

  

        return binomialCoeff(n, m) * 

                             RencontresNumber(n - m, 0);

    }

  

    // Программа для водителя

    public static void main(String[] args)

    {

        int n = 7, m = 2;

        System.out.println(RencontresNumber(n, m));

    }

}

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

python3

# Рекурсивная программа CPP для поиска
# n-й номер Rencontres

  
# Возвращает значение биномиального коэффициента C (n, k)

def binomialCoeff(n, k):

  

    # Базовые случаи

    if (k == 0 or k == n):

        return 1

  

    # Рекуррентное отношение

    return (binomialCoeff(n - 1, k - 1

          + binomialCoeff(n - 1, k))

  
# Возврат Реконструкции номер D (n, m)

def RencontresNumber(n, m):

  

    # базовое состояние

    if (n == 0 and m == 0):

        return 1

  

    # базовое состояние

    if (n == 1 and m == 0):

        return 0

  

    # базовое состояние

    if (m == 0):

        return ((n - 1) * (RencontresNumber(n - 1, 0

                         + RencontresNumber(n - 2, 0)))

  

    return (binomialCoeff(n, m) *

            RencontresNumber(n - m, 0))

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

n = 7; m = 2

print(RencontresNumber(n, m))

  
# Этот код предоставлен Смитой Динеш Семвал.

C #

// Рекурсивная C # программа для поиска n-го Rencontres
// Номер

using System;

  

class GFG {

      

    // Возвращает значение биномиального коэффициента

    // C (n, k)

    static int binomialCoeff(int n, int k)

    {

          

        // Базовые случаи

        if (k == 0 || k == n)

            return 1;

  

        // Рекуррентное отношение

        return binomialCoeff(n - 1, k - 1) + 

                     binomialCoeff(n - 1, k);

    }

  

    // Возвращаем Recontres number D (n, m)

    static int RencontresNumber(int n, int m)

    {

          

        // базовое условие

        if (n == 0 && m == 0)

            return 1;

  

        // базовое условие

        if (n == 1 && m == 0)

            return 0;

  

        // базовое условие

        if (m == 0)

            return (n - 1) * 

                (RencontresNumber(n - 1, 0) 

                + RencontresNumber(n - 2, 0));

  

        return binomialCoeff(n, m) * 

                 RencontresNumber(n - m, 0);

    }

  

    // Программа для водителя

    public static void Main()

    {

        int n = 7, m = 2;

          

        Console.Write(RencontresNumber(n, m));

    }

}

  
// Этот код предоставлен
// Смита Динеш Семвал

PHP

<?php
// Рекурсивная PHP-программа для
// найти n-й Rencontres
// Номер

  
// Возвращает значение бинома
// Коэффициент C (n, k)

function binomialCoeff($n, $k)

{

      

    // Базовые случаи

    if ($k == 0 || $k == $n)

        return 1;

  

    // Рекуррентное отношение

    return binomialCoeff($n - 1,$k - 1) +

              binomialCoeff($n - 1, $k);

}

  
// Возвращаем Recontres number D (n, m)

function RencontresNumber($n, $m)

{

      

    // базовое условие

    if ($n == 0 && $m == 0)

        return 1;

  

    // базовое условие

    if ($n == 1 && $m == 0)

        return 0;

  

    // базовое условие

    if ($m == 0)

        return ($n - 1) * (RencontresNumber($n - 1, 0) +

                           RencontresNumber($n - 2, 0));

  

    return binomialCoeff($n, $m) * 

           RencontresNumber($n - $m, 0);

}

  

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

    $n = 7; 

    $m = 2;

    echo RencontresNumber($n, $m),"\n";

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

Выход:

924

Ниже приведена реализация с использованием динамического программирования:

C ++

// Программа CPP на основе DP для поиска n-го Rencontres
// Номер
#include <bits/stdc++.h>

using namespace std;

#define MAX 100

  
// Заполняет таблицу C [n + 1] [k + 1] так, что C [i] [j]
// представляет таблицу биномиального коэффициента
// iCj

int binomialCoeff(int C[][MAX], int n, int k)

{

    // Рассчитать значение биномиального коэффициента

    // снизу вверх

    for (int i = 0; i <= n; i++) {

        for (int j = 0; j <= min(i, k); j++) {

  

            // Базовые случаи

            if (j == 0 || j == i)

                C[i][j] = 1;

  

            // Вычисляем значение, используя ранее

            // сохраненные значения

            else

                C[i][j] = C[i - 1][j - 1] + 

                          C[i - 1][j];

        }

    }

}

  
// Возвращаем Recontres number D (n, m)

int RencontresNumber(int C[][MAX], int n, int m)

{

    int dp[n+1][m+1] = { 0 };

  

    for (int i = 0; i <= n; i++) {

        for (int j = 0; j <= m; j++) {

            if (j <= i) {

  

                // базовый вариант

                if (i == 0 && j == 0)

                    dp[i][j] = 1;

  

                // базовый вариант

                else if (i == 1 && j == 0)

                    dp[i][j] = 0;

  

                else if (j == 0)

                    dp[i][j] = (i - 1) * (dp[i - 1][0] + 

                                          dp[i - 2][0]);

                else

                    dp[i][j] = C[i][j] * dp[i - j][0];

            }

        }

    }

  

    return dp[n][m];

}

  
// Программа для водителя

int main()

{

    int n = 7, m = 2;

  

    int C[MAX][MAX];

    binomialCoeff(C, n, m);

  

    cout << RencontresNumber(C, n, m) << endl;

    return 0;

}

Джава

// основанная на DP Java-программа для поиска n-го Rencontres
// Номер

  

import java.io.*;

  

class GFG {

  

    static int MAX = 100;

  

    // Заполняет таблицу C [n + 1] [k + 1] так, что C [i] [j]

    // представляет таблицу биномиального коэффициента

    // iCj

    static void binomialCoeff(int C[][], int n, int k)

    {

  

        // Рассчитать значение биномиального коэффициента

        // снизу вверх

        for (int i = 0; i <= n; i++) {

            for (int j = 0; j <= Math.min(i, k); j++)

            {

  

                // Базовые случаи

                if (j == 0 || j == i)

                    C[i][j] = 1;

  

                // Вычисляем значение, используя ранее

                // сохраненные значения

                else

                    C[i][j] = C[i - 1][j - 1] + 

                                         C[i - 1][j];

            }

        }

    }

  

    // Возвращаем Recontres number D (n, m)

    static int RencontresNumber(int C[][], int n, int m)

    {

        int dp[][] = new int[n + 1][m + 1];

  

        for (int i = 0; i <= n; i++) {

            for (int j = 0; j <= m; j++) {

                if (j <= i) {

  

                    // базовый вариант

                    if (i == 0 && j == 0)

                        dp[i][j] = 1;

  

                    // базовый вариант

                    else if (i == 1 && j == 0)

                        dp[i][j] = 0;

  

                    else if (j == 0)

                        dp[i][j] = (i - 1) * (dp[i - 1][0

                                           + dp[i - 2][0]);

                    else

                        dp[i][j] = C[i][j] * dp[i - j][0];

                }

            }

        }

  

        return dp[n][m];

    }

  

    // Программа для водителя

    public static void main(String[] args)

    {

        int n = 7, m = 2;

  

        int C[][] = new int[MAX][MAX];

        binomialCoeff(C, n, m);

  

        System.out.println(RencontresNumber(C, n, m));

    }

}

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

Python 3

# Основанная на DP Python 3 программа для поиска n-го
№ Rencontres Number

  

MAX = 100

  
# Заполняет таблицу C [n + 1] [k + 1] так, что C [i] [j]
# представляет таблицу биномиального коэффициента
# iCj

def binomialCoeff(C, n, k) :

      

    # Рассчитать значение биномиального коэффициента

    # снизу вверх

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

        for j in range(0, min(i, k) + 1) :

              

            # Базовые случаи

            if (j == 0 or j == i) :

                C[i][j] = 1

  

            # Рассчитать стоимость, используя ранее

            # сохраненные значения

            else :

                C[i][j] = (C[i - 1][j - 1

                               + C[i - 1][j])

                  

  
# Возврат Реконструкции номер D (n, m)

def RencontresNumber(C, n, m) :

    w, h = m+1, n+1

    dp= [[0 for x in range(w)] for y in range(h)] 

      

  

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

        for j in range(0, m+1) :

            if (j <= i) :

                  

                # базовый вариант

                if (i == 0 and j == 0) :

                    dp[i][j] = 1

  

                # базовый вариант

                elif (i == 1 and j == 0) :

                    dp[i][j] = 0

  

                elif (j == 0) :

                    dp[i][j] = ((i - 1) * 

                     (dp[i - 1][0] + dp[i - 2][0]))

                else :

                    dp[i][j] = C[i][j] * dp[i - j][0]

                      

    return dp[n][m]

  

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

n = 7

m = 2

C = [[0 for x in range(MAX)] for y in range(MAX)] 

  
binomialCoeff(C, n, m)

  

print(RencontresNumber(C, n, m))

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

C #

// Программа на C # на основе DP
// найти n-й Rencontres
// Номер

using System;

  

class GFG

{

    static int MAX = 100;

  

    // Заполняет таблицу C [n + 1] [k + 1]

    // такой, что C [i] [j]

    // представляет таблицу

    // биномиальный коэффициент iCj

    static void binomialCoeff(int [,]C, 

                              int n, int k)

    {

  

        // Рассчитать значение

        // Биномиальный коэффициент

        // снизу вверх

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

        {

            for (int j = 0; 

                     j <= Math.Min(i, k); j++)

            {

  

                // Базовые случаи

                if (j == 0 || j == i)

                    C[i,j] = 1;

  

                // Рассчитать значение, используя

                // ранее сохраненные значения

                else

                    C[i, j] = C[i - 1, j - 1] + 

                              C[i - 1, j];

            }

        }

    }

  

    // Возвращаем Recontres

    // число D (n, m)

    static int RencontresNumber(int [,]C, 

                                int n, int m)

    {

        int [,]dp = new int[n + 1, 

                            m + 1];

  

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

        {

            for (int j = 0; j <= m; j++) 

            {

                if (j <= i) 

                {

  

                    // базовый вариант

                    if (i == 0 && j == 0)

                        dp[i, j] = 1;

  

                    // базовый вариант

                    else if (i == 1 && j == 0)

                        dp[i, j] = 0;

  

                    else if (j == 0)

                        dp[i, j] = (i - 1) * 

                                   (dp[i - 1, 0] + 

                                    dp[i - 2, 0]);

                    else

                        dp[i, j] = C[i, j] *

                                  dp[i - j, 0];

                }

            }

        }

  

        return dp[n, m];

    }

  

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

    static public void Main ()

    {

        int n = 7, m = 2;

        int [,]C = new int[MAX, MAX];

        binomialCoeff(C, n, m);

      

        Console.WriteLine(RencontresNumber(C, n, m));

    }

}

  
// Этот код добавлен
// от akt_mit

PHP

<?php
// Программа на основе DP для поиска n-го Rencontres
// Номер

$MAX=100;

  
// Заполняет таблицу C [n + 1] [k + 1] так, что C [i] [j]
// представляет таблицу биномиального коэффициента
// iCj

function binomialCoeff(&$C, $n, $k)

{

    // Рассчитать значение биномиального коэффициента

    // снизу вверх

    for ($i = 0; $i <= $n; $i++) {

        for ($j = 0; $j <= min($i, $k); $j++) {

  

            // Базовые случаи

            if ($j == 0 || $j == $i)

                $C[$i][$j] = 1;

  

            // Вычисляем значение, используя ранее

            // сохраненные значения

            else

                $C[$i][$j] = $C[$i - 1][$j - 1] + 

                        $C[$i - 1][$j];

        }

    }

}

  
// Возвращаем Recontres number D (n, m)

function RencontresNumber($C, $n, $m)

{

    $dp=array_fill(0,$n+1,array_fill(0,$m+1,0));

  

    for ($i = 0; $i <= $n; $i++) {

        for ($j = 0; $j <= $m; $j++) {

            if ($j <= $i) {

  

                // базовый вариант

                if ($i == 0 && $j == 0)

                    $dp[$i][$j] = 1;

  

                // базовый вариант

                else if ($i == 1 && $j == 0)

                    $dp[$i][$j] = 0;

  

                else if ($j == 0)

                    $dp[$i][$j] = ($i - 1) * ($dp[$i - 1][0] + 

                                        $dp[$i - 2][0]);

                else

                    $dp[$i][$j] = $C[$i][$j] * $dp[$i - $j][0];

            }

        }

    }

  

    return $dp[$n][$m];

}

  
// Программа для водителя

  

    $n = 7;

    $m = 2;

  

    $C=array(array());

    binomialCoeff($C, $n, $m);

  

    echo RencontresNumber($C, $n, $m);

  
// Этот код добавлен
// по миц
?>

Выход:

924

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

Rencontres Number (Подсчет частичных неисправностей)

0.00 (0%) 0 votes