Joachim's web pages [Home] [Math] [CiO]

Combinatòria i Optimització
Col·lecció d'implementacions d'algorismes

Camins en un tauler d'escacs --- exercici 7 de la llista complementària

# -*-tcl-*-

# Number of shortest lattice paths from (1,1) to (m,n):
proc P { m n } {
    if { $m == 1 ¦¦ $n == 1 } {
        return 1
    }
    return [expr {[P [expr {$m-1}] $n] + [P $m [expr {$n-1}]]}]
}

--- esclar, la solució sintètica i molt mes simple és el coeficient binomial "m+n-2 sobre m-1".

Shuffles --- exercici 1

# -*-tcl-*-

# Number of shuffles of two decks of cards of cardinality m and n:
proc SS { m n } {
    if { $m == 0 || $n == 0 } {
	return 1
    } else {   
	return [expr {[SS [expr {$m-1}] $n] + [SS $m [expr {$n-1}]]}]
    }
}

--- esclar, la solució sintètica i molt mes simple és el coeficient binomial "m + n sobre m".

12 jogades de daus amb suma 30 --- exercici 17

# -*-tcl-*-

# Event: throw a dice twelve times.  
# How many possible events with sum 30?
proc P { sum length } {
    if { $sum == 0 && $length == 0 } {
	return 1
    }
    if { $sum <= 0 ¦¦ $length == 0 } {
	return 0
    }
    set res 0
    for { set i 1 } { $i < 7 } {incr i } {
	incr res [P [expr {$sum-$i}] [expr {$length-1}]]
    }
    return $res
}


# Test that these results sum up to all possibilitites:
proc Ptest { length } {
    set total [expr {pow(6,$length)}]
    set subtotal 0
    for {set sum 0} {$sum <= 6*$length} {incr sum} {
        incr subtotal [P $sum $length]
    }
    
    if { $subtotal == $total } {
        return OK
    } else {
        return "test not passed"
    }
}


# -*-maple-*-

# Event: throw a dice twelve times.  
# How many possible events with sum 30?
P := proc(r::integer, n::nonnegint)
    option remember;
    if r = 0 and n = 0 then
        RETURN(1)
    end if;
    if r <= 0 or n = 0 then
        RETURN(0)
    end if;
    P(r,n) := add(P(r-i,n-1),i=1..6);
end proc;

Amb la tècnica de funcions generadores:

# -*-maple-*-

g := taylor( (x+x^2+x^3+x^4+x^5+x^6)^12, x=0, 31 );
coeff( g, x^30 );

Pagament de 85 euros --- exercici 18

# -*-tcl-*-
package require Tclx

# How many ways to pay 85 euros with coins/bills of size {1 5 10 20}?
# n is the desired amount
# L is a list of types of coins available
proc P { n L } {
    if { $n == 0 } {
        return 1
    }
    if { [llength $L] == 0 } {
        # If no coins available, can't pay:
        return 0
    }
    set thisCoin [lvarpop L]; # L is truncated
    set res 0
    for { set i 0 } { $i <= $n } {incr i} {
        # i is the number of thisCoins
        incr res [P [expr {$n - $i*$thisCoin}] $L]
    }
    return $res
}

Last updated: 2006-03-21 by Joachim Kock.