Рубрики

Способы расстановки шаров так, чтобы смежные шары были разных типов

Есть «p» шарики типа P, «q» шарики типа Q и «r» шарики типа R. Используя шарики, мы хотим создать прямую линию так, чтобы не было двух смежных шаров одного типа.

Примеры :

Input  : p = 1, q = 1, r = 0
Output : 2
There are only two arrangements PQ and QP

Input  : p = 1, q = 1, r = 1
Output : 6
There are only six arrangements PQR, QPR,
QRP, RQP, PRQ and RPQ

Input  : p = 2, q = 1, r = 1
Output : 6
There are only six arrangements PQRP, QPRP,
PRQP, RPQP, PRPQ and PQPR

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

Наивное решение:
Наивное решение этой проблемы — рекурсивное решение. Мы рекурсивно призываем к трем случаям
1) Последний размещаемый мяч относится к типу P
2) Последний размещаемый мяч относится к типу Q
3) Последний размещаемый мяч относится к типу R

Ниже приведена реализация вышеуказанной идеи.

C ++

// C ++ программа для подсчета количества способов упорядочить три
// типы шариков такие, что нет двух шариков одного цвета
// смежны друг с другом
#include<bits/stdc++.h>

using namespace std;

  
// Возвращает количество договоренностей с последним размещенным мячом
// 'последний'. 'last' равно 0 для 'p', 1 для 'q' и 2 для 'r'

int countWays(int p, int q, int r, int last)

{

    // если количество шариков любого цвета становится меньше

    // чем 0, количество способов аранжировки равно 0.

    if (p<0 || q<0 || r<0)

        return 0;

  

    // Если требуется последний шар типа P и номер

    // шаров типа P равно 1, а количество шаров

    // другой цвет равен 0, количество путей равно 1.

    if (p==1 && q==0 && r==0 && last==0)

        return 1;

  

    // Тот же случай, что и выше для 'q' и 'r'

    if (p==0 && q==1 && r==0 && last==1)

        return 1;

    if (p==0 && q==0 && r==1 && last==2)

        return 1;

  

    // если последний требуемый мяч равен P и количество путей

    // сумма количества способов сформировать последовательность с 'p-1' P

    // шары, q Q шары и r R шары, заканчивающиеся на Q и R.

    if (last==0)

        return countWays(p-1,q,r,1) + countWays(p-1,q,r,2);

  

    // То же, что и в предыдущем случае для 'q' и 'r'

    if (last==1)

        return countWays(p,q-1,r,0) + countWays(p,q-1,r,2);

    if (last==2)

        return countWays(p,q,r-1,0) + countWays(p,q,r-1,1);

}

  
// Возвращает количество необходимых договоренностей

int countUtil(int p, int q, int r)

{

   // Три случая возникают:

   return countWays(p, q, r, 0) +  // Последние необходимые шары типа P

          countWays(p, q, r, 1) +  // Последние необходимые шары типа Q

          countWays(p, q, r, 2); // Последние необходимые шары типа R

}

  
// Код драйвера для проверки выше

int main()

{

    int p = 1, q = 1, r = 1;

    printf("%d", countUtil(p, q, r));

    return 0;

}

Джава

// Java-программа для подсчета числа
// способов упорядочить три типа
// шары такие, что нет двух
// один и тот же цвет смежны друг с другом

class GFG {

      

    // Возвращает количество договоренностей

    // где находится последний размещенный мяч

    // 'последний'. 'last' равно 0 для 'p',

    // 1 для «q» и 2 для «r»

    static int countWays(int p, int q, int r, int last) 

    {

        // если количество шариков любого

        // цвет становится меньше 0

        // количество способов аранжировки равно 0.

        if (p < 0 || q < 0 || r < 0)

        return 0;

      

        // Если требуется последний шар

        // типа P и числа

        // шаров типа P = 1

        // пока количество шаров

        // другой цвет равен 0

        // путей это 1.

        if (p == 1 && q == 0 && r == 0 && last == 0)

            return 1;

      

        // Тот же случай, что и выше для 'q' и 'r'

        if (p == 0 && q == 1 && r == 0 && last == 1)

            return 1;

        if (p == 0 && q == 0 && r == 1 && last == 2)

            return 1;

      

        // если требуется последний шар P

        // а количество путей

        // сумма количества путей

        // сформировать последовательность с 'p-1' P

        // шаров, Q Q шаров и R R шаров

        // заканчивая Q и R.

        if (last == 0)

        return countWays(p - 1, q, r, 1) +

               countWays(p - 1, q, r, 2);

      

        // То же, что и в предыдущем случае для 'q' и 'r'

        if (last == 1)

            return countWays(p, q - 1, r, 0) +

                   countWays(p, q - 1, r, 2);

          

        if (last == 2)

        return countWays(p, q, r - 1, 0) +

               countWays(p, q, r - 1, 1);

      

        return 0;

    }

      

