教えて下さい

 投稿者: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

と全部で19タイプであらわすことができました。
たぶんこの分解方法の総数はA034836で与えられるのであろうが、例96のように具体的にどう分解されるかをみるときには、どのようなプログラムになるのでしょうか?
例の約数の個数で使われた副プログラムのアイデアが上手く使えそうなのですが、未だ作りかえる技術を持ちません。
重ね重ねよろしくお願いします。
 

Re: 教えて下さい

 投稿者:山中和義  投稿日: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
>
> と全部で19タイプであらわすことができました。

前回と同様に外部ルーチンで、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となります。
 

Re: 教えて下さい

 投稿者:GAI  投稿日:2013年 8月17日(土)20時52分7秒
  > No.3113[元記事へ]

山中和義さんへのお返事です。


ありがとうございます。

A034836は
勘違いしておりました。



が示したいところでした。
 

Re: 教えて下さい

 投稿者:山中和義  投稿日: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 個

 

戻る