Partage
  • Partager sur Facebook
  • Partager sur Twitter

Exercices pour débutants en C

Au menu : zSommeChiffres (nombres, algo)

1 novembre 2008 à 20:07:54

Citation : candide

Citation : yoch


J'édite mon post plus haut...



Le problème n'est toujours pas résolu.


Fichtre ! Je fatigue, décidément...
#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');
}

int main(void)
{
   affichage_binaire(5);
  return 0;
}
  • Partager sur Facebook
  • Partager sur Twitter
1 novembre 2008 à 20:15:34

Citation : yoch


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');
}


Oui mais c'est ce que je te dis, ça affiche :

00000000000000000000000000000101


au lieu de

101


ce qui nécessite la première boucle écrite par crys' dans son 3ème code ou encore la ligne 13 de mon 2ème code ci-dessus.
  • Partager sur Facebook
  • Partager sur Twitter
1 novembre 2008 à 21:33:25

C'est juste, je n'ai pas respecté l'énoncé. :-°

Je propose ceci :
#include <stdio.h>

void affichage_binaire(const unsigned int n)
{
    if (n > 1)
        affichage_binaire(n>>1);
    putchar('0'+(n&1));
}

int main(void)
{
    affichage_binaire(5);
    return 0;
}
  • Partager sur Facebook
  • Partager sur Twitter
1 novembre 2008 à 21:51:20

Citation : yoch


Je propose ceci :

#include <stdio.h>

void affichage_binaire(const unsigned int n)
{
    if (n > 1)
        affichage_binaire(n>>1);
    putchar('0'+(n&1));
}

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


Pas mal. L'usage des opérateurs binaires n'est pas indispensable mais ton code est compact et il traite le cas de l'entrée valant 0. En adaptant comme ceci :


void affichage_binaire(const unsigned int n)
{
    if (n > 1)
        affichage_binaire(n/2);
    putchar('0'+n%2);
}


on obtient un code que je trouve meilleur que le corrigé proposé.

  • Partager sur Facebook
  • Partager sur Twitter
1 novembre 2008 à 23:43:05

Ton code présente en plus l'avantage (sur le mien) d'être générique :
#include <stdio.h>

void affichage_base(const unsigned int n, const unsigned int base)
{
    if (n >= base)
        affichage_base(n/base, base);
    putchar('0'+n%base);
}


int main(void)
{
    affichage_base(1000, 8);
    return 0;
}
  • Partager sur Facebook
  • Partager sur Twitter
1 novembre 2008 à 23:59:58

Oulah, en voyant cela, je me dis que mon code est éléphantesque :-°

/*	Decimal2Bin
	Fait par VeKoX

	Version : 1.0
*/

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

int main (void)
{
	// Déclaration des variables
	char nombreEntre[65] = {0};
	long quotient = 0;
	long nombreBin[64] = {0};
	int i = 0, j;

	printf("Veuillez entrer le nombre decimal : ");
	fgets(nombreEntre, sizeof nombreEntre, stdin);

	quotient = strtol(nombreEntre, NULL, 10);

	while (quotient != 0)
	{
		nombreBin[i] = quotient % 2;
		printf("\n%ld / 2 = ", quotient);
		quotient = quotient / 2;
		printf("%ld\treste %ld", quotient, nombreBin[i]); 
		i++;
	}

	printf("\n\nLe nombre binaire est ");

	for (j = i-1; j >= 0; j--)
		if ((j % 4) == 0)
			printf("%ld ", nombreBin[j]);
		else
			printf("%ld", nombreBin[j]);

	printf("%c", 8);

	system("PAUSE > nul");
	return EXIT_SUCCESS;
}


Bon, il affiche certes le développement et sépare les bits par paquets de 4 mais quand même :-°
  • Partager sur Facebook
  • Partager sur Twitter
2 novembre 2008 à 0:45:18

Citation : zx-spectrum


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



On va probablement devoir se contenter de trier des vecteurs (*) d'entiers. Un vrai tri générique (ie capable de s'adapter à n'importe quel type de données), c'est bien plus compliqué.

(*) c'est-à-dire un objet (pas au sens de la POO) dont la représentation en mémoire est une suite d'entiers (int) autrement dit pour parler simplement : des tableaux qu'ils soient statiques ou dynamiques.

