# -*- coding: utf-8 -*- """ Created on Sun Jan 17 20:33:27 2016 @author: Gérard M. MAMOU on Spyder 2.3.0 with Python 2.7 E3A CONCOURS ART ET METIERS ParisTech - ESTP - POLYTECH Epreuve de Mathématiques 1 - PSI Durée 4h, 7 pages Programme de Mathématiques et d'Informatique pour tous, Filière PSI https://fr.wikipedia.org/wiki/Problème_du_cavalier """ #Exercice I : Mouvement du cavalier sur un jeu d'Echec #----------------------------------------------------- #Q0/ #a) Le cavalier va en b1, on pourrait croire par récurrence que c'est une # bonne position mais très vite on voit qu'il va repasser par une case # déjà touchée, donc il n'accomplira pas sa mission. #b) S'il ne va pas en b1 tout de suite, de même il ne pourra jamais y revenir # car pour aller en b1 par la suite il faudra qu'il passe par une case # déjà touchée dans ce démarrage #Les Questions #------------- #1. Ecrire une fonction Indice qui aux coordonnées [i, j] d'une case # renvoie son indice. def Indice(coordonnees): rc=coordonnees[0]*8+coordonnees[1] return rc #end def print(Indice([2,1])) #Affiche 17 print(Indice([7,7])) #Affiche 63 #2. Ecrire une fonction Coord qui, à l'indice n d'une case renvoie la liste # [i, j] de ses coordonnées. def Coord(indice): rc1=indice/8 rc2=indice-rc1*8 return [rc1, rc2] #end def print(Coord(17)) #Affiche [2, 1] print(Coord(63)) #Affiche [7, 7] #3. On considère la fonction Python CasA suivante : def CasA(n): Deplacements = [ [1, -2], [2, -1], [2, 1], [1, 2], [-1, 2], [-2, 1], [-2, -1], [-1, -2]] L=[] i, j=Coord(n) for d in Deplacements: u=i+d[0] v=j+d[1] if u>=0 and u<8 and v>=0 and v<8: L.append(Indice([u, v])) #end if #end for return L #end def #3.1 Que renvoient CasA(0) et CasA(39)? print(CasA(0)) #Affiche [17, 10] print(CasA(39)) #Affiche [45, 54, 22, 29] #3.2 Expliquer en une phrase ce que fait cette fonction #Cette fonction renvoie en OUTPUT sous forme de liste les indices des positions # possibles d'être atteintes en un coup par un cheval partant de la case dont # l'indice est donné en INPUT #4. def Init(): global ListeCA global ListeCoups ListeCoups=[] ListeCA=[] for i in range(64): ListeCA.append(CasA(i)) #end for #end def Init() print(ListeCoups) #Affiche [] print(ListeCA[0]) #Affiche [17, 10] #5. #Réonse f. Elle renvoit [17, 10] #6. print(ListeCA[1]) #Affiche [16, 18, 11] print(ListeCA[16]) #Affiche [33, 26, 10, 1] #6.1 Ecrire une fonction OcupePosition def OccupePosition(n): rc=False ListeCoups.append(n) CasePermises=ListeCA[n] for k in CasePermises: ListeCA[k].remove(n) if ListeCA[k]==[]: rc=True else: rc=rc or False #end if #end for return rc #end def print("Avant OccupePosition(1)") print(ListeCoups) #Affiche [] print(ListeCA[16]) #Affiche [33, 26, 10, 1] print(ListeCA[18]) print(ListeCA[11]) rc=OccupePosition(1) print("Après OccupePosition(1)") print(rc) #Affiche False print(ListeCA[16]) #Affiche [33, 26, 10] print(ListeCA[18]) print(ListeCA[11]) print(ListeCoups) #Affiche [1] #6.2 Ecrire une fonction LiberePosition def LiberePosition(): n=ListeCoups.pop() CasePermises=ListeCA[n] for k in CasePermises: ListeCA[k].append(n) #end for #end def Init() print("Avant OccupePosition(1)") print("Avant LiberePosition()") print(ListeCoups) #Affiche [] print(ListeCA[16]) #Affiche [33, 26, 10, 1] print(ListeCA[18]) print(ListeCA[11]) rc=OccupePosition(1) print("Après OccupePosition(1)") print("Avant LiberePosition()") print(rc) #Affiche False print(ListeCA[16]) #Affiche [33, 26, 10] print(ListeCA[18]) print(ListeCA[11]) print(ListeCoups) #Affiche [1] LiberePosition() print("Après LiberePosition()") print(ListeCA[16]) #Affiche [33, 26, 10, 1] print(ListeCA[18]) print(ListeCA[11]) print(ListeCoups) #Affiche [] #6.3 Ecrire une fonction TestePosition print len(ListeCA[16]) #Affiche 4 def TestePosition(n): SituationCritique=OccupePosition(n) if SituationCritique: if len(ListeCoups)==63: return True else: LiberePosition() return False #end if else: buffer=ListeCA[n] CasesJouables=ListeCA[n] Flag=False for k in CasesJouables: rc=TestePosition(k) if rc: Flag=True break #end if #end for ListeCA[n]=buffer if Flag: return True else: LiberePosition() return False #end if #end if #end def print("Demarrage") Init() resultat=TestePosition(1) print(resultat)
Run
Reset
Share
Import
Link
Embed
Language▼
English
中文
Python Fiddle
Python Cloud IDE
Follow @python_fiddle
Browser Version Not Supported
Due to Python Fiddle's reliance on advanced JavaScript techniques, older browsers might have problems running it correctly. Please download the latest version of your favourite browser.
Chrome 10+
Firefox 4+
Safari 5+
IE 10+
Let me try anyway!
url:
Go
Python Snippet
Stackoverflow Question