Форум программистов, компьютерный форум, киберфорум
QBasic
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.56/9: Рейтинг темы: голосов - 9, средняя оценка - 4.56
Регистрация: 23.10.2013
Сообщений: 5,076
Записей в блоге: 8
1

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

19.02.2017, 09:52. Показов 1730. Ответов 14

Дано натуральное число. Определить, можно ли
представить это число в виде суммы двух квадратов.
Если можно, то сделать это. Если нет, то вынести на
экран слово NET.

QBasic/QuickBASIC
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
REM
REM  пример:  778 = 49 + 729 
REM
 
CLS
INPUT "N = "; n
 
FOR i = 1 TO 1000
FOR j = i TO 1000
   IF n = i * i + j * j THEN
      PRINT n; "="; i ^ 2; "+"; j ^ 2
      GOTO 1000
   END IF
NEXT j, i
 
PRINT "NET"
1000
END
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
19.02.2017, 09:52
Ответы с готовыми решениями:

Представление рационального числа x > 0 в виде суммы квадратов двух других
Вопрос в том, можно ли представить любое рациональное число (из Q) в виде суммы квадратов двух...

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

Найти все числа, которые можно представить в виде суммы квадратов двух
Дано натуральное число n. Среди чисел 1, 2, . , n найти все те, которые можно представить в виде...

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

14
Платежеспособный зверь
8753 / 4179 / 1606
Регистрация: 28.10.2009
Сообщений: 11,321
20.02.2017, 08:31 2
Лучший ответ Сообщение было отмечено echs как решение

Решение

Цитата Сообщение от echs Посмотреть сообщение
Определить, можно ли
представить это число в виде суммы двух квадратов.
Лучше реши такую задачу: представить введённое число в виде суммы квадратов (число слагаемых должно быть минимально).
Пример:

100=52+52+52+52или
100=62+82
но ответ 102 (одно слагаемое)
Решение есть всегда, так как, например 3=12+12+12
1
Регистрация: 23.10.2013
Сообщений: 5,076
Записей в блоге: 8
20.02.2017, 10:18  [ТС] 3
кот Бегемот
Спасибо!
Я могу уже сейчас предположить, как выглядит алгоритм.
1. Проверяется, не является ли заданное число точным квадратом.
Если да, то это уже ответ.
2. Проверяется, не является ли заданное число суммой двух
квадратов. Если да, то это уже ответ
3. аналогично (сумма трех квадратов)
4. то же самое о четырех квадратов...
...
Не берусь судить насколько оптимален этот алгоритм, но
он будет работать - это точно
Для ускорения работы, можно задать массив и заполнить
его квадратами натуральных чисел
Еще раз спасибо за предложенную задачу.

Добавлено через 2 минуты
Еще большую скорость программы можно сделать,
если просчитать все заранее и заполнить файл...
Тогда программе останется только найти и выдать
на экран результат.
0
Платежеспособный зверь
8753 / 4179 / 1606
Регистрация: 28.10.2009
Сообщений: 11,321
20.02.2017, 11:38 4
Лучший ответ Сообщение было отмечено echs как решение

Решение

Цитата Сообщение от echs Посмотреть сообщение
Проверяется, не является ли заданное число суммой двух
квадратов. Если да, то это уже ответ
Сначала да, проверяется, не будет ли число квадратом. А вот дальше хуже... Надо Вам почитать литературку по динамическому программированию...
1
4826 / 1501 / 393
Регистрация: 25.04.2010
Сообщений: 4,242
Записей в блоге: 1
20.02.2017, 19:09 5
Лучший ответ Сообщение было отмечено echs как решение

Решение

echs, там будет два аспекта:
1) Нахождение неповторяющихся комбинаций(для исключения зеркалок и комбинаций
длиннее уже посчитанной, ибо нет смысла считать, если заранее знаем, что будет длиннее)
2) Рекурсивность (функция которая будет находить подкомбинации, т.к. чем дальше
идём, тем меньше комбинаций из набора возможных остаётся)
При этом нужно будет хранить минимальную комбинацию где-то в глобалке и каждый раз
актуализировать.

А квадраты чисел в массив - это обязательно.

