Le problème du sac à dos, stratégie 1: prendre l'objet de plus grande valeur
Code : Tout sélectionner
def strat_1b(liste_objet, masse_dispo):
sac = []
i = 0
while masse_dispo > 0:
if liste_objet[i][1] <= masse_dispo:
masse_dispo = masse_dispo-liste_objet[i][1]
sac.append(liste_objet[i])
i = i + 1
return sac
maison = [(9700, 7), (3500, 8), (2600, 3)]
strat_1b(maison, 20)Code : Tout sélectionner
def rendu_monnaie(systeme:list, montant:int)->int:
"""
:param system (list): système de pièces
:param montant (int): somme à rendre
:return nbre (int) : nombre de pièces à rendre
>>> rendu_monnaie([1, 2, 5, 10], 8)
3
>>> rendu_monnaie([1, 2, 5, 10], 23)
4
>>> rendu_monnaie([1, 2, 5, 10], 0)
0
"""
assert montant>=0, "la somme à rendre doit être positive"
nbre = 0
liste = []
i = len(systeme)-1
while montant > 0 and i>=0:
if systeme[i] <= montant:
montant = montant - systeme[i]
nbre += 1
liste.append(systeme[i])
else:
i = i-1
return liste
def rendu_dict(systeme:list, montant:int)->int:
"""
:param system (list): système de pièces
:param montant (int): somme à rendre
:return nbre (int) : nombre de pièces à rendre
>>> rendu_monnaie([1, 2, 5, 10], 8)
3
>>> rendu_monnaie([1, 2, 5, 10], 23)
4
>>> rendu_monnaie([1, 2, 5, 10], 0)
0
"""
assert montant>=0, "la somme à rendre doit être positive"
nbre = 0
i = len(systeme)-1
dico = {i: 0 for i in systeme }
while montant > 0 and i >= 0:
if systeme[i] <= montant:
montant = montant - systeme[i]
nbre += 1
dico[systeme[i]] += 1
else:
i = i-1
return dico
print(rendu_dict([1, 2, 10], 92 ))Code : Tout sélectionner
def indice_maxi(L):
"""
renvoie le maximum et les indices où se il se trouve
:param L(list):
:return (tuple):
"""
liste_maxi = []
nb_max = L[0]
for i in range(len(L)):
if L[i] == nb_max:
liste_maxi.append(i)
if L[i] > nb_max:
nb_max = L[i]
liste_maxi = [i]
return (nb_max, liste_maxi)Code : Tout sélectionner
from random import randint
class Chat():
def __init__(self, nom, couleur, age):
self.nom = nom
self.coul = couleur
self.age = age
def miauler(self):
L = ["miaou", "Mewou", "MaaAAAAAAAAww"]
return L[(randint(0, 2))]
def chant(self, nb_max):
L = []
for i in range (0, randint(1, nb_max)):
L.append(self.miauler())
return L
chat1 = Chat("Pixie", "gris", 15)
chat2 = Chat("Tikie", "roux", 0.8)
chat3 = Chat("Garfield", "roux", 20)
class FamilleChat:
def __init__(self, nom, liste_chat = []):
self.f = nom
self.l = liste_chat
def nb_chat(self):
return len(self.l)
def afficher(self):
nb_chaton = 0
nb_chats = 0
for i in range(self.nb_chat()):
if self.l[i].age > 1:
nb_chats = nb_chats + 1
else:
nb_chaton = nb_chaton + 1
print("Le nombre de chat adulte est de",nb_chats,"et le nombre de chaton est de",nb_chaton)
def ajouter_chat(self, chat):
self.l.append(chat)
famille1 = FamilleChat("Tux",[chat1, chat2])
famille1.ajouter_chat(chat3)
famille1.afficher()
from random import randint
class Chat():
Code : Tout sélectionner
def __init__(self, nom, couleur, age):
self.nom = nom
self.coul = couleur
self.age = age
def miauler(self):
L = ["miaou", "Mewou", "MaaAAAAAAAAww"]
return L[(randint(0, 2))]
def chant(self, nb_max):
L = []
for i in range (0, randint(1, nb_max)):
L.append(self.miauler())
return Lchat1 = Chat("Pixie", "gris", 15)
chat2 = Chat("Tikie", "roux", 0.8)
chat3 = Chat("Garfield", "roux", 20)
class FamilleChat:
Code : Tout sélectionner
def __init__(self, nom, liste_chat = []):
self.f = nom
self.l = liste_chat
def nb_chat(self):
return len(self.l)
def afficher(self):
nb_chaton = 0
nb_chats = 0
for i in range(self.nb_chat()):
if self.l[i].age > 1:
nb_chats = nb_chats + 1
else:
nb_chaton = nb_chaton + 1
print("Le nombre de chat adulte est de",nb_chats,"et le nombre de chaton est de",nb_chaton)
def ajouter_chat(self, chat):
self.l.append(chat)famille1 = FamilleChat("Tux")
famille2 = FamilleChat("Linux")
famille1.ajouter_chat(chat3)
famille1.afficher()
famille2.afficher()
Code : Tout sélectionner
class Chat:
def __init__(self, nom, couleur, age):
self.nom = nom
self.coul = couleur
self.age = age
def miauler(self):
L = ["miaou", "Mewou", "MaaAAAAAAAAww"]
return L[(randint(0, 2))]
def chant(self, nb_max):
L = []
for i in range (0, randint(1, nb_max)):
L.append(self.miauler())
return L
chat1 = Chat("Pixie", "gris", 15)
chat2 = Chat("Tikie", "roux", 0.8)
chat3 = Chat("Garfield", "roux", 20)
class FamilleChat:
def __init__(self, nom, liste_chat):
self.f = nom
self.l = liste_chat
def nb_chat(self):
return len(self.l)
def afficher(self):
nb_chaton = 0
nb_chats = 0
for i in range(self.nb_chat()):
if self.l[i].age > 1:
nb_chats = nb_chats + 1
else:
nb_chaton = nb_chaton + 1
print("Le nombre de chat adulte est de",nb_chats,"et le nombre de chaton est de",nb_chaton)
def ajouter_chat(self, chat):
self.l.append(chat)
famille1 = FamilleChat("Tux")
famille2 = FamilleChat("Linux")
famille1.ajouter_chat(chat3)
famille1.afficher()
famille2.afficher()
Code : Tout sélectionner
def inverser(tab):
if len(tab) == 1:
return tab
else:
x0 = tab.pop(0)
print(tab)
return inverser(tab)+[x0]
print(inverser([1,2,3,4,5]))
Code : Tout sélectionner
def palindrome(mot):
if len(mot) == 0 or len(mot) ==1:
return True
else:
if mot[0] == mot[len(mot)-1]:
mot = mot[1 : -1]
return palindrome(mot)
else:
return False
Code : Tout sélectionner
import copy
class Pile:
def __init__(self):
self.pile = []
def est_vide(self):
return self.pile == []
def empiler(self, elem):
self.pile.append(elem)
def depiler(self):
assert len(self.pile ) > 0, ("non")
return self.pile.pop()
def sommet(self):
assert len(self.pile) > 0, ("non")
return self.pile[len(self.pile)-1]
def taille(self):
return len(self.pile)
def afficher(self):
for i in range(self.taille()):
print(self.pile[i])
#Partie A
laby = [
[0,1,0,0,0,0],
[0,1,1,1,1,0],
[0,1,0,1,0,0],
[0,1,0,1,1,0],
[0,1,1,0,1,0],
[0,0,0,0,1,0]]
laby2 =[
[0,1,0,0,0,0,0,0,0],
[0,1,1,1,1,0,1,1,0],
[0,1,0,1,0,0,1,0,0],
[0,1,0,1,1,1,1,1,0],
[0,1,0,0,0,1,1,0,0],
[0,1,0,1,1,0,1,1,0],
[0,1,0,1,0,0,0,1,0],
[0,1,1,1,0,1,1,1,0],
[0,0,0,0,0,1,0,0,0]]
laby3 =[ #pas de sortie
[0,1,0,0,0,0,0,0,0],
[0,1,1,1,1,0,1,1,0],
[0,1,0,1,0,0,1,0,0],
[0,1,0,1,1,1,1,1,0],
[0,1,0,0,0,1,1,0,0],
[0,1,0,1,1,0,1,1,0],
[0,1,0,1,0,0,0,1,0],
[0,1,1,1,0,1,1,1,0],
[0,0,0,0,0,0,0,0,0]]
def hauteur(tab):
return len(tab)
def largeur(tab):
return len(tab[0])
def afficher_grille(tab):
return tab
# a) renvoi la liste des cases voisines où je peux me déplacer
# b) [(1,1)] car on ne peut que se déplacer vers cette case depuis l'emplacement (0,1)
#Partie B
def voisins(T,v):
V = []
i, j = v[0],v[1]
for a in (-1,1):
if 0<=i+a<hauteur(T):
if T[i+a][j]==1:
V.append((i+a,j))
if 0<=j+a<largeur(T):
if T[i][j+a]==1:
V.append((i,j+a))
return V
def parcours(laby, entree, sortie):
tab = copy.deepcopy(laby)
p = Pile()
v = entree
tab[v[0]][v[1]] = 'x'
recherche = True
while recherche == True:
vois = voisins(tab, v)
if vois == []:
if p.est_vide():
return False
else:
v = p.depiler()
else:
p.empiler(v)
v = vois[0]
tab[v[0]][v[1]] = 'x'
if v == sortie:
p.empiler(v)
recherche = False
return p.afficher()
#1 tab←−copie de laby
#2 p←− Pile()
#3 v←− entree
#4 case v dans tab←− 0
#5 recherche ←− Vrai
#6 Tant Que recherche est Vraie
# 7 vois ← voisins(tab, v)
# 8 Si la liste vois est vide alors
# 9 Si p est vide alors
# 10 retourner Faux
# 11 sinon
# 12 v ←− p.depiler()
# 13 FinSi
# 14 sinon
# 15 on empile p avec v
# 16 v ←− 1er voisin
# 17 case v dans tab←− 0
# 18 Si v = sortie alors
# 19 on empile p avec v
# 20 recherche←− False
# 21 FinSi
#22 FinTantQue
#23 retourner p
Code : Tout sélectionner
class Maillon:
def __init__(self, valeur = None, suivant = None):
self.val = valeur
self.suiv = suivant
def __str__(self):
if self.val is not None:
return str(self.val) + "-" + str(self.suiv)
else:
return str(self.val)
class ListeC:
def __init__(self, premier = None, prem_suiv=None):
self.prem = Maillon(premier, prem_suiv )
def __str__(self):
return str(self.prem)
def __repr__(self):
return str(self.prem)
def est_vide(self):
return self.prem.val is None
def tete(self):
if self.prem.val is not None:
return self.prem.val
def longueur(self):
n = 0
c = self.prem
while c is not None:
n = n + 1
c = c.suiv
return n
def __getitem__(self, n):
if self.prem is None or n > self.longueur()-1:
raise IndexError("Indice invalide")
if n == 0 :
return self.prem.val
else:
cpt = 0
p = self.prem
while cpt < n:
cpt = cpt+1
p = p.suiv
return p.val
def ajoute(self, valeur):
"""
ajoute un élement en fin de liste
"""
m = Maillon(valeur)
if self.prem.val is None:
self.prem = m
else:
p = self.prem
while p.suiv is not None:
print(self.prem)
p = p.suiv
p.suiv = m
def ajoute_debut(self, valeur):
"""
ajoute un élement en debut de liste
"""
m = Maillon(valeur)
if self.prem.val is None:
self.prem = m
else:
p = self.prem
self.prem = m
m.suiv = p