|
|
> No.1794[元記事へ]
ＧＡＩさんへのお返事です。
> 10桁のランダムな数字を書いた時
> そこに使用した各数字の頻度を表にすることを考える。（０，１，２，３・・の順で）
>
> ランダムな数字：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・・・・②の回数での使用頻度となる。
>
> ここで、①でのランダムな数字と調査結果の②の数字がピタリ一致するものを探すことがしたい。
> 果たして、この条件を満たす１０桁の数は存在するか？
> また存在すれば何個あるのか？
単純に考えると、総当りとなるが、これも、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
|
|