Partage

Exercices pour débutants en C

Au menu : zSommeChiffres (nombres, algo)

31 octobre 2008 à 10:00:28

Il n'y a rien de difficile à comprendre dans la récursivité, c'est juste une fonction qui s'auto-appelle pour effectuer la même action avec des paramètres différent.

Prenons par exemple une fonction de décomptage :
void decompte(int nombre)
{
    printf("%d\n", nombre);
    if(nombre > 0)
        decompte(nombre - 1);
}

Lors du premier appel de cette fonction, on va par exemple lui envoyer le nombre 8.
Elle va donc afficher 8, et, puisque 8 > 0, va s'appeler elle même en envoyant en paramètre 8 - 1.
Donc, lors du second appel, elle reçoit 7. Elle va afficher 7 et rebelote, elle va s'appeler encore une fois en envoyant en paramètre 7 - 1.
Cela va continuer jusqu'à 0 puisque on appelle la fonction tant que le nombre est supérieur à 0.
31 octobre 2008 à 10:16:55

Citation : jaloyan



Citation : zx-spectrum
U(n+1) = U(n) + 1

Tu est sur?

Je dirais plutôt :
U(n+1) = U(n) + U




je suis sur de ma formule :
exemple de ma suite
U(0)=0
U(1)= U(0) + 1 ---------> U(1)=1
U(2)= U(1) + 1 ---------> U(2)= U(1)+1 ---------> U(2)=2
par un raisonnement réccurent on a
U(n+1) = U(n) +1
et non pas U(n+1) = U(n) + U ?
C'est tellement simple, que t'y perd ton latin ! :p
Ici la solution récursive est simple a trouver pour le cas des suites numériques et aussi pour le calcul des factorielles(c'est un autres exemple de suite) que tu définis par :
U(n+1) = U(n) * (n+1) avec n >0;

Merci Brugnar pour ta reponse, c'est beaucoup plus clair de la facon dont tu l'expliques. :)

31 octobre 2008 à 10:25:51

Citation : zx-spectrum

Citation : jaloyan



Citation : zx-spectrum
U(n+1) = U(n) + 1

Tu est sur?

Je dirais plutôt :
U(n+1) = U(n) + U




je suis sur de ma formule :
exemple de ma suite
U(0)=0
U(1)= U(0) + 1 ---------> U(1)=1
U(2)= U(1) + 1 ---------> U(2)= U(1)+1 ---------> U(2)=2
par un raisonnement réccurent on a
U(n+1) = U(n) +1
et non pas U(n+1) = U(n) + U ?
C'est tellement simple, que t'y perd ton latin ! :p
Ici la solution récursive est simple a trouver pour le cas des suites numériques et aussi pour le calcul des factorielles(c'est un autres exemple de suite) que tu définis par :
U(n+1) = U(n) * (n+1) avec n >0;

Merci Brugnar pour ta reponse, c'est beaucoup plus clair de la facon dont tu l'expliques. :)



AH si tu parlais de factorielles à travers ton U, j'ai compris, je pensais que tu faisais du développement de calculs.

Car en effet, soit U et n deux nombre réels,

U(n + 1) = U(n) + U * 1 = U(n) + U

simple développement de débutant.

Mais c'est peut être moi qui ait mal compris ton énoncé.
31 octobre 2008 à 12:04:00

Citation : Jaloyan1


Car en effet, soit U et n deux nombre réels,

U(n + 1) = U(n) + U * 1 = U(n) + U



Le jour venu, tu comprendras. Sache juste que non, ça ne se développe pas.
31 octobre 2008 à 12:07:03

U est une fonction ou un nombre?

car c'est toute la différence.
31 octobre 2008 à 12:18:30

Citation : Jaloyan1

U est une fonction ou un nombre?

car c'est toute la différence.


Je pense qu'il s'agit plutôt d'un shadok.
31 octobre 2008 à 14:23:29

Puisqu'on est en plein sur le thème de la récursivité... j'ai un autre exemple pour ceux qui veulent comprendre comment ça fonctionne.

Imaginons un tableau d'entiers naturels distincts, rempli avec des valeurs quelconques.
Exemple: tab = {5, 8, 64, 30, 27, 2, 41, 12, 88, 61} (10 valeurs)
Vous souhaitez écrire un algorithme afin de trouver la valeur minimale de ce tableau.
Imaginons une fonction mintab(tab, n), capable de renvoyer la plus petite des n valeurs de tab.

La solution qui vous semble la plus évidente est je pense, une solution itérative, qui consiste à parcourir le tableau de case en case, et de le comparer avec le plus petit nombre déjà trouvé.
Concrètement...
fonction mintab(tab, n):
    min = tab[0]
    Pour i allant de 1 à (n - 1)
    - Si tab[i] < min
    --- min = tab[i]
    retourner min

Ainsi, dans cet algorithme, à tout instant, min contient le plus petit nombre entre T[0] et T[i] (c'est ce qu'on appelle un invariant de boucle... c'est juste pour info, pas besoin de le retenir pour comprendre) et donc à la fin de la boucle, min contient le plus petit nombre de tout le tableau.

Maintenant, imaginons une autre façon d'écrire cette fonction, sans aucune boucle cette fois.
Impossible vous vous dites ? Peut-être pas...
La seule façon de trouver un quelconque minimum, y compris dans la solution précédente, est de comparer des nombres 2 à 2 (grâce à l'opérateur < ).
mintab est très simple si n = 2, c'est à dire que le tableau n'a que 2 cases, puisqu'on sait comparer 2 valeurs entre elles. Il suffit alors de retourner le plus petit entre tab[0] et tab[1].
Mais si n > 2, comment faire sans boucle ?
Eh bien il suffit tout simplement de remarquer, en observant le tableau, que le minimum de ce tableau correspond en réalité au minimum entre
1. La première case du tableau tab[0]
2. Le minimum du sous-tableau {tab[1], tab[2], tab[3], ..., tab[n - 1]}
Et quel est le minimum de ce sous-tableau ss_tab = {tab[1], tab[2], tab[3], ..., tab[n - 1]} ? Eh bien c'est tout simplement le minimum entre
1. La première case de ce sous-tableau ss_tab[0]
2. Le minimum du sous-tableau {ss_tab[1], ss_tab[2], ss_tab[3], ..., ss_tab[n - 1]}
Et ainsi de suite... jusqu'à ce qu'on ait plus qu'un sous-tableau de 2 cases, dont le minimum serait très facile à trouver

Ainsi, la fonction mintab peut s'écrire également de la façon suivante:
fonction mintab(tab, n):
    // Soit on est dans le cas ou le tableau n'a que 2 cases
    Si n == 2
    - Si tab[0] < tab[1]
    --- retourner tab[0]
    - Sinon
    --- retourner tab[1]

    // Soit on est dans le cas plus complexe ou le tableau a plus de 2 cases
    // et il faut rappeler la fonction sur le sous tableau tab[1 .. (n-1)]
    min = mintab(tab[1 .. (n-1)], n - 1)
    // On peut maintenant comparer tab[0] avec le minimum de ce sous-tableau
    Si tab[0] < min
    - retourner tab[0]
    Sinon
    - retourner min

Voila donc la solution récursive au problème.

Et concrètement en C, qu'est-ce que ça donnerait ?

#include <stdio.h>

int mintab(int tab[], size_t size) {
    /*  tab contient size valeurs. Ses indices vont donc de 0 à (size - 1). */
    int min;

    /*  si le sous-tableau tab contient 2 valeurs
        alors on retourne la plus petite de ces valeurs. */
    if(size == 2) {
        return tab[0] < tab[1] ? tab[0] : tab[1];
    }

    /*  on rappelle la fonction sur le sous-tableau
        de (size - 1) cases formé de tab[1] jusqu'à tab[size - 1]. */
    min = mintab(tab + 1, size - 1);

    /*  ainsi, la plus petite valeur du sous-tableau tab correspond à
        la plus petite valeur entre sa case d'indice 0, et le minimum du sous-tableau formé à partir de tab[1]. */
    return tab[0] < min ? tab[0] : min;
}

int main(void) {
    int tab[10] = {5, 8, 64, 30, 27, 2, 41, 12, 88, 61};
    printf("%d\n", mintab(tab, 10));
    return 0;
}

Qui donne à l'exécution:
2

Process returned 0 (0x0)   execution time : 0.057 s
Press any key to continue.

31 octobre 2008 à 14:30:45

Citation : Jaloyan1



Je n'ai pas pu le tester ton code, car il y a un truc qui me chatouille bien ,essaie ton code avec 1 base 10 et base 2 en 2eme arg.



Pourquoi n'as-tu pu tester le code ? Tu remplaces la fonction conversion de yoch par ma fonction conversion_. Et je n'ai pas vu de problème avec les données que tu proposes.

#include <stdio.h>

static char digit[] = "0123456789ABCDEF";

void conversion_(int nombre, int base)
{
  if (nombre != 0)
    {
      conversion_(nombre / base, base);
      putchar(digit[nombre % base]);
    }
}



void conversion(int nombre, int base)
{
  int quotien, reste;

  quotien = nombre / base;
  reste = nombre % base;
  if (quotien != 0)
    conversion(quotien, base);
  putchar(digit[reste]);
}



int main(void)
{
  int nombre, base = 17;

  puts("entrez le nombre en decimal");
  scanf("%d", &nombre);
  while (base > 16 || base < 2)
    {
      puts
        ("entrez la base auquelle vous voulez convertir votre nombre [2-16]");
      scanf("%d", &base);
    }
  printf("%d en base %d est egal a ", nombre, base);
  conversion_(nombre, base);
  printf("\n");
  conversion(nombre, base);
  return 0;
}


candide@candide-desktop:~$ ./x
entrez le nombre en decimal
5
entrez la base auquelle vous voulez convertir votre nombre [2-16]
2
5 en base 2 est egal a 101
101candide@candide-desktop:~$ ./x
entrez le nombre en decimal
1
entrez la base auquelle vous voulez convertir votre nombre [2-16]
2
1 en base 2 est egal a 1
1candide@candide-desktop:~$
31 octobre 2008 à 17:11:19

A quand la correction de l'exercice au fait ?
31 octobre 2008 à 18:23:46

Correction pour zBinary



Envois des résultats à réponse : 10

Enfin la correction. :) L'exercice consistait à la base à convertir un nombre de la base décimale vers la base binaire. C'est donc cet exercice que je corrigerais et je ne donnerais pas de fonction générique car c'est hors-sujet.
Plusieurs méthodes (algorithmes) étaient possibles afin de résoudre l'exercice. Je vais en citer trois :
  • Par divisions successives
  • Par soustractions successives
  • Par accès aux bits avec l'opérateur &

Divisions successives


C'est l'algorithme que la plupart des participants ont codé, c'est aussi le plus connu. On trouve les valeurs binaires à partir des restes des divisions par 2 (à l'aide de l'opérateur %). L'implémentation récursive était conseillée car plus simple que l'itérative et elle reste logique :
void bin(unsigned val)
{
    if(val == 0) return;
    bin(val/2);
    putchar((val%2)? '1':'0');
}

On exploite, avec ce code, la pile d'appel. Les valeurs sont "écrites" dans la pile d'appel et dés que les appels récursifs cessent (val==0), On affiche les résultats des modulos (dans un ordre inverse à l'ordre des calcules). Voyons cela de plus près :
Appel de bin(25)
    val = 25 donc != 0
    Appel de bin(12)
        val = 12 donc != 0
        Appel de bin(6)
            val = 6 donc != 0
            Appel de bin(3)
                val = 3 donc != 0
                Appel de bin(1)
                    val = 1 donc != 0
                    Appel de bin(0)
                        val = 0 donc Arrêt
                On affiche 1%2 donc 1
            On affiche 3%2 donc 1
        On affiche 6%2 donc 0
    On affiche 12%2 donc 0
On affiche 25%2 donc 1

Au final, on affiche bien 11001 qui équivaut à 25 en binaire ! ;)

Soustractions successives


Il existe un autre algorithme dans lequel on utilise les soustractions. Un petit exemple pour vous l'expliquer :

Nous voulons convertir 25 en binaire
Nous allons chercher la dernière puissance de 2 inférieur à 25 donc 16

25 >= 16 est vrai : on affiche 1
25 >= 16 donc : on continu avec 25-16 (9) et 16/2 (8)
9 >= 8 est vrai, on affiche 1
9 >= 8 donc : on continu avec 9-8 (1) et 8/2 (4)
1 >= 4 est faux, on affiche 0
1 < 4 donc : on continu avec 1 et 4/2 (2)
1 >= 2 est faux, on affiche 0
1 < 2 donc : on continu avec 1 et 2/2 (1)
1 >= 1 est vrai, on affiche 1


Encore une fois, cela fonctionne bien, on affiche 11001.
Voici une implémentation possible que je vous propose :
void bin(unsigned val)
{
    unsigned twoPow = 1;
    for(; twoPow <= val ; twoPow*=2){}
    for(twoPow/=2 ; twoPow >=1 ; twoPow/=2)
    {
        if(val >= twoPow){
            val -= twoPow;
            putchar('1');}
        else putchar('0');
    }
}


Accès aux bits avec l'opérateur &


Le dernier algorithme que je vais vous proposer exploite l'opérateur bitwise &. Il compare les bits de deux nombres deux à deux en renvoyant 1 si les deux bits valent 1 ou sinon 0 (on dit que c'est "l'un et l'autre"). Mais comment lire les bits avec & ? C'est plus simple que vous ne le pensez : Une puissance de deux en binaire a la même apparence qu'une puissance de dix en décimal (1 vaut 1, 2 vaut 10, 4 vaut 100, 8 vaut 1000, 16 vaut 10000, etc...). On n'a donc qu'à utiliser & entre la valeur à convertir et une puissance de deux pour savoir si le bit "correspondant" à la puissance de deux vaut 1.
Par exemple : 25 est stocker dans un octet qui vaut alors 00011001. Si l'on fait 25&16 on a :

