Рубрики

Подсчитайте количество способов разделить число на 4 части

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

Примеры :

Input:  n =  5
Output: 1
There is only one way (1, 1, 1, 2)

Input:  n =  6
Output: 2
There are two ways (1, 1, 1, 3) and 
(1, 1, 2, 2)

Input:  n =  8
Output: 5
There are five ways (2, 2, 2, 2), (1, 1, 1, 5),
(1, 1, 3, 3), (1, 1, 2, 4) and (1, 2, 2, 3)

Метод 1 (простое решение) Запустите четыре вложенных цикла, чтобы сгенерировать все возможные различные четверки. Ниже приведена реализация простого алгоритма на C ++.
Ниже приведена реализация вышеуказанного подхода:

C ++

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

using namespace std;

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

int countWays(int n)

{

    int counter = 0; // Инициализировать результат

  

    // Генерируем все возможные четверки и приращения

    // счетчик, когда сумма четверки равна n

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

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

            for (int k = j; k < n; k++)

                for (int l = k; l < n; l++)

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

                       counter++;

    return counter;

}

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

int main()

{

   int n = 8;

   cout << countWays(n);

   return 0;

}

Джава

// Простая Java-программа для подсчета количества способов
// представить число n как сумму четырех.

  

import java.io.*;

  

class GFG {

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

static int countWays(int n) 

    int counter = 0; // Инициализировать результат

  

    // Генерируем все возможные четверки и приращения

    // счетчик, когда сумма четверки равна n

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

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

            for (int k = j; k < n; k++) 

                for (int l = k; l < n; l++) 

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

                    counter++; 

    return counter; 

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

      

    public static void main (String[] args) {

        int n = 8

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

    }

}

python3

# Простая программа на python3 для подсчета
# количество способов представить число
# n как сумма четырех.

  
# Возвращает количество путей

def countWays(n):

  

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

  

    # Генерация всех возможных четверок

    # и счетчик приращений, когда сумма

    # четверка равна n

    for i in range(1, n):

        for j in range(i, n):

            for k in range(j, n):

                for l in range(k, n):

                    if (i + j + k + l == n):

                        counter += 1

    return counter

  
Код водителя

if __name__ == "__main__":

  

    n = 8

    print (countWays(n))

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

C #

// Простая программа на C # для подсчета числа
// способов представить число n как
// сумма четырех.

using System;

  

class GFG

{

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

static int countWays(int n) 

    int counter = 0; // Инициализировать результат

  

    // Генерируем все возможные четверки

    // и счетчик приращения, когда сумма

    // четверка равна n

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

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

            for (int k = j; k < n; k++) 

                for (int l = k; l < n; l++) 

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

                    counter++; 

    return counter; 

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

static public void Main ()

{

    int n = 8; 

    Console.WriteLine(countWays(n)); 

}
}

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

PHP

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

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

function countWays($n)

{

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

    $counter = 0;

  

    // Генерируем все возможные четверки

    // и счетчик приращения при сумме

    // четверки равен n

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

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

            for ($k = $j; $k < $n; $k++)

                for ( $l = $k; $l < $n; $l++)

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

                    $counter++;

    return $counter;

}

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

$n = 8;

echo countWays($n);

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


Выход :

5

Временная сложность вышеуказанного решения составляет O (n 4 )

Метод 2 (использует динамическое программирование)
Идея основана на ниже рекурсивном решении.

countWays(n, parts, nextPart) = ∑countWays(n, parts, i)
                          nextPart <= i  Input number
parts    --> Count of parts of n. Initially parts = 4
nextPart --> Starting point for next part to be tried
             We try for all values from nextPart to n.

We initially call the function as countWays(n, 4, 1)
 

Ниже приведено динамическое программирование, основанное на решении вышеуказанной идеи.

C ++

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

using namespace std;

int dp[5001][5001][5];

  
// "parts" - это количество оставшихся частей, n - это оставленное значение.
// «nextPart» является отправной точкой, с которой мы начинаем
// для следующей части.

int countWaysUtil(int n, int parts, int nextPart)

{

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

    if (parts == 0 && n == 0) return 1;

    if (n <= 0 || parts <= 0) return 0;

  

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

    if (dp[n][nextPart][parts] != -1)

       return dp[n][nextPart][parts];

  

    int ans = 0; // Инициализировать результат

  

    // Подсчитаем количество путей для оставшегося числа ni

    // остальные части "parts-1" и для всей части

    // изменяется от 'nextPart' до 'n'

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

        ans += countWaysUtil(n-i, parts-1, i);

  

    // Сохраняем вычисленный ответ в таблице и возвращаем

    // результат

    return (dp[n][nextPart][parts] = ans);

}

  
// Эта функция в основном инициализирует таблицу dp и
// вызывает countWaysUtil ()

int countWays(int n)

{

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

    return countWaysUtil(n, 4, 1);

}

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

int main()

{

   int n = 8;

   cout << countWays(n) << endl;

   return 0;

}

Джава

// Решение для подсчета числа на основе динамического программирования
// способов представить n как сумму четырех чисел

class GFG 

