Рубрики

Взлом целого числа, чтобы получить максимальный продукт

При заданном числе n задача разбить таким образом, чтобы умножение его частей было максимизировано.

Input : n = 10
Output : 36
10 = 4 + 3 + 3 and 4 * 3 * 3 = 36
is maximum possible product.

Input : n = 8
Output : 18
8 = 2 + 3 + 3 and 2 * 3 * 3 = 36
is maximum possible product.

Математически нам дано n, и нам нужно максимизировать a1 * a2 * a3…. * aK такое, что n = a1 + a2 + a3… + aK и a1, a2,… ak> 0.

Обратите внимание, что нам нужно разбить данное целое как минимум на две части в этой задаче для максимизации продукта.

Теперь из концепции максимумов-минимумов мы знаем, что если целое число нужно разбить на две части, то для максимизации их произведения эти части должны быть равны. Используя эту концепцию, давайте разбить n на (n / x) x, тогда их произведение будет x (n / x) , теперь, если мы возьмем производную этого продукта и сделаем ее равной 0 для максимумов, мы узнаем, что значение х должен быть е (основание натурального логарифма) для максимального продукта. Поскольку мы знаем, что 2 <e <3, мы должны разбивать каждое целое число на 2 или 3 только для максимального продукта.
Далее 6 = 3 + 3 = 2 + 2 + 2, но 3 * 3> 2 * 2 * 2, то есть каждый триплет из 2 можно заменить на кортеж 3 для максимального продукта, поэтому мы будем продолжать ломать число только с точки зрения 3, пока число не останется равным 4 или 2, которое мы будем разбивать на 2 * 2 (2 * 2> 3 * 1) и 2 соответственно, и мы получим наш максимальный продукт.
Короче говоря, процедура для получения максимального продукта выглядит следующим образом: попробуйте разбить целое число в степени только 3 и, когда целое число остается небольшим (<5), затем используйте грубую силу.
Сложность приведенной ниже программы составляет O (log N) из-за метода многократного возведения в квадрат .

Ниже приведена реализация вышеуказанного подхода:

C ++

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

using namespace std;

  
// метод, возвращающий x ^ a в log (a) раз

int power(int x, int a)

{

    int res = 1;

    while (a)

    {

        if (a & 1)

            res = res * x;

        x = x * x;

        a >>= 1;

    }

    return res;

}

  
// Метод возвращает максимальный продукт, полученный
// ломаем N

int breakInteger(int N)

{

    // базовый случай 2 = 1 + 1

    if (N == 2)

        return 1;

  

    // базовый случай 3 = 2 + 1

    if (N == 3)

        return 2;

  

    int maxProduct;

  

    // взлом на основе мода с 3

    switch (N % 3)

    {

        // Если делится равномерно, то разбить на все 3

        case 0:

            maxProduct = power(3, N/3);

            break;

  

        // Если деление дает mod как 1, то break как

        // 4 + степень 3 для оставшейся части

        case 1:

            maxProduct = 2 * 2 * power(3, (N/3) - 1);

            break;

  

        // Если деление дает mod как 2, то break как

        // 2 + степень 3 для оставшейся части

        case 2:

            maxProduct = 2 * power(3, N/3);

            break;

    }

    return maxProduct;

}

  
// Код драйвера для тестирования вышеуказанных методов

int main()

{

    int maxProduct = breakInteger(10);

    cout << maxProduct << endl;

    return 0;

}

Джава

// Java программа для поиска максимального продукта путем взлома
// Целое число

  

