|
投稿者：永野護
投稿日：2011年 7月28日(木)13時25分18秒
|
|
|
|
a^5+b^5+c^5+d^5=e^5という方程式の正の整数解を求めるために
for a=1 to 150
for b=1 to 150
for c=1 to 150
for d=1 to 150
for e=1 to 150
if a^5+b^5+c^5+d^5=e^5 then print a;b;c;d;e
next
next
next
next
next
end
---------------------------------------------------
というプログラムを作って実行すると時間がかかりすぎます。
ちなみにc++言語ではできました。
この問題を解くためになにか計算上の工夫、あるいはプログラム上の工夫
とかありますでしょうか。良い手がありましたら、教えてください。
|
|
|
|
投稿者：山中和義
投稿日：2011年 7月28日(木)19時29分48秒
|
|
|
|
> No.1602[元記事へ]
永野護さんへのお返事です。
> a^5+b^5+c^5+d^5=e^5という方程式の正の整数解を求めるために
●数値計算
4*150^4=303750000000より、倍精度範囲で整数を正確に処理できます。2進モードで実行可能です。
したがって、10進モードより3倍程度速くなります。
次に、FOR-NEXT文内で毎回計算するのではなく、そのFOR-NEXT文で影響するもののみにします。
たとえば、FOR b=1 TO 50内で、aすなわちa^5は変化しません。
●数学
a,b,c,dの組は、a^5+b^5+c^5+d^5の式が対称式なので、a≦b≦c≦dとしても題意を満たします。
FOR a=1 TO 150 !1≦a≦b≦c≦d≦150
LET wa=a^5
FOR b=a TO 150
LET wb=wa+b^5
FOR c=b TO 150
LET wc=wb+c^5
FOR d=c TO 150
LET t=wc+d^5
LET e=d !t^5を求める
DO WHILE e^5<t
LET e=e+1
LOOP
IF e^5=t THEN PRINT a;b;c;d;e !条件を満たす
NEXT d
NEXT c
NEXT b
NEXT a
END
|
|
|
|
投稿者：永野護
投稿日：2011年 7月29日(金)13時45分43秒
|
|
|
|
山中様へ。早速の回答ありがとうございました。
プログラムを作っていただいたことに感謝します。
暑い日が続きます。ご健康をお祈りいたします。
敬具。
|
|
|
|
投稿者：山中和義
投稿日：2011年 7月29日(金)22時55分4秒
|
|
|
|
> 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
|
|
|
|
投稿者：永野護
投稿日：2011年 7月30日(土)10時53分59秒
|
|
|
|
山中様、再三にわたる回答ありがとうございました。
参考にさせていただきます。
いつもプログラムを作っていただいていることに深く
感謝します。
敬具
|
|
|
|
投稿者：藤村明憲
投稿日：2011年 7月30日(土)10時58分38秒
|
|
|
|
> No.1602[元記事へ]
永野護さんへのお返事です。
山中和義さんのプログラムを改良してみました。
eの値はa,b,c,dにより一意的に決定されるので、その整数性を判定するようにしました。
実行時間が1/4ぐらいになると思います。
OPTION ARITHMETIC NATIVE
LET t0=TIME
LET R=150 !検索範囲
LET p=CEIL(4^.2*R) !eの上限 R^5+R^5+R^5+R^5=e^5
DIM S(p) !p=198
FOR i=1 TO p
LET S(i)=i^5
NEXT i
FOR a=1 TO R !1≦a≦b≦c≦d≦150
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 t=wc+S(d)
LET e=ROUND(t^.2) !左辺の5乗根に近似する整数
IF S(e)=t THEN PRINT a;b;c;d;e !条件を満たす
NEXT d
NEXT c
NEXT b
NEXT a
PRINT "計算時間=";TIME-t0
END
【参考情報】
eの整数性を判定するのに、当初は最内側のFOR～NEXTを
FOR d=c TO R
LET t=wc+S(d)
LET e=t^.2 !tの5乗根
IF e=INT(e) THEN PRINT a;b;c;d;e !条件を満たす
NEXT d
としていました。
ところが2進モードでは、t=61917364224 (=144^5) のとき、
LET e=t^.2 で、eの値が 144.0000000000000284 となり、解は得られませんでした。
（10進モードでは問題なく実行できました。）
|
|
|
|
投稿者：山中和義
投稿日：2011年 7月30日(土)11時26分26秒
|
|
|
|
> No.1608[元記事へ]
藤村明憲さんへのお返事です。
> LET e=ROUND(t^.2) !左辺の5乗根に近似する整数
> IF S(e)=t THEN PRINT a;b;c;d;e !条件を満たす
特にこの問題では多桁の整数を扱う必要があるので、1000桁モードや有理数モードを考慮すると、
ｎ乗根を直接求めるのは無理があると思います。
|
|
|
|
投稿者：永野護
投稿日：2011年 7月31日(日)11時38分57秒
|
|
|
|
藤村様、回答ありがとうございました。
参考にさせていただきます。
敬具
|
|
|
戻る