    // Возвращает количество необходимых договоренностей

    static int countUtil(int p, int q, int r) {

        // Три случая возникают:

        return countWays(p, q, r, 0) + // Последние необходимые шары типа P

               countWays(p, q, r, 1) + // Последние необходимые шары типа Q

               countWays(p, q, r, 2);  // Последние необходимые шары типа R

    }

      

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

    public static void main(String[] args) 

    {

        int p = 1, q = 1, r = 1;

        System.out.print(countUtil(p, q, r));

    }

}

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

python3

# Python3 программа для подсчета
# количество способов организовать
# три типа мячей такие
# что нет двух одинаковых шаров
# цвет примыкает к каждому
# Другой

  
# Возвращает количество договоренностей
# где последний размещенный мяч
# 'последний'. 'last' равно 0 для 'p',
№ 1 для «д» и 2 для «г»

def countWays(p, q, r, last):

      

    # если количество шаров

    # любой цвет становится меньше

    № 0 число

    Количество способов аранжировки равно 0.

    if (p < 0 or q < 0 or r < 0):

        return 0;

  

    # Если требуется последний мяч

    № типа P и номер

    Количество шаров типа P равно 1

    # в то время как количество шаров

    # другой цвет 0 число

    Количество путей - 1.

    if (p == 1 and q == 0 and

        r == 0 and last == 0):

        return 1;

  

    # Тот же случай, что и выше

    # для 'q' и 'r'

    if (p == 0 and q == 1 and

        r == 0 and last == 1):

        return 1;

          

    if (p == 0 and q == 0 and 

        r == 1 and last == 2):

        return 1;

  

    # если требуется последний шар P

    # и количество способов

    # сумма количества способов

    # для формирования последовательности с 'p-1' P

    # шаров, Q Q шаров и R R

    # шары, оканчивающиеся на Q и R.

    if (last == 0):

        return (countWays(p - 1, q, r, 1) + 

                countWays(p - 1, q, r, 2));

  

    # То же, что и выше

    # для 'q' и 'r'

    if (last == 1):

        return (countWays(p, q - 1, r, 0) + 

                countWays(p, q - 1, r, 2));

    if (last == 2):

        return (countWays(p, q, r - 1, 0) + 

                countWays(p, q, r - 1, 1));

  
# Возвращает количество
# необходимые меры

def countUtil(p, q, r):

      

    # Три случая возникают:

    # Последние необходимые шары типа P

    # Последние необходимые шары типа Q

    # Последние необходимые шары типа R

    return (countWays(p, q, r, 0) + 

            countWays(p, q, r, 1) + 

            countWays(p, q, r, 2)); 

  
Код водителя

p = 1

q = 1;

r = 1;

print(countUtil(p, q, r));

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

C #

// C # программа для подсчета числа
// способов упорядочить три типа
// шары такие, что нет двух
// один и тот же цвет смежны друг с другом

using System;

  

class GFG {

      

    // Возвращает количество договоренностей

    // где находится последний размещенный мяч

    // 'последний'. 'last' равно 0 для 'p',

    // 1 для «q» и 2 для «r»

    static int countWays(int p, int q,

                            int r, int last) 

    {

          

        // если количество шариков любого

        // цвет становится меньше 0

        // количество способов

        // договоренности это 0.

        if (p < 0 || q < 0 || r < 0)

            return 0;

      

        // Если требуется последний шар

        // типа P и числа

        // шаров типа P = 1

        // пока количество шаров

        // другой цвет равен 0

        // путей это 1.

        if (p == 1 && q == 0 && r == 0 

                              && last == 0)

            return 1;

      

        // Тот же случай, что и выше для 'q' и 'r'

        if (p == 0 && q == 1 && r == 0 

                               && last == 1)

            return 1;

        if (p == 0 && q == 0 && r == 1 

                               && last == 2)

            return 1;

      

        // если требуется последний шар P

        // а количество путей

        // сумма количества путей

        // сформировать последовательность с 'p-1' P

        // шаров, Q Q шаров и R R шаров

        // заканчивая Q и R.

        if (last == 0)

            return countWays(p - 1, q, r, 1) +

                    countWays(p - 1, q, r, 2);

      

        // То же, что и в предыдущем случае для 'q' и 'r'

        if (last == 1)

            return countWays(p, q - 1, r, 0) +

                countWays(p, q - 1, r, 2);

          

        if (last == 2)

            return countWays(p, q, r - 1, 0) +

                    countWays(p, q, r - 1, 1);

      

        return 0;

    }

      

