##TP - Structures algorithmiques

##1-Alternative
##Lecture
"""
Question 1 : Comme x=-2, on entre dans le if x vaut alors 2. Comme on est entré dans le if, on n'entre pas dans le else, x vaut 2.
"""
x=-2
if not (x>0 and x<5):
    x=-x
else :
    x=2*x
print(x)

"""
Question 2 : Comme (x,y)=(1,2), on entre dans le if donc z=x=1. Comme on est entré dans le if, on n'entre pas dans le else, z vaut 1.
"""
x,y=1,2
if not (x>y) :
    z=x
else :
    z=y
print(z)

"""
Question 3 : Comme x=-2, on entre dans le if donc x=2. Puis comme x=2 est compris entre 0 et 5 strictement, on entre dans le deuxième if donc x=-2*2=-4.
"""
x=-2
if not ((x>0) and (x<5)) :
    x=-x
if (x>0) and (x<5) :
    x=-2*x
print(x)

"""
Question 4 : Comme x=-3, on n'entre pas dans le if, ni dans le premier elif mais dans le deuxième elif donc y=(-3)*(-3)+6*(-3)+8=-1. Comme on est entré dans le deuxième elif, on n'entre ni dans le troisième elif ni dans le else donc y=-1.
"""
x=-3
if x<-4 :
    y=0
elif x<-3 :
    y=4-x
elif x<-1 :
    y=x*x+6*x+8
elif x<3:
    y=2-x
else :
    y=-2
print(y)

"""
Question 5 : Comme (x,y)=(2,3) et (d,c)=(5,4), on entre dans le if puis dans le if imbriqué donc k=y=3. Comme on est entré dans le if imbriqué, on n'entre pas dans le else imbriqué. Comme on est entré dans le if, on n'entre pas dans le else donc k=3.
"""
x,y=2,3
d,c=5,4
if x>0 and x<d :
    if y>0 and y<c :
        k=y
    else :
        k=x
else :
    k=1
print(k)

"""
Question 6 : Comme (x,y)=(3,-2), on n'entre pas dans le if ni dans le elif donc on entre dans le else et y=3-(-2)=5.
"""
x,y=3,-2
if x<y :
    y=y-x
elif x==y :
    y=0
else :
    y=x-y
print(y)

##Programmes utilisant des alternatives
"""
Question 7 :
Fonction racine
 Entrée : un réel x
 Sortie : -le réel égal à sa racine carré si x est positif
          -le booléen False sinon.
"""
from math import sqrt #On a besoin de la fonction racine carrée

def racine(x):
    if x>=0 : #Si x est positif
        return sqrt(x) #On renvoie sa racine carrée
    else : #Sinon
        return False #On renvoie le booléen False

#On teste sa fonction sur au moins deux exemples.
print(racine(4))
print(racine(-4))

"""
Question 8 :
Fonction bissextile
Entrée : n un entier
Sortie : - booléen True si (n<1582 et n multiple de 4) ou (n>1582 et n multiple de 4 sauf si n multiple de 100 et n non multiple de 400)
         - booléen False sinon.
"""
def bissextile(n):
    #Si on est avant octobre 1582 et que n est multiple de 4
    if n<1582 and n%4==0 :
        return True #L'année est bissextile

    #Sinon si on est après 1582 et que n est un mutltiple de 4
    elif n>=1582 and n%4==0 :
        #Si n est un multiple de 100 mais pas de 400
        if n%100==0 and n%400!=0 :
            return False #L'année n'est pas bissextile
        else : #Sinon
            return True #L'année est bissextile

    #Sinon n n'est pas multiple de 4
    else :
        return False #L'année n'est pas bissextile

print(bissextile(2000))
print(bissextile(2004))
print(bissextile(2002))

#Le if imbriqué peut être inclus dans le premier if.
def bissextile1(n):
    #Si on est avant octobre 1582 et que n est multiple de 4
    if n<1582 and n%4==0 :
        return True #L'année est bissextile

    #Sinon si on est après 1582 et que n est un mutltiple de 4 mais pas multiple de 100 et pas de 400
    elif n>=1582 and n%4==0 and not(n%100==0 and n%400!=0) :
            return True #L'année est bissextile

    #Sinon n n'est pas multiple de 4 ou n est multiple de 4 et de 100 mais pas de 400
    else :
        return False #L'année n'est pas bissextile

