Partage

Exercices pour débutants en C

Au menu : zSommeChiffres (nombres, algo)

<< 1 ... 47 48 49 ... 55 >>

28 janvier 2010 à 13:36:28

Citation : darkipod

Merci Candide pour ton lien sur les combinaisons, j'entreperçois enfin
votre débat sur le sujet
en fait si j'ai bien compris :
123456789
912345678
891234567
....
ont la même somme de leur chiffre, et si j'ai bien suivi
votre algo évite de calculer "plusieurs fois" la même chose !

Non, mon algo n'utilise pas du tout les combinaisons avec répétitions (dont l'intérêt aurait été qu'on dispose d'une formule explicite avec des factorielles) et jusqu'à présent personne ici n'a utilisé de façon efficace quelque chose de similaire.

Mon algorithme (et celui de Gurney) est un algorithme de programmation dynamique et qui d'un point de vue pratique reste très efficace.

darkipod

28 janvier 2010 à 13:59:43

merci pour la lecture

je vais etudier le tuto de yoch sur le sujet, pour essayer de vous suivre :-°

PS: apres deux petites heures de reflections.
si on considere un nombre sur 9 positions :
ex : 9 8 7 6 5 4 3 2 1
comme l'a dit pouet_forever on a 9! cas ou on obtient le même nombre pour la somme des chiffres
soit 9x8x7x6x5x4x3x2x1 = 362880 cas ou on obtient la même chose
si je compare à 999999999 cela represente 0.03% ou on obtient la même chose ?
Avec mon raisonnement on devrait gagner 0.03% de temps à l'execution ?
question : pourquoi se tracasser les meninges pour si peu ?
Ou bien
je me suis trompé quelque part, ou j'ai loupé quelque chose ? :-°

colbseton

30 janvier 2010 à 0:00:31

Je poste mes solutions, certainement les plus naïves.

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

int Zsomme_int(int n)
{
    int s=0;

    while(n)
    {
        s += n%10;
        n/=10;
    }
    return s;
}

int Zsomme_char(char *scr)
{
    int s=0, i;

    for(i=0; scr[i]!='\0'; i++)
        s+= scr[i] - '0';
    return s;
}

int somme_egale(int n,int s_voulue)
{
    int c=0, i=0;

    for(; i<n; i++)
        if(Zsomme_int(i)==s_voulue)
            c+=1;
    return c;
}

int main(void)
{
    int n = 92538;
    char *chaine = "92538";

    printf("%d -> %d\n", n , Zsomme_int(n));
    printf("%d\n", Zsomme_char(chaine));
    printf("%d", somme_egale(1000, 27));

    return 0;
}

candide

30 janvier 2010 à 0:29:16

Citation : Colb-Seton

Je poste mes solutions, certainement les plus naïves.
#include <stdio.h>
#include <stdlib.h>

Ton code est presque

parfait, il y a juste à retirer le 2ème #include qui est inutile.

colbseton

30 janvier 2010 à 10:30:27

J'y pense jamais, mon IDE me le met automatiquement

.
Merci.

Anonyme

30 janvier 2010 à 10:43:42

S'il te plaît, mets ton code entre balises secret!

fondation

30 janvier 2010 à 10:50:28

Bonjour.

Je pense que vous êtes tous nuls.
Pour cette fonction nous n'avons pas besoin d'utiliser des chaines de caractères ou des tableaux.
Voici mon algorithme, simple et concis :
Image utilisateur

Nous utilisons des divisions entière par dix, et donc nous décalons les chiffres vers la gauche tout en récupérant les restes que nous les additionnons entre eux.

Voilà un pro.

Au revoir.

Anonyme

30 janvier 2010 à 11:03:02

Euh, c'est ironique ?

colbseton

30 janvier 2010 à 11:18:51

T'es tellement pro que tu as exactement le même algo que moi pour le traitement des nombres en int , t'as juste changé les noms de variables.
Pour un pro, tu indentes mal.
Comme l'indique le nom du topic, c'est des exos pour débutants.

Tu dois savoir que les int stock des nombres qui vont de 2 147 483 648 à 2 147 483 647.
Pour traiter de très grands nombres, les char sont préférables, mais vu ta réponse, tu le savais déjà.

Arthurus

30 janvier 2010 à 11:31:56

@fondation : Ce genre d'intervention a tendance à nous énerver !!
Franchement (et ce message amical sera le dernier de ce genre), évite de nous énerver... Tu vas le regretter amèrement comme tous ceux qui sont déjà passé avant toi

fondation

30 janvier 2010 à 11:39:55

J'ai mis le type int à titre d'exemple, mais l'on aurait largement pu utilisé le type long.

Adroneus

30 janvier 2010 à 11:57:16

... Waaaaaa... et? voici une remarque très constructive et intelligente

Anonyme

30 janvier 2010 à 12:11:30

Oui, enfin un pro qui propose un code ne compilant pas parce qu'il oublie une accolade fermante (celle du main()), qui ne récupère pas la valeur renvoyée par la fonction add_chiffre, c'est un peu la honte quoi.
A ignorer.