    // Возвращает количество необходимых договоренностей

    static int countUtil(int p, int q, int r)

    {

          

        // Три случая возникают:

        // 1. Последние необходимые шары типа P

        // 2. Последние необходимые шары типа Q

        // 3. Последние необходимые шары типа R

        return countWays(p, q, r, 0) + 

               countWays(p, q, r, 1) + 

               countWays(p, q, r, 2); 

    }

      

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

    public static void Main() 

    {

        int p = 1, q = 1, r = 1;

          

        Console.Write(countUtil(p, q, r));

    }

}

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

PHP

<?php
// PHP программа для подсчета числа
// способов устроить три
// типы шариков такие, что
// нет двух шаров одного цвета
// смежны друг с другом

  
// Возвращает количество договоренностей
// где находится последний размещенный мяч
// 'последний'. 'last' равно 0 для 'p',
// 1 для «q» и 2 для «r»

function countWays($p, $q

                   $r, $last)

{

      

    // если количество шаров

    // любой цвет становится меньше

    // чем 0 количество

    // Способ размещения 0.

    if ($p < 0 || $q 

           < 0 || $r < 0)

        return 0;

  

    // Если требуется последний шар

    // типа P и числа

    // шаров типа P = 1

    // пока количество шаров

    // другой цвет равен 0

    // путей это 1.

    if ($p == 1 && $q == 0 && 

        $r == 0 && $last == 0)

        return 1;

  

    // Тот же случай, что и выше

    // для 'q' и 'r'

    if ($p == 0 && $q == 1 && 

        $r == 0 && $last == 1)

        return 1;

          

    if ($p == 0 && $q == 0 &&

        $r == 1 && $last == 2)

        return 1;

  

    // если требуется последний шар P

    // а количество путей

    // сумма количества путей

    // сформировать последовательность с 'p-1' P

    // шаров, q Q шаров и r R

    // шары, оканчивающиеся на Q и R.

    if ($last == 0)

        return countWays($p - 1, $q, $r, 1) + 

               countWays($p - 1, $q, $r, 2);

  

    // То же, что и выше

    // для 'q' и 'r'

    if ($last == 1)

        return countWays($p, $q - 1, $r, 0) + 

               countWays($p, $q - 1, $r, 2);

    if ($last == 2)

        return countWays($p, $q, $r - 1, 0) + 

               countWays($p, $q, $r - 1, 1);

}

  
// Возвращает количество
// необходимые договоренности

function countUtil($p, $q, $r)

{

      

    // Три случая возникают:

    // Последние необходимые шары типа P

    // Последние необходимые шары типа Q

    // Последние необходимые шары типа R

    return countWays($p, $q, $r, 0) + 

           countWays($p, $q, $r, 1) + 

           countWays($p, $q, $r, 2); 

}

  

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

    $p = 1; 

    $q = 1;

    $r = 1;

    echo(countUtil($p, $q, $r));

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


Выход:

6

Сложность времени этого решения является экспоненциальной.

Мы можем заметить, что есть много подзадач, решаемых снова и снова, поэтому проблему можно решить с помощью динамического программирования (DP). Мы легко можем сделать памятное решение этой проблемы.

C ++

// C ++ программа для подсчета количества способов упорядочить три
// типы шариков такие, что нет двух шариков одного цвета
// смежны друг с другом
#include<bits/stdc++.h>

using namespace std;

#define MAX 100

  
// таблица для хранения результатов подзадач

int dp[MAX][MAX][MAX][3];

  
// Возвращает количество договоренностей с последним размещенным мячом
// 'последний'. 'last' равно 0 для 'p', 1 для 'q' и 2 для 'r'

int countWays(int p, int q, int r, int last)

