|
投稿者：GAI
投稿日：2013年 8月17日(土)15時19分59秒
|
|
|
|
プログラムを分析していたら、例えばC=24で
24=24*1
=12*2
=8*3
=6*4
=6*2*2
=4*3*2
=3*2*2*2
というように、24をいろいろな積で表すすべての可能性に分解してそれから構成される数N
（上からN=8388608,6144,1152,864,480,360,420)
を調べ、この中の最小で360を決めているように読めました。
そこで今度はN=96なら、これを幾つかの積で表す場合
手動で行ってみるとかなり面倒なことになり
96=96*1
=48*2
=32*3
=24*4
=16*6
=12*8
=24*2*2
=16*3*2
=12*4*2
=8*6*2
=8*4*3
=6*4*4
=12*2*2*2
=8*3*2*2
=6*4*2*2
=4*4*3*2
=6*2*2*2*2
=4*3*2*2*2
=3*2*2*2*2*2
と全部で１９タイプであらわすことができました。
たぶんこの分解方法の総数はA034836で与えられるのであろうが、例96のように具体的にどう分解されるかをみるときには、どのようなプログラムになるのでしょうか？
例の約数の個数で使われた副プログラムのアイデアが上手く使えそうなのですが、未だ作りかえる技術を持ちません。
重ね重ねよろしくお願いします。
|
|
|
|
投稿者：山中和義
投稿日：2013年 8月17日(土)20時15分7秒
|
|
|
|
> No.3112[元記事へ]
GAIさんへのお返事です。
> そこで今度はN=96なら、これを幾つかの積で表す場合
> 手動で行ってみるとかなり面倒なことになり
> 96=96*1
> =48*2
> =32*3
> =24*4
> =16*6
> =12*8
> =24*2*2
> =16*3*2
> =12*4*2
> =8*6*2
> =8*4*3
> =6*4*4
> =12*2*2*2
> =8*3*2*2
> =6*4*2*2
> =4*4*3*2
> =6*2*2*2*2
> =4*3*2*2*2
> =3*2*2*2*2*2
>
> と全部で１９タイプであらわすことができました。
前回と同様に外部ルーチンで、NをN/DとDに分解します。
再帰呼び出しで、DをNとして分解を続けます。
OPTION ARITHMETIC RATIONAL !多桁の整数
DIM F(20) !約数の積
PRINT " 1" !1のとき
PRINT "1: 1 個"
FOR N=2 TO 100 !2以上の自然数
LET C=0
CALL try(1,F,N, C)
PRINT STR$(N);":"; C;"個"
NEXT N
END
EXTERNAL SUB try(i,F(),N, C) !約数の積に分解する 例 12の場合、12=6*2=4*3=3*2*2
OPTION ARITHMETIC RATIONAL !多桁の整数
FOR D=1 TO INT(N/2) !約数の候補
IF MOD(N,D)=0 THEN !大きい順に F/1,F/2,F/3,…,3,2
LET F(i)=N/D
IF i=1 OR (i>1 AND F(i-1)>=F(i)) THEN
IF D=1 THEN !分解が完了なら
LET C=C+1
PRINT F(1); !結果を表示する
FOR K=2 TO i
PRINT "*";F(K);
NEXT K
PRINT
ELSE
CALL try(i+1,F,D, C) !次へ
END IF
END IF
END IF
NEXT D
END SUB
実行結果
1
1: 1個
2
2: 1 個
3
3: 1 個
4
2 * 2
4: 2 個
5
5: 1 個
6
3 * 2
6: 2 個
7
7: 1 個
8
4 * 2
2 * 2 * 2
8: 3 個
9
3 * 3
9: 2 個
10
5 * 2
10: 2 個
11
11: 1 個
12
6 * 2
4 * 3
3 * 2 * 2
12: 4 個
13
13: 1 個
14
7 * 2
14: 2 個
15
5 * 3
15: 2 個
16
8 * 2
4 * 4
4 * 2 * 2
2 * 2 * 2 * 2
16: 5 個
17
17: 1 個
18
9 * 2
6 * 3
3 * 3 * 2
18: 4 個
19
19: 1 個
20
10 * 2
5 * 4
5 * 2 * 2
20: 4 個
21
7 * 3
21: 2 個
22
11 * 2
22: 2 個
23
23: 1 個
24
12 * 2
8 * 3
6 * 4
6 * 2 * 2
4 * 3 * 2
3 * 2 * 2 * 2
24: 7 個
25
5 * 5
25: 2 個
26
13 * 2
26: 2 個
27
9 * 3
3 * 3 * 3
27: 3 個
28
14 * 2
7 * 4
7 * 2 * 2
28: 4 個
29
29: 1 個
30
15 * 2
10 * 3
6 * 5
5 * 3 * 2
30: 5 個
96 ← 96 * 1 * 1
48 * 2 ← 48 * 2 * 1
32 * 3 ← 32 * 3 * 1
24 * 4 ← 24 * 4 * 1
24 * 2 * 2
16 * 6 ← 16 * 6 * 1
16 * 3 * 2
12 * 8 ← 12 * 8 * 1
12 * 4 * 2
12 * 2 * 2 * 2 ← NG
8 * 6 * 2
8 * 4 * 3
8 * 3 * 2 * 2 ← NG
6 * 4 * 4
6 * 4 * 2 * 2 ← NG
6 * 2 * 2 * 2 * 2 ← NG
4 * 4 * 3 * 2 ← NG
4 * 3 * 2 * 2 * 2 ← NG
3 * 2 * 2 * 2 * 2 * 2 ← NG
96: 19 個
の7個は、NGとなります。
|
|
|
|
投稿者：GAI
投稿日：2013年 8月17日(土)20時52分7秒
|
|
|
|
> No.3113[元記事へ]
山中和義さんへのお返事です。
ありがとうございます。
A034836は
勘違いしておりました。
が示したいところでした。
|
|
|
|
投稿者：山中和義
投稿日：2013年 8月18日(日)10時21分6秒
|
|
|
|
> No.3113[元記事へ]
GAIさんへのお返事です。
効率を考えると、約数の検索範囲は、1から√nまでとするのがよいでしょう。
処理時間はO(n/2)がO(√n)になるので、大きなnについてはかなり期待できます。
ただし、分解式の出現する順番は、降順（1番目の数）になりません。
!問題
!自然数Nを正の約数の積に分解する
!例 48の場合
! 48
! 24 * 2
! 16 * 3
! 12 * 4
! 12 * 2 * 2
! 8 * 6
! 8 * 3 * 2
! 6 * 4 * 2
! 6 * 2 * 2 * 2
! 4 * 4 * 3
! 4 * 3 * 2 * 2
! 3 * 2 * 2 * 2 * 2
!計 12個
OPTION ARITHMETIC RATIONAL !多桁の整数
DIM F(20) !約数の積
FOR N=1 TO 100 !自然数
LET C=0
CALL try(1,F,N, C)
PRINT STR$(N);":"; C;"個"
NEXT N
END
EXTERNAL SUB try(i,F(),N, C) !約数の積に分解する 例 12の場合、12=6*2=4*3=3*2*2
OPTION ARITHMETIC RATIONAL !多桁の整数
FOR D=1 TO INTSQR(N) !約数の候補
IF MOD(N,D)=0 THEN
LET W=N/D
IF i=1 OR (i>1 AND F(i-1)>=W) THEN !並びは大きい順に ※1番目は無条件
LET F(i)=W
IF D=1 THEN !分解が完了なら
LET C=C+1
PRINT F(1); !結果を表示する
FOR K=2 TO i
PRINT "*";F(K);
NEXT K
PRINT
ELSE
CALL try(i+1,F,D, C) !次へ
END IF
END IF
IF D>1 AND D*D<>N THEN !平方数以外なら、もう一方も
IF i=1 OR (i>1 AND F(i-1)>=D) THEN
LET F(i)=D
CALL try(i+1,F,W, C) !次へ
END IF
END IF
END IF
NEXT D
END SUB
実行結果（一部）
96
48 * 2
32 * 3
3 * 2 * 2 * 2 * 2 * 2
24 * 4
24 * 2 * 2
4 * 3 * 2 * 2 * 2
4 * 4 * 3 * 2
16 * 6
16 * 3 * 2
6 * 2 * 2 * 2 * 2
6 * 4 * 4
6 * 4 * 2 * 2
12 * 8
12 * 4 * 2
12 * 2 * 2 * 2
8 * 6 * 2
8 * 4 * 3
8 * 3 * 2 * 2
96: 19 個
|
|
|
戻る