Рубрики

Минимальное количество квадратов, сумма которых равна заданному числу n

Число всегда можно представить в виде суммы квадратов других чисел. Обратите внимание, что 1 — это квадрат, и мы всегда можем разбить число на (1 * 1 + 1 * 1 + 1 * 1 +…). Дано число n, найти минимальное количество квадратов, сумма которых равна X.

Примеры :

Input:  n = 100
Output: 1
100 can be written as 102. Note that 100 can also be 
written as 52 + 52 + 52 + 52, but this
representation requires 4 squares.

Input:  n = 6
Output: 3

Идея проста, мы начинаем с 1 и идем до числа, квадрат которого меньше или равен n. Для каждого числа x мы повторяем для nx. Ниже приведена рекурсивная формула.

If n = 1 and x*x <= n 

Ниже приведено простое рекурсивное решение на основе приведенной выше рекурсивной формулы.

C ++

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

using namespace std;

  
// Возвращает количество минимальных квадратов, сумма которых равна n

int getMinSquares(unsigned int n)

{

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

    // если n - идеальный квадрат, то минимальное необходимое квадратик - 1 (144 = 12 ^ 2)

    if (sqrt(n) - floor(sqrt(n)) == 0)

        return 1;

    if (n <= 3)

        return n;

  

    // getMinSquares остальная часть таблицы, использующая рекурсив

    // формула

    int res = n; // Максимально необходимое количество квадратов - n (1 * 1 + 1 * 1 + ..)

  

    // Проходим все меньшие числа

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

    for (int x = 1; x <= n; x++) {

        int temp = x * x;

        if (temp > n)

            break;

        else

            res = min(res, 1 + getMinSquares(n - temp));

    }

    return res;

}

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

int main()

{

    cout << getMinSquares(6);

    return 0;

}

Джава

// Наивная рекурсивная JAVA-программа для поиска минимума
// количество квадратов, сумма которых равна заданному числу

class squares {

    // Возвращает количество минимальных квадратов, сумма которых равна n

    static int getMinSquares(int n)

    {

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

        if (n <= 3)

            return n;

  

        // getMinSquares остальная часть таблицы, использующая рекурсив

        // формула

        int res = n; // Требуемое максимальное количество квадратов

        // n (1 * 1 + 1 * 1 + ..)

  

        // Проходим все меньшие числа

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

        for (int x = 1; x <= n; x++) {

            int temp = x * x;

            if (temp > n)

                break;

            else

                res = Math.min(res, 1 + getMinSquares(n - temp));

        }

        return res;

    }

    public static void main(String args[])

    {

        System.out.println(getMinSquares(6));

    }

}
/ * Этот код предоставлен Раджатом Мишрой * /

питон

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

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

def getMinSquares(n):

  

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

    if n <= 3:

        return n;

  

    # getMinSquares остальная часть таблицы

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

    res = n # Требуется максимум квадратов

            # - это n (1 * 1 + 1 * 1 + ..)

  

    # Пройдите все меньшие числа

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

    for x in range(1, n + 1):

        temp = x * x;

        if temp > n:

            break

        else:

            res = min(res, 1 + getMinSquares(n 

                                  - temp))

      

    return res;

  
# Драйверная программа

print(getMinSquares(6))

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

C #

// Наивная рекурсивная программа на C #
// найти минимальное количество
// квадраты, сумма которых равна
// на указанное число

using System;

  

class GFG {

  

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

    // квадраты, сумма которых равна n

    static int getMinSquares(int n)

    {

  

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

        if (n <= 3)

            return n;

  

        // getMinSquares остальная часть

        // таблица с использованием рекурсии

        // формула

  

        // Требуемое максимальное количество квадратов

        // n (1 * 1 + 1 * 1 + ..)

        int res = n;

  

        // Проходим все меньшие числа

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

        for (int x = 1; x <= n; x++) {

            int temp = x * x;

            if (temp > n)

                break;

            else

                res = Math.Min(res, 1 + getMinSquares(n - temp));

        }

        return res;

    }

  

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

