Задачи,советы и ответы - часть 45
Совет 1 (общий)
Скорее всего, для решения этой задачи придется пойти на полный перебор. Оценку сверху на количество циклов, которое может потребоваться, легко получить, упорядочив слагаемые по величине: a<b<c<d< sqrt(N).
Совет 2 (общий)
Решение может быть найдено и меньше чем за N2 циклов, если проанализировать четность N и в цикле шагать не через 1, а через 2. Так, например, если N нечетно, то среди искомых слагаемых имеется либо одно, либо три нечетных числа. Если N четно, то искомое разложение может состоять либо из четырех четных, либо из четырех нечетных, либо из двух четных и двух нечетных слагаемых. Цикл перебора можно оформить в виде подпрограммы, которой передаются начальные значения управляющих переменных. Подпрограмма PROBA получает 5 параметров, первые 4 из которых задают четность (параметр = 1) или нечетность (параметр = 0) подбираемых слагаемых а, Ь, с и d.
Программа 2_26.bas
RЕМ Разложение числа на сумму квадратов
DECLARE SUB PROBA (Al AS INTEGER, Bl AS INTEGER,Cl AS INTEGER, Dl AS INTEGER,N AS LONG)
INPUT "Введите натуральное число - ", N& IF (N& MOD 2)=0 THEN
REM Если число N - четное
PROBA 0,0,1,1,N&
PROBA 0, 0,0,0,N&
PROBA 1,1,1,1,N& ELBE
REM Если число N - нечетное
PROBA 0,0,0,1,N&
PROBA 0,1,1,1,N& END IF END
SUB PROBA (Al AS INTEGER,Bl AS INTEGER,Cl AS INTEGER,Dl AS INTEGER,N AS LONG)
'Подпрограмма перебора вариантов
Q=INT(SQR{N)+.5) : ' Определение верхней границы
FOR A%=A1 TO Q STEP 2: S1=A%*A%
FOR B%=B1 TO Q STEP 2: S2=S1+B%*B%
FOR C%=C1 TO Q STEP 2: S3=S2+C%*C%
FOR D%=D1 TO Q STEP 2
IF S3+D%*D%=N THEN
PRINT "Искомые слагаемые :"
PRINT "a=";A%,"b=";B%,"c=";C%,"d=";D% END
END IF
NEXT D%: NEXT C%: NEXT B%: NEXT A% END SUB
Программа 2_26.с
/* Разложение числа на сумму квадратов */
#include <math.h>
#include <stdlib.h>
#include <conio.h>
void proba(int al,int bl,int cl,int dl,long N) ;