print(bissextile1(2000))
print(bissextile1(2004))
print(bissextile1(2002))

#En fait, on peut se passer d'alternative mais la lecture de l'algorithme en devient plus compliquée.
#En effet, il suffit de renvoyer le booléen représentant les alternatives de l'algorithme précédent pour lesquelles les réponses étaient True.
def bissextile2(n):
    return ( (n<1582 and n%4==0) or (n>=1582 and n%4==0 and not(n%100==0 and n%400!=0)) )

print(bissextile2(2000))
print(bissextile2(2004))
print(bissextile2(2002))

"""
Question 9 :
Fonction sol2ndDegre
 Entrées : a,b et c trois réels avec a!=0
 Sortie : on calcule Delta=b*b-4*a*c.
          -Si Delta est positif, on renvoie le couple des réels solutions de l'équation.
          -Si Delta est nul, on renvoie le réel racine double de l'équation.
          -Si Delta est négatif, la fonction ne renvoie rien.
"""
def sol2ndDegre(a,b,c):
    Delta= b*b-4*a*c #Calcul du discriminant
    if Delta>0 : #Si le discriminant est positif
        x1 = (-b-sqrt(Delta))/(2*a) #x1 première racine
        x2 = (-b+sqrt(Delta))/(2*a) #x2 deuxième racine
        return x1,x2 #on renvoie le couple des solutions
    elif Delta==0 : #Sinon si le discriminant est nul
        x0 = -b/(2*a) #x0 est la racine double
        return x0 #on la renvoie
    #Sinon le discriminant est négatif et on ne fait rien

print(sol2ndDegre(1,2,1))
print(sol2ndDegre(1,3,2))
print(sol2ndDegre(1,0,3))


"""
Exercice 1 : Jeu de devinette
1) La fonction jeuDevinette prend en entrées 4 booléens et renvoie la chaîne de caractère
 "hirondelle" si rep1, rep2, rep3, rep4 = True,True,False,False ;
 "dauphin" si rep1, rep2, rep3, rep4 = True,False,True,True
 "chat" si rep1, rep2, rep3, rep4 = True,False,False,True
 "diplodocus" si rep1, rep2, rep3, rep4 = False,False,False,False
 "tyrannosaure" si rep1, rep2, rep3, rep4 = False,False,False,True.
 et la chaîne "impossible" sinon.
"""
def jeuDevinette(rep1,rep2,rep3,rep4):
    #Si les réponses correspondent à l'hirondelle
    if rep1 and rep2 and not rep3 and not rep4 :
         return "hirondelle" #On renvoie hirondelle

    #Sinon si les réponses correspondent au dauphin
    elif rep1 and not rep2 and rep3 and rep4 :
        return "dauphin" #On renvoie dauphin

    #Sinon si les réponses correspondent au chat
    elif rep1 and not rep2 and not rep3 and rep4 :
        return "chat" #On renvoie chat

    #Sinon si les réponses correspondent au diplodocus
    elif not rep1 and not rep2 and not rep3 and not rep4 :
        return "diplodocus" #On renvoie diplodocus

    #Sinon si les réponses correspondent au tyrannosaure
    elif not rep1 and not rep2 and not rep3 and rep4 :
        return"tyrannosaure" #On renvoie tyrannosaure
    else :
        return "impossible" #On renvoie la réponse

print(jeuDevinette(True,True,False,True))
print(jeuDevinette(True,True,True,True))

#Avec un unique return.
def jeuDevinette2(rep1,rep2,rep3,rep4):
    reponse="impossible" #Variable contenant la réponse de l'ordinateur

    #Si les réponses correspondent à l'hirondelle
    if rep1 and rep2 and not rep3 and not rep4 :
        reponse="hirondelle" #La réponse devient hirondelle

    #Sinon si les réponses correspondent au dauphin
    elif rep1 and not rep2 and rep3 and rep4 :
        reponse="dauphin" #La réponse devient dauphin

    #Sinon si les réponses correspondent au chat
    elif rep1 and not rep2 and not rep3 and rep4 :
        reponse="chat" #La réponse devient chat

    #Sinon si les réponses correspondent au diplodocus
    elif not rep1 and not rep2 and not rep3 and not rep4 :
        reponse="diplodocus" #La réponse devient diplodocus

    #Sinon si les réponses correspondent au tyrannosaure
    elif not rep1 and not rep2 and not rep3 and rep4 :
        reponse="tyrannosaure" #La réponse devient tyrannosaure
    return reponse #On renvoie la réponse

