|
|
> No.1602[元記事へ]
永野護さんへのお返事です。
別解
!「コンピュータの基本アルゴリズムの課題」として
!S1=1^5、S2=2^5、S3=3^5、… 、Sn=n^5、すなわちデータ列{Sn}を考える。
!これはn^5が順に並んだものである。
!したがって、「a^5+b^5+c^5+d^5=e^5を満たす自然数a,b,c,d,eの組」は
! この1～n個のデータ列から、重複を許して4個選んだ数の和が、データ列{Sn}の中に同じ値を見つける「探索」の問題
!に置き換えることができる。
!逐次探索すると毎回の走査が必要で時間がかかる。
!S1,S,…,Snは整列された（小さい順）データ列だから、２分探索が可能である。
LET t0=TIME
LET R=150 !検索範囲
DIM S(R) !データ列
FOR i=1 TO R
LET S(i)=i^5
NEXT i
FOR a=1 TO R !1≦a≦b≦c≦d≦150 ※H(150,4)=C(150+4-1,4)通り
FOR b=a TO R
LET wb=S(a)+S(b)
FOR c=b TO R
LET wc=wb+S(c)
FOR d=c TO R
LET key=wc+S(d)
!２分探索
LET L=d !下限 ※d^5≦a^5+b^5+c^5+d^5=e^5
LET H=R !上限
DO WHILE L<=H !逆転したら終了
LET M=INT((L+H)/2) !中央
IF S(M)<=key THEN LET L=M+1 !絞り込む
IF S(M)>=key THEN LET H=M-1
LOOP
IF L=H+2 THEN !見つかったら
PRINT a;b;c;d;M !条件を満たす
END IF
NEXT d
NEXT c
NEXT b
NEXT a
PRINT "計算時間=";TIME-t0
END
|
|