{

  

static int dp[][][] = new int[5001][5001][5];

  
// "parts" - это количество оставшихся частей, n - это оставленное значение.
// «nextPart» является отправной точкой, с которой мы начинаем
// для следующей части.

static int countWaysUtil(int n, int parts, int nextPart)

{

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

    if (parts == 0 && n == 0) return 1;

    if (n <= 0 || parts <= 0) return 0;

  

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

    if (dp[n][nextPart][parts] != -1)

    return dp[n][nextPart][parts];

  

    int ans = 0; // Инициализировать результат

  

    // Подсчитаем количество путей для оставшегося числа ni

    // остальные части "parts-1" и для всей части

    // изменяется от 'nextPart' до 'n'

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

        ans += countWaysUtil(n-i, parts-1, i);

  

    // Сохраняем вычисленный ответ в таблице и возвращаем

    // результат

    return (dp[n][nextPart][parts] = ans);

}

  
// Эта функция в основном инициализирует таблицу dp и
// вызывает countWaysUtil ()

static int countWays(int n)

{

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

    {

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

        {

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

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

        }

    }

    return countWaysUtil(n, 4, 1);

}

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

public static void main(String[] args) 

{

    int n = 8;

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

}
}

  
/ * Этот код предоставлен PrinciRaj1992 * /

python3

# Решение на основе динамического программирования
# считать количество способов представления
# n как сумма четырех чисел

  

dp = [[[-1 for i in range(5)] 

           for i in range(501)]

           for i in range(501)] 

  
# "parts" - количество оставшихся частей, n -
# значение слева "nextPart" начинается
# точка, с которой мы начинаем пытаться
# для следующей части.

def countWaysUtil(n, parts, nextPart):

      

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

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

        return 1

    if (n <= 0 or parts <= 0):

        return 0

  

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

    if (dp[n][nextPart][parts] != -1):

        return dp[n][nextPart][parts]

  

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

  

    # Подсчитать количество путей для оставшихся

    № количество оставшихся частей "части-1",

    # и для всех частей, начиная от

    # 'nextPart' до 'n'

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

        ans += countWaysUtil(n - i, parts - 1, i) 

  

    # Хранить вычисленный ответ в таблице

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

    dp[n][nextPart][parts] = ans 

    return (ans)

  
# Эта функция в основном инициализирует дп
# таблица и вызовы countWaysUtil ()

def countWays(n):

    return countWaysUtil(n, 4, 1)

  
Код водителя

n = 8

print(countWays(n))

  
# Этот код добавлен
# от sahishelangia

C #

// Решение для подсчета числа на основе динамического программирования
// способов представить n как сумму четырех чисел

using System;

      

class GFG 

{

  

static int [,,]dp = new int[5001, 5001, 5];

  
// "parts" - это количество оставшихся частей, n - это оставленное значение.
// «nextPart» является отправной точкой, с которой мы начинаем
// для следующей части.

static int countWaysUtil(int n, int parts, int nextPart)

{

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

    if (parts == 0 && n == 0) return 1;

    if (n <= 0 || parts <= 0) return 0;

  

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

    if (dp[n,nextPart,parts] != -1)

    return dp[n,nextPart,parts];

  

    int ans = 0; // Инициализировать результат

  

    // Подсчитаем количество путей для оставшегося числа ni

    // остальные части "parts-1" и для всей части

    // изменяется от 'nextPart' до 'n'

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

        ans += countWaysUtil(n - i, parts - 1, i);

  

    // Сохраняем вычисленный ответ в таблице и возвращаем

    // результат

    return (dp[n,nextPart,parts] = ans);

}

  
// Эта функция в основном инициализирует таблицу dp и
// вызывает countWaysUtil ()

static int countWays(int n)

{

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

    {

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

        {

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

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

        }

    }

    return countWaysUtil(n, 4, 1);

}

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

public static void Main(String[] args) 

{

    int n = 8;

    Console.WriteLine(countWays(n));

}
}

  
// Этот код предоставлен Rajput-Ji

PHP

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

$dp = array_fill(0, 501, 

      array_fill(0, 501, 

      array_fill(0, 5, -1)));

  
// "parts" - количество оставшихся частей, n -
// значение слева "nextPart" начинается
// точка, с которой мы начинаем
// для следующей части.

function countWaysUtil($n, $parts, $nextPart)

{

    global $dp;

      

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

    if ($parts == 0 && $n == 0) return 1;

    if ($n <= 0 || $parts <= 0) return 0;

  

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

    if ($dp[$n][$nextPart][$parts] != -1)

    return $dp[$n][$nextPart][$parts];

  

    $ans = 0; // Инициализировать результат

  

    // Подсчитать количество путей для оставшихся

    // число ni оставшихся частей "parts-1",

    // и для всех частей, отличающихся от

    // 'nextPart' к 'n'

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

        $ans += countWaysUtil($n - $i

                              $parts - 1, $i);

  

    // Сохраняем вычисленный ответ в таблице

    // и возвращаем результат

    return ($dp[$n][$nextPart][$parts] = $ans);

}

  
// Эта функция в основном инициализирует дп
// таблица и вызовы countWaysUtil ()

function countWays($n)

{

    return countWaysUtil($n, 4, 1);

}

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

$n = 8;

echo countWays($n);

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


Выход :

5

Временная сложность этого решения составляет O (n 3 ). Есть Θ (n 2 ) записей, каждая запись заполняется только один раз, а заполнение записи занимает O (n) времени.

Метод 3 (AO (n 2 Log n) решение)
Мы можем использовать решение, обсуждаемое в этом посте, чтобы найти все четверки.

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

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

Подсчитайте количество способов разделить число на 4 части

0.00 (0%) 0 votes