Je pense par ailleurs qu'il faudrait préciser la tache exacte que doit effectuer le programme. Je trouve qu'afficher à l'écran un résultat n'est pas une bonne tâche, l'écran (stdout) est trop particulier, en particulier ce n'est pas un objet. D'ailleurs, cette remarque valait pour la conversion en base 2, en général, on n'est pas intéressé par afficher la représentation en base 2 mais on est intéressé par pouvoir y accéder via un tableau. Ainsi, je ne suis pas sur que le premier algorithme donné lors de la conversion soit si aisément transposable dans le cas où on veut stocker le représentation binaire.

Personnellement, pour préciser, je dirais que le programme de tri doit trier un tableau d'entiers donné en paramètre, plus précisément, il doit modifier ce tableau pour que son contenu soit trié (c'est ce que fait la fonction standard qsort). Mais ce n'est pas à moi de le faire, c'est à crys', l'auteur de l'exercice de donner des consignes.

Citation : VeKoX

Oulah, en voyant cela, je me dis que mon code est éléphantesque



Le problème c'est que tu fais du zèle, personne ne t'a demandé de sortir le papier-cadeau ;) . Le coeur de ton programme est entre les lignes 23 et 30, tout le reste c'est du marketing. Tu aurais du isoler cette partie du reste du code et la placer dans une fonction dont la seule tâche aurait été de convertir. Au passage, ton code n'est pas en mesure de convertir 0 en binaire. C'est ce genre de situation qui me fait apprécier la liberté que donne ce qu'on appelle les boucles infinies.
  • Partager sur Facebook
  • Partager sur Twitter
2 novembre 2008 à 0:57:28

Pour l'exercice, il serait judicieux de faire une fonction par algorithme de tri, histoire d'organiser son code. Le programme devra afficher le temps d'exécution de chaque tri mais aussi son nombre de comparaisons/échanges. On laisse la taille du tableau à trier au choix. Vous devez réfléchir à la manière d'implémenter les différents tris, à la manière de calculer le temps d'exécution de chaque tri et à la manière de compter le nombre de comparaisons et le nombre d'échanges pour chaque tri.

Bon codage ! :)
  • Partager sur Facebook
  • Partager sur Twitter
2 novembre 2008 à 9:29:14

merci pour les precisions de l'enoncé, c'est plus clair pour moi :)
  • Partager sur Facebook
  • Partager sur Twitter
2 novembre 2008 à 19:49:24

Citation : candide

On va probablement devoir se contenter de trier des vecteurs (*) d'entiers. Un vrai tri générique (ie capable de s'adapter à n'importe quel type de données), c'est bien plus compliqué.


Je ne trouve pas qu'un tri générique soit tellement plus compliqué a implémenter. Personnellement, l'analyse attentive du prototype de qsort() m'a beaucoup aidé dans ce sens.
  • Partager sur Facebook
  • Partager sur Twitter
2 novembre 2008 à 20:05:34

Citation : yoch


Je ne trouve pas qu'un tri générique



Générique comme qsort, n'est-ce pas ?

Citation : yoch


Personnellement, l'analyse attentive du prototype de qsort() m'a beaucoup aidé dans ce sens.


L'interface est une chose, l'implémentation en est une autre. Je ne vois pas en quoi l'examen attentif de l'interface aide à implémenter le code. Si tu trouves qu'implémenter un vrai qsort est facile, tant mieux pour toi mais ce n'est pas l'opinion générale. En tout cas, il est certainement nettement plus compliqué de faire un tri par sélection (sélection c'est un exemple) et générique que de faire un tri par sélection juste pour une liste d'entiers. C'est plus compliqué parce que ça demande de connaitre beaucoup plus de C. D'ailleurs, par exemple Plauger (spécialiste bien connu du C et du C++) s'est planté dans son livre en écrivant son qsort générique (il l'a reconnu dans un message sur le forum clc si je me rappelle bien), et il s'est planté dans la partie généricité pas dans l'algorithme quick sort en tant que tel, comme quoi ....

Donc pour me résumer, pour écrire un tri par insertion générique, on commence par écrire un tri par insertion sur des entiers et qui soit béton et ensuite, on l'adapte pour le rendre générique. Je dis pas que ce soit difficile mais je me demande si tu ne sous-estimes pas la difficulté de la tâche.
  • Partager sur Facebook
  • Partager sur Twitter
2 novembre 2008 à 21:07:04

Citation : candide

L'interface est une chose, l'implémentation en est une autre. Je ne vois pas en quoi l'examen attentif de l'interface aide à implémenter le code.


Je vais essayer de m'expliquer. Le prototype de qsort() est le suivant :
void qsort (void *base, size_t nmemb, size_t size, int (*compar)(const void*, const void *))

Il apparait clairement que pour obtenir une fonction générique, on fait abstraction du type du tableau (avec void*), et on a besoin de connaitre le nombre et la taille de ses éléments. Ce qui n'est pas forcement évident pour le premier venu.

Citation : candide

Si tu trouves qu'implémenter un vrai qsort est facile, tant mieux pour toi mais ce n'est pas l'opinion générale. En tout cas, il est certainement nettement plus compliqué de faire un tri par sélection (sélection c'est un exemple) et générique que de faire un tri par sélection juste pour une liste d'entiers. C'est plus compliqué parce que ça demande de connaitre beaucoup plus de C.