candide

30 janvier 2010 à 12:16:56

Citation : Colb-Seton

J'y pense jamais, mon IDE me le met automatiquement .

Et bien n'utilise plus d'IDE ou alors apprend à l'utiliser

. Je suppose que tu as codeblocks. codeblocks permet de créer un fichier template et que tu pourras lancer à chaque nouveau programme ce qui t'évite de recopier toujours le même code.

GurneyH

30 janvier 2010 à 12:20:41

fondation, c'est très bien, tu a presque réussi à faire l'exercice pour débutants.

Tu nous montre pous N = "1234567891234567489" et S = 42.

Zeste de Savoir, le site qui en a dans le citron !

Pouet_forever

30 janvier 2010 à 18:49:56

Trop fort les posts inutiles :lol:

GurneyH

30 janvier 2010 à 18:54:33

zSommeChiffre : Correction

La fonction zSommeChiffres

int zSommeChiffres(int n);
Tant que n n'est pas nul, on procède par divisions successives de n par 10, en ajoutant le reste de la division à la somme.

Exemple :

n = 5316
somme = somme + 5316 % 10, n = 5316 / 10 -> somme = 6,  n = 531
somme = somme + 531  % 10, n = 531  / 10 -> somme = 7,  n = 53
somme = somme + 53   % 10, n = 53   / 10 -> somme = 10, n = 5
somme = somme + 5    % 10, n = 5    / 10 -> somme = 15, n = 0
n = 0 -> on retourne somme = 15

Version itérative

int zSommeChiffres(int n)
{
    int somme = 0;

    while(n > 0)
    {
        somme += n % 10;
        n /= 10;
    }

    return somme;
}

Version récursive

int zSommeChiffresRec(int n)
{
    if (n <= 0)
        return 0;
    else
	return n % 10 + zSommeChiffres(n / 10);
}

A noter que dans le cas ou n est négatif, les 2 fonctions retourne 0.
On pourrait retourner une valeur négative, pour indiquer une erreur.

La fonction zSommeChiffresChar

int zSommeChiffresChar(char *src);
Pour obtenir un entier correspondant au code ascii d'un chiffre, il suffit de faire entier = car - '0'.
Pour chaque caractère de src, on ajoute à somme l'entier correspondant à ce caractère...

Version itérative

int zSommeChiffresChar(char *src)
{
    int somme = 0;
    int i;

    for (i = 0; src[i] != '\0'; i++)
        somme += src[i] - '0';

    return somme;
}

Version récursive

int zSommeChiffresChar(char *src)
{
    if(*src == '\0')
	return 0;
    else
        return *src - '0' + zSommeChiffresCharRec(src + 1);
}

Pour ces 2 fonctions, on pourrait tester si le caractère courant est bien un chiffre.
Si le caractère n'est pas un chiffre, 2 options:

On peut renvoyer une erreur(nombre négatif.)
Simplement ignorer le caractère et passer au suivant

Compter le nombre de fois ou une somme S donnée apparait entre 0 et N.

Une fois la fonction zSommeChiffres codée, ce problème est simple à résoudre.
Pour i de 0 à n, on teste si la somme des chiffres de i est égale à s. Si oui, on incrémente un compteur.

int nombreSdansN(int n, int s)
{
    int cpt = 0;
    int i;

    for(i = 0; i <= n; i++)
        cpt += zSommeChiffres(i) == s;

    return cpt;
}

Programme complet

Un petit main de test, comprenant un appel à toutes nos fonctions.

#include <stdio.h>

int zSommeChiffres(int n)
{
    int somme = 0;

    while(n > 0)
    {
        somme += n % 10;
        n /= 10;
    }

    return somme;
}



int zSommeChiffresRec(int n)
{
    if (n <= 0)
        return 0;
    else
	return n % 10 + zSommeChiffresRec(n / 10);
}



int zSommeChiffresChar(char *src)
{
    int somme = 0;
    int i;

    for (i = 0; src[i] != '\0'; i++)
        somme += src[i] - '0';

    return somme;
}



int zSommeChiffresCharRec(char *src)
{
    if(*src == '\0')
	return 0;
    else
        return *src - '0' + zSommeChiffresCharRec(src + 1);
}


int nombreSdansN(int n, int s)
{
    int cpt = 0;
    int i;

    for(i = 0; i <= n; i++)
        cpt += zSommeChiffres(i) == s;

    return cpt;
}


int main(void)
{
    int n = 1000000;
    int s = 42;
    
    printf("%d\n", zSommeChiffres(5316));
    printf("%d\n", zSommeChiffresRec(5316));
    printf("%d\n", zSommeChiffresChar("5316"));
    printf("%d\n", zSommeChiffresCharRec("5316"));

    printf("%d\n", nombreSdansN(n, s));

    return 0;
}

Et voilà le second exercice de Janvier est résolu. :soleil:

Pour aller plus loin.