Цитата Сообщение от echs Посмотреть сообщение
Еще большую скорость программы можно сделать,
если просчитать все заранее и заполнить файл...
Проснись Карл! Ограничение не оговорено. Задача на вычисление, а не на кеширование.)))
1
Регистрация: 23.10.2013
Сообщений: 5,076
Записей в блоге: 8
20.02.2017, 20:16  [ТС] 6
Quiet Snow
Спасибо! Вы всегда сумеете подсказать что-то
интересное и полезное. В данном случае я о рекурсии
даже не подумал, считая, что тут она не пройдет...
Ну раз так, то еще раз Большое Вам Спасибо!!
0
Платежеспособный зверь
8753 / 4179 / 1606
Регистрация: 28.10.2009
Сообщений: 11,321
22.02.2017, 19:26 7
Я так понял, задача нерешаема.
Упростим задание.
Не станем искать числа, которые, будучи возведёнными в квадрат, в сумме дадут исходное число.
Сформулируем задачу проще:
Найти минимальное число слагаемых, квадраты которых в сумме дадут введённое число.
Пример:
4 - ответ - 1 (2*2=4)
5 - ответ - 2 (понятно, что это 2*2+1*1)
Сами слагаемые искать не надо. В ответе только минимальное их количество.
1
4826 / 1501 / 393
Регистрация: 25.04.2010
Сообщений: 4,242
Записей в блоге: 1
23.02.2017, 07:17 8
Цитата Сообщение от кот Бегемот Посмотреть сообщение
Я так понял, задача нерешаема.
Решаема, любой каприз за ваши деньги.
0
6141 / 908 / 305
Регистрация: 25.02.2011
Сообщений: 1,292
Записей в блоге: 1
23.02.2017, 10:53 9
Цитата Сообщение от кот Бегемот Посмотреть сообщение
представить введённое число в виде суммы квадратов (число слагаемых должно быть минимально)
Решение на VBA (переделать на QBasic не составит труда, но может быть проблема с объявлением больших массивов)
Выдает, как минимальное количество слагаемых, так и сами слагаемые:
Visual Basic
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Sub www()
Dim n As Long, i As Long, j As Long, k As Long
n = 999
ReDim a(1 To n) As Long, t(1 To n) As String
 
For i = 1 To n
    If Int(Sqr(i)) = Sqr(i) Then
        a(i) = 1
        t(i) = Str$(Int(Sqr(i))) + "^2"
    Else
        a(i) = i + 1
        For j = Int(Sqr(i)) To 1 Step -1
            k = i - j * j
            If a(k) + 1 < a(i) Then
                a(i) = a(k) + 1
                t(i) = t(k) + " +" + Str$(j) + "^2"
            End If
        Next j
    End If
Next i
Debug.Print a(n), t(n) + " =" + Str$(n)
End Sub
Добавлено через 40 минут
Вариант 2
Должно работать немного быстрее, т.к. не формируем текстовый массив с оптимальными решениями, а восстанавливаем решение после динамического программирования:
Visual Basic
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Sub www2()
Dim n As Long, i As Long, j As Long, t As String
n = 9999
ReDim a(n) As Long, b(n) As Long
For i = 1 To n
    a(i) = i + 1
    For j = Int(Sqr(i)) To 1 Step -1
        If a(i - j * j) + 1 < a(i) Then
            a(i) = a(i - j * j) + 1
            b(i) = j
        End If
Next j, i
i = n
While a(i)
    t = t + " +" + Str$(b(i)) + "^2"
    i = i - b(i) * b(i)
Wend
Debug.Print a(n), Mid$(t, 3) + " =" + Str$(n)
End Sub
Добавлено через 57 минут
пример найденного решения:
3510^2 + 147^2 + 63^2 = 12345678

Добавлено через 13 минут
Цитата Сообщение от echs Посмотреть сообщение
Дано натуральное число. Определить, можно ли
представить это число в виде суммы двух квадратов.
echs, Ваш код из первого сообщения ужасен, нет никакой оптимизации вычислений, Вы делаете 1 млн проверок, когда для числа 778 достаточно сделать всего 8 проверок.
QBasic/QuickBASIC
1
2
3
4
5
6
7
8
9
10
DIM n AS LONG, i AS LONG, j AS LONG, t AS STRING
n = 778
FOR i = INT(SQR(n)) TO -INT(-SQR(n / 2)) STEP -1
    j = n - i * i
    IF SQR(j) = INT(SQR(j)) THEN
        t = STR$(SQR(j)) + "^2 +" + STR$(i) + "^2 =" + STR$(n)
        EXIT FOR
    END IF
NEXT i
IF t = "" THEN PRINT "NET" ELSE PRINT t
0
Платежеспособный зверь
8753 / 4179 / 1606
Регистрация: 28.10.2009
Сообщений: 11,321
23.02.2017, 11:11 10
m-ch, у меня нет VBA и переделывать вашу программу на QBasic тоже нет желания, потому что что-то мне подсказывает, что она неверна. Запустите, пожалуйста её для n=23
Если она выдаст 4*4+2*2+1+1+1, значит мои подозрения верны, потому что оптимальное разбиение 3*3+3*3+2*2+1
0
6141 / 908 / 305
Регистрация: 25.02.2011
Сообщений: 1,292
Записей в блоге: 1
23.02.2017, 11:51 11
Цитата Сообщение от кот Бегемот Посмотреть сообщение
Запустите, пожалуйста её для n=23
3^2 + 3^2 + 2^2 + 1^2 = 23
Цитата Сообщение от кот Бегемот Посмотреть сообщение
и переделывать вашу программу на QBasic тоже нет желания
сделаю это за Вас (найдите отличия и проверьте работоспособность в QBasic, т.к. у меня нет QBasic)
QBasic/QuickBASIC
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
DIM n AS LONG, i AS LONG, j AS LONG, t AS STRING
n = 9999
DIM a(n) AS LONG, b(n) AS LONG
FOR i = 1 TO n
    a(i) = i + 1
    FOR j = INT(SQR(i)) TO 1 STEP -1
        IF a(i - j * j) + 1 < a(i) THEN
            a(i) = a(i - j * j) + 1
            b(i) = j
        END IF