{

    // если количество шариков любого цвета становится меньше

    // чем 0, количество способов аранжировки равно 0.

    if (p<0 || q<0 || r<0)

        return 0;

  

    // Если требуется последний шар типа P и номер

    // шаров типа P равно 1, а количество шаров

    // другой цвет равен 0, количество путей равно 1.

    if (p==1 && q==0 && r==0 && last==0)

        return 1;

  

    // Тот же случай, что и выше для 'q' и 'r'

    if (p==0 && q==1 && r==0 && last==1)

        return 1;

    if (p==0 && q==0 && r==1 && last==2)

        return 1;

  

    // Если эта подзадача уже оценена

    if (dp[p][q][r][last] != -1)

        return dp[p][q][r][last];

  

    // если последний требуемый мяч равен P и количество путей

    // сумма количества способов сформировать последовательность с 'p-1' P

    // шары, q Q шары и r R шары, заканчивающиеся на Q и R.

    if (last==0)

       dp[p][q][r][last] = countWays(p-1,q,r,1) + countWays(p-1,q,r,2);

  

    // То же, что и в предыдущем случае для 'q' и 'r'

    else if (last==1)

       dp[p][q][r][last] = countWays(p,q-1,r,0) + countWays(p,q-1,r,2);

    else // (последнее == 2)

       dp[p][q][r][last] =  countWays(p,q,r-1,0) + countWays(p,q,r-1,1);

  

    return dp[p][q][r][last];

}

  
// Возвращает количество необходимых договоренностей

int countUtil(int p, int q, int r)

{

   // Инициализируем массив 'dp'

   memset(dp, -1, sizeof(dp));

  

   // Три случая возникают:

   return countWays(p, q, r, 0) +  // Последние необходимые шары типа P

          countWays(p, q, r, 1) +  // Последние необходимые шары типа Q

          countWays(p, q, r, 2); // Последние необходимые шары типа R

}

  
// Код драйвера для проверки выше

int main()

{

    int p = 1, q = 1, r = 1;

    printf("%d", countUtil(p, q, r));

    return 0;

}

Джава

// Java-программа для подсчета числа
// способов устроить три
// типы шариков такие, что нет
// два шарика одного цвета
// смежны друг с другом

import java.util.Arrays;

  

class GFG 

{

  

    static final int MAX = 100;

      

    // таблица для хранения результатов подзадач

    static int dp[][][][] = new int[MAX][MAX][MAX][3];

      

    // Возвращает количество договоренностей

    // где находится последний размещенный мяч

    // 'последний'. 'last' равно 0 для 'p',

    // 1 для «q» и 2 для «r»

    static int countWays(int p, int q, int r, int last)

    {

        // если количество шариков любого

        // цвет становится меньше 0

        // количество способов аранжировки равно 0.

        if (p < 0 || q < 0 || r < 0)

        return 0;

      

        // Если требуется последний шар

        // типа P и числа

        // шаров типа P = 1

        // пока количество шаров

        // другой цвет равен 0

        // путей это 1.

        if (p == 1 && q == 0 && r == 0 && last == 0)

            return 1;

      

        // Тот же случай, что и выше для 'q' и 'r'

        if (p == 0 && q == 1 && r == 0 && last == 1)

            return 1;

          

        if (p == 0 && q == 0 && r == 1 && last == 2)

            return 1;

      

        // Если эта подзадача уже оценена

        if (dp[p][q][r][last] != -1)

            return dp[p][q][r][last];

      

        // если требуется последний шар P и

        // количество путей это сумма

        // количество способов формирования последовательности

        // с 'p-1' P шариками, q Q balss и

        // r R шары, оканчивающиеся на Q и R.

        if (last == 0)

        dp[p][q][r][last] = countWays(p - 1, q, r, 1) + 

                            countWays(p - 1, q, r, 2);

      

        // То же, что и в предыдущем случае для 'q' и 'r'

        else if (last == 1)

        dp[p][q][r][last] = countWays(p, q - 1, r, 0) + 

                            countWays(p, q - 1, r, 2);

        // (последнее == 2)

        else 

        dp[p][q][r][last] = countWays(p, q, r - 1, 0) + 

                            countWays(p, q, r - 1, 1);

      

        return dp[p][q][r][last];

    }

      

    // Возвращает количество необходимых договоренностей

    static int countUtil(int p, int q, int r)

    {

        // Инициализируем массив 'dp'

        for (int[][][] row : dp)

        {

            for (int[][] innerRow : row) 

            {

                for (int[] innerInnerRow : innerRow)

                {

                    Arrays.fill(innerInnerRow, -1);

                }

            }

        };

      

        // Три случая возникают:

        return countWays(p, q, r, 0) + // Последние необходимые шары типа P

            countWays(p, q, r, 1) +    // Последние необходимые шары типа Q

            countWays(p, q, r, 2);       // Последние необходимые шары типа R

    }

  

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