-> 00011001
-> 00010000
&> 00010000


Par contre si le bit correspondant à 16 vaut 0, on obtient :


-> 00001001
-> 00010000
&> 00000000


Si le bit "lu" (par la puissance de deux) vaut 0, & renvoi 0 et dans le cas contraire, & renvoi un nombre forcément différent de 0. A partir de là, on peut très facilement lire l'ensemble des bits d'un nombre stocké en mémoire vive :
void bin(unsigned val)
{
    unsigned twoPow = 1;
    for(; twoPow <= val ; twoPow*=2){} //On trouve la puissance de deux de départ
    for(twoPow/=2 ; twoPow >= 1 ; twoPow/=2)
        putchar((twoPow & val)?'1':'0');
}


Merci pour votre participation ! :)
31 octobre 2008 à 20:00:58

en effet, c'était simple cet exo, à quand le suivant?
31 octobre 2008 à 21:58:19

merci pour les solutions commentées, pour ma part j'avais trouvé que la première, j'analyse la dernière qui me semble être "un masquage" de bits
1 novembre 2008 à 2:02:43

Les solutions proposées me semblent excellentes (néanmoins le premier et le dernier code ne savent pas traiter l'entrée 0). Je pense qu'il aurait été bien de donner la solution itérative naturelle aussi.

Il existe une autre méthode : le langage C sait convertir de lui-même en base 16 ou 8 via la fonction fprintf(), voici un exemple pour ceux qui ne connaissent pas :


#include <stdio.h>

int main(void)
{
  char ch[5] = { 0 };
  int n = 2009;

  sprintf(ch, "%x", (unsigned) n);
  printf("%d en base 16 : %s\n", n, ch);
  sprintf(ch, "%o", (unsigned) n);
  printf("%d en base  8 : %s\n", n, ch);

  return 0;
}


2009 en base 16 : 7d9
2009 en base  8 : 3731


A partir de là, la conversion de la base 16 ou 8 vers la base 2 est facile, c'est juste des regroupements de chiffres (octaux ou hexadécimaux) suivis du remplacement par l'équivalent en base 2. Lors de l'affichage, il vaut veiller à supprimer les éventuels zéros dominants. Voilà ce que ça donne, c'est certes plus compliqué que les précédentes solutions mais le principe est différent.


#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <limits.h>

int convertir(int n)
{
  int k;
  char ch[(sizeof(int) * CHAR_BIT) / 3 + 2] = { 0 };
  char *t[8] = { "000", "001", "010", "011", "100", "101", "110", "111" };
  int n8 = sprintf(ch, "%o", n);        /* le nombre de chiffres en octal */

  printf("%ld", strtol(t[ch[0] - '0'], NULL, 10));      /* car pas de zeros
                                                           dominants */
  for (k = 1; k < n8; k++)
    printf("%s", t[ch[k] - '0']);

  printf("\n\n");
  return 0;
}

int main(void)
{
      printf("Entier a convertir en base 2 (-1 pour quitter):\n");
  while (1)
    {
      int n;

      scanf("%d", &n);
      if (n == -1)
        break;
      else
        convertir(n);
    }
  return 0;
}
Entier a convertir en base 2 (-1 pour quitter):
2009
11111011001

1
1

0
0

1024
10000000000

4095
111111111111

-1
1 novembre 2008 à 11:32:02

en effet, ca pourrait être comme cela aussi, mais au niveau vitesse, je me demande lequel de ces trois fonctions est la plus rapide.
1 novembre 2008 à 13:58:15

U(n+1) = U(n)+ U?? :o
C'est quoi U la dedans? :-°
Non je pense que c'est bien U(n+1) = U(n) + 1 dans la cas ou les valeurs sont 1 2 3 4 5 6 7 ... :)
1 novembre 2008 à 14:00:06

Titre : zTri
N° et mois : 1, novembre
Sujet : Récupération des secondes système, comparatif de tris

Objectif



L'objectif de cet exercice est de réaliser un comparatif de différents algorithmes de tri en O(n²). Pour cela, vous devez savoir comment récupérer les secondes système (time.h) et connaître quelques algorithmes de tri en O(n²). En voici trois :
  • Le tri à bulles
  • Le tri par sélection
  • Le tri par insertion
On peut par exemple avoir :
Combien d'éléments voulez-vous trier ? 50000
Tri par insertion en cours ... 12 secondes
Tri par sélection en cours ... 8 secondes
Tri à bulles en cours ........ 15 secondes

Et pourquoi pas faire un petit classement à la fin. :)
Le but est bien sur que vous essayez d'implémenter les algorithmes de tris par vous-même et il serait aussi bien de compter le nombre de comparaisons/échanges pour chaque algo. ;)
http://www.siteduzero.com/forum-83-329 [...] html#r3108402

Bonne chance ! ;)
1 novembre 2008 à 14:20:12

Citation : crys'


L'objectif de cet exercice est de réaliser un comparatif de différents algorithmes de tri en O(n²).(...)
Je ne vous demande pas d'implémenter ces tris (sauf si vous y tenez), vous trouverez les fonctions de ces tris à la pelle sur internet et même certains sur le SdZ.



Si les tris ne sont pas implémentés, je vois pas l'intérêt, l'exercice devient très limité. Et implémenter ces algorithmes est relativement aisé pour ne pas dire obligatoire à connaitre. S'il faut aller chercher du code sur Internet, il faudra adapter l'interface ce qui n'est pas forcément commode.

Par ailleurs, pour que l'exercice soit vraiment intéressant, il serait bien que les nombres de comparaisons et de copies d'éléments effectuées soient comptabilisés et comparés.

1 novembre 2008 à 14:33:41

Hum, j'y avait bien pensé mais es-tu sur que ce soit à la portée des débutants ?
1 novembre 2008 à 14:44:43

Citation : crys'

Hum, j'y avait bien pensé mais es-tu sur que ce soit à la portée des débutants ?



Pensé à quoi ? Implémenter les tris ou compter les comparaisons + recopies ?

Pour ce qui est de l'implémentation des tris, bien sur que c'est à la portée d'un débutant, conceptuellement c'est très simple (le tri à bulle est le moins simple) et d'un point de vue des techniques de C requises, c'est le minimum syndical (boucles, conditions, tableau, fonctions). Donc oui, ça me parait tout à fait à la portée du débutant mais je reconnais qu'il y a des débutants qui n'ont aucun gout à coder de petits algorithmes et là, ne pas y arriver, c'est donc plus une affaire d'absence d'intéret et de motivation que d'incapacité intellectuelle.
1 novembre 2008 à 16:31:12

