Рубрики

Рекурсивно разбить число на 3 части, чтобы получить максимальную сумму

Учитывая число n, мы можем разделить его только на три части n / 2, n / 3 и n / 4 (мы будем рассматривать только целую часть). Задача состоит в том, чтобы найти максимальную сумму, которую мы можем сделать, рекурсивно разделив число на три части и суммируя их вместе.

Примеры:

Input : n = 12
Output : 13
// We break n = 12 in three parts {12/2, 12/3, 12/4} 
// = {6, 4, 3},  now current sum is = (6 + 4 + 3) = 13 
// again we break 6 = {6/2, 6/3, 6/4} = {3, 2, 1} = 3 + 
// 2 + 1 = 6 and further breaking 3, 2 and 1 we get maximum
// summation as 1, so breaking 6 in three parts produces
// maximum sum 6 only similarly breaking 4 in three   
// parts we can get maximum sum 4 and same for 3 also.
// Thus maximum sum by breaking number in parts  is=13

Input : n = 24
Output : 27
// We break n = 24 in three parts {24/2, 24/3, 24/4} 
// = {12, 8, 6},  now current sum is = (12 + 8 + 6) = 26
// As seen in example, recursively breaking 12 would
// produce value 13. So our maximum sum is 13 + 8 + 6 = 27.
// Note that recursively breaking 8 and 6 doesn't produce
// more values, that is why they are not broken further.

Input : n = 23
Output : 23
// we break n = 23 in three parts {23/2, 23/3, 23/4} = 
// {10, 7, 5}, now current sum is = (10 + 7 + 5) = 22. 
// Since  after further breaking we can not get maximum
// sum hence number is itself maximum i.e; answer is 23

Простое решение этой проблемы — сделать это рекурсивно . В каждом вызове мы должны проверять только max ((max (n / 2) + max (n / 3) + max (n / 4)), n) и возвращать его. Потому что либо мы можем получить максимальную сумму, разбив число на части, либо число само по себе является максимальным. Ниже приведена реализация рекурсивного алгоритма.

C ++

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

using namespace std;

  
// Функция для поиска максимальной суммы

int breakSum(int n)

{

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

    if (n==0 || n == 1)

        return n;

  

    // рекурсивно ломаем номер и возвращаем

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

    return max((breakSum(n/2) + breakSum(n/3) +

                breakSum(n/4)),  n);

}

  
// Драйвер программы для запуска дела

int main()

{

    int n = 12;

    cout << breakSum(n);

    return 0;

}

Джава

// Простая рекурсивная JAVA-программа для поиска
// максимальная сумма путем рекурсивного разбиения
// номер в 3 частях.

import java.io.*;

  

class GFG {

     

    // Функция для поиска максимальной суммы

    static int breakSum(int n)

    {

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

        if (n==0 || n == 1)

            return n;

   

        // рекурсивно ломаем номер и возвращаем

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

        return Math.max((breakSum(n/2) + breakSum(n/3) +

                    breakSum(n/4)),  n);    

    }

          

    // Программа драйвера для проверки вышеуказанной функции

    public static void main (String[] args) {

        int n = 12;

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

    }

}
// Этот код предоставлен Амитом Кумаром

python3

# Простая рекурсивная программа на Python3 для
# найти максимальную сумму путем рекурсивного разбиения
# номер в 3-х частях.

  
# Функция поиска максимальной суммы