class GFG{

// метод, возвращающий x ^ a в log (a) раз

static int power(int x, int a)

{

    int res = 1;

    while (a>0)

    {

        if ((a & 1)>0)

            res = res * x;

        x = x * x;

        a >>= 1;

    }

    return res;

}

  
// Метод возвращает максимальный продукт, полученный
// ломаем N

static int breakInteger(int N)

{

    // базовый случай 2 = 1 + 1

    if (N == 2)

        return 1;

  

    // базовый случай 3 = 2 + 1

    if (N == 3)

        return 2;

  

    int maxProduct=-1;

  

    // взлом на основе мода с 3

    switch (N % 3)

    {

        // Если делится равномерно, то разбить на все 3

        case 0:

            maxProduct = power(3, N/3);

            break;

  

        // Если деление дает mod как 1, то break как

        // 4 + степень 3 для оставшейся части

        case 1:

            maxProduct = 2 * 2 * power(3, (N/3) - 1);

            break;

  

        // Если деление дает mod как 2, то break как

        // 2 + степень 3 для оставшейся части

        case 2:

            maxProduct = 2 * power(3, N/3);

            break;

    }

    return maxProduct;

}

  
// Код драйвера для тестирования вышеуказанных методов

public static void main(String[] args)

{

    int maxProduct = breakInteger(10);

    System.out.println(maxProduct);

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

python3

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

    
# метод возврата x ^ a в log (a) время

def power(x, a): 

   

    res = 1

    while (a):

        if (a & 1): 

            res = res * x; 

        x = x * x; 

        a >>= 1;

          

    return res; 

    
# Метод возвращает максимальный продукт, полученный
# ломать N

def breakInteger(N):

    # базовый вариант 2 = 1 + 1

    if (N == 2): 

        return 1

    

    # базовый вариант 3 = 2 + 1

    if (N == 3): 

        return 2

    

    maxProduct=0

    

    # взлом на основе мода с 3

    if(N % 3==0): 

        # Если делится поровну, то разбей на все 3

        maxProduct = power(3, int(N/3)); 

        return maxProduct; 

    elif(N%3==1):

        # Если деление дает мод как 1, то разбить как

        # 4 + сила 3 для оставшейся части

        maxProduct = 2 * 2 * power(3, int(N/3) - 1); 

        return maxProduct;

    elif(N%3==2):

        # Если деление дает мод как 2, то разбить как

        # 2 + сила 3 для оставшейся части

        maxProduct = 2 * power(3, int(N/3));

        return maxProduct;

       

    
# Код драйвера для тестирования вышеуказанных методов

  

   

maxProduct = breakInteger(10); 

print(maxProduct); 

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

C #

// C # программа для поиска максимального продукта путем взлома
// Целое число

  

class GFG{ 

// метод, возвращающий x ^ a в log (a) раз

static int power(int x, int a) 

    int res = 1; 

    while (a>0) 

    

        if ((a & 1)>0) 

            res = res * x; 

        x = x * x; 

        a >>= 1; 

    

    return res; 

  
// Метод возвращает максимальный продукт, полученный
// ломаем N

static int breakInteger(int N) 

    // базовый случай 2 = 1 + 1

    if (N == 2) 

        return 1; 

  

    // базовый случай 3 = 2 + 1

    if (N == 3) 

        return 2; 

  

    int maxProduct=-1; 

  

    // взлом на основе мода с 3

    switch (N % 3) 

    

        // Если делится равномерно, то разбить на все 3

        case 0: 

            maxProduct = power(3, N/3); 

            break

  

        // Если деление дает mod как 1, то break как

        // 4 + степень 3 для оставшейся части

        case 1: 

            maxProduct = 2 * 2 * power(3, (N/3) - 1); 

            break

  

        // Если деление дает mod как 2, то break как

        // 2 + степень 3 для оставшейся части

        case 2: 

            maxProduct = 2 * power(3, N/3); 

            break

    

    return maxProduct; 

  
// Код драйвера для тестирования вышеуказанных методов

public static void Main() 

    int maxProduct = breakInteger(10); 

    System.Console.WriteLine(maxProduct); 



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

PHP

<?php
// PHP программа для поиска максимального продукта путем взлома
// Целое число

    
// метод, возвращающий x ^ a в log (a) раз

function power($x, $a

    $res = 1; 

    while ($a

    

        if ($a & 1) 

            $res = $res * $x

        $x = $x * $x

        $a >>= 1; 

    

    return $res

    
// Метод возвращает максимальный продукт, полученный
// ломаем N

function breakInteger($N

    // базовый случай 2 = 1 + 1

    if ($N == 2) 

        return 1; 

    

    // базовый случай 3 = 2 + 1

    if ($N == 3) 

        return 2; 

    

    $maxProduct=0; 

    

    // взлом на основе мода с 3

    switch ($N % 3) 

    

        // Если делится равномерно, то разбить на все 3

        case 0: 

            $maxProduct = power(3, $N/3); 

            break

    

        // Если деление дает mod как 1, то break как

        // 4 + степень 3 для оставшейся части

        case 1: 

            $maxProduct = 2 * 2 * power(3, ($N/3) - 1); 

            break

    

        // Если деление дает mod как 2, то break как

        // 2 + степень 3 для оставшейся части

        case 2: 

            $maxProduct = 2 * power(3, $N/3); 

            break

    

    return $maxProduct

    
// Код драйвера для тестирования вышеуказанных методов

  

   

    $maxProduct = breakInteger(10); 

    echo $maxProduct

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


Выход:

36

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

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

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

Взлом целого числа, чтобы получить максимальный продукт

0.00 (0%) 0 votes