print(jeuDevinette2(True,True,False,True))
print(jeuDevinette2(True,True,True,True))

"""
2) jouerJeu ne prend pas de paramètre d'entrée, elle pose les 4 questions au joueur et affiche la réponse de l'ordinateur.
"""
def jouerJeu():
    #repk est la réponse à la question k."
    rep1 = int(input("Est-ce que l'animal existe encore aujourd'hui ?"))==1
    rep2 = int(input("Est-ce que l'animal vole ?"))==1
    rep3 = int(input("Est-ce que l'animal nage ?"))==1
    rep4 = int(input("Est-il carnivore ?"))==1
    #On obtient la réponse de l'ordinateur en utilisant la fonction jeuDevinette
    reponse= jeuDevinette(rep1,rep2,rep3,rep4)
    print(reponse) #On affiche cette réponse



##2-Les boucles
##Lecture
"""
Question 10 : Comme i=5, l'algorithme affixhe successivement 4,3,2,1,0,-1. Quand i=-1, le test du while est faux, on n'y entre pas.
"""
i=5
while i>=0 :
    i=i-1
    print(i)

"""
Question 11 : Comme i=2, l'algorithme affiche successivement "x",3,4,5,"x",6. En effet, comme 3 est un muliple de 3 on entre dans le if et on affiche la chaîne "x" puis l'entier 3 ... Quand i=6, on n'entre plus dans le while.

Attention, on rappelle que lors de l'affichage d'une chaîne de caractère avec la fonction print, les guillemets ne sont pas visibles.
"""
i=2
while i<6 :
    i=i+1
    if i%3==0 :
        print("x")
    print(i)

"""
Question 12 : Comme i=5, la boucle while va s'effectuer jusqu'à ce que i=-1 qui sera alors affiché. L'algorithme affiche -1.
"""
i=5
while i>=0 :
    i=i-1
print(i)

"""
Question 13 :  Comme i=0, on entre dans le while, i devient 1, comme 1 n'est pas multiple de 3 on n'entre pas dans le if mais dans le else et on affiche 1. Puis on recommence,comme 1 est plus petit que 7, on entre dans le while, i devient 2 ... L'algorithme affiche successivement 1,2,5,8.
"""
i=0
while i<=7:
    i=i+1
    if i%3==0 :
        i=i+1
    else :
        print(i)

"""
Question 14 : Comme a=1 et b=1, premier passage dans le for, on affiche 1 puis c=1+1=2, a=1 et b=2; deuxième passage dans le for, on affiche 1 puis c=1+2=3, a=2 et b=3 ... La boucle s'effectue 10 fois pour i allant de 1 à 10. L'algorithme affiche donc successivement les dix nombres suivants 1,1,2,3,5,8,13,21,34,55.
"""
a=1
b=1
for i in range(1,11):
    print(a)
    c=a+b
    a=b
    b=c

#Ré-écriture avec un while.
a=1 #initialisation
b=1
while a<89 :
    print(a)
    c=a+b
    a=b #incrémentation de a
    b=c

"""
Question 15 : Comme  x=11, au premier passage dans le for, n=0, on affiche (0,11) puis comme x est impair on n'entre pas dans le if mais dans le else donc x devient 34; au deuxième passage dans le for, n=1, on affiche (1,34), ... La boucle s'effectue 10 fois de n allant de 0 à 9 donc l'algorithme affiche successivement les 10 couples suivants  (0,11),(1,34),(2,17),(3,52),(4,26),(5,13),(6,40),(7,20),(8,10),(9,5).
"""
x=11
for n in range(0,10) :
    print(n,x)
    if x%2==0 :
        x=x//2
    else :
        x=3*x+1

#Ré-écriture avec un while
x=11
n=0 #on initialise n
while n<10 :
    print(n,x)
    n=n+1 #on incrémente n
    if x%2==0 :
        x=x//2
    else :
        x=3*x+1


