25-NSIJ1PO1-2

  Énoncé   Sujet

1. Il est possible de jouer la case 1 et 3 :

2. def initialiser(n):
       return [False] * n
   

3. def victoire(tab):
       for etat_case in tab:
           if etat_case == False:
               return False
       return True
   

4. def indice_premiere_case_occupee(tab):
       for i in range(len(tab)):
           if tab[i]:
               return i
       return None
   

5. def coup_valide(tab, case):    
       return 0 <= case < len(tab) and (case == 0 or \ 
           case == indice_premiere_case_occupee(tab) + 1)
   

6. def changer_case(tab, case):
       if coup_valide(tab, case):
           tab[case] = not tab[case]
       return tab
   

7. print('Vider case', n)
   

8. >>> vider(3)
   Vider case 1
   Vider case 3
   Remplir case 1
   Vider case 2
   Vider case 1
   

9. def remplir(n):
       if n == 1:
           print('Remplir case 1'):
       elif n > 1:
           remplir(n - 1)
           vider(n - 2)
           print('Remplir case', n)
           remplir(n - 2)
   

   Le processus est le suivant :

   

10. Puisque la fonction vider s'appelle elle-même deux fois, elle est de complexité exponentielle suivant la taille du baguenaudier. Elle devient donc trop lente dès que cette taille devient un peu trop grande.