On 1/11/07, Volkan YAZICI <[EMAIL PROTECTED]> wrote:
On Jan 11 12:18, Volkan YAZICI wrote:
> (define (available-changes amount coins)
> (cond
> ((= amount 0) '())
> ((< amount 0) #f)
> (else
> (append-map
> (lambda (coin)
> (let ((avails (available-changes (- amount coin) coins)))
> (cond
> ((not avails) '())
> ((null? avails) (list coin))
> (else
> (append-map
> (lambda (changes)
> (list (cons coin changes)))
> avails)))))
> coins))))
Sorun şu ki yukarıdaki kod neredeyse çalışıyormuş. Çok ufak bir
corner-case dışında. Onun için ufak bir düzeltme ile çalışan kod
aşağıda:
(define (available-changes amount coins)
(cond
((= amount 0) #f)
((< amount 0) '())
(else
(append-map
(lambda (coin)
(let ((avails (available-changes (- amount coin) coins)))
(cond
((not avails) (list coin))
((null? avails) '())
(else
(append-map
(lambda (changes)
(list (cons coin changes)))
avails)))))
coins))))
Fakat para birimleri arasına 1 eklendiği zaman olasılık uzayı
inanılmaz şekilde artıyor ve program sonsuz bir d,Av(Bng,A|(Bye girmişcesine
benim yavaş makinemde neredeyse saatlerce ,Ag(Balışıyor. (Bunun ddışında
Guile'ın stack depth overflow noktasına gelip swap'ten yemeye
başladığını s,Av(Bylemiyorum bile.)
Şimdi sorumu yeniden soruyorum, bu işi daha optimize bir şekilde
yapmanın yolu var mıdır? Yani para birimi i,Ag(Binde 1 varken de algoritma
,Ag(Balışabilsin.
İyi çalışmalar.
Merhaba,
Su sekilde de olabilir (algoritmanin kalan kisminin ne yaptigini
cozemedim, ama boyle calisiyor).
(define (available-changes amount coins)
(cond
((= amount 0) '(()) ) ; bu miktar hic para koymadan saglanabilir
((< amount 0) '() ) ; bu miktar saglanamaz
(else
(append-map
(lambda (coin)
(let ((avails (available-changes (- amount coin) coins)))
(append-map
(lambda (changes)
(list (cons coin changes)))
avails)))
coins))))
--
Mehmet
_______________________________________________
cs-lisp mailing list
[email protected]
http://church.cs.bilgi.edu.tr/lcg
http://cs.bilgi.edu.tr/mailman/listinfo/cs-lisp
