そんなのある?

 投稿者:GAI  投稿日:2012年 2月28日(火)19時57分0秒
  10桁のランダムな数字を書いた時
そこに使用した各数字の頻度を表にすることを考える。(0,1,2,3・・の順で)

ランダムな数字:2 9 8 4 0 2 8 3 9 9・・・・①
上の数の各数字の使用頻度調査
        0 1 2 3 4 5 6 7 8 9 の数字が
        1 0 2 1 1 0 0 0 2 3・・・・②の回数での使用頻度となる。

ここで、①でのランダムな数字と調査結果の②の数字がピタリ一致するものを探すことがしたい。
果たして、この条件を満たす10桁の数は存在するか?
また存在すれば何個あるのか?

これをプログラムに組んで頂きたいです。
 

Re: そんなのある?

 投稿者:山中和義  投稿日:2012年 3月 2日(金)10時35分34秒
  > No.1794[元記事へ]

GAIさんへのお返事です。

> 10桁のランダムな数字を書いた時
> そこに使用した各数字の頻度を表にすることを考える。(0,1,2,3・・の順で)
>
> ランダムな数字:2 9 8 4 0 2 8 3 9 9・・・・①
> 上の数の各数字の使用頻度調査
>         0 1 2 3 4 5 6 7 8 9 の数字が
>         1 0 2 1 1 0 0 0 2 3・・・・②の回数での使用頻度となる。
>
> ここで、①でのランダムな数字と調査結果の②の数字がピタリ一致するものを探すことがしたい。
> 果たして、この条件を満たす10桁の数は存在するか?
> また存在すれば何個あるのか?


単純に考えると、総当りとなるが、これも、PCでは困難です。。。

  LET P=5 !p進法p桁
  DIM A(0 TO P-1) !使用頻度
  DIM B(0 TO P-1) !各桁の数値 ※B(0)が最上位
  FOR i=P^(P-1) TO P^P-1 !p桁の範囲
  !FOR i=6210001000 TO 10^10-1 !10桁の範囲
     MAT A=ZER
     LET t=i
     FOR k=0 TO P-1 !1p進法p桁へ(進数変換)
        LET w=MOD(t,P)
        LET A(w)=A(w)+1
        LET B((P-1)-k)=w
        LET t=INT(t/P)
     NEXT k
     FOR k=0 TO P-1 !並びが一致するか
        IF A(k)<>B(k) THEN EXIT FOR
     NEXT k
     IF k>P-1 THEN MAT PRINT A;
  NEXT i
  END


そこで、

10進法10桁の数なので、自然数10の分割を考える。(自然数10を10個の非負の整数の和で表す)
ただし、a[0]≦a[1]≦a[2]≦ … ≦a[8]≦a[9](昇順に並べたもの)とする。
その組は、
  1  1  1  1  1  1  1  1  1  1
  1  1  1  1  1  1  1  1  2  0
    :
  1  1  2  6  0  0  0  0  0  0  ← ※
    :
 10  0  0  0  0  0  0  0  0  0
の42通り。(この値を分割数という)

この並びを、数 0,1,2,3,4,5,6,7,8,9 の使用頻度とすると、
まず、0に着目すると、
 並びの中に「0の個数」と「数値の1つ」が同じもの
を探す。
すなわち、上記の←が条件を満たす。
同様に、1,2に着目すると、上で選んだ数値を除くことに注意して、上記の※が条件を満たす。
次に、6に着目すると、この並びでは条件を満たさないが、
  6  2  1  0  0  0  1  0  0  0  ← ※
と並べ替えると条件を満たす。

うまく並べ替えられるかは、
まず、分割した数の並びMの使用頻度Aを求める。
  M:  1  1  2  6  0  0  0  0  0  0
    ↓
  A:  6  2  1  0  0  0  1  0  0  0
同様に、並びAの使用頻度Bを求める。
  A:  6  2  1  0  0  0  1  0  0  0
    ↓
  B:  6  2  1  0  0  0  1  0  0  0
それらが一致するかどうかで確認できる。


また、これらのことはn進法n桁でも議論できる。


PUBLIC NUMERIC C !分割数
LET C=0
LET N=10 !n進法n桁
DIM M(0 TO N-1) !数の並び
MAT M=ZER
CALL search(0,0,M,N)
END

EXTERNAL SUB search(p,s,M(),N) !バックトラック法で検索する
IF p=0 THEN LET t=1 ELSE LET t=M(p-1) !昇順
FOR i=t TO N-s !※sは、0から(p-1)番目までの和
   LET M(p)=i !p番目を設定する
   IF s+i=N THEN !条件を満たせば
      LET C=C+1
      CALL try(N,M,C)
   ELSE
      CALL search(p+1,s+i,M,N) !次へ
   END IF
   LET M(p)=0 !元に戻す
NEXT i
END SUB

EXTERNAL SUB try(N,M(),C)
DIM A(0 TO N),B(0 TO N) !※Nは、10,0,0,…,0のような並びに対応するため
MAT A=ZER !並びMの使用頻度Aを求める
FOR i=0 TO N-1
   LET t=M(i)
   LET A(t)=A(t)+1
NEXT i
MAT B=ZER !並びAの使用頻度Bを求める
FOR i=0 TO N-1
   LET t=A(i)
   LET B(t)=B(t)+1
NEXT i
FOR i=0 TO N-1 !並びA,Bが同じかどうか確認する
   IF A(i)<>B(i) THEN EXIT FOR
NEXT i
IF i>N-1 THEN
   FOR j=0 TO N-1 !結果を表示する
      PRINT B(j);
   NEXT j
   PRINT
END IF
END SUB

 

Re: そんなのある?

 投稿者:山中和義  投稿日:2012年 3月 2日(金)15時47分21秒
  > No.1799[元記事へ]

 

戻る