ExemplesCours.ipynb

Kernel: Unknown Kernel

Factorielle

def factorielleIt(n):
    r = 1
    for i in range(1,n+1):
        r *=i
    return r

factorielleIt(5)

120

def factorielleRec(n):
    if n == 0:
        return 1
    return n * factorielleRec(n-1)

factorielleRec(5)

120

Hanoi

def print_hanoi_actions(n, t1, t2, t3):
    if n == 0:
        return
    print_hanoi_actions(n-1,t1,t3,t2)
    print "Move from " + t1 + " to " + t2
    print_hanoi_actions(n-1,t3,t2,t1)

print_hanoi_actions(3,"Tower 1","Tower 2","Tower 3")

Move from Tower 1 to Tower 2
Move from Tower 1 to Tower 3
Move from Tower 2 to Tower 3
Move from Tower 1 to Tower 2
Move from Tower 3 to Tower 1
Move from Tower 3 to Tower 2
Move from Tower 1 to Tower 2

class Towers:
    
    def __init__(self,n):
        self.towers = (range(n,0,-1),[],[])
        self.size = n
    
    def move(self,i,j):
        t1,t2 = self.towers[i], self.towers[j]
        if len(t1) == 0 or (len(t2) != 0 and t1[-1]>t2[-1]):
            raise ValueError("Invalid action")
        print "Move from Tower " + str(i) + " to Tower " + str(j)
        t2.append(t1.pop())
    
    def pretty_print(self):
        res = ""
        n = self.size
        for i in xrange(n):
            line = ""
            for t in self.towers:
                if len(t) > i:
                    v = t[i]
                else:
                    v = 0
                stars = v*"*"
                spaces = (n-v)*" "
                line+= spaces + stars + "|" + stars + spaces + " "
            line+="\n"
            res = line + res
        return res

        
    
    

T = Towers(3)
print T.pretty_print()

  *|*      |       |    
 **|**     |       |    
***|***    |       |    

def hanoi(n, T, t1, t2, t3):
    if n == 0:
        return
    hanoi(n-1,T,t1,t3,t2)
    T.move(t1,t2)
    print T.pretty_print()
    hanoi(n-1,T,t3,t2,t1)

T = Towers(3)
print T.pretty_print()
hanoi(3,T,0,1,2)

  *|*      |       |    
 **|**     |       |    
***|***    |       |    

Move from Tower 0 to Tower 1
   |       |       |    
 **|**     |       |    
***|***   *|*      |    

Move from Tower 0 to Tower 2
   |       |       |    
   |       |       |    
***|***   *|*    **|**  

Move from Tower 1 to Tower 2
   |       |       |    
   |       |      *|*   
***|***    |     **|**  

Move from Tower 0 to Tower 1
   |       |       |    
   |       |      *|*   
   |    ***|***  **|**  

Move from Tower 2 to Tower 0
   |       |       |    
   |       |       |    
  *|*   ***|***  **|**  

Move from Tower 2 to Tower 1
   |       |       |    
   |     **|**     |    
  *|*   ***|***    |    

Move from Tower 0 to Tower 1
   |      *|*      |    
   |     **|**     |    
   |    ***|***    |    

T = Towers(4)
print T.pretty_print()
hanoi(4,T,0,1,2)

   *|*        |         |     
  **|**       |         |     
 ***|***      |         |     
****|****     |         |     

Move from Tower 0 to Tower 2
    |         |         |     
  **|**       |         |     
 ***|***      |         |     
****|****     |        *|*    

Move from Tower 0 to Tower 1
    |         |         |     
    |         |         |     
 ***|***      |         |     
****|****   **|**      *|*    

Move from Tower 2 to Tower 1
    |         |         |     
    |         |         |     
 ***|***     *|*        |     
****|****   **|**       |     

Move from Tower 0 to Tower 2
    |         |         |     
    |         |         |     
    |        *|*        |     
****|****   **|**    ***|***  

Move from Tower 1 to Tower 0
    |         |         |     
    |         |         |     
   *|*        |         |     
****|****   **|**    ***|***  

Move from Tower 1 to Tower 2
    |         |         |     
    |         |         |     
   *|*        |       **|**   
****|****     |      ***|***  

Move from Tower 0 to Tower 2
    |         |         |     
    |         |        *|*    
    |         |       **|**   
****|****     |      ***|***  

Move from Tower 0 to Tower 1
    |         |         |     
    |         |        *|*    
    |         |       **|**   
    |     ****|****  ***|***  

Move from Tower 2 to Tower 1
    |         |         |     
    |         |         |     
    |        *|*      **|**   
    |     ****|****  ***|***  

Move from Tower 2 to Tower 0
    |         |         |     
    |         |         |     
    |        *|*        |     
  **|**   ****|****  ***|***  

Move from Tower 1 to Tower 0
    |         |         |     
    |         |         |     
   *|*        |         |     
  **|**   ****|****  ***|***  

Move from Tower 2 to Tower 1
    |         |         |     
    |         |         |     
   *|*     ***|***      |     
  **|**   ****|****     |     

Move from Tower 0 to Tower 2
    |         |         |     
    |         |         |     
    |      ***|***      |     
  **|**   ****|****    *|*    

Move from Tower 0 to Tower 1
    |         |         |     
    |       **|**       |     
    |      ***|***      |     
    |     ****|****    *|*    

Move from Tower 2 to Tower 1
    |        *|*        |     
    |       **|**       |     
    |      ***|***      |     
    |     ****|****     |