Рубрики

Количество неотрицательных интегральных решений a + b + c = n

Учитывая число n, найдите количество способов, которыми мы можем добавить 3 неотрицательных целых числа так, чтобы их сумма была n.

Примеры :

Input : n = 1
Output : 3
There are four ways to get sum 1.
(1, 0, 0), (0, 1, 0) and (0, 0, 1)

Input : n = 2
Output : 6
There are six ways to get sum 2.
(2, 0, 0), (0, 2, 0), (0, 0, 2), (1, 1, 0)
(1, 0, 1) and (0, 1, 1)

Input : n = 3
Output : 10
There are ten ways to get sum 10.
(3, 0, 0), (0, 3, 0), (0, 0, 3), (1, 2, 0)
(1, 0, 2), (0, 1, 2), (2, 1, 0), (2, 0, 1),
(0, 2, 1) and (1, 1, 1)

Метод 1 [Грубая сила: O (n 3 )]
Простое решение состоит в том, чтобы рассмотреть все триплеты, используя три цикла. Для каждого триплета проверьте, равна ли его сумма n. Если сумма равна n, увеличить количество решений.

Ниже приведена реализация.

C ++

// Наивное решение C ++ для подсчета решений
// a + b + c = n
#include<bits/stdc++.h>

using namespace std;

  
// Возвращает количество решений a + b + c = n

int countIntegralSolutions(int n)

{

    // Инициализировать результат

    int result = 0;

  

    // Рассмотрим все триплеты и приращение

    // результат всякий раз, когда сумма триплета равна n.

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

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

          for (int k=0; k<=(n-i-j); k++)

             if (i + j + k == n)

              result++;

  

    return result;

}

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

int main()

{

    int n = 3;

    cout <<  countIntegralSolutions(n);

    return 0;

}

Джава

// Наивное Java-решение для подсчета
// решения a + b + c = n

import java.io.*;

  

class GFG 

{

    // Возвращает количество решений a + b + c = n

    static int countIntegralSolutions(int n)

    {

        // Инициализировать результат

        int result = 0;

      

        // Рассмотрим все триплеты и приращение

        // результат всякий раз, когда сумма триплета равна n.

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

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

            for (int k = 0; k <= (n - i - j); k++)

                if (i + j + k == n)

                result++;

      

        return result;

    }

  

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

    public static void main (String[] args) 

    {

        int n = 3;

        System.out.println( countIntegralSolutions(n));

      

    }

}

  
// Эта статья предоставлена vt_m

python3

# Python3 код для подсчета
# решения a + b + c = n

  
# Возвращает количество решений
# a + b + c = n

def countIntegralSolutions (n):

  

    # Инициализировать результат

    result = 0

      

    # Рассмотрим все тройки и

    # увеличивать результат всякий раз, когда

    # сумма триплета равна n.

    for i in range(n + 1):

        for j in range(n + 1):

            for k in range(n + 1):

                if i + j + k == n:

                    result += 1

      

    return result

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

n = 3

print(countIntegralSolutions(n))

  
# Этот код предоставлен "Sharad_Bhardwaj".

C #

// Наивное C # решение для подсчета
// решения a + b + c = n

using System;

  

class GFG {

      

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

    // из a + b + c = n

    static int countIntegralSolutions(int n)

    {

          

        // Инициализировать результат

        int result = 0;

      

        // Рассмотрим все триплеты и приращение

        // результат всякий раз, когда сумма триплета равна n.

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

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

                for (int k = 0; k <= (n - i - j); k++)

                    if (i + j + k == n)

                    result++;

      

        return result;

    }

  

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

    public static void Main () 

    {

        int n = 3;

        Console.Write(countIntegralSolutions(n));

      

    }

}

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

PHP

<?php
// Наивное решение PHP
// посчитать решения
// a + b + c = n

  
// Возвращает количество
// решения a + b + c = n

function countIntegralSolutions( $n)

{

      

    // Инициализировать результат

    $result = 0;

  

    // Рассмотрим все триплеты и приращение

    // результат всякий раз, когда сумма триплета равна n.

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

        for ($j = 0; $j <= $n - $i; $j++)

            for ($k = 0; $k <= ($n - $i - $j); $k++)

            if ($i + $j + $k == $n)

            $result++;

  

    return $result;

}

  

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

    $n = 3;

    echo countIntegralSolutions($n);

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


Выход :

10

Метод 2 [Прямая формула: O (1)]
Если мы более внимательно посмотрим на схему, то обнаружим, что количество решений равно ((n + 1) * (n + 2)) / 2. Задача эквивалентна распределению n + 1 одинаковых шаров (для 0 до n) в трех коробках и решение n + 2 C 2 . В общем случае, если имеется m переменных (или блоков) и n возможных значений, формула становится n + m-1 C m-1 .

C ++

// Наивное решение C ++ для подсчета решений
// a + b + c = n
#include<bits/stdc++.h>

using namespace std;

  
// Возвращает количество решений a + b + c = n

int countIntegralSolutions(int n)

{

    return ((n+1)*(n+2))/2;

}

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

int main()

{

    int n = 3;

    cout <<  countIntegralSolutions(n);

    return 0;

}

Джава

// Java-решение для подсчета
// решения a + b + c = n

import java.io.*;

  

class GFG 

{

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

    // из a + b + c = n

    static int countIntegralSolutions(int n)

    {

    return ((n + 1) * (n + 2)) / 2;

          

    }

      

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

    public static void main (String[] args) 

    {

        int n = 3;

        System.out.println ( countIntegralSolutions(n));

          

    }

}
// Эта статья предоставлена vt_m

python3

# Python3 решение для подсчета
# решения a + b + c = n

  
# Возвращает количество решений
# a + b + c = n

def countIntegralSolutions (n):

    return int(((n + 1) * (n + 2)) / 2)

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

n = 3

print(countIntegralSolutions(n))

  
# Этот код предоставлен "Sharad_Bhardwaj".

C #

// C # решение для подсчета
// решения a + b + c = n

using System;

  

class GFG {

      

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

    // из a + b + c = n

    static int countIntegralSolutions(int n)

    {

        return ((n + 1) * (n + 2)) / 2;

    }

      

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

    public static void Main (String[] args) 

    {

        int n = 3;

        Console.Write ( countIntegralSolutions(n));

          

    }

}

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

PHP

<?php
// Наивное решение PHP
// посчитать решения
// a + b + c = n

  
// Возвращает количество решений
// из a + b + c = n

function countIntegralSolutions($n)

{

    return (($n + 1) * ($n + 2)) / 2;

}

  

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

    $n = 3;

    echo countIntegralSolutions($n);

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


Выход :

10

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

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

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

Количество неотрицательных интегральных решений a + b + c = n

0.00 (0%) 0 votes