Implémenter un tri rapide n'est pas trivial du tout. Mais je trouve qu'il est aussi difficile d'implémenter l'algo de tri que de le rendre générique. Je te concède que cela demande de connaitre un peu plus de C, mais pas tant que ça.

Citation : candide

Donc pour me résumer, pour écrire un tri par insertion générique, on commence par écrire un tri par insertion sur des entiers et qui soit béton et ensuite, on l'adapte pour le rendre générique.


La dessus, je suis absolument d'accord. C'est ce que toute personne sensée devrait faire.

Ton avis m'intéresse sur mon qsort(), si tu es d'accord, je te l'envoie par MP.
  • Partager sur Facebook
  • Partager sur Twitter
3 novembre 2008 à 19:56:27

bonjour
pour le 000 que je suis
j'ai du mal a faire le distingo entre :

Le tri à bulles
Le tri par sélection

j'ai regarde sur wikipedia, mais c'est pas clair dans ma tete.
si quelqu'un peut m'aiguiller (pas me doner la solution toute faite!)
merci

  • Partager sur Facebook
  • Partager sur Twitter
3 novembre 2008 à 20:03:05

La difference avec le tri bulle c'est que tu ne swap l'element qu'une fois arrivé au bout, alors qu'avec le tri bulle, tu swap dès que l'element en superieur
  • Partager sur Facebook
  • Partager sur Twitter
3 novembre 2008 à 20:06:20

merci pour ta reponse
"swap" c'est quoi cette bebete?
:-° j'ai un peu de mal avec les contractures verbiales ! :lol:
@+
  • Partager sur Facebook
  • Partager sur Twitter
3 novembre 2008 à 20:23:23

Citation : crys'

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)


Pour info, clock() donne des résultats beaucoup plus précis que time().

Citation : crys'

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

Peut on implémenter d'autres algos plus performants ? (tris par tas, tri rapide...)

Il serait judicieux aussi de bien définir le statut des données a trier, les tris réagissant différemment selon l'état des données (ex. un tableau déjà trié ralentit affreusement le tri rapide).
  • Partager sur Facebook
  • Partager sur Twitter
3 novembre 2008 à 20:26:40

Ne te met pas de nœud dans la tête, le tri à bulles à le tri par sélection sont deux tris différents et bien différents. ;) Leurs seuls points communs sont qu'ils sont tous deux en O(n²) et qu'ils sont basés sur des comparaisons.
Le tri par sélection "sélectionne" la plus grande valeur du tableau et l'échange avec la dernière valeur. On réitère cette étape sur le tableau en ignorant la dernière case. Au fur et à mesure du déroulement de l'algorithme, le tableau se trie (en commençant donc par la fin - ou le début si l'on a choisi de s'intéresser à la plus petite valeur).
[ 2 | 3 | 0 | 4 | 1 ]  // plus grande valeur : 4
[ 2 | 3 | 1 | 0 | 4 ]  // échange avec la dernière case
[ 2 | 3 | 1 | 0 ]  [ 4 ]  // plus grande valeur : 3
[ 2 | 0 | 1 | 3 ]  [ 4 ]  // échange avec la dernière case
[ 2 | 0 | 1 ]  [ 3 | 4 ]  // plus grande valeur : 2
[ 1 | 0 | 2 ]  [ 3 | 4 ]  // échange avec la dernière case
[ 1 | 0 ]  [ 2 | 3 | 4 ]  // plus grande valeur : 1
[ 0 | 1 ]  [ 2 | 3 | 4 ]  // échange avec la dernière case
[ 0 ]  [ 1 | 2 | 3 | 4 ]
[ 0 | 1 | 2 | 3 | 4 ]