je trouve que le principe de comparaison des secondes ne sert pas à grand chose.
1 novembre 2008 à 16:38:06

Citation : Jaloyan1

je trouve que le principe de comparaison des secondes ne sert pas à grand chose.



Tu viens de découvrir la définition d'exercice, bravo. Personne n'a jamais dit que ça devait "servir à quelque chose", c'est pour s'entrainer, c'est tout.
1 novembre 2008 à 16:41:15

Citation : Goost

Citation : Jaloyan1

je trouve que le principe de comparaison des secondes ne sert pas à grand chose.



Tu viens de découvrir la définition d'exercice, bravo. Personne n'a jamais dit que ça devait "servir à quelque chose", c'est pour s'entrainer, c'est tout.



Tu me fais penser à Prologin. :)
1 novembre 2008 à 16:52:56

Bonsoir,

Je tenais a mettre ma solution au zBinary si elle ne serait pas proposée (méthode opérateurs binaires).

Voici :

#include <stdio.h>
#include <limits.h>

void affichage_binaire(unsigned int n)
{
    int i;
    for (i = (sizeof(n)*CHAR_BIT)-1 ; i >= 0 ; i--)
        putchar( ((n >> i)&1) ? '1' : '0');
    putchar('\n');
}

Soit encore mieux :
#include <stdio.h>
#include <limits.h>

