Problem 113 「非はずみ数」 †
ある数の桁を左から右へと順に見たとき, 任意の桁の数が自身の左にある桁の数以上であるとき, その数を増加数 (increasing number) と呼ぶ; 例えば134468は増加数である.
同様に, 任意の桁の数が自身の右にある桁の数以上であるとき, その数を減少数 (decreasing number) と呼ぶ; 例えば66420がそうである.
増加数でも減少数でもない数を "はずみ"数 ("bouncy" number) と呼ぶ; 155349がそうである.
nが大きくなるにつれ, n以下のはずみ数の割合は大きくなる. 例えば, 100万未満では, はずみ数でない数は12951個しかない. 同様に, 10＾10未満では277032個しかない.
googol数 (10＾100) 未満ではずみ数でないものの数を答えよ.
解法
一桁ごとの動的計画法で片が付きます。
増加数でも減少数でもない数はどこかでエッジ、Ｘ＜Ｙ，Ｚ＜ＹかＸ＞Ｙ，Ｚ＞Ｙとなる部分ができますのでその場合計算から除外して計算が進みます。
増加数と減少数を別々に数えていき、最後に増加数でもあり減少数でもある数を集計から除けば答えです。
計算量はとても少なく済みます。
私の実感してるＰｒｏｌｏｇ言語の利点は全体がわからなくても細部がわかってれば細部を記述してるうちに勝手に答えが出てくる点と。
自然に実装してるといやでもモジュールの粒度を細かくしたほうが幸せになるなあと感じさせる構造を言語自体が持ってるという点です。
今回の問題ではそれがよく表れていて、記述している間に自然にモジュールが細かくなりました。
sum関数ももう少し細かいモジュールに分けるとほうがよい設計になります。
sum([],0):-!.
sum([[_,0,_,_]|Rest],Result):-
!,
sum(Rest,Result).
sum([[_,_,_,C]|Rest],Result):-
!,
sum(Rest,Re),
Result is Re+C.
union_sum([],E,[E]):-!.
union_sum([[X,Y,T,C]|Rest],[X,Y,T,C1],Result):-
!,
C2 is C+C1,
union_sum(Rest,[X,Y,T,C2],Result).
union_sum([E|Rest],E1,[E1|Result]):-
!,
union_sum(Rest,E,Result).
type(X,Y,Z,0):-X=<Y,Y=<Z,!.
type(X,Y,Z,1):-Z=<Y,Y=<X,!.
next_e([X,Y,T,C],Z,[Y,Z,T,C]):-
type(X,Y,Z,T).
next_calc(DP,Result):-
member(E,DP),
between(0,9,Z),
next_e(E,Z,Result).
dp(_,100,Sum):-!,Ans is Sum-9*98,write(Ans).
dp(DP,Keta,Sum):-
!,
findall(E,next_calc(DP,E),DP1),
msort(DP1,[Top|DP2]),
union_sum(DP2,Top,DP3),
Keta1 is Keta+1,
sum(DP3,Add),
Sum1 is Sum+Add,
dp(DP3,Keta1,Sum1).
seedType(X,X,T):-!,member(T,[0,1]).
seedType(X,Y,0):-X<Y,!.
seedType(_,_,1):-!.
seed([X,Y,T,1]):-
between(0,9,X),
between(0,9,Y),
seedType(X,Y,T).
main113:-
findall(E,seed(E),DP),
sum(DP,Sum),
dp(DP,2,Sum).
最終更新：2014年03月05日 22:28