##Programmes utilisant des boucles.
"""
Question 16 :
Fonction sommeN
 Entrée : n un entier non nul
 Sortie : l'entier égale à la somme des entiers de 1 à n.
"""
def sommeN(n):
    som=0 #som contient la somme des entiers, on l'initialise à 0
    for i in range(1,n+1) : #Pour tout les entiers de 1 à n inclus
        som=som+i #On ajoute i à som. On peut aussi écrire som += i.
    return som #On renvoie som

#On teste la fonction
print(sommeN(1000))
print(sommeN(1000000))
print(sommeN(10000000))

#Ré-écriture avec le while.
def sommeNw(n):
    som=n #som contient la somme des entiers, on l'initialise à n (ou à 0)
    i=n-1 #On parcourt les eniers, on l'initialise à n-1 (ou à 1)
    while i>0 : #Tant que i est strictement positif (ou inférieur à n)
        som=som+i #On ajoute i à la somme contenue dans som
        i=i-1 #On décrémente (ou incrémente) i
    return som #On renvoie som

print(sommeNw(1000))
print(sommeNw(1000000))
print(sommeNw(10000000))

"""
Dans cette question, on préférera la version utilisant la boucle for car on sait que l'algorithme doit effectuer n itérations.
"""

"""
Question 17 :
Fonction sommeNbImpairs
 Entrées : n1 et n2 deux entiers avec n1<=n2
 Sortie : l'entier égale à la somme des nombres impairs compris entre a et b inclus.
"""
def sommeNbImpairs(n1,n2):
    som=0 #som contient la somme des nombres impairs, on l'initialise à 0
    for i in range(n1,n2+1): #on parcourt les entiers i de n1 à n2 inclus
        if i%2 == 1: #Si i est impair
            som+=i #On l'ajoute à som
    return som #On renvoie som

print(sommeNbImpairs(0,3))
print(sommeNbImpairs(1,3))
print(sommeNbImpairs(1,4))
print(sommeNbImpairs(2,2))
print(sommeNbImpairs(3,3))

#Ou bien
def sommeNbImpairs2(n1,n2):
    som=0 #som contient la somme des nombres impairs, on l'initialise à 0
    if n1%2==1 :
        n=n1
    else :
        n=n1+1
    for i in range(n,n2+1,2): #on parcourt les entiers i de n1 à n2 inclus avec un pas de 2
        som+=i #On l'ajoute à som
    return som #On renvoie som

print(sommeNbImpairs2(0,3))
print(sommeNbImpairs2(1,3))
print(sommeNbImpairs2(1,4))
print(sommeNbImpairs2(2,2))
print(sommeNbImpairs2(3,3))

#Ré-écriture avec le while.
def sommeNbImpairsw(n1,n2):
    som=0 #som contient la somme des nombres impairs, on l'initialise à 0
    if a%2==0 : #Si a est pair
        impair=a+1 #On commence à a+1
    else : #Sinon
        impair=a #On commence à a
    while impair< b+1 : #Tant que impair est inférieur à b
        som += impair #On ajoute impair à som
        impair += 2 #On passe à l'entier impair suivant
    return som

print(sommeNbImpairsw(0,3))
print(sommeNbImpairsw(1,3))
print(sommeNbImpairsw(1,4))
print(sommeNbImpairsw(2,2))
print(sommeNbImpairsw(3,3))

"""
Dans cette question, on préférera la version utilisant la boucle for car on sait que l'algorithme doit effectuer (n2-n1)//2 itérations.
"""

"""
Question 18 :
Fonction sommeK
 Entrées : deux entiers n non nul et k
 Sortie : l'entier égale à la somme des puissances k des entiers de 1 à n.
"""
def sommeK(n,k):
    som=0 #contient la somme des puissances kèmes des entiers, initialisée à 0
    for i in range(1,n+1): #On parcourt les n premiers entiers
        som += i**k #On ajoute à som la puissance kème de i
    return som #On renvoie som

print(sommeK(3,2))

#Ré-écriture
def sommeKw(n,k):
    som=0 #contient la somme des puissances kèmes des entiers, initialisée à 0
    i=1 #Variable pour parcourir les entiers, on initialise i à 1
    while i< n+1 : #Tant que i est inférieur ou égale à n
        som += i**k #On ajoute la puissance kème de i à som
        i=i+1 #On incrémente i
    return som #On renvoie som