def breakSum(n) :

  

    # базовые условия

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

        return

  

    # рекурсивно ломать номер и

    # верните, какой максимум вы можете получить

    return max((breakSum(n // 2) + 

                breakSum(n // 3) +

                breakSum(n // 4)), n) 

  
Код водителя

if __name__ == "__main__"

  

    n = 12

    print(breakSum(n))

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

C #

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

using System;

  

class GFG {

      

    // Функция для поиска максимальной суммы

    static int breakSum(int n)

    {

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

        if (n==0 || n == 1)

            return n;

  

        // рекурсивно ломаем номер

        // и вернем, какой максимум ты

        // можно получить

        return Math.Max((breakSum(n/2)

                       + breakSum(n/3) 

                 + breakSum(n/4)), n); 

    }

          

    // Драйвер программы для проверки

    // вышеуказанная функция

    public static void Main () 

    {

        int n = 12;

          

        Console.WriteLine(breakSum(n));

    }

}

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

PHP

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

  
// Функция для поиска максимальной суммы

function breakSum($n)

{

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

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

        return $n;

  

    // рекурсивно ломаем номер и

    // вернуть максимум, который вы можете получить

    return max((breakSum(intval($n / 2)) + 

                breakSum(intval($n / 3)) +

                breakSum(intval($n / 4))), $n);

}

  
// Драйвер программы для запуска дела

$n = 12;

echo breakSum($n);

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


Выход :

13

Эффективным решением этой проблемы является использование динамического программирования, поскольку при рекурсивном разбиении числа на части нам приходится выполнять некоторые перекрывающиеся задачи. Например, часть n = 30 будет {15,10,7}, а часть 15 будет {7,5,3}, поэтому мы должны повторить процесс 7 раз два для дальнейшего разрушения. Чтобы избежать этой проблемы, мы используем динамическое программирование . Мы храним значения в массиве, и если для какого-либо числа в рекурсивных вызовах у нас уже есть решение для этого числа, поэтому мы прямо извлекаем его из массива.

C ++

// Программа на C ++, основанная на динамическом программировании
// найти максимальную сумму путем рекурсивного разбиения
// число в 3 частях.
#include<bits/stdc++.h>
#define MAX 1000000

using namespace std;

  

int breakSum(int n)

{

    int dp[n+1];

  

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

    dp[0] = 0, dp[1] = 1;

  

    // Заполняем снизу вверх используя рекурсив

    // формула

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

       dp[i] = max(dp[i/2] + dp[i/3] + dp[i/4], i);

  

    return dp[n];

}

  
// Драйвер программы для запуска дела

int main()

{

    int n = 24;

    cout << breakSum(n);

    return 0;

}

Джава

// Простая рекурсивная JAVA-программа для поиска
// максимальная сумма путем рекурсивного разбиения
// номер в 3 частях.

import java.io.*;

  

class GFG {

  

    final int MAX = 1000000;

      

    // Функция для поиска максимальной суммы

    static int breakSum(int n)

    {

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

   

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

        dp[0] = 0;  dp[1] = 1;

       

        // Заполняем снизу вверх используя рекурсив

        // формула

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

           dp[i] = Math.max(dp[i/2] + dp[i/3] + dp[i/4], i);

       

        return dp[n]; 

    }

          

    // Программа драйвера для проверки вышеуказанной функции

    public static void main (String[] args) {

        int n = 24;

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

    }

}
// Этот код предоставлен Амитом Кумаром

python3

# Программа Python, основанная на динамическом программировании
# найти максимальную сумму путем рекурсивного разбиения
# номер в 3-х частях.

  

MAX = 1000000

  

def breakSum(n):

  

    dp = [0]*(n+1)

  

    # базовые условия

    dp[0] = 0

    dp[1] = 1

  

    # Заполнить снизу вверх, используя рекурсив

    # формула.

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

        dp[i] = max(dp[int(i/2)] + dp[int(i/3)] + dp[int(i/4)], i);

  

    return dp[n]

  

  
# Драйвер программы для запуска дела

n = 24

print(breakSum(n))

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

C #

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

using System;

  

class GFG {

      

    // Функция для поиска максимальной суммы

    static int breakSum(int n)

    {

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

  

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

        dp[0] = 0; dp[1] = 1;

      

        // Заполняем снизу вверх

        // используя рекурсивную формулу.

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

            dp[i] = Math.Max(dp[i/2] + 

                  dp[i/3] + dp[i/4], i);

      

        return dp[n]; 

    }

          

    // Драйвер программы для проверки

    // вышеуказанная функция

    public static void Main () 

    {

        int n = 24;

        Console.WriteLine(breakSum(n));

    }

}

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

PHP

<?php
// Программа на основе динамического программирования PHP
// найти максимальную сумму путем рекурсивного разбиения
// число в 3 частях.

function breakSum($n)

{

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

  

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

    $dp[0] = 0;

    $dp[1] = 1;

  

    // Заполняем снизу вверх, используя

    // рекурсивная формула.

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

    $dp[$i] = max($dp[(int)($i / 2)] + 

                  $dp[(int)($i / 3)] + 

                  $dp[(int)($i / 4)], $i);

  

    return $dp[$n];

}

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

$n = 24;

echo breakSum($n);

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


Выход:

27

Сложность времени: O (n)
Вспомогательное пространство: O (n)

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

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

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

Рекурсивно разбить число на 3 части, чтобы получить максимальную сумму

0.00 (0%) 0 votes