Le tri à bulles ne fonctionne pas du tout sous le même principe (cf mon tutoriel). ;)
  • Partager sur Facebook
  • Partager sur Twitter
3 novembre 2008 à 20:28:46

merci crys, je vais etudier ton memo
@+
  • Partager sur Facebook
  • Partager sur Twitter
3 novembre 2008 à 20:33:36

Citation : zx-spectrum


"swap" c'est quoi cette bebete?
:-° j'ai un peu de mal avec les contractures verbiales ! :lol:



C'est pas une contracture verbiale, c'est de l'anglais.
http://dictionary.reverso.net/english-french/swap
  • Partager sur Facebook
  • Partager sur Twitter
4 novembre 2008 à 7:34:50

merci pour l'info, to swap = echanger
je suis faché aussi avec l'anglais :lol:
  • Partager sur Facebook
  • Partager sur Twitter
4 novembre 2008 à 16:28:59

Voici ce que j'ai fait :

Prototype des fonctions de tri identique a qsort().
void fonction_de_tri (void *base, size_t nmemb, size_t size, int (*compar)(const void*, const void *))


sortie :
-----------------
  9  -1   2   6  -3   7  10  -8  -4   0  -2   4  -9  -7   8   6   1  -5
 -9  -8  -7  -5  -4  -3  -2  -1   0   1   2   4   6   6   7   8   9  10
 0.000s - 36 permutations, 20 appels

tri my_qsort en cours sur 10000 entiers tries...
 1.313s - 19998 permutations, 19998 appels

tri my_qsort en cours sur 10000 entiers tries a l'envers...
 1.234s - 19998 permutations, 19998 appels

tri my_qsort en cours sur 25000 entiers aleatoires...
 0.031s - 173862 permutations, 33316 appels

-----------------
  9  -1   2   6  -3   7  10  -8  -4   0  -2   4  -9  -7   8   6   1  -5
 -9  -8  -7  -5  -4  -3  -2  -1   0   1   2   4   6   6   7   8   9  10
 0.000s - 22 permutations, 9 appels

tri my_qsort2 en cours sur 10000 entiers tries...
 1.547s - 0 permutations, 9998 appels

tri my_qsort2 en cours sur 10000 entiers tries a l'envers...
 1.906s - 5000 permutations, 9998 appels

tri my_qsort2 en cours sur 25000 entiers aleatoires...
 0.031s - 146113 permutations, 16633 appels

-----------------
  9  -1   2   6  -3   7  10  -8  -4   0  -2   4  -9  -7   8   6   1  -5
 -9  -8  -7  -5  -4  -3  -2  -1   0   1   2   4   6   6   7   8   9  10
 0.000s - 88 permutations, 0 appels

tri my_triselection en cours sur 10000 entiers tries...
 1.265s - 0 permutations, 0 appels

tri my_triselection en cours sur 10000 entiers tries a l'envers...
 4.547s - 49995000 permutations, 0 appels

tri my_triselection en cours sur 25000 entiers aleatoires...
 22.140s - 143398064 permutations, 0 appels

-----------------
  9  -1   2   6  -3   7  10  -8  -4   0  -2   4  -9  -7   8   6   1  -5
 -9  -8  -7  -5  -4  -3  -2  -1   0   1   2   4   6   6   7   8   9  10
 0.000s - 89 permutations, 0 appels

tri my_tribulle en cours sur 10000 entiers tries...
 0.000s - 0 permutations, 0 appels

tri my_tribulle en cours sur 10000 entiers tries a l'envers...
 6.562s - 49995000 permutations, 0 appels

tri my_tribulle en cours sur 25000 entiers aleatoires...
 33.235s - 143908654 permutations, 0 appels


Process returned 0 (0x0)   execution time : 73.953 s
Press any key to continue.
  • Partager sur Facebook
  • Partager sur Twitter
4 novembre 2008 à 20:41:12

Citation : yoch

1 void fonction_de_tri (void *base, size_t nmemb, size_t size, int (*compar)(const void*, const void *))




bonjour yoch, moi qui suit un "007"
j'ai du mal a decripter ta procedure fonction_de_tri :
void *base : tu envoie en entree une fonction par un pointeur ?
int (*compar)(const void*,const void*) : alors la c'est quoi ?
n'oublie pas qu'on débute pour ma part j'ai a peine digerer les pointeurs! :-°
si tu peux expliquer merci
Quantum Simplicity :p
  • Partager sur Facebook
  • Partager sur Twitter