    public static void Main()

    {

        Console.Write(getMinSquares(6));

    }

}

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

PHP

<?php
// Наивная рекурсивная PHP-программа
// найти минимальное количество
// квадраты, сумма которых равна
// на указанное число

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

function getMinSquares($n)

{

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

    if ($n <= 3)

        return $n;

  

    // getMinSquares остальная часть

    // таблица с использованием рекурсивной формулы

      

    // Максимально необходимое количество квадратов

    // равен n (1 * 1 + 1 * 1 + ..)

    $res = $n

  

    // Проходим все меньшие числа

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

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

    {

        $temp = $x * $x;

        if ($temp > $n)

            break;

        else

            $res = min($res, 1 + 

                       getMinSquares($n

                                     $temp));

    }

    return $res;

}

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

echo getMinSquares(6);

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


Выход :

3

Временная сложность вышеуказанного решения является экспоненциальной. Если мы рисуем полное дерево рекурсии, мы можем наблюдать, что многие подзадачи решаются снова и снова. Например, когда мы начинаем с n = 6, мы можем достичь 4, вычитая один 2 раза и вычитая 2 один раз. Таким образом, подзадача для 4 вызывается дважды.
Поскольку те же самые подзадачи вызываются снова, эта проблема имеет свойство Перекрывающиеся подзадачи. Таким образом, проблема минимальной квадратной суммы имеет оба свойства (см. Это и это ) задачи динамического программирования. Как и другие типичные проблемы динамического программирования (DP) , повторных вычислений с одинаковыми подзадачами можно избежать, построив таблицу временных массивов [] [] по принципу «снизу вверх». Ниже представлено решение на основе динамического программирования.

C ++

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

using namespace std;

  
// Возвращает количество минимальных квадратов, сумма которых равна n

int getMinSquares(int n)

{

    // Создать динамическую таблицу программирования

    // хранить кв

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

  

    // getMinSquares таблица для записей базового варианта

    dp[0] = 0;

    dp[1] = 1;

    dp[2] = 2;

    dp[3] = 3;

  

    // getMinSquares остальная часть таблицы, использующая рекурсив

    // формула

    for (int i = 4; i <= n; i++) {

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

        // как 1 * 1 + 1 * 1 + ...

        dp[i] = i;

  

        // Проходим все меньшие числа, чтобы

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

        for (int x = 1; x <= ceil(sqrt(i)); x++) {

            int temp = x * x;

            if (temp > i)

                break;

            else

                dp[i] = min(dp[i], 1 + dp[i - temp]);

        }

    }

  

    // Сохранить результат и освободить дп []

    int res = dp[n];

    delete[] dp;

  

    return res;

}

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

int main()

{

    cout << getMinSquares(6);

    return 0;

}

Джава

// JAVA-программа на основе динамического программирования для нахождения минимума
// количество квадратов, сумма которых равна заданному числу

class squares {

    // Возвращает количество минимальных квадратов, сумма которых равна n

    static int getMinSquares(int n)

    {

  

        // Здесь нужно добавить проверку для n. Если пользователь вводит 0 или 1 или 2

        // создание массива ниже будет OutOfBounds.

        if (n <= 3)

            return n;

  

        // Создать динамическую таблицу программирования

        // хранить кв

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

  

        // getMinSquares таблица для записей базового варианта

        dp[0] = 0;

        dp[1] = 1;

        dp[2] = 2;

        dp[3] = 3;

  

        // getMinSquares остальная часть таблицы, использующая рекурсив

        // формула

        for (int i = 4; i <= n; i++) {

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

            // как 1 * 1 + 1 * 1 + ...

            dp[i] = i;

  

            // Проходим все меньшие числа, чтобы

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

            for (int x = 1; x <= Math.ceil(Math.sqrt(i)); x++) {

                int temp = x * x;

                if (temp > i)

                    break;

                else

                    dp[i] = Math.min(dp[i], 1 + dp[i - temp]);

            }

        }

  

        // Сохранить результат и освободить дп []

        int res = dp[n];

  

        return res;

    }

