両替プログラム
２ちゃんの某 Prolog スレで、「両替の問題を解いてください．prolog始めて3週間で出た学校の課題です＞＜； 」なんてのを見かけたので、Prolog の勉強を兼ねて書いてみることに。なんとかそれっぽくうごくコードにはできました。
factorize([F | Fs], N, As) :- factorize1(F, Fs, N, [0 | As]). factorize1(F, [], N, [0 | As]) :- M is N mod F, M = 0, A is N // F, reverse([A | As], Result), write(Result), nl, !, fail. factorize1(F, Fs, N, [A | As]) :- N >= F, N1 is N - F, A1 is A + 1, factorize1(F, Fs, N1, [A1 | As]), !. factorize1(_, Fs, N, As) :- factorize(Fs, N, As).
?- factorize([10, 5, 1], 30, []). [3, 0, 0] [2, 2, 0] [2, 1, 5] [2, 0, 10] [1, 4, 0] [1, 3, 5] [1, 2, 10] [1, 1, 15] [1, 0, 20] [0, 6, 0] [0, 5, 5] [0, 4, 10] [0, 3, 15] [0, 2, 20] [0, 1, 25] [0, 0, 30] No
で。問題は、この動きを Smalltalk で表現すること。継続渡しを使ったバックトラッキングっていうんでしょうかね。とりあえず、普通に再帰で書いてみると、
Integer >> factorizedBy: factors do: aBlock
"3 factorizedBy: #(3 2 1) do: [: each | Transcript cr; show: each]"
^ self factorizedBy: factors startingWith: #() do: aBlock
Integer >> factorizedBy: factors startingWith: amplitudes do: aBlock
| amps index factor rest |
amps _ amplitudes.
index _ amps size + 1.
factor _ factors at: index.
rest _ self -
(index = 1 ifTrue: [0] ifFalse: [(amps * (factors first: amps size)) sum]).
index = factors size ifTrue: [
rest \\ factor = 0 ifTrue: [aBlock value: (amps copyWith: rest // factor)].
^ self].
rest // factor to: 0 by: -1 do: [: amp |
self factorizedBy: factors startingWith: (amps copyWith: amp) do: aBlock]
30 factorizedBy: #(10 5 1) do: [: each | Transcript cr; show: each]
"=> #(3 0 0)
#(2 2 0)
#(2 1 5)
#(2 0 10)
#(1 4 0)
#(1 3 5)
#(1 2 10)
#(1 1 15)
#(1 0 20)
#(0 6 0)
#(0 5 5)
#(0 4 10)
#(0 3 15)
#(0 2 20)
#(0 1 25)
#(0 0 30) "悪戦苦闘のすえの継続渡しだと、
factors: factors amplitudes: amplitudes ifFail: failBlock "27 factors: #(24 11 3) amplitudes: #(0) ifFail: [^ nil]" | factor | factor _ factors first. (factors size = 1 and: [amplitudes last isZero]) ifTrue: [ self \\ factor = 0 ifTrue: [ Transcript cr; show: (amplitudes allButLast copyWith: self // factor)]. ^ failBlock value]. ^ self factors: factors allButFirst amplitudes: (amplitudes copyWith: 0) ifFail: [ ^ self >= factors first ifTrue: [ amplitudes at: amplitudes size put: (amplitudes last + 1). self - factor factors: factors amplitudes: amplitudes ifFail: failBlock] ifFalse: [failBlock value]]
30 factors: #(10 5 1) amplitudes: #(0) ifFail: [^ nil] "=> #(0 0 30) #(0 1 25) #(0 2 20) #(0 3 15) #(0 4 10) #(0 5 5) #(0 6 0) #(1 0 20) #(1 1 15) #(1 2 10) #(1 3 5) #(1 4 0) #(2 0 10) #(2 1 5) #(2 2 0) #(3 0 0) "
見通しワル…、ってか読みにくっ(^_^;)。