4 novembre 2008 à 21:00:13

Citation : zx-spectrum

bonjour yoch, moi qui suit un "007"
j'ai du mal a decripter ta procedure fonction_de_tri :
void *base : tu envoie en entree une fonction par un pointeur ?
int (*compar)(const void*,const void*) : alors la c'est quoi ?
n'oublie pas qu'on débute pour ma part j'ai a peine digerer les pointeurs! :-°
si tu peux expliquer merci
Quantum Simplicity :p



Salut,

J'ai repris l'interface de la fonction standard qsort() de <stdlib.h>... Voir ici et la.

void* base est un pointeur de type void*, c'est a dire un pointeur qui fait abstraction de ce qui est pointé. (voir aussi déréférencement)

int (*compar)(const void*,const void*) est un pointeur de fonction utilisateur [que l'on doit fournir a qsort() - voir liens ci-dessus].

Tout cela permet d'utiliser la même fonction pour trier des tableaux de char, de int, de double, de pointeurs, etc...
  • Partager sur Facebook
  • Partager sur Twitter
4 novembre 2008 à 21:12:54

bon merci yoch pour tes exlications.
pour l'instant je me sens un peu dépassé (voire beaucoup pour l'instant :p )
je range cela de coté, je sais maintenant que dans une fonction on peut envoyer autre chose que de simples variables et des tableaux .
@+
  • Partager sur Facebook
  • Partager sur Twitter
5 novembre 2008 à 8:10:34

gné c'est quoi ces posts?

J'ai rien compris.
  • Partager sur Facebook
  • Partager sur Twitter
5 novembre 2008 à 21:13:26

Et précisément, qu'est-ce que tu n'as pas compris ?
  • Partager sur Facebook
  • Partager sur Twitter
5 novembre 2008 à 21:23:46

Arf, j'essairais de les faires quand j'aurais appris comment les faire, mais la je stagne au début de la partie 2...Je dois réviser...J'ai le bac cette année...et les parents sur le dos... :euh:
Mais dès que j'ai appris ces parties je le fais, ça commence a devenir vraiment interressant le C :p
  • Partager sur Facebook
  • Partager sur Twitter
TCOM 2014
5 novembre 2008 à 21:29:02

Citation : crys'

Et précisément, qu'est-ce que tu n'as pas compris ?



pour etre franc, tout à partir du post de yoch.
http://www.siteduzero.com/forum-83-329 [...] html#r3119377

Il n'y a pas autant de permutations?

Et j'ai lu la doc de qsort();
et j'ai rien compris aussi.
  • Partager sur Facebook
  • Partager sur Twitter
5 novembre 2008 à 21:45:37

Citation : Jaloyan1

Citation : shareman

Et précisément, qu'est-ce que tu n'as pas compris ?



pour etre franc, tout à partir du post de yoch.
http://www.siteduzero.com/forum-83-329 [...] html#r3119377

Il n'y a pas autant de permutations?


Ah bon ? Tu es sur ? As tu bien vu le nombre d'éléments a trier ?
(le premier affichage est un simple test)

Citation : Jaloyan1

Et j'ai lu la doc de qsort();
et j'ai rien compris aussi.


Le site de -ed- présente assez bien l'emploi de qsort(). Fais des test, cela t'aidera...
  • Partager sur Facebook
  • Partager sur Twitter
6 novembre 2008 à 13:22:56

et ca ca veut dire quoi?
-----------------
  9  -1   2   6  -3   7  10  -8  -4   0  -2   4  -9  -7   8   6   1  -5
 -9  -8  -7  -5  -4  -3  -2  -1   0   1   2   4   6   6   7   8   9  10
 0.000s - 88 permutations, 0 appels

tri my_triselection en cours sur 10000 entiers tries...
 1.265s - 0 permutations, 0 appels




0 permutations?
C'est quoi?
C'est cela qui m'a fait désorienter.

c'est le même algo, mais pas le même nombre de permutations.

et que veut dire les 2 lignes du debuts avec la troisième qui suit?

pourrais-tu m'envoyer le code source de ce programme pour que je comprenne mieux son fonctionnement?
  • Partager sur Facebook
  • Partager sur Twitter