Задачи,советы и ответы - часть 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) ;

Содержание Назад Вперед