Notre fonction nombreSdansN fonctionne, mais elle est inexploitable pour de grandes valeurs de n.
Comment faire mieux ? En abandonnant les fonctions zSommeChiffres et zSommeChiffresChar !

Voyons le problème autrement...

Quelle somme peut-on obtenir au maximum un nombre à k chiffres ?
La réponse est simple, c'est Smax = k * 9.

Avec k = 0, Smax = 0. :-°

Avec k = 1, Smax = 9.
Avec k = 2, Smax = 18.
...

Pour un nombre à 1 chiffre, on a Smax = 9. Combien de fois peut-on obtenir une somme comprise entre 0 et 9? On a évidemment une solution :
Pour obtenir une somme de 0 -> le nombre(chiffre) 0
Pour obtenir une somme de 1 -> le nombre(chiffre) 1
...

Pour un nombre à 2 chiffres, on a Smax = 18. Combien de fois peut-on obtenir une somme comprise entre 0 et 18?

Prenons un exemple, combien de fois peut-on obtenir la somme 12 avec un nombre à 2 chiffres?

On sait que la Smax pour un nombre à 1 chiffre = 9
Pour obtenir 12, les solutions sont :
Les nombres à 1 chiffre qui ont une somme de 12 -> 0.
Les nombres à 1 chiffre qui ont une somme de 11 -> 0.
Les nombres à 1 chiffre qui ont une somme de 10 -> 0.
Les nombres à 1 chiffre qui ont une somme de 9 auquel on rajoute le chiffre 3 -> 1 possibilité.
Les nombres à 1 chiffre qui ont une somme de 8 auquel on rajoute le chiffre 4 -> 1.
Les nombres à 1 chiffre qui ont une somme de 7 auquel on rajoute le chiffre 5 -> 1.
Les nombres à 1 chiffre qui ont une somme de 6 auquel on rajoute le chiffre 6 -> 1.
Les nombres à 1 chiffre qui ont une somme de 5 auquel on rajoute le chiffre 7 -> 1.
Les nombres à 1 chiffre qui ont une somme de 4 auquel on rajoute le chiffre 8 -> 1.
Les nombres à 1 chiffre qui ont une somme de 3 auquel on rajoute le chiffre 9 -> 1.
On a donc, 7 possibilités pour obtenir une somme de 12 avec un nombre à 2 chiffres.

On définit p(k, s) = le nombre de possibilités d'obtenir une somme s avec k chiffres.
p(0, s) = 0
p(1, s) = p(0, s) + p(0, s - 1) ... + p(0, s - i) avec i < 10 .
p(2, s) = p(1, s) + p(1, s - 1) ... + p(1, s - i) avec i < 10.
p(k, s) = p(k - 1, s) + p(k - 1, s - 1) ... + p(k - 1, s - i) avec i < 10.

On peut coder une première fonction récursive qui retourne p, en fonction de k et s.

int nombreSpourKchiffres(int k, int s)
{
    if(s > k * 9)
        return 0;
    else if(k == 1)
        return 1;
    else
    {
        /* S précédent à k - 1 permettant d'obtenir une somme S en ajoutant un
         * chiffre.
         */
        int preS;
        /* Nombre de possiblités d'obtenir une somme s avec k chiffres. */
        int nbrP = 0;
        for(preS = s; preS >= 0 && s - preS < 10; --preS)
            nbrP += nombreSpourKchiffres(k - 1, preS);

        return nbrP;
    }
}



int main(void)
{
    /* Nombre de possibilités d'obtenir une somme de 42 avec un nombre à 9
     * chiffres
     */
    printf("%d\n", nombreSpourKchiffres(9, 42));

    return 0;
}

}

Reste à pouvoir trouver le nombre de possibilités d'une somme s dans l'intervalle[0, n], avec n un nombre entier quelconque.

Une exemple:
s = 9 et n = 213

