Homework on Fractals
RoadMap
1. Step By Step
IsPalindrome(*)
Dans ce premier exercice, on vous demande d’écrire une fonction récursive
qui vérifie si une chaine sring
est Palindrome ou non.
Une chaine est palindrome si elle se lit de droite a gauche comme de gauche a droite.
Par exemple la chaine madam
est palindrome.
Voici le lien isPalindrome de l’exercice.
Contraintes:
- Vous ne pouvez pas utiliser des variables globales.
- Vous ne pouvez pas utiliser des boucles.
- Vous ne pouvez ajouter structures auxiliaires comme un tableau.
- Vous devez ignorer la casse. i.e ne faite pas la différence entre majuscule et minuscules.
CountBy(**)
Cet exercice vous demande d’écrire une fonction récursive countToBy
qui
reçoit deux entiers \(n\) et \(m\) et qui affiche une séquence qui saut par
\(m\) jusqu’à atteindre \(n\). Voici une liste d’exemples pour comprendre
cette fonction:
// compter jusqu'a 10 en sautant par 1
countToBy(10, 1); // affichera 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
// compter jusqu'a 30 en sautant par 4
countToBy(30, 4); // affichera 2, 6, 10, 14, 18, 22, 26, 30
Noter qu’on commence par forcement par \(1\). Par exemple dans le deuxième appel, on a commence par 2 pour pouvoir atteindre exactement 30 a la fin!!
Voici le lien countToBy de l’exercice.
En cas ou \(m\) ou \(n\) sont strictement inférieur a \(1\), vous devez envoyer une
exception
entière e.
Par exemple si la valeur finale notée \(n\) est inférieure a 1, on exécute le code suivant:
//lancer une exception en cas ou n est inferieur a 1
if ( n < 1)
throw n;
Combin (***)
Dans ce défi, on vous demande d’écrire une fonction récursive combin
qui accepte deux
entiers n et k et qui renvoie le nombre de combinaison
\(C_n^k\).
On rappelle que la formule de cette combine est donne par:
\[C_n^k = \dfrac{n!}{k!(n - k)!}\]Malheureusement, cette définition ne vas vous aider dans extraire la relation de récurrence. Visiter cette page Wikipedia pour voir la liste de formules utiles.
Voici le lien de l’exercice avec des tests: Combin.
Ce défi est difficile et nécessite la technique de Memoization presentee dans la lecture.
2. Number of Partitions (**)
On définit nombre de partitions
d’un entier positif \(n\) en utilisant au max
\(m\) comme le nombre d’alternatives pour décomposer \(n\) en une somme de
nombres inférieur a \(m\) en séquence croissante.
Prenons par exemple l’entier \(n=6\) et la partie max \(m=4\). Alors on peut trouver \(\mathbf{9}\) façons pour décomposer \(n\). Voici la liste de ces décomposition:
1. 6 = 2 + 4
2. 6 = 1 + 1 + 4
3. 6 = 3 + 3
4. 6 = 1 + 2 + 3
5. 6 = 1 + 1 + 1 + 3
6. 6 = 2 + 2 + 2
7. 6 = 1 + 1 + 2 + 2
8. 6 = 1 + 1 + 1 + 1 + 2
9. 6 = 1 + 1 + 1 + 1 + 1 + 1
Votre tâche (si vous l’acceptez) consiste a écrire une fonction
count_partitions(n, n)
qui renvoie le nombre de partitions comme expliqué.
Dans le projet partitions.zip , vous trouver le code de départ avec des tests unitaires qui vous de devez passer.
Indice 1: Essayez de proposer une récurrence sur \(m\) qui représente le nombre maximal pour un terme dans la somme.
Indice 2: Dans l’exemple précédant, quel est la différence entre les deux premiers lignes et le reste?
3. Fractals
Sierpensky
Dans cet exercice, on doit dessiner le Triangle de Sierpensky en utilisant les objets graphiques de la bibliothèque de Stanford.
Comme le montre la figure, un triangle de Sierpensky est tout simplement un
triangle isocèle rempli. Un triangle de Sierpensky est la superposition de
trois
triangles de Sierpensky d’ordre \(1\).
Dans le projet Sierpensky.zip , vous trouverez
le code départ qui demande a l’utilisateur un entier order
et qui doit afficher
le triangle de Sierpensky de set ordre.
Votre role est de remplir la fonction:
void Sierpensky( GWindow &app, float x, float y , float width, int order)
Où:
app
: est la fenêtre ou on doit afficher le triangle.x, y
: représente les coordonnes du premier point du trianglewidth
: est la longueur de chaque arrête.order
: est l’ordre du triangle.
Afin de vous aider, le code fournit une fonction prête pour tracer un triangle rempli:
void draw_triangle(GWindow &app, float x, float y, float width)
Où:
app
: est la fenêtre ou on doit afficher le triangle.x, y
: représente les coordonnes du premier point du trianglewidth
: est la longueur de chaque arrête.
Sierpensky Carpet
Le tapis de Sierpiński (1916), du nom de Wacław Sierpiński, est une fractale obtenue à partir d’un carré. Le tapis se fabrique en découpant le carré en neuf carrés égaux avec une grille de trois par trois, et en supprimant la pièce centrale, et en appliquant cette procédure indéfiniment aux huit carrés restants.
Dans le projet carpet.zip , vous trouvez le code de la fonction
void carpet(GWindow &win, int x, int y, int width , int order)
ou:
win
: est la fenêtre d’affichage.x, y
: la position de carpet dans la fenêtre.width
: est la longueur de carpet.order
: est l’ordre du carpet.
Afin de tracer un rectangle dans une fenêtre vous utiliser le code suivant:
// ajouter un rectangle dans le point (x, y) de longueur [width]
GRect * rect = new GRect(x, y, width, width);
//remplir le rectangle
rect->setFilled(true);
//ajouter le triangle a la fenetre
win.add(rect);
Votre tache est de produire le tapis d’ordre \(5\), comme le montre le figure suivante: