Thursday, May 25, 2006
Révisions : quand l'algorithmique creuse...
Comme bon nombre de personnes aiment à le répéter, les mathématiques jouent souvent un rôle primordial dans les choses de la vie. Ayant commencé à réviser (découvrir...) mon cours d'algorithmique, je viens d'avoir l'occasion de me pencher sur le problème suivant : "Quel est le nombre de parts maximum de pizza que l'on peut obtenir en donnant x coups de couteaux dans celle-ci?".
Comme pour toute application strictement mathématique, on va devoir se définir des limites à notre abstraction :
- la pizza est en fait un plan de R² (une pizza infinie, en somme);
- les parts de pizzas n'ont rien à voir avec des parts triangulaires traditionelles, quand le mathématicien a faim, il ne s'en préoccupe pas.
Déterminons une équation de récurrence :
Soit T(n) le nombre maximum de parts obtenu avec n coups de couteau, cherchons à exprimer ce nombre de façon empirique :
¶ 17:06 
Comme pour toute application strictement mathématique, on va devoir se définir des limites à notre abstraction :
- la pizza est en fait un plan de R² (une pizza infinie, en somme);
- les parts de pizzas n'ont rien à voir avec des parts triangulaires traditionelles, quand le mathématicien a faim, il ne s'en préoccupe pas.
Déterminons une équation de récurrence :
Soit T(n) le nombre maximum de parts obtenu avec n coups de couteau, cherchons à exprimer ce nombre de façon empirique :
On remarque que T(1) = 2; T(2) = 4; T(3) = T(2) + 3; ...
T(n) = T(n-1) + n
Voici donc notre équation de récurrence qui nous permet de calculer le nouveau nombre de part en connaissant le nombre de parts précédent.
Preuve
- quand on ajoute une nième droite D(n), on augmente le nombre de régions de k >= 0 : T(n) = T(n-1) + k, k >=0;
- quelle est la valeur maximum prise par k? La nième droite D(n) peut couper les n-1 autres droites au plus en n-1 points donc cela engendre au plus n nouvelles régions. k <= n ; - T(n) = T(n-1) + n ; T(1) = 2.
Résolution
Elle se fait par la méthode des facteurs sommants :
T(n) = T(n-1) + n
+ T(n-1) = T(n-2) + n-1
+ ...
+ T(2) = T(1) + 2
+ T(1) = 2
________________________
T(n) = n + n-1 + n-2 + ... + 2 + 1 + 1 = n(n+1)/2 +1
Pour n coups de couteaux, on peut donc avoir un maximum de [n(n+1)/2] +1 parts de pizza. A noter que ça serait plus judicieux d'adapter ça au cas réel où toutes les droites se coupent au centre de la pizza, en donnant aussi un angle limite minimal pour savoir si une portion peut toujours être considérée comme une part. Et comme dirais John Macadam Jr. , il faudrait aussi rajouter une dimension à l'espace, juste pour la garniture :)
Je laisse aussi le soin à John de se délecter de la part #3 ... oui, celle dépourvue de cROUTE (humhum..).
Well, étonnant, non?
T(n) = T(n-1) + n
Voici donc notre équation de récurrence qui nous permet de calculer le nouveau nombre de part en connaissant le nombre de parts précédent.
Preuve
- quand on ajoute une nième droite D(n), on augmente le nombre de régions de k >= 0 : T(n) = T(n-1) + k, k >=0;
- quelle est la valeur maximum prise par k? La nième droite D(n) peut couper les n-1 autres droites au plus en n-1 points donc cela engendre au plus n nouvelles régions. k <= n ; - T(n) = T(n-1) + n ; T(1) = 2.
Résolution
Elle se fait par la méthode des facteurs sommants :
T(n) = T(n-1) + n
+ T(n-1) = T(n-2) + n-1
+ ...
+ T(2) = T(1) + 2
+ T(1) = 2
________________________
T(n) = n + n-1 + n-2 + ... + 2 + 1 + 1 = n(n+1)/2 +1
Pour n coups de couteaux, on peut donc avoir un maximum de [n(n+1)/2] +1 parts de pizza. A noter que ça serait plus judicieux d'adapter ça au cas réel où toutes les droites se coupent au centre de la pizza, en donnant aussi un angle limite minimal pour savoir si une portion peut toujours être considérée comme une part. Et comme dirais John Macadam Jr. , il faudrait aussi rajouter une dimension à l'espace, juste pour la garniture :)
Je laisse aussi le soin à John de se délecter de la part #3 ... oui, celle dépourvue de cROUTE (humhum..).
Well, étonnant, non?