Soit nP le nombre de possibilités.
np = 0
nP = nP + p(2, s) = 10 (nombre de possibilités d'avoir une somme s avec 2 chiffres)
np = nP + p(2, s - 1) = 9 (nombre de possibilités d'avoir une somme s - 1 avec 2 chiffres)
np = np + p(2, s - 2) = 1 (nombre de possibilités d'avoir une somme s - 2 avec 2 chiffres)

Le dernier chiffre(3) est inférieur à la somme, pas de possibilité d'obtenir une somme de 9 avec 1 chiffre.

Le programme complet:

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

int p(int k, int s)
{
    if (s > k * 9)
        return 0;
    else if (k == 1)
        return 1;
    else
    {
        /* S précédent à k - 1 permettant d'obtenir une somme S en ajoutant un
         * chiffre.
         */
        int preS;
        /* Nombre de possiblités d'obtenir une somme s avec k chiffres. */
        int nbrP = 0;
        for (preS = s; preS >= 0 && s - preS < 10; --preS)
            nbrP += p(k - 1, preS);

        return nbrP;
    }
}

long long nombreSdansNChar(char const *limit, int s)
{
    long cpt = 0;
    int n, d;

    for (n = (int)strlen(limit) - 1; n > 0 && s > 0; --n)
        for (d = *limit++ - '0'; d > 0  && s > 0; --d)
            cpt += p(n, s--);

    if (s <= *limit - '0')
        cpt++;

    return cpt;
}

int main(void)
{
    /* Nombre de possibilités d'obtenir une somme de 27 avec un nombre à 9
     * chiffres
     */
    printf("%lld\n", nombreSdansNChar("1000000000", 27));

    return 0;
}

On a déjà un programme bien plus efficace, que la version naïve...

On peut faire mieux!
La fonction nombreSpourKchiffres effectue beaucoup d'appel inutiles. Elle s'appelle, pour des calculs déjà effectués.
On va stocker dans un tableau, l'ensemble de ces calculs et vérifier pour p(s, k) s'ils ont déjà été calculés...

Version récursive dynamique.

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


#define MAX_CHIFFRES    50
#define MAX_SOMME       ((MAX_CHIFFRES) * 9)

long long dynTab[MAX_CHIFFRES + 1][MAX_SOMME] = {{0}};

long long pDyn(int k, int s)
{
    if (s > k * 9)
        return 0;
    else if (k == 1)
        return 1;
    else
    {
        if (dynTab[k][s] == 0)
        {
            /* p(k, s) n'a jamais été évalué */
            int preS;
            for (preS = s; preS >= 0 && s - preS < 10; --preS)
                dynTab[k][s] += pDyn(k - 1, preS);
        }

        return dynTab[k][s];
    }
}


long long nombreSdansNChar(char const *limit, int s)
{
    long long cpt = 0;
    int n, d;

    for (n = (int)strlen(limit) - 1; n > 0 && s > 0; --n)
        for (d = *limit++ - '0'; d > 0  && s > 0; --d)
            cpt += pDyn(n, s--);

    if (s <= *limit - '0')
        cpt++;

    return cpt;
}

int main(void)
{
    /* Nombre de possibilités d'obtenir une somme de 27 avec un nombre à 9
     * chiffres
     */
    printf("%lld\n", nombreSdansNChar("123456789012", 27));

    return 0;
}

Le résultat est instantané! :magicien:

c'est déjà très bien, mais on peut encore aller plus loin!
On va "dérécursifier" :pirate:

notre fonction p !

Version itérative dynamique

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

enum
{
    MAX_CHIFFRES  =  50,
    MAX_SOMME =      ((MAX_CHIFFRES) * 9)
};


long long pIterDyn(int k, int s)
{
    long long dynTab[MAX_CHIFFRES + 1][MAX_SOMME] = {{0}};
    int lin, col;

    for(col = 0; col < 10; ++col)
        dynTab[1][col] = 1;

    for(lin = 2; lin <= k; lin++)
    {
        int preS;

        dynTab[lin][0] = 1;
        for(col = 1; col <= lin * 9; col++)
            for (preS = col; preS >= 0 && col - preS < 10; --preS)
                dynTab[lin][col] += dynTab[lin - 1][preS];

    }
    return dynTab[k][s];
}



long long nombreSdansNChar(char const *limit, int s)
{
    long long cpt = 0;
    int n, d;

    for (n = (int)strlen(limit) - 1; n > 0 && s > 0; --n)
        for (d = *limit++ - '0'; d > 0  && s > 0; --d)
            cpt += pIterDyn(n, s--);

    if (s <= *limit - '0')
        cpt++;

    return cpt;
}



int main(void)
{
    /* Nombre de possibilités d'obtenir une somme de 27 avec un nombre à 9
     * chiffres
     */
    printf("%lld\n", nombreSdansNChar("1000000000", 27));

    return 0;
}

Cette forme itérative nous permet si on le désire d'économiser de la place en mémoire.
En effet, on remarque que pour calculer la ligne courante, on a besoin que de la ligne précédente. On a donc besoin uniquement d'un tableau de taille [2][MAX_SOMME].

Pour ceux que le sujet intéresse,
http://en.wikipedia.org/wiki/Digit_sum
http://en.wikipedia.org/wiki/Digital_root

edit: Correction d'une erreur signalée par candide(overflow. >_<

)

Zeste de Savoir, le site qui en a dans le citron !

candide

30 janvier 2010 à 19:08:16

Bravo Gurney, c'est de l'excellent travail, on peut pas dire que tu ne prennes pas ta tâche au sérieux et j'espère que les zéros sauront apprécier le soin dont tu fais preuve.

En particulier, bravo pour les références que tu as trouvées, je vais les examiner.

darkipod

30 janvier 2010 à 21:49:54

Franchement bravo pour la correction et toutes les explications,
avec les deux exos proposés j'en ai appris pas mal, même si j'ai
pas tout digéré

je note au passage que les exos du début sont pas mal aussi pour les avoir fait.
je trouve extra que certains proposent autre chose que des solutions simples,
ça permet d'ouvrir son esprit, même si je comprends pour ma part pas tout :-°

GurneyH

31 janvier 2010 à 8:25:56

Titre : zArray1D
Mois : Premier exercice de février 2010
Sujet : Pratique des tableaux à une dimension.
Connaissances requises : Partie 2 : [Théorie] Techniques avancées . Les tableaux

Objectif

En parcourant le forum C, on se rend compte que la manipulation des tableaux pose pas mal de problèmes.
Je vous propose, en complément des exercices du tuto de M@teo21, une série d'exercices qui va vous permettre de pratiquer. Ils sont rangés par ordre croissant de difficulté.

Pour ce premier exercice de février, on se contentera des tableaux à 1 dimension.

Exercice 1:

Ecrire les fonctions

int indexMin(int tableau[], int tailleTableau);
int indexMax(int tableau[], int tailleTableau);

qui retournent respectivement l'index de la valeur mini, et l'index de la valeur maxi du tableau.
Si plusieurs éléments ont la même valeur, la fonction indexMin , retourne l'index le plus petit, tandis que la fonction indexMax retourne l'index le plus grand.
Exercice 2:
Ecrire la fonction

void afficherEltCommuns(int tableau1[], int tableau2[], 
                        int tailleTableau1, int tailleTableau2);

qui affiche les éléments communs aux 2 tableaux(l'intersection des 2 tableaux).
L'ordre est sans importance.
Exemple:

avec
tableau1 = 0, 1, -1, 3, 8
tableau2 = 10, 1, 11, 7, 98, 8, 7, 8

afficherEltCommuns(tableau1, tableau2, tailleTableau1, tailleTableau2);

[1, 8]

avec
tableau1 = 0, 1, 10, 11, 10
tableau2 = 10, 1, 11, 7, 98, 8, 7, 10

afficherEltCommuns(tableau1, tableau2, tailleTableau1, tailleTableau2);

[1, 10, 11, 10]

Exercice 3:
Ecrire les fonctions

void triCroissant(int tableau[], int tailleTableau);
void triDecroissant(int tableau[], int tailleTableau);

qui trient respectivement un tableau dans l'ordre croissant et dans l'ordre décroissant.
Aider vous pour cela, de la fonction int indexMax(int tableau[], int tailleTableau); et int indexMin(int tableau[], int tailleTableau); , en appliquant ce principe:

On recherche l'index de la valeur maxi
On insère l'élément max à la bonne position dans le tableau
On répète les 2 premières opérations sur le reste du tableau tant que le tableau n'est pas entièrement trié

Exercice 4:Honteusement pompé dans le forum :lol:

Ecrire la fonction

void zeroADroite(int tableau[], int tailleTableau);

qui décale les élément nul d'un tableau vers la droite. Au final, un élément nul, ne doit avoir aucun élément non nul à sa droite.
exemple

tableau[] = {1, 0, 4, 0, 0, -7}
zeroADroite(tableau, 6);
tableau[] = {1, 4, -7, 0, 0, 0}

Je vous invite à faire TOUS ces exercices de 2 manières différentes :

Une première fois avec le formalisme tableau
Une seconde fois avec le formalisme pointeur.

Pas de panique, je vous donne un exemple avec le premier exercice du tuto de M@teo21 sur les tableaux

Exemple:

Formalisme tableaux

int sommeTableau(int tableau[], int tailleTableau)
{
    int somme = 0;
    int i;

    for(i = 0; i < tailleTableau; ++i)
    {
        somme += tableau[i];
    }

    return somme;
}

Formalisme pointeurs

int sommeTableau2(int tableau[], int tailleTableau)
{
    int somme = 0;
    int *end = tableau + tailleTableau;

    for(; tableau != end; tableau++)
    {
        somme += *tableau;
    }

    return somme;
}

Je pense que vous avez déjà de quoi vous amuser. :lol:

Les exercices suivants sont
Pour les plus avancés
Exercice 5:(proposé par candide)
Ecrire un programme qui affiche le n premières lignes du triangle de Pascal
Exemple, avec n = 10 :

1
1   1
1   2   1
1   3   3   1
1   4   6   4   1
1   5  10  10   5   1
1   6  15  20  15   6   1
1   7  21  35  35  21   7   1
1   8  28  56  70  56  28   8   1
1   9  36  84 126 126  84  36   9   1

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

Rappelez vous que l'exercice porte sur les tableaux à 1 dimension.
Le but est ici, d'arriver à construire la ligne courante à partir de la précédente sans copie d'éléments, simplement par échange...
Vous pouvez vous limiter aux 17 premières lignes.

Exercice 6:
Ecrire la fonction

int mode(int tableau[], int tailleTableau);

qui retourne le mode(l'élément le plus fréquent) de tableau[]. Si 2 éléments sont présents le même nombre de fois, la fonction pourra retourner l'un ou l'autre.

Exercice 7:
Ecrire la fonction

int kEmeElt(int tableau[], int tailleTableau, int k);

qui retourne le k ième plus grand élément de tableau[]
exemple :

tableau[] = {0, 1, 10, 1, 3, 5}

avec k = 0 -> 0
avec k = 1 -> 1
avec k = 2 -> 1
avec k = 3 -> 3
avec k = 4 -> 5
avec k = 5 -> 10

Quelques rappels

Pour faire des tests, le plus simple est de stocker le tableau en dur dans votre programme(pas de lecture sur l'entrée standard, etc...)
Pas besoin, de faire de la programmation modulaire, ici ce n'est pas le but... Tout dans un seul fichier!
Prenez votre temps! Vous avez 15 jours! Le but est de progresser, pas de poster sa solution le plus rapidement possible.

Pour les 2 derniers exercices, pour les plus avancés le but est de trouver une solution un minimum efficace. Idéalement, vos solutions devraient pouvoir traiter les tableaux de tailles > 1000000 avec des valeurs dans la plage totale d'un entier signé.

Postes vos réponses ici.

Zeste de Savoir, le site qui en a dans le citron !

TerresMinees

31 janvier 2010 à 10:28:05

voila mes soluces.

Ex 2

void afficherEltCommuns(int tableau1[], int tableau2[],
                        int tailleTableau1, int tailleTableau2)
{
    int j;
printf("[");
    for(j= 0;j < tailleTableau1;j++)
    {
        if(tableau1[j] == tableau2[j])
        {
            printf("%d ", tableau1[j]);
        }
    }
    printf("]");
}

Ex 3

Ex. 3 == ex 5 de m@t' nan ?

en faisant celui de mat, ca m'a donné ca :

void ordonnerTableau(int tableau[], int tailleTableau)
{
    int i, j;

    for(j= 0;j < tailleTableau;j++)
    {
        for(i= 0;i < tailleTableau;i++)
        {
            if(tableau[j] < tableau[i])
            {
                int sauvegarde = tableau[j];
                tableau[j] = tableau[i];
                tableau[i] = sauvegarde;
            }
        }
    }
}

Ex 4 == ex 3 mais avec des zéros au lieu de la taille du chiffre j'crois.

Ex 7

J'ai repris le code de ma fonction ordonnerTableau

#include <stdio.h>
#include <stdlib.h>
int kEmeElt(int tableau[], int tailleTableau, const int K);

int main(int argc, char *argv[])
{
    int tab[10] = {9, 50, 9, 17, 150, 641, 25, 874, 945, 156};
    const int K = 6;
    int result = 0, i;

    result = kEmeElt(tab, 10, K);
    printf("[%d]\n\n", result);

    for (i = 0 ; i < 10 ; i++)
    {
        printf("%d\n", tab[i]);
    }
    return 0;
}
int kEmeElt(int tableau[], int tailleTableau, const int K)
{
    int i, j;


    for(j= 0;j < tailleTableau;j++)
    {
        for(i= 0;i < tailleTableau;i++)
        {
            if(tableau[j] > tableau[i])
            {
                int sauvegarde = tableau[j];
                tableau[j] = tableau[i];
                tableau[i] = sauvegarde;
            }
        }
    }


    return tableau[K-1];
}

Dites moi ce qui va pas (si c'est le cas) pour que je puisse m'améliorer.

GurneyH

31 janvier 2010 à 10:32:40

Citation : TerresMinées

Ex. 3 == ex 5 de m@t' nan ?

Non.

Justement tu dois te servir de la fonction de l'exercice 1(comment ça, tu n'as pas fait l'exercice 1?) pour trier ton tableau...
Tu auras un tri différent...

Zeste de Savoir, le site qui en a dans le citron !

TerresMinees

31 janvier 2010 à 10:38:32

bah en fait je l'ai pas trop compris, ca veut dire quoi index mini/maxi ? Le chiffre le plus petit/grand ?

GurneyH

31 janvier 2010 à 10:51:48

Citation : TerresMinees

bah en fait je l'ai pas trop compris, ca veut dire quoi index mini/maxi ? Le chiffre le plus petit/grand ?

L'index, c'est la position du chiffre mini ou maxi dans le tableau.

je te donne un exemple

tableau[] = {1, 2, 10, -1}

l'index du min est 3, (en C les tableaux commencent à l'indice 0)
l'index du max est 2.

Ta soluce pour l'exercice 2, est fausse. Tu affiches les éléments communs aux 2 tableaux et qui sont à la même place!
Il peuvent être à une position différente, il n'en reste pas moins qu'ils sont communs. Donc, il faut les afficher.

Prend ton temps et lis bien les énoncés.

Zeste de Savoir, le site qui en a dans le citron !

TerresMinees

31 janvier 2010 à 11:53:21

Mon hypothèse se révèle être exacte. youpiha
pour ton avant-dernière réponse, "un tri différent" ? Cela revient au même, c'est juste la méthode qui diffère non ?
Pour ton exo, faut utiliser la valeur maxi alors qu'avec l'exo de mat, (la méthode que j'ai proposé ici), j'ai regardé chaque indices.
Et pis même :

Citation

1. On recherche l'index de la valeur maxi
2. On insère l'élément max à la bonne position dans le tableau
3. On répète les 2 premières opérations sur le reste du tableau tant que le tableau n'est pas entièrement trié

Ca sert à quoi de répéter les premières opérations si la valeur maxi est déjà triée ?
Cela ne triera pas le reste du tableau non ? J'ai vraiment du mal à comprendre les gens ces derniers temps. (pas qu'avec tes énoncés :-p )

Effectivement, pour l'ex 2, je n'avais pas fait attention.
Je devrai peut-être lire et relire les énoncés huhu :lol:

Pouet_forever

31 janvier 2010 à 12:57:51

Voilà mes réponses pour les 5 premiers

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

int index(int * tab, int sz, char compar) {
	int ind = 0;
	int i;
	
	for (i = 0; i < sz; i++)
		switch (compar) {
			case '<':
				if (tab[i] < tab[ind])
					ind = i;
				break;
			case '>':
				if (tab[i] > tab[ind])
					ind = i;
				break;
			default:
				break;
		}
	
	return ind;
}

int indexMin(int * tab, int sz) {
	return index(tab, sz, '<');
}

int indexMax(int * tab, int sz) {
	return index(tab, sz, '>');
}

void afficherEltCommuns(int * tab1, int * tab2, 
                        int sz1, int sz2) {
	int i, j;
	
	for (i = 0; i < sz1; i++)
		for (j = 0; j < sz2; j++)
			if (tab1[i] == tab2[j])
				printf("%d ", tab1[i]);
	puts("");
}

void swap(int * tab, int x, int y) {
	int tmp = tab[x];
	tab[x] = tab[y];
	tab[y] = tmp;
}

void tri(int * tab, int sz, int (*ind)(int *, int)) {
	int i, id;
	
	for (i = 0; i < sz-1; i++) {
		id = ind(tab+i, sz-i);
		swap(tab, i, id+i);
	}
}

void triCroissant(int * tab, int sz) {
	tri(tab, sz, indexMin);
}

void triDecroissant(int * tab, int sz) {
	tri(tab, sz, indexMax);
}

void zeroADroite(int * tab, int sz) {
	int * fin = tab + sz;
	int * tmp = tab;
	
	for ( ; tab < fin; tab++) {
		*tmp = *tab;
		if (*tab != 0)
			tmp++;
	}
	
	for ( ; tmp < fin; tmp++)
		*tmp = 0;
}

void triangle_de_pascal(int nb_lignes) {
	int tab[100] = { 1 };
	int i, j;
	int indice = 0;
	
	for (i = 0; i < nb_lignes; i++) {
		for (j = 0; j <= indice; j++) {
			printf("%d ", tab[j]);
		}
		indice++;
		for (j = indice-1; j >= 1; j--) {
			tab[j] += tab[j-1];
		}
		tab[indice] = 1;
		puts("");
	}
}

void affiche_tab(int * tab, int sz) {
	int i;
	
	for (i = 0; i < sz; i++)
		printf("%d ", tab[i]);
	puts("");
}

#define SZ_TAB0 6
#define SZ_TAB1 5
#define SZ_TAB2 7

int main(void) {
	int tab1[SZ_TAB1] = { 3, 4, 5, 1, 2 };
	int tab2[SZ_TAB2] = { 1, 2, 3, 4, 5, 6, 7 };
	int tab0[SZ_TAB0] = { 1, 0, 4, 0, 0, -7 };
	
	printf("ind max: %d\n", indexMax(tab1, SZ_TAB1));
	printf("ind min: %d\n", indexMin(tab1, SZ_TAB1));
	printf("Elt com: ");
	afficherEltCommuns(tab1, tab2, SZ_TAB1, SZ_TAB2);
	
	printf("Tri cro: ");
	triCroissant(tab1, SZ_TAB1);
	affiche_tab(tab1, SZ_TAB1);
	
	printf("Tri dec: ");
	triDecroissant(tab1, SZ_TAB1);
	affiche_tab(tab1, SZ_TAB1);
	
	printf("Zer a d: ");
	zeroADroite(tab0, SZ_TAB0);
	affiche_tab(tab0, SZ_TAB0);
	
	printf("Tri pas:\n");
	triangle_de_pascal(10);
	return EXIT_SUCCESS;
}

Pour les 2 derniers je les avais fait mais pour une taille > 1000000 je vais réfléchir encore un peu :lol:

Anonyme

31 janvier 2010 à 13:02:13

L'index, c'est l'adresse ?

Pouet_forever

31 janvier 2010 à 13:16:30

@TerresMinees : Il y a plusieurs types de tris, celui-là en est un

Celui présenté dans le cours de M@teo est le tri à bulles je crois

Une fois que tu as mis un élément à la bonne place, tu n'y touches plus, tu continues sur le reste

@ Etienne-02 : L'index c'est sa place dans le tableau, ou l'indice

TerresMinees

31 janvier 2010 à 13:48:53

merci pouet.

Par contre, je suis entrain de faire l'exo 2, et je crois que j'ai besoin d'utiliser l'allocation dynamique, mais je sais pas encore le faire... mince alors.

bon allez, le poste ma chose avec l'exo 2 incomplet, et du code merdique à en promener sa baignoire.

Mais dites moi comment l'améliorer, pour m'améliorer.

/*
SOLUCES D'EXOS DU SdZ par terresMinees
chuis pas un boss basez-vous pas sur mes sources 
*/

#include <stdio.h>
#include <stdlib.h>
int kEmeElt(int tableau[], int tailleTableau, const int K);
int indexMin(int tableau[], int tailleTableau);
int indexMax(int tableau[], int tailleTableau);
void afficherEltCommuns(int tableau1[], int tableau2[],
                        int tailleTableau1, int tailleTableau2);
void copie(int tableauOriginal[], int tableauCopie[], int tailleTableau);


int main(int argc, char *argv[])
{
    int tab[10] = {9, 50, 9, 17, 150, 641, 25, 874, 945, 156};
    int tab_2[10] = {8, 25, 65, 98, 12, 24, 39, 85, 75, 26};
    const int K = 6;
    int result = 0, i;

    result = kEmeElt(tab, 10, K);
    printf("[%d PLUS GRAND INDEX DU TAB : %d]\n\n", K, result);

    printf("CONTENU DU TAB\n========\n");
    for (i = 0 ; i < 10 ; i++)
    {
        printf("%d\n", tab[i]);
    }
    printf("========\n");
    int index_min_tab = indexMin( tab, 10);
    printf("[INDEX MIN DU TAB == %d ==]", index_min_tab);

    printf("[LISTE ELEMENTS COMMUNS\n");

    afficherEltCommuns(tab, tab_2,
                        10, 10);
    printf("]\n");

    return 0;
}

// ====================== FUNCTIONS =======================

// EXO 1
int indexMin(int tableau[], int tailleTableau)
{
    int index_min = tableau[0], i;
    for (i = 0 ; i < tailleTableau ; i++)
    {
        if(tableau[i] < index_min)
        {
            index_min = tableau[i];
        }
    }
    return index_min;
}


int indexMax(int tableau[], int tailleTableau)
{
    int index_max = tableau[0], i;
    for (i = 0 ; i < tailleTableau ; i++)
    {
        if(tableau[i] < index_max)
        {
            index_max = tableau[i];
        }
    }
    return index_max;
}

//=======================================
//EXO 2
//AFFICHE LES éLéMENTS COMMUNS
void afficherEltCommuns(int tableau1[], int tableau2[],
                        int tailleTableau1, int tailleTableau2)
{
    int i, j, taillePlusGrandTab, tab_grand[], tab_petit[];
    if(tailleTableau1 < tailleTableau2)
    {
        taillePlusGrandTab = tailleTableau2;
        copie(tab_grand, tableau2, tailleTableau2)
        copie(tab_petit, tableau1, tailleTableau1)
    }
    else
    {
        taillePlusGrandTab = tailleTableau1;
        copie(tab_grand, tableau1, tailleTableau1)
        copie(tab_petit, tableau2, tailleTableau2)
    }


    for(j= 0;j < taillePlusGrandTab;j++)
    {
        for(i= 0;i < taillePlusGrandTab;i++)
        {
            if(tab_grand[j] == tab_petit[i])
            {
                printf("%d\n", tab_grand[j]);
            }
        }
    }
}


//==========================================
// EXO 7
//RETOURNE LE Kieme PLUS GRAND INDICE DU TAB

int kEmeElt(int tableau[], int tailleTableau, const int K)
{
    int i, j;


    for(j= 0;j < tailleTableau;j++)
    {
        for(i= 0;i < tailleTableau;i++)
        {
            if(tableau[j] > tableau[i])
            {
                int sauvegarde = tableau[j];
                tableau[j] = tableau[i];
                tableau[i] = sauvegarde;
            }
        }
    }


    return tableau[K-1];
}
void copie(int tableauOriginal[], int tableauCopie[], int tailleTableau)
{
    int i;
    for (i = 0 ; i < tailleTableau ; i++)
    {
        tableauOriginal[i] = tableauCopie[i];
    }
}

GurneyH

31 janvier 2010 à 14:24:59

@Pouet: J'ai juste jeté un oeil, mais pour le triangle de Pascal, 2 boucles devraient suffire, non?

Pour les 2 derniers exercices, pour toi on peut même pousser la limite à 10^9 en moins d'une minute...

@terreMinées: Pas d'allocation dynamique...

Zeste de Savoir, le site qui en a dans le citron !

<< 1 ... 47 48 49 ... 55 >>

Exercices pour débutants en C

Au menu : zSommeChiffres (nombres, algo)

zSommeChiffre : Correction

La fonction zSommeChiffres

La fonction zSommeChiffresChar

Compter le nombre de fois ou une somme S donnée apparait entre 0 et N.

Programme complet

Pour aller plus loin.

Ex 2

Ex 3

Ex 7

Supprimer

Modérer

Signaler le message aux modérateurs