Представить число N в виде суммы натуральных чисел, являющихся полными квадратами

@alexfandr · Регистрация: 15.11.2018

Студворк — интернет-сервис помощи студентам

Я вывожу минимальное количество квадратов, сумма которых равна N. А как вывести сами эти квадраты?

Java
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
import java.util.*;
class SumsSqr { 
    static int getMinSquares(int n) 
    { 
        if (n <= 3) 
            return n; 
  
        int res = n; 
        for (int i = 1; i <= n; i++) { 
            int k = i * i; 
            if (k > n) 
                break; 
            else
                res = Math.min(res, 1 + getMinSquares(n - k)); 
        } 
       return res; 
    } 
    public static void main(String args[]) 
    { 
        Scanner inp = new Scanner(System.in);
        int n;
        System.out.println("Введите N ");
        n = inp.nextInt();
        System.out.println(getMinSquares(n)); 
        inp.close();
    } 
}

alicesmagic · 09.10.2019, 02:44

alexfandr, в вашей реализации время выполнения программы увеличивается в геометрической прогрессии в зависимости от величины передаваемого числа в метод. Передав число 100, я так и не смогла дождаться результата.
Я написала свой вариант без рекурсии, который считает очень быстро. Там два метода, выполняющие примерно одно и то же, но один возвращает коллекцию квадратов, а второй строку разложения числа на квадраты. Какой больше понравится

Вот:

Кликните здесь для просмотра всего текста

Java
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
53
54
55
56
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
 
public class GetSquares {
    static List<Integer> getListSquares(int n) {
        List<Integer> res = new ArrayList<>();
        List<Integer> squares = new ArrayList<>();
        for (int i = 1; i * i <= n; i++) {
            squares.add(i * i);
        }
        Collections.reverse(squares);
        while (n > 0) {
            if (squares.get(0) <= n) {
                res.add(squares.get(0));
                n -= squares.get(0);
            } else {
                squares.remove(0);
            }
        }
        return res;
    }
 
    static String getStringSquares(int n) {
        String res = n + " = ";
        List<Integer> squares = new ArrayList<>();
        for (int i = 1; i * i <= n; i++) {
            squares.add(i);
        }
        Collections.reverse(squares);
        while (n > 0) {
            if (squares.get(0) * squares.get(0) <= n) {
                res += squares.get(0) + "*" + squares.get(0) + " + ";
                n -= squares.get(0) * squares.get(0);
            } else {
                squares.remove(0);
            }
        }
        return res.substring(0, res.length() - 3);
    }
 
    public static void main(String args[]) {
        Scanner inp = new Scanner(System.in);
        int n;
        System.out.print("Введите натуральное число: ");
        n = inp.nextInt();
        System.out.println("Натуральные числа, являющиеся полными квадратами, " +
                "сумма которых равна " + n + ":");
        System.out.println(getListSquares(n));
        System.out.println("Число " + n + ", представленное в виде суммы " +
                "квадратов натуральных чисел:");
        System.out.println(getStringSquares(n));
        inp.close();
    }
}

Code
1
2
3
4
5
Введите натуральное число: 10000000
Натуральные числа, являющиеся полными квадратами, сумма которых равна 10000000:
[9998244, 1681, 64, 9, 1, 1]
Число 10000000, представленное в виде суммы квадратов натуральных чисел:
10000000 = 3162*3162 + 41*41 + 8*8 + 3*3 + 1*1 + 1*1

@alexfandr · 09.10.2019, 15:02 **[ТС]**

alicesmagic, классно, спасибо) Мы еще интерфейсы и коллекции по java не проходили, но вроде я разобрался. Чем то похоже на списки и контейнеры из с++

@ViktorFX · 09.10.2019, 19:27

alicesmagic, Мне понравилась идея начинать с больших и постепенно "спускаться" к разнице.
Я бы еще усовершенствовал метод получения тех самых квадратов. Что если число будет еще больше, генерить список из десятков тысяч элементов? 3162 можно получить взяв (int) корень из 10млн.

alicesmagic · 10.10.2019, 00:42

Сообщение от ViktorFX

3162 можно получить взяв (int) корень из 10млн.

ViktorFX, точно ведь!!! Тогда же все упрощается до безобразия!!! Ну вот как такая светлая мысль не пришла мне в голову?