    public static void main(String[] args)

    {

        int p = 1, q = 1, r = 1;

        System.out.print(countUtil(p, q, r));

    }

}

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

C #

// C # программа для подсчета числа
// способов устроить три
// типы шариков такие, что нет
// два шарика одного цвета
// смежны друг с другом

using System;

  

class GFG 

  

    static int MAX = 101; 

      

    // таблица для хранения результатов подзадач

    static int[,,,] dp = new int[MAX, MAX, MAX, 4]; 

      

    // Возвращает количество договоренностей

    // где находится последний размещенный мяч

    // 'последний'. 'last' равно 0 для 'p',

    // 1 для «q» и 2 для «r»

    static int countWays(int p, int q, int r, int last) 

    

        // если количество шариков любого

        // цвет становится меньше 0

        // количество способов аранжировки равно 0.

        if (p < 0 || q < 0 || r < 0) 

        return 0; 

      

        // Если требуется последний шар

        // типа P и числа

        // шаров типа P = 1

        // пока количество шаров

        // другой цвет равен 0

        // путей это 1.

        if (p == 1 && q == 0 && r == 0 && last == 0) 

            return 1; 

      

        // Тот же случай, что и выше для 'q' и 'r'

        if (p == 0 && q == 1 && r == 0 && last == 1) 

            return 1; 

          

        if (p == 0 && q == 0 && r == 1 && last == 2) 

            return 1; 

      

        // Если эта подзадача уже оценена

        if (dp[p, q, r, last] != -1) 

            return dp[p, q, r, last]; 

      

        // если требуется последний шар P и

        // количество путей это сумма

        // количество способов формирования последовательности

        // с 'p-1' P шариками, q Q balss и

        // r R шары, оканчивающиеся на Q и R.

        if (last == 0) 

        dp[p, q, r, last] = countWays(p - 1, q, r, 1) + 

                            countWays(p - 1, q, r, 2); 

      

        // То же, что и в предыдущем случае для 'q' и 'r'

        else if (last == 1) 

        dp[p, q, r, last] = countWays(p, q - 1, r, 0) + 

                            countWays(p, q - 1, r, 2); 

        // (последнее == 2)

        else

        dp[p, q, r, last] = countWays(p, q, r - 1, 0) + 

                            countWays(p, q, r - 1, 1); 

      

        return dp[p, q, r, last]; 

    

      

    // Возвращает количество необходимых договоренностей

    static int countUtil(int p, int q, int r) 

    

        // Инициализируем массив 'dp'

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

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

        for(int k = 0; k < MAX; k++)

        for(int l = 0; l < 4; l++)

        dp[i, j, k, l] = -1;

      

        // Три случая возникают:

        return countWays(p, q, r, 0) + // Последние необходимые шары типа P

            countWays(p, q, r, 1) + // Последние необходимые шары типа Q

            countWays(p, q, r, 2); // Последние необходимые шары типа R

    

  

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

    static void Main() 

    

        int p = 1, q = 1, r = 1; 

        Console.WriteLine(countUtil(p, q, r)); 

    

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

python3

# Python3 программа для подсчета количества способов
# расставить три типа шаров так, что нет
# два шарика одного цвета соседствуют друг с другом

MAX = 100

  
# таблица для хранения результатов подзадач

dp = [[[[-1] * 4 for i in range(MAX)] 

                 for j in range(MAX)] 

                 for k in range(MAX)]; 

  
# Возвращает количество договоренностей, где последний
# помещенный шар является 'последним'. 'last' равно 0 для 'p',
№ 1 для «д» и 2 для «г»

