Bien que mon TIPE ne soit pas exactement orienté option informatique, une question qui est tombée lors de mes oraux blancs portait sur la complexité de mon algorithme. Et comme une de mes fonctions utilise un random.randrange, j'ai pu répondre pour le meilleur cas, mais je me suis retrouvé bien désarmé quant à la complexité en moyenne.
Présentation de la fonction posant problème :
- J'ai à disposition un tableau TAB de taille n*n (en gros, une grille), et je souhaite poser aléatoirement sur cette grille un nombre X d'avions. Bien évidemment, on ne peut pas avoir deux avions sur la même case. Pour déterminer le nombre d'avions déjà posés, on dispose également d'un compteur C. On a également X <= n².
- Pour ce faire, j'ai un pseudo-code du genre :
Code : Tout sélectionner
C = 0
while C != X :
(i,j) = rd.randint(0, n), rd.randint (0,n) #On affecte à i et j deux entiers aléatoires de [0, n]
if not TAB[i][j] : #Les avions sont étiquetés par un nombre différent de 0, donc si TAB[i][j] == 0, c'est que la case est libre
TAB[i][j] == C
C += 1
Merci d'avance !