Java
1
2
3
4
5
6
7
8
9
static List<Integer> getListSquares(int n) {
    List<Integer> res = new ArrayList<>();
    while (n > 0) {
        int squareRoot = (int) Math.sqrt(n);
        res.add(squareRoot * squareRoot);
        n -= squareRoot * squareRoot;
    }
    return res;
}

Добавлено через 1 минуту
alexfandr, рада, что смогла помочь)) Но вот видите, как оказалось решается это намного проще

@Aviz__ · 10.10.2019, 12:46

alexfandr, идея у тебя была такая?

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Helper {
 
    public static void main(String[] args) {
        long num = 133;
        System.out.print(num + " = ");
        printSumOfSquare(num);
    }
 
    static void printSumOfSquare(long n) {
        if (n == 0) {
            System.out.print('0');
            return;
        }
        int tmp = (int)Math.sqrt(n);
        System.out.print(tmp + "*" + tmp + " + ");
        printSumOfSquare(n - tmp * tmp);
    }
}

резулт:
133 = 11*11 + 3*3 + 1*1 + 1*1 + 1*1 + 0

alicesmagic · 10.10.2019, 13:06

Aviz__, ну, как вариант)) Только не люблю я рекурсию, хоть вот убей)

@Aviz__ · 10.10.2019, 13:15

Сообщение от alicesmagic

не люблю

правильно делаешь)) в java она плохо сделана. но, как видишь, код выглядит проще))

alicesmagic · 10.10.2019, 13:21

Сообщение от Aviz__

правильно делаешь)) в java она плохо сделана. но, как видишь, код выглядит проще))

Компактнее, да... но вряд ли проще. Что может быть проще старого доброго Вайла?

@Goongala · 10.10.2019, 13:33

Сообщение от Aviz__

в java она плохо сделана

што с ней не так в жаве?

@Aviz__ · 10.10.2019, 14:00

Сообщение от Gungala

што с ней не так в жаве?

стек растет, нельзя, как в с сделать хвастатую((

https://habr.com/ru/post/319282/

@alexfandr · 10.10.2019, 15:32 **[ТС]**

Aviz__, тоже спасибо) код выглядит компактнее

@alexfandr · 11.10.2019, 11:43 **[ТС]**

alicesmagic, можете проверить пожалуйста, какой вывод выдает ваша программа при вводе 32. Просто вариант который предложил Aviz__, с рекурсией выдает не самое минимальное количество квадратов (их должно быть всего 2 [16 + 16] )
Я думаю надо перебирать все возможные разложения числа и выдавать минимальный

@Aviz__ · 11.10.2019, 16:15

alexfandr, вот, доделай

Java
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
public class Helper {
    public static void main(String[] args) {
        System.out.println(getMinCountSquares(103));
        System.out.println(getMinCountSquares(104));
        System.out.println(getMinCountSquares(32));
        System.out.println(getMinCountSquares(33));
    }
 
    private static List<Integer> getListOfSquare(int n) {
        List<Integer> integerList = new ArrayList<>();
        for (int i = 2; i < (int)Math.sqrt(n) + 1; i++) {
            integerList.add(i*i);
        }
        return integerList;
    }
 
    private static String getMinCountSquares(int n) {
        if (isTrueSquare(n))
            return n + " = " + (int)Math.sqrt(n) + "^2";
        List<Integer> squaresList = getListOfSquare(n);
        int min = n;
        int tmpMin;
        int indexMinSqu = 0;
        int firstMin = n % squaresList.get(squaresList.size() - 1);
        for (int i = squaresList.size() - 1; i >= 0; i--) {
            tmpMin = n % squaresList.get(i);
            if (isTrueSquare(tmpMin) && firstMin >= n/squaresList.get(i)) {
                indexMinSqu = i;
                //min = 0;
                break;
            }
            if (min > tmpMin) {
                min = tmpMin;
                indexMinSqu = i;
            }
        }
        tmpMin = n/squaresList.get(indexMinSqu);
        return n + " = " + + tmpMin + " * " +
                (int)Math.sqrt(squaresList.get(indexMinSqu)) + "^2 + " +
                (n - tmpMin * squaresList.get(indexMinSqu)) + " единиц";
    }
 
    private static boolean isTrueSquare(int n) {
        int sqrt = (int)Math.sqrt(n);
        return sqrt*sqrt == n;
    }
}

резулт:

Кликните здесь для просмотра всего текста

103 = 1 * 10^2 + 3 единиц
104 = 1 * 10^2 + 4 единиц // тут косит((
32 = 2 * 4^2 + 0 единиц
33 = 2 * 4^2 + 1 единиц

alicesmagic · 12.10.2019, 04:51

alexfandr, да, действительно, у меня тоже этот косяк. Программа выдает верную, но не самую оптимальную раскладку на квадраты. Спасибо, что заметили и сказали. Попробую решить по другому. Хотя Авиз уже решил, но мне тоже хочется поломать голову)