    public static void main(String args[])

    {

        System.out.println(getMinSquares(6));

    }

} / * Этот код предоставлен Раджатом Мишрой * /

питон

# Python на основе динамического программирования
# программа для поиска минимального количества
# квадраты, сумма которых равна
# номер

from math import ceil, sqrt

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

def getMinSquares(n):

  

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

    # хранить sq и таблицу getMinSquares

    # для записей базового случая

    dp = [0, 1, 2, 3]

  

    # getMinSquares остальная часть таблицы

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

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

          

        # максимальное значение это я, как я всегда могу

        # быть представленным как 1 * 1 + 1 * 1 + ...

        dp.append(i)

  

        # Пройдите все меньшие числа

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

        for x in range(1, int(ceil(sqrt(i))) + 1):

            temp = x * x;

            if temp > i:

                break

            else:

                dp[i] = min(dp[i], 1 + dp[i-temp])

  

    # Сохранить результат

    return dp[n]

  
# Драйверная программа

print(getMinSquares(6))

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

C #

// Динамическое программирование на основе
// C # программа для поиска минимума
// количество квадратов, сумма которых
// равно заданному числу

using System;

  

class squares {

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

    // квадраты, сумма которых равна n

    static int getMinSquares(int n)

    {

  

        // Здесь нужно добавить проверку для n. Если пользователь вводит 0 или 1 или 2

        // создание массива ниже будет OutOfBounds.

  

        if (n <= 3)

            return n;

  

        // Создать динамическое программирование

        // таблица для хранения sq

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

  

        // getMinSquares таблица для базы

        // записи дел

        dp[0] = 0;

        dp[1] = 1;

        dp[2] = 2;

        dp[3] = 3;

  

        // getMinSquares для отдыха

        // таблица с использованием рекурсивной формулы

        for (int i = 4; i <= n; i++) {

            // максимальное значение i, как я могу

            // всегда будет представлен

            // как 1 * 1 + 1 * 1 + ...

            dp[i] = i;

  

            // Проходим все меньшие числа, чтобы

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

            for (int x = 1; x <= Math.Ceiling(Math.Sqrt(i)); x++) {

                int temp = x * x;

                if (temp > i)

                    break;

                else

                    dp[i] = Math.Min(dp[i], 1 + dp[i - temp]);

            }

        }

  

        // Сохранить результат и освободить дп []

        int res = dp[n];

  

        return res;

    }

  

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

    public static void Main(String[] args)

    {

        Console.Write(getMinSquares(6));

    }

}

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

PHP

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

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

function getMinSquares($n)

{

    // Создать динамическое программирование

    // таблица для хранения sq

    $dp;

  

    // getMinSquares таблица для

    // записи базового случая

    $dp[0] = 0;

    $dp[1] = 1;

    $dp[2] = 2;

    $dp[3] = 3;

  

    // getMinSquares остальная часть

    // таблица с использованием рекурсивной формулы

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

    {

        // максимальное значение i, как я могу

        // всегда будет представлен

        // как 1 * 1 + 1 * 1 + ...

        $dp[$i] = $i;

  

        // пройти через все меньшее

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

        // найти минимум

for ($x = 1; $x <= ceil(sqrt($i)); $x++) 

        {

            $temp = $x * $x;

            if ($temp > $i)

                break;

            else $dp[$i] = min($dp[$i], 

                              (1 + $dp[$i - $temp]));

        }

    }

  

    // Сохранить результат

    // и свободный дп []

    $res = $dp[$n];

  
// удалить $ dp;

  

    return $res;

}

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

echo getMinSquares(6);

      
// Этот код добавлен
// от shiv_bhakt.
?>


Выход:

3

Спасибо Gaurav Ahirwar за то, что он предложил это решение.

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

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

Минимальное количество квадратов, сумма которых равна заданному числу n

0.00 (0%) 0 votes