print(sommeKw(3,2))

"""
Dans cette question, on préférera la version utilisant la boucle for car on sait que l'algorithme doit effectuer n itérations.
"""

"""
Question 19 :
Fonction sommeMultiples35
 Entrée : un entier n
 Sortie : l'entier égale à la somme des nombres multiples de 3 ou 5 strictement inférieur à n.
"""
def sommeMultiples35(n):
    som=0 #som contient la somme, on l'intialise à 0
    for i in range(1,n): #On parcourt les entiers de 1 à n exclus
        if i%3==0 or i%5==0 : #Si i est multiple de 3 ou 5
            som += i #On ajoute i à som
    return som #On renvoie som

print(sommeMultiples35(10))
print(sommeMultiples35(1435))

#Ré-écriture avec le while.
def sommeMultiples35w(n):
    som=0 #som contient la somme, on l'initialise à 0
    i=3 #Le premier multiple de 3 ou 5 est 3
    while i<n : #Tant que i est inférieur à n
        if i%3==0 or i%5==0 : #Si i est multiple de 3 ou 5
            som += i #On ajoute i à som
        i=i+1 #On incrémente i de 1
    return som #On renvoie som

print(sommeMultiples35w(10))
print(sommeMultiples35w(1435))

"""
Question 20 :
Fonction bricole
 Entrée : un entier n
 Sortie : l'entier obtenu après les manipulations demandées.
"""
def bricole(n):
    deb=n//1000 #3 premires chiffres de n
    fin=n-deb*1000 #3 derniers chiffres de n
    for i in range(fin):#On itère fin fois
        temp=deb*13 #Variable temporaire
        temp_deb=temp//1000 #3 premiers chiffres de temp
        deb=temp-temp_deb*1000 #On actualise deb
    return deb

print(bricole(317010))

#Ré-écriuture avec le while
def bricolew(n):
    deb=n//1000 #3 premiers chiffres de n
    fin=n-deb*1000 #3 derniers chiffres de n
    cpt=0 #Compteur du nombre d'itérations
    while cpt<fin : #Tant qu'on a pas itéré fin fois
        cpt += 1 #On incrémente le compteur
        temp=deb*13 #Variable temporaire
        temp_deb=temp//1000 #3 premiers chiffres de temp
        deb=temp-temp_deb*1000 #On actualise deb
    return deb

print(bricole(317010))

"""
Dans cette question, on préférera la version utilisant la boucle for car on sait que l'algorithme doit effectuer fin itérations.
"""


"""
Exercice 2 : Palindromes
1) Fonction retourner
 Entrée : un entier n
 Sortie : l'entier dont l'écriture est l'inverse de celle de n.
"""
def retourner(n):
    taille=1 #Nombre de chiffres de l'entier n
    nb=n//10 #On enlève le chiffre des unités
    while nb!=0: #Tant qu'il reste des chiffres
        taille += 1 #On incrémente la taille de n
        nb=nb//10 #On retire le chiffre des unités de nb
    n_ret = 0 #nombre retourner
    n_fin = n #nombre restant à retourner
    for i in range(taille): #On itère taille fois
        chiffre = n_fin%10 #On récupère le chiffre des unités de ce qui reste n_fin
        n_ret = n_ret*10+chiffre #On actualise n_ret
        n_fin = n_fin//10 #On retire l'unité den_fin
    return n_ret #On renvoie le nombre retourné

print(retourner(123))

#Ré-écriture
def retournerw(n):
    nb=n//10 #On enlève le chiffre des unités
    unite=n%10 #chiffre des unités
    n_ret = 0 #nombre retourné
    while nb!=0 : #Tant qu'il reste des nombres à retourner
        n_ret=n_ret*10+unite
        unite=nb%10
        nb=nb//10
    n_ret = n_ret*10+unite #On ajoute le dernier chiffre
    return n_ret

print(retournerw(123))

"""
Dans cette question, on préférera la version utilisant la boucle while car ça nous évite de devoir calculer la taille de n, c'est-à-dire le nombre de chiffres le contituant.
"""