Добавлено через 3 часа 57 минут
Блин. Задачка оказалась куда сложнее, чем казалась на первый взгляд

В процессе проб и ошибок пока только одни ошибки)
Aviz__, решила посмотреть как ты решил проблему, но тоже увидела косяки. Попробуй разложить у себя 95, например

Добавлено через 1 час 13 минут
Не зря ломала голову))) Все-таки получилось!

Кликните здесь для просмотра всего текста

Java
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
import java.util.*;
 
public class getMinSquares {
    private static ArrayList<Integer> getMinSquares(int n) {
        ArrayList<Integer> res = new ArrayList<>();
        int[] squares = new int[(int) Math.sqrt(n) + 1];
        for (int i = 0; i < squares.length; i++) {
            squares[i] = i * i;
        }
        for (int i = 0; i < squares.length; i++) {
            for (int j = i; j < squares.length; j++) {
                for (int k = j; k < squares.length; k++) {
                    for (int l = k; l < squares.length; l++) {
                        if (squares[i] + squares[j] + squares[k] + squares[l] == n) {
                            if (squares[i] != 0) res.add(squares[i]);
                            if (squares[j] != 0) res.add(squares[j]);
                            if (squares[k] != 0) res.add(squares[k]);
                            if (squares[l] != 0) res.add(squares[l]);
                            return res;
                        }
                    }
                }
            }
        }
        return res;
    }
 
    public static void main(String args[]) {
        for (int i = 90; i <= 100; i++) {
            System.out.println(i + " - " + getMinSquares(i));
        }
    }
}

Code
1
2
3
4
5
6
7
8
9
10
11
90 - [9, 81]
91 - [1, 9, 81]
92 - [1, 1, 9, 81]
93 - [4, 25, 64]
94 - [4, 9, 81]
95 - [1, 4, 9, 81]
96 - [16, 16, 64]
97 - [16, 81]
98 - [49, 49]
99 - [1, 49, 49]
100 - [100]

@Hamster83 · 12.10.2019, 12:10

alexfandr, минуточку

Добавлено через 5 минут

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
private static void printNumberSquares(int num) {
        int halfNum = num / 2;
        int square0 = 0;
        int square1 = 0;
 
        for (int i = 1; i <= halfNum; i++) {
            square0 = (int) Math.sqrt(i);
            square1 = (int) Math.sqrt(num - square0 * square0);
            if (num == square0 * square0 + square1 * square1) {
                break;
            }
        }
 
        if (num == square0 * square0 + square1 * square1) {
            System.out.format("%d = %d * %d + %d * %d", num, square0, square0, square1, square1);
        } else {
            square0 = (int) Math.sqrt(num);
            String remainder = num - square0 * square0 != 0 ? "+ " + (num - square0 * square0) : "";
            System.out.format("%d = %d * %d %s", num, square0, square0, remainder);
        }
    }

Добавлено через 7 минут
или еще короче

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
private static void printNumberSquares(int num) {
        int halfNum = num / 2;
        int square0, square1;
 
        for (int i = 1; i <= halfNum; i++) {
            square0 = (int) Math.sqrt(i);
            square1 = (int) Math.sqrt(num - square0 * square0);
            if (num == square0 * square0 + square1 * square1) {
                System.out.format("%d = %d * %d + %d * %d", num, square0, square0, square1, square1);
                return;
            }
        }
        square0 = (int) Math.sqrt(num);
        String remainder = num - square0 * square0 != 0 ? "+ " + (num - square0 * square0) : "";
        System.out.format("%d = %d * %d %s", num, square0, square0, remainder);
    }

alicesmagic · 12.10.2019, 13:10

Hamster83, надо бы доработать код)) Не до конца раскладываются числа:
printNumberSquares(31) -> 31 = 5 * 5 + 6
А сотня так и вообще разложилась так: 100 = 6 * 6 + 8 * 8.
Хотя по условию нужно минимум квадратов: 100 = 10 * 10

