各桁の和 - しばっち

2022/05/15 (Sun) 15:04:04

※投稿内容がたろささんのものとは異なるようなので新規に返事致します。

>30桁の自然数で各桁の和が25になるものはいくつあるでしょうか。
>　同様に120桁の自然数で各桁の和が60になるものはいくつあるでしょうか。
>この問題の解き方がわかりません。どなたか解き方を教えてください。


一番簡単なのは総当たり法で1から10^KETA-1までをループさせる方法です。
質問では30桁とありますが、30桁では組み合わせ数が10^30-1となるのでまず終わりません。
(量子コンピュータならいける ?)

ここでは8桁で各桁の和が6となるものを数えます。
なお、15桁以上では1000桁モードや有理数モードで実行する必要があります。

LET KETA=8
LET TOTAL=6
FOR I=1 TO 10^KETA-1
IF SUM(I)=TOTAL THEN
LET COUNT=COUNT+1
PRINT COUNT;":";I
END IF
NEXT I
END

EXTERNAL FUNCTION SUM(X)
DO
LET S=S+MOD(X,10)
LET X=INT(X/10)
LOOP UNTIL X=0
LET SUM=S
END FUNCTION

次は各桁ごとにループさせて多重ループをつくる方法です。

下記のプログラムは8重ループなので8桁固定ですが
構造が単純なので桁数の増減(改造)は簡単だと思います。(FORループを加えていくだけ!?)

そしてFOR文の間にあるIF文でTOTALを超えた時点でループを抜けていくところが
上の総当たり法と違うところです。これでかなり早くなります。2進モードで実行してください。

なお、各ループを0～9までとしていますが0～1や0～7、0～15とすれば2進法や8進法、16進法に対応します。


LET TOTAL=6
FOR N8=0 TO 9
IF N8>TOTAL THEN EXIT FOR
FOR N7=0 TO 9
IF N7+N8>TOTAL THEN EXIT FOR
FOR N6=0 TO 9
IF N6+N7+N8>TOTAL THEN EXIT FOR
FOR N5=0 TO 9
IF N5+N6+N7+N8>TOTAL THEN EXIT FOR
FOR N4=0 TO 9
IF N4+N5+N6+N7+N8>TOTAL THEN EXIT FOR
FOR N3=0 TO 9
IF N3+N4+N5+N6+N7+N8>TOTAL THEN EXIT FOR
FOR N2=0 TO 9
IF N2+N3+N4+N5+N6+N7+N8>TOTAL THEN EXIT FOR
FOR N1=0 TO 9
IF N1+N2+N3+N4+N5+N6+N7+N8>TOTAL THEN EXIT FOR
IF N1+N2+N3+N4+N5+N6+N7+N8=TOTAL THEN
LET COUNT=COUNT+1
PRINT COUNT;":";
PRINT USING"#":N8;
PRINT USING"#":N7;
PRINT USING"#":N6;
PRINT USING"#":N5;
PRINT USING"#":N4;
PRINT USING"#":N3;
PRINT USING"#":N2;
PRINT USING"#":N1
END IF
NEXT N1
NEXT N2
NEXT N3
NEXT N4
NEXT N5
NEXT N6
NEXT N7
NEXT N8
END


下記のプログラムは上のプログラムの多重ループを再帰呼び出しで行っていること
以外は上と基本同じです。

なお、2重のDO LOOPでも多重ループの代わりが行えますが制御がしにくいです。
2進モードで実行してください。


PUBLIC NUMERIC KETA,COUNT,A(30),TOTAL
LET KETA=8
LET TOTAL=6
CALL RECURSIVE(A,1)
END

EXTERNAL SUB RECURSIVE(A(),I)
IF I>KETA+1 THEN EXIT SUB
LET P=SUM(A)
IF P>TOTAL THEN EXIT SUB
IF P=TOTAL THEN
LET COUNT=COUNT+1
PRINT COUNT;":";
LET FL=0
FOR J=1 TO KETA
IF A(J)<>0 AND FL=0 THEN LET FL=1
IF FL=1 THEN PRINT USING "#":A(J);
NEXT J
PRINT
EXIT SUB
END IF
FOR J=0 TO 9
LET A(I)=J
CALL RECURSIVE(A,I+1)
LET A(I)=0
NEXT J
END SUB

EXTERNAL FUNCTION SUM(A())
LET S=0
FOR I=1 TO KETA
LET S=S+A(I)
NEXT I
LET SUM=S
END FUNCTION