"""
2) Fonction estPalindrome
 Entrée : un entier n
 Sortie : booléen True si n est un palindrome
          et False sinon.
"""
def estPalindrome(n):
    return not n%10==0 and n==retourner(n)  #les nombres terminant par 0 ne sont pas des palindromes

print(estPalindrome(123))
print(estPalindrome(2002))

"""
3) Fonction plusHautPalindrome
 Entrée : pas d'entrée
 Sortie : l'entier palindrome le plus grand issu du produit de deux entiers à trois chiffres.
"""
def plusHautPalindrome():
    pGd=10000 #plus petit pd de deux nombres à 3 chiffres, par la suite contiendra la plus grand palindrome rencontré
    for n1 in range(10,1000): #le premier nombre va de 100 à 999
        for n2 in range(n1,1000): #le deuxième nombre va de n1 à 1000 pour éviter de retester des couples (n1,n2)
            if (estPalindrome(n1*n2) and pGd<n1*n2): #Si on a trouvé un nouveau palindrome plus gd
                pGd = n1*n2 #On le mémorise
    return pGd

#Ou bien, en évitant les tests inutiles.
def plusHautPalindrome():
    pGd=10201 #101*101=Plus petit palindrome obtenu comme produit de deux nombres à 3 chiffres car les kx100 finissent par 2 zéros et ne sont donc pas des palindromes
    for n1 in range(101,1000): #le premier nombre va de 101 à 1000 car kx100 fini par 2 zéros et n'est donc pas un palindrome
        if not n1%10 == 0 : #tout les multiples de 10 donne un produit kxn1 terminant par un zéro donc qui n'est pas palindrome
            for n2 in range(n1,1000): #le deuxième nombre va de n1 à 1000 pour éviter de retester des couples (n1,n2)
                if (not n2%10==0 and estPalindrome(n1*n2) and pGd<n1*n2): #Si on a trouvé un nouveau palindrome plus gd
                    pGd = n1*n2 #On le mémorise
    return pGd

#Ré-écriture avec while
def plusHautPalindromew():
    n1=101 #nombre 1, on ne teste pas 100, car kx100 fini par 2 zéros et n'est donc pas un palindrome.
    pGd=10201 #101*101=Plus petit palindrome obtenu comme produit de deux nombres à 3 chiffres car les kx100 finissent par 2 zéros et ne sont donc pas des palindromes
    while n1<1000 :
        n2 = n1 #nombre 2
        while n2<1000 :
            if (not n2%10==0 and estPalindrome(n1*n2) and pGd<n1*n2): #Si on a trouvé un nouveau palindrome plus gd
                pGd = n1*n2 #On le mémorise
            n2+=1 #On passe à l'entier n2 suivant

        n1+=1 #on passe à l'entier n1 suivant
        if n1%10==0 :
            n1+=1
    return pGd


"""
Exercice 3 : Suite de Syracuse.
1) Fonction decompteSyracuse
 Entrée : un entier N
 Sortie : l'entier égale au nombre de termes contenus dans la suite de Syracuse partant de N avant d'atteindre 1.
"""
def decompteSyracuse(N):
    u=N #terme de la suite de Syracuse commençant à N
    cpt = 1 #compteur de termes
    while u!=1: #Tant que la suite n'a pas atteint 1
        if u%2==0: #Si le terme est pair
            u=u/2 #On le divise par 2
        else: #Sinon, il est impair
            u=3*u+1 #On multiplie par 3 et on ajoute 1
        cpt +=1 #On augmente le compteur de 1
    return cpt #On renvoie le compteur

print(decompteSyracuse(30))

"""
On est obligé d'utiliser une boucle for, on ne sait pas combien d'itérations l'algorithme va effectuer.
"""

"""
2) Fonction plusLongueSyracuse
 Entrée : pas d'entrée
 Sortie : l'entier N compris entre 1 et 1 000 000 maximisant decompteSyracuse.
"""
def plusLongueSyracuse():
    cpt_max = decompteSyracuse(1) #Plus grand nombre de termes de la suite de Syracuse nécessaire pour atteindre 1, on commence par N=1
    for N in range(2,1000000): #Pour tout entier de 2 à 1 000 000
        if cpt_max<decompteSyracuse(N): #Si la sjuite de Syracuse est plus longue en partant de N
            cpt_max=decompteSyracuse(N) #On actualise la valeur de cpt_max
    return cpt_max