def countWays(p, q, r, last):

  

    # если количество шариков любого цвета становится меньше

    # 0 количество способов аранжировки равно 0.

    if (p < 0 or q < 0 or r < 0): 

        return 0

  

    # Если требуется последний мяч типа P и

    # количество шаров типа P равно 1, а число

    Количество шаров другого цвета равно 0

    # путей это 1.

    if (p == 1 and q == 0 and 

        r == 0 and last == 0): 

        return 1

  

    # Тот же случай, что и выше для 'q' и 'r'

    if (p == 0 and q == 1 and

        r == 0 and last == 1): 

        return 1

    if (p == 0 and q == 0 and 

        r == 1 and last == 2): 

        return 1

  

    # Если эта подзадача уже оценена

    if (dp[p][q][r][last] != -1): 

        return dp[p][q][r][last]; 

  

    # если последний требуемый мяч равен P и числу

    Количество путей - это сумма количества способов

    # последовательность форм с 'p-1' P шарами, q Q шарами

    # и r R шарики, заканчивающиеся на Q и R.

    if (last == 0):

        dp[p][q][r][last] = (countWays(p - 1, q, r, 1) + 

                             countWays(p - 1, q, r, 2)); 

  

    # То же, что и в предыдущем случае для 'q' и 'r'

    elif (last == 1):

        dp[p][q][r][last] = (countWays(p, q - 1, r, 0) + 

                             countWays(p, q - 1, r, 2)); 

    else:

          

        # (Последний == 2)

        dp[p][q][r][last] = (countWays(p, q, r - 1, 0) + 

                             countWays(p, q, r - 1, 1)); 

  

    return dp[p][q][r][last]; 

  
# Возвращает количество необходимых договоренностей

def countUtil(p, q, r):

      

    # Три случая возникают:

    # Последние необходимые шары типа P

    # Последние необходимые шары типа Q

    # Последние необходимые шары типа R

    return (countWays(p, q, r, 0) + 

            countWays(p, q, r, 1) + 

            countWays(p, q, r, 2));

  
Код водителя

p, q, r = 1, 1, 1

print(countUtil(p, q, r)); 

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

PHP

<?php
// PHP-программа для подсчета количества способов
// расставляем шары трех типов так, чтобы
// нет двух шаров одного цвета
// друг другу

$MAX = 100; 

  
// таблица для хранения результатов подзадач

$dp = array_fill(0, $MAX, array_fill(0, $MAX

      array_fill(0, $MAX, array_fill(0, 3, -1)))); 

  
// Возвращает количество договоренностей, где последний
// помещенный шар 'последний'. 'last' равно 0 для 'p',
// 1 для «q» и 2 для «r»

function countWays($p, $q, $r, $last

{

    global $dp;

      

    // если количество шариков любого цвета становится меньше

    // чем 0, количество способов аранжировки равно 0.

    if ($p < 0 || $q < 0 || $r < 0) 

        return 0; 

  

    // Если требуется последний шар типа P и

    // количество шаров типа P равно 1, а число

    // шаров другого цвета равно 0

    // way is 1.

    if ($p == 1 && $q == 0 && $r == 0 && $last == 0) 

        return 1; 

  

    // Тот же случай, что и выше для 'q' и 'r'

    if ($p == 0 && $q == 1 && $r == 0 && $last == 1) 

        return 1; 

    if ($p == 0 && $q == 0 && $r == 1 && $last == 2) 

        return 1; 

  

    // Если эта подзадача уже оценена

    if ($dp[$p][$q][$r][$last] != -1) 

        return $dp[$p][$q][$r][$last]; 

  

    // если последний требуемый шар равен P и числу

    // way - сумма количества способов сформировать

    // последовательность с 'p-1' P шарами, q Q шарами и r

    // R шарики, заканчивающиеся на Q и R.

    if ($last == 0) 

    $dp[$p][$q][$r][$last] = countWays($p - 1, $q, $r, 1) + 

                             countWays($p - 1, $q, $r, 2); 

  

    // То же, что и в предыдущем случае для 'q' и 'r'

    else if ($last == 1) 

    $dp[$p][$q][$r][$last] = countWays($p, $q - 1, $r, 0) + 

                             countWays($p, $q - 1, $r, 2); 

    else // (последнее == 2)

    $dp[$p][$q][$r][$last] = countWays($p, $q, $r - 1, 0) + 

                             countWays($p, $q, $r - 1, 1); 

  

    return $dp[$p][$q][$r][$last]; 

  
// Возвращает количество необходимых договоренностей

function countUtil($p, $q, $r

  
// Три случая возникают:

return countWays($p, $q, $r, 0) + // Последние необходимые шары типа P

       countWays($p, $q, $r, 1) + // Последние необходимые шары типа Q

       countWays($p, $q, $r, 2); // Последние необходимые шары типа R

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

$p = 1;

$q = 1;

$r = 1; 

print(countUtil($p, $q, $r)); 

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


Выход:

6

Временная сложность: O (p * q * r)
Вспомогательное пространство: O (p * q * r * 3)

Эта статья предоставлена Бхавук Чавла . Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью и отправить ее по почте на contrib@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

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

Способы расстановки шаров так, чтобы смежные шары были разных типов

0.00 (0%) 0 votes