@Hamster83 · 12.10.2019, 13:27

alicesmagic,

Я в условии задачи не видел что надо найти максимальное количество квадратов натуральных чисел ))

надо бы доработать код)) Не до конца раскладываются числа:
printNumberSquares(31) -> 31 = 5 * 5 + 6

а что по твоему в должно быть результатом?

Как по мне, если число нельзя представить суммой квадратов двух натуральных чисел - надо бросать исключение.
Ведь в итоге можно дораскладываться до того, что число будет представлено как-то так: 1*1 + 1*1 + 1*1 ...

А сотня так и вообще разложилась так: 100 = 6 * 6 + 8 * 8.
Хотя по условию нужно минимум квадратов: 100 = 10 * 10

Не совсем так, требуется найти сумму квадратов.

alicesmagic · 12.10.2019, 15:04

Сообщение от alexfandr

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

Так сказано в условии. Поэтому для сотни минимальное количество квадратов равно одному. 100 = 10 * 10

Сообщение от Hamster83

а что по твоему в должно быть результатом?

31 = 5 * 5 + 6 : Какое же здесь представление через сумму квадратов? 6 тоже нужно раскладывать. В вашем формате представления должно быть так: 31 = 5 * 5 + 2 * 2 + 1 * 1 + 1 * 1

Сообщение от Hamster83

Как по мне, если число нельзя представить суммой квадратов двух натуральных чисел - надо бросать исключение. Ведь в итоге можно дораскладываться до того, что число будет представлено как-то так: 1*1 + 1*1 + 1*1 ...

В условии не говорится про сумму квадратов только двух натуральных чисел. Нужно разложить на минимально возможное для данного конкретного числа количество квадратов. Не нужно раскладывать по единицам. Любое натуральное число можно разложить на четыре квадрата. Теорема Лагранжа.

Новые блоги и статьи Все статьи Все блоги /
Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL3_image 8Observer8 27.01.2026 Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .	влияние грибов на сукцессию anaschu 26.01.2026 Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .	Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .
Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .	Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .	Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly 8Observer8 24.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	моя боль iceja 24.01.2026 Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .

Представить число N в виде суммы натуральных чисел, являющихся полными квадратами

Решение

Решение

@alexfandr 168 / 8 / 1 Регистрация: 15.11.2018 Сообщений: 256
	09.10.2019, 15:02 [ТС]
	alicesmagic, классно, спасибо) Мы еще интерфейсы и коллекции по java не проходили, но вроде я разобрался. Чем то похоже на списки и контейнеры из с++ 1

@ViktorFX 528 / 263 / 70 Регистрация: 11.12.2016 Сообщений: 1,223
	09.10.2019, 19:27
	alicesmagic, Мне понравилась идея начинать с больших и постепенно "спускаться" к разнице. Я бы еще усовершенствовал метод получения тех самых квадратов. Что если число будет еще больше, генерить список из десятков тысяч элементов? 3162 можно получить взяв (int) корень из 10млн. 1

alicesmagic 233 / 130 / 27 Регистрация: 24.08.2016 Сообщений: 875
	10.10.2019, 13:06
	Aviz__, ну, как вариант)) Только не люблю я рекурсию, хоть вот убей) 0

@alexfandr 168 / 8 / 1 Регистрация: 15.11.2018 Сообщений: 256
	10.10.2019, 15:32 [ТС]
	Aviz__, тоже спасибо) код выглядит компактнее 0

@alexfandr 168 / 8 / 1 Регистрация: 15.11.2018 Сообщений: 256
	11.10.2019, 11:43 [ТС]
	alicesmagic, можете проверить пожалуйста, какой вывод выдает ваша программа при вводе 32. Просто вариант который предложил Aviz__, с рекурсией выдает не самое минимальное количество квадратов (их должно быть всего 2 [16 + 16] ) Я думаю надо перебирать все возможные разложения числа и выдавать минимальный 1

alicesmagic 233 / 130 / 27 Регистрация: 24.08.2016 Сообщений: 875
	12.10.2019, 13:10
	Hamster83, надо бы доработать код)) Не до конца раскладываются числа: `printNumberSquares(31)` -> `31 = 5 * 5 + 6` А сотня так и вообще разложилась так: `100 = 6 * 6 + 8 * 8`. Хотя по условию нужно минимум квадратов: `100 = 10 * 10` 0