NEXT j, i
i = n
WHILE a(i)
    t = t + " +" + STR$(b(i)) + "^2"
    i = i - b(i) * b(i)
WEND
PRINT a(n), MID$(t, 3) + " =" + STR$(n)
0
Платежеспособный зверь
8753 / 4179 / 1606
Регистрация: 28.10.2009
Сообщений: 11,321
23.02.2017, 12:05 12
Спасибо, m-ch. Лет 20 назад я сделал практически такую же программу на QBasic, тоже основываясь на динамическом программировании, но моя прога почему-то работала гораздо медленнее. Что и не нравилось.
Идея была та же самая, только исполнение с другого конца: в цикле перебирались все i до n, во вложенном перебирались все квадраты, которые можно отнять, начиная с 1 до int(sqr(i)), затем так же отнимал j-i*i и увеличивал k на 1, а затем сравнивал с минимумом и.т.д.
Кстати, начальный массив значений я брал равным i, а не i+1 так как больше, чем i слагаемых быть не может и если изначально извлекался корень, программа сразу заканчивалась.
Ваше решение более аккуратное. Строковый вывод результатов понравился.
0
6141 / 908 / 305
Регистрация: 25.02.2011
Сообщений: 1,292
Записей в блоге: 1
23.02.2017, 12:13 13
Цитата Сообщение от кот Бегемот Посмотреть сообщение
Кстати, начальный массив значений я брал равным i, а не i+1 так как больше, чем i слагаемых быть не может
Я специально указал i+1, а не i, т.к. это заведомо большее значение, чем может быть число слагаемых, тем самым гарантировано хоть раз будет выполнено условие a(i - j * j) + 1 < a(i)
и соответственно правильно будет сформирована конечная текстовая строка.

Проверил для всех чисел от 1 до 9999999
Любое из этих чисел можно получить не более чем из 4х слагаемых
На FreeBasic расчет производился менее 3х минут.
0
Платежеспособный зверь
8753 / 4179 / 1606
Регистрация: 28.10.2009
Сообщений: 11,321
23.02.2017, 12:27 14
Цитата Сообщение от m-ch Посмотреть сообщение
Любое из этих чисел можно получить не более чем из 4х слагаемых
Это теорема Лагранжа.
0
6141 / 908 / 305
Регистрация: 25.02.2011
Сообщений: 1,292
Записей в блоге: 1
23.02.2017, 16:45 15
Цитата Сообщение от кот Бегемот Посмотреть сообщение
Это теорема Лагранжа.
Не помню такую, на оказывается что есть.
Поиск 4х слагаемых производится достаточно быстро для больших чисел:
QBasic/QuickBASIC
1
2
3
4
5
6
7
8
9
10
11
12
13
14
DIM n AS DOUBLE, n1 AS DOUBLE, n2 AS DOUBLE, n3 AS DOUBLE, i1 AS LONG, i2 AS LONG, i3 AS LONG, i4 AS LONG
n = 199999999999999#
DO
    FOR i1 = INT(SQR(n)) TO -INT(-SQR(n / 4)) STEP -1
        n1 = n - CDBL(i1) * i1
        FOR i2 = INT(SQR(n1)) TO -INT(-SQR(n1 / 3)) STEP -1
            n2 = n1 - CDBL(i2) * i2
            FOR i3 = INT(SQR(n2)) TO -INT(-SQR(n2 / 2)) STEP -1
                n3 = n2 - CDBL(i3) * i3
                i4 = INT(SQR(n3))
                IF n3 = CDBL(i4) * i4 THEN EXIT DO
    NEXT i3, i2, i1
LOOP WHILE 0
PRINT STR$(i1) + "^2 +" + STR$(i2) + "^2 +" + STR$(i3) + "^2 +" + STR$(i4) + "^2 =" + STR$(n)
результат:
14142135^2 + 4197^2 + 154^2 + 57^2 = 199999999999999
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
23.02.2017, 16:45

Найти все числа, которые можно представить в виде суммы квадратов двух натуральных чисел.
Дано натуральное число n. Среди чисел 1,2, …, n найти все те, которые можно представить в виде...

Числа,не превосходящие N, и представимые в виде суммы квадратов двух каких-нибудь различных натуральных чисел
1. Найти все натуральные числа, не превосходящие заданного числа N, и пред-ставимые в виде суммы...

Найти все те числа, которые можно представить в виде суммы квадратов двух натуральных чисел
Ребята, помогите решить задачу на Free Pascal, пожалуйста! Дано натуральное число n. Среди чисел...

Множества: напечатать все целые числа из заданного диапазона, представимые в виде суммы двух квадратов
В возрастающем порядке напечатать все целые числа из диапазона 1..10 000, представимые в виде...


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

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

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