Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
TheMrPonchik
0 / 0 / 0
Регистрация: 19.02.2019
Сообщений: 1
1

Найти наименьшее количество членов суммы квадратов

19.02.2019, 13:31. Просмотров 120. Ответов 0

Нужно найти наименьшее количество членов суммы квадратов
Будет понятнее на примерах

Дано:
3
Вывод:
1 1 1

Дано:
10
Вывод:
3 1

Дано:
12
Вывод:
2 2 2

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

Добавлено через 1 час 7 минут
Нашёл код, который вычисляет количество этих чисел

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
// A dynamic programming based C++ program to find minimum 
// number of squares whose sum is equal to a given number 
#include "pch.h"
#include <iostream>
#include <algorithm>
 
using namespace std;
 
// Returns count of minimum squares that sum to n 
int getMinSquares(int n)
{
    // Create a dynamic programming table 
    // to store sq 
    int *dp = new int[n + 1];
 
    // getMinSquares table for base case entries 
    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 3;
 
    // getMinSquares rest of the table using recursive 
    // formula 
    for (int i = 4; i <= n; i++)
    {
        // max value is i as i can always be represented 
        // as 1*1 + 1*1 + ... 
        dp[i] = i;
 
        // Go through all smaller numbers to 
        // to recursively find minimum 
        for (int x = 1; x <= i; x++) {
            int temp = x * x;
            if (temp > i)
                break;
            dp[i] = min(dp[i], 1 + dp[i - temp]);
        }
    }
 
    // Store result and free dp[] 
    int res = dp[n];
    delete[] dp;
 
    return res;
}
 
// Driver program 
int main()
{
    cout << getMinSquares(10) << endl;
    return 0;
}
но не сами числа
нужны сами числа
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.02.2019, 13:31
Ответы с готовыми решениями:

В файле с целыми числами найти количество парных, количество удвоенных нечетных, количество квадратов нечетных
Задано файл, компонентами которого являются целые числа. Найти: a) количество парных среди...

Найти наименьшее натуральное число, непредставимое в виде суммы элементов массива Р
Дан массив P, содержащий N натуральных чисел. Найти наименьшее натуральное число, непредставимое в...

Найти числа, которые представимы в виде суммы квадратов двух натуральных чисел
Используя операторы цикла while или do...while Дано натуральное число N. Среди чисел 1, 2, …, N...

Перевести с Delphi на C++. Найти элементы последовательности, представимые в виде суммы двух квадратов
Всем доброго утра! помогите пожалуйста перевести программу на С++!! Дано натуральное число N....

Найти все натуральные числа, представимые в виде суммы квадратов трёх натуральных чисел
Помогите пожалуйста в задаче: Найти все натуральные числа от 1 до N, представимые в виде суммы...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.02.2019, 13:31

Найти все натуральные числа от 1 до n, суммы квадратов цифр которых равна самому числу
Найти все натуральные числа от 1 до n, сумма квадратов цифр которых равна самому числу Помогите...

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

Найти разность между суммой квадратов и квадратом суммы первых ста натуральных чисел
Сумма квадратов первых десяти натуральных чисел равна 12 + 22 + ... + 102 = 385 Квадрат суммы...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru