Задачи,советы и ответы - часть 45
Совет 1 (общий)
a<b<c<d< sqrt(N). Совет 2 (общий) Программа 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) ;
Скорее всего, для решения этой задачи придется пойти на полный перебор. Оценку сверху на количество циклов, которое может потребоваться, легко получить, упорядочив слагаемые по величине:
Решение может быть найдено и меньше чем за N2 циклов, если проанализировать четность N и в цикле шагать не через 1, а через 2. Так, например, если N нечетно, то среди искомых слагаемых имеется либо одно, либо три нечетных числа. Если N четно, то искомое разложение может состоять либо из четырех четных, либо из четырех нечетных, либо из двух четных и двух нечетных слагаемых. Цикл перебора можно оформить в виде подпрограммы, которой передаются начальные значения управляющих переменных. Подпрограмма PROBA получает 5 параметров, первые 4 из которых задают четность (параметр = 1) или нечетность (параметр = 0) подбираемых слагаемых а, Ь, с и d.