RoadMap

  1. Step By Step
  2. Number of Partitions
  3. Fractals

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:

  1. Vous ne pouvez pas utiliser des variables globales.
  2. Vous ne pouvez pas utiliser des boucles.
  3. Vous ne pouvez ajouter structures auxiliaires comme un tableau.
  4. 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\).

Illustration des triangles de Sierpensky de différent ordres.

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 triangle
  • width: 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 triangle
  • width: 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.

Construction progressive du tapis de Sierpensky.

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:

Bon courage!!!