void affichage_binaire(unsigned int n)
{
    int i;
    for (i = (sizeof(n)*CHAR_BIT)-1 ; i >= 0 ; i--)
        putchar( ((n >> i)&1) + '0');
    putchar('\n');
}


EDIT : correction du code...
1 novembre 2008 à 17:59:33

Citation : yoch

Bonsoir,

Je tenais a mettre ma solution au zBinary si elle ne serait pas proposée (méthode opérateurs binaires).

Voici



C'est très proche de la 3ème méthode proposée par l'auteur (la seule différence c'est que tu utilises un nouvel opérateur binaire). Et ton code n'est pas satisfaisant car il ne supprime pas les zéros dominants voire faux dans le second cas (moi j'ai un '1' qui apparait comme bit dominant).
1 novembre 2008 à 18:08:10

Citation : candide

Et ton code n'est pas satisfaisant car il ne supprime pas les zéros dominants voire faux dans le second cas (moi j'ai un '1' qui apparait comme bit dominant).


Pourrais tu expliquer ?
1 novembre 2008 à 18:23:34

Citation : yoch


Pourrais tu expliquer ?



Voilà ce que mon dernier essai donne :

#include <stdio.h>
#include <limits.h>

void affichage_binaire(unsigned int n)
{
    int i;
    for (i = sizeof(n)*CHAR_BIT ; i >= 0 ; i--)
        putchar( ((n >> i)&1) ? '1' : '0');
    putchar('\n');
}

int main(void)
{
   affichage_binaire(5);
  return 0;
}


candide@candide-desktop:~$ ./x
100000000000000000000000000000101
candide@candide-desktop:~$
1 novembre 2008 à 18:58:59

Citation : candide

Citation : yoch


Pourrais tu expliquer ?



Voilà ce que mon dernier essai donne :

#include <stdio.h>
#include <limits.h>

void affichage_binaire(unsigned int n)
{
    int i;
    for (i = sizeof(n)*CHAR_BIT ; i >= 0 ; i--)
        putchar( ((n >> i)&1) ? '1' : '0');
    putchar('\n');
}

int main(void)
{
   affichage_binaire(5);
  return 0;
}



candide@candide-desktop:~$ ./x
100000000000000000000000000000101
candide@candide-desktop:~$


Oula, désolé, c'est une bête erreur d'algo...

#include <stdio.h>
#include <limits.h>

void affichage_binaire(unsigned int n)
{
    int i;
    for (i = sizeof(n)*CHAR_BIT ; i > 0 ; i--)
        putchar( ((n >> i)&1) ? '1' : '0');
    putchar('\n');
}

int main(void)
{
   affichage_binaire(5);
  return 0;
}


J'édite mon post plus haut...
1 novembre 2008 à 19:30:13

Citation : yoch


J'édite mon post plus haut...



Le problème n'est toujours pas résolu.
1 novembre 2008 à 19:46:24

bonjour

Citation : crys

L'objectif de cet exercice est de réaliser un comparatif de différents algorithmes de tri en O(n²). Pour cela, vous devez savoir comment récupérer les secondes système (time.h) et connaître quelques algorithmes de tri en O(n²). En voici trois :

Le tri à bulles
Le tri par sélection
Le tri par insertion



peux tu stp nous doner un type bien definie de structure a trier ?