Exercice : Pas de chiffres qui se répètent

Voir le sujet précédent Voir le sujet suivant Aller en bas

Exercice : Pas de chiffres qui se répètent

Message par Napoléon le Sam 22 Déc - 23:02

Code:
bool is_valid(int value)
{
    char buffer[20];
    char *pi, *pj;

    itoa(value, buffer, 10);

    bool valid = true;

    pi = buffer + 1;
    while (valid && *pi != 0)
    {
        pj = pi - 1;

        while (pj >= buffer && *pi != *pj) pj--;
        valid = (*pi != *pj);

        pi++;
    }

    return valid;
}
La fonction ci-dessus a été proposée par manianis.
Elle vérifie si un nombre donné ne contient pas des chiffres qui se répètent plus qu'une fois.

La question est :
1. Proposer d'autres solutions, et la comparer avec celle proposée ici.
2. Peut-on écrire un algorithme "le plus court possible" qui répond à la question.

L'Objectif est de partager avec vous le plaisir de résoudre des problèmes Smile ni + ni -
@+

_________________
Nabil - tunis
خير الناس أنفعهم للناس
avatar
Napoléon
Admin
Admin

Masculin
Nombre de messages : 2934
Localisation : Tunisie
Réputation : 122
Points : 5340
Date d'inscription : 19/03/2007

Feuille de personnage
Capacité linguistique:
999/1000  (999/1000)

http://infomath.online-talk.net

Revenir en haut Aller en bas

Re: Exercice : Pas de chiffres qui se répètent

Message par Napoléon le Ven 28 Déc - 0:13

Pas de réponses?
Ou c'est les vacances?
Wink

_________________
Nabil - tunis
خير الناس أنفعهم للناس
avatar
Napoléon
Admin
Admin

Masculin
Nombre de messages : 2934
Localisation : Tunisie
Réputation : 122
Points : 5340
Date d'inscription : 19/03/2007

Feuille de personnage
Capacité linguistique:
999/1000  (999/1000)

http://infomath.online-talk.net

Revenir en haut Aller en bas

Re: Exercice : Pas de chiffres qui se répètent

Message par suneddine le Ven 28 Déc - 0:34

on est occupé par la révision, pas de vacances
avatar
suneddine
Nombre Réel
Nombre Réel

Masculin
Nombre de messages : 730
Age : 32
Localisation : tunisie
Réputation : 5
Points : 3790
Date d'inscription : 11/11/2007

Feuille de personnage
Capacité linguistique:
995/1000  (995/1000)

Revenir en haut Aller en bas

Re: Exercice : Pas de chiffres qui se répètent

Message par moudhafer le Mar 22 Juin - 15:16

cet algo est en o(n²) moi que je propose on trie la chaine de l'netier en un tri en O(nlog.n)comme ca si il y en a des chiffres qui se repete ils seront en block par exemple 1354621354 ser 112334456 et puis on parcourt la chain en O(n) pour detecter les block
NB: l'algo proposé est ecrit en C,nn?en C il n'y a pas le type bool

moudhafer
Entier Naturel
Entier Naturel

Masculin
Nombre de messages : 58
Age : 28
Localisation : france
Réputation : 0
Points : 2832
Date d'inscription : 26/05/2010

Revenir en haut Aller en bas

Re: Exercice : Pas de chiffres qui se répètent

Message par informix le Mar 22 Juin - 17:59

moudhafer a écrit:NB: l'algo proposé est ecrit en C,nn?en C il n'y a pas le type bool

Smile non, ça dépend du compilateur. Sur Windows, Visual Studio 200X comprend lorsqu'on lui met le type Bool.

De plus, même s'il n'y a pas le type Bool, un petit "define" résoud le problème. Very Happy

_________________
informix, Ecole d'ingénieurs
Les passions font vivre l'Homme; sa sagesse le fait seulement durer.
avatar
informix
Nombre Rationnel
Nombre Rationnel

Nombre de messages : 399
Réputation : 4
Points : 3994
Date d'inscription : 19/03/2007

Feuille de personnage
Capacité linguistique:
1000/1000  (1000/1000)

Revenir en haut Aller en bas

Re: Exercice : Pas de chiffres qui se répètent

Message par moudhafer le Jeu 24 Juin - 2:18

aaa d'accord parce que moi je compile sur linux,en tout cas c pas ca notre probleme Wink
a propos mon idée ca vous va???

moudhafer
Entier Naturel
Entier Naturel

Masculin
Nombre de messages : 58
Age : 28
Localisation : france
Réputation : 0
Points : 2832
Date d'inscription : 26/05/2010

Revenir en haut Aller en bas

Re: Exercice : Pas de chiffres qui se répètent

Message par Timon le Mer 7 Juil - 16:17

moudhafer a écrit:NB: l'algo proposé est ecrit en C,nn?en C il n'y a pas le type bool
Ca dépend. En C89, non. En revanche, le C99 définit un type _Bool et une macro bool (voir ceci).

Timon
Entier Naturel
Entier Naturel

Masculin
Nombre de messages : 61
Localisation : France
Réputation : 0
Points : 3630
Date d'inscription : 14/01/2008

Feuille de personnage
Capacité linguistique:
1000/1000  (1000/1000)

http://tm.timon.free.fr

Revenir en haut Aller en bas

Re: Exercice : Pas de chiffres qui se répètent

Message par moudhafer le Jeu 8 Juil - 1:47

oui ta raison pour le 99 oui,deja le 99 est plus simplifié comme par exemple la definition des variables au milieu des lignes des codes qui est possible en 99 pas en 89,et c'est pa ca le probleeeeeeeeeeeeeeeeeeeeeme,vous pensez quoi de mon idée!!!

moudhafer
Entier Naturel
Entier Naturel

Masculin
Nombre de messages : 58
Age : 28
Localisation : france
Réputation : 0
Points : 2832
Date d'inscription : 26/05/2010

Revenir en haut Aller en bas

Re: Exercice : Pas de chiffres qui se répètent

Message par methodiX le Jeu 8 Juil - 3:29

Alors, je reprends la question posée au début de ce Topic:

On cherche le meilleur algorithme qui vérifie si une chaine contient des caractères qui se répètent plus qu'une fois ou non.

L'algorithme proposé en haut est en O(n²)
Ce lui de @moudhafer est en O(n+n.Log(n)) <à simplifier le O(...)>

Y-a-t-il mieux ?


_________________
Sami - Methodix, tunis
Le génie de Newton a consisté à dire que la lune tombe alors que tout le monde voit bien qu'elle ne tombe pas.
(Paul Valéry)
_____
Cliquer ici: Voir les nouveaux messages depuis votre dernière visite
Cliquer ici: Astuce: Utiliser l'outil "Recherche" du forum
avatar
methodiX
Admin
Admin

Masculin
Nombre de messages : 1260
Localisation : Le couloir de l'école polytechnique de Tunis
Réputation : 68
Points : 4722
Date d'inscription : 22/03/2007

Feuille de personnage
Capacité linguistique:
1000/1000  (1000/1000)

Revenir en haut Aller en bas

Re: Exercice : Pas de chiffres qui se répètent

Message par Timon le Jeu 8 Juil - 12:36

methodiX a écrit:Ce lui de @moudhafer est en O(n+n.Log(n)) <à simplifier le O(...)>
Se simplifie par O(n.log(n)).

methodiX a écrit:Y-a-t-il mieux ?
Certainement : O(n)
En marquant tous les chiffres déjà trouvés (tableau de 10 booléens ou variable d'au moins 10 bits).
Code:
int chiffres_uniques(int valeur)
{
  unsigned int chiffres = 0;
  unsigned int valeur_absolue = abs(valeur);
  while(valeur_absolue > 0)
  {
      const unsigned int chiffre = valeur_absolue % 10;
      if(((chiffres >> chiffre) & 1u) == 1u)
      {
        return 0;
      }
      chiffres |= 1u << chiffre;
      valeur_absolue /= 10;
  }
  return 1;
}
Note : ne fonctionne que pour les valeurs dans l'intervalle [-INT_MAX, INT_MAX]. Malheureusement, |INT_MIN| peut être supérieur à INT_MAX.
La solution pourraît être de faire comme manianis : utiliser itoa() ou, plus portable, sprintf(), pour inscrire la valeur dans une chaîne de caractères. Le problème alors est de déterminer à la compilation quelle taille donner au tableau de caractères.
D'après la formule d'Eric Sosman, les valeurs de type long peuvent être inscrites sur au plus BIG_ENOUGH caractères :
Code:
#define BIG_ENOUGH (1 + (sizeof(long) * CHAR_BIT + 2) / 3 + 1)
Ce qui donne :
Code:
int chiffres_uniques(int valeur)
{
  unsigned int chiffres = 0;
  char s_valeur[BIG_ENOUGH + 1];
  int num_chiffre = 0;
 
  sprintf(s_valeur, "%d", valeur);
 
  if(!isdigit(s_valeur[0]))
  {
      ++num_chiffre;
  }
 
  for( ; s_valeur[num_chiffre] != '\0'; ++num_chiffre)
  {
      const unsigned int chiffre = s_valeur[num_chiffre] - '0';
      if(((chiffres >> chiffre) & 1u) == 1u)
      {
        return 0;
      }
      chiffres |= 1u << chiffre;
  }
  return 1;
}

Timon
Entier Naturel
Entier Naturel

Masculin
Nombre de messages : 61
Localisation : France
Réputation : 0
Points : 3630
Date d'inscription : 14/01/2008

Feuille de personnage
Capacité linguistique:
1000/1000  (1000/1000)

http://tm.timon.free.fr

Revenir en haut Aller en bas

Re: Exercice : Pas de chiffres qui se répètent

Message par moudhafer le Jeu 8 Juil - 15:39

en fait j'ai pas bien compris le decalage?le decallage vers le gauche fais effectue des multiplications par des puissances de 2:nn?
so j'ai compris : tu veux dire,on alloue un tableau de 10 cases indicées par les char "0" jusqu'au "9", et on parcourt la chaine et à chaque fois en test si tab[ch[i]] est égale à 0 ou non !!!
aaaa bonne idée Smile
par contre si tu peux expliquer un peu ton code s'il te plait Very Happy

moudhafer
Entier Naturel
Entier Naturel

Masculin
Nombre de messages : 58
Age : 28
Localisation : france
Réputation : 0
Points : 2832
Date d'inscription : 26/05/2010

Revenir en haut Aller en bas

Re: Exercice : Pas de chiffres qui se répètent

Message par Timon le Jeu 8 Juil - 19:39

moudhafer a écrit:en fait j'ai pas bien compris le decalage?le decallage vers le gauche fais effectue des multiplications par des puissances de 2:nn?
Oui, mais ce n'est pas l'objectif ici.
Code:
1u << n
Donne une valeur où seul le bit n vaut 1. Ainsi, en écrivant :
Code:
valeur |= 1u << n
Je force le bit n de valeur à prendre la valeur 1.
Code:
(valeur >> n) & 1u
me permet d'extraire le bit n.
so j'ai compris : tu veux dire,on alloue un tableau de 10 cases indicées par les char "0" jusqu'au "9", et on parcourt la chaine et à chaque fois en test si tab[ch[i]] est égale à 0 ou non !!!
Plutôt
Code:
tab[ch[i] - '0']
mais sinon, tu as bien compris.
par contre si tu peux expliquer un peu ton code s'il te plait Very Happy
Qu'est-ce qui ne te semble pas clair à part ça ?

Timon
Entier Naturel
Entier Naturel

Masculin
Nombre de messages : 61
Localisation : France
Réputation : 0
Points : 3630
Date d'inscription : 14/01/2008

Feuille de personnage
Capacité linguistique:
1000/1000  (1000/1000)

http://tm.timon.free.fr

Revenir en haut Aller en bas

Re: Exercice : Pas de chiffres qui se répètent

Message par moudhafer le Ven 9 Juil - 2:30

d'accooooooord donc au lieu d'allouer un tableau de 10 cases tu vas utiliser un entier de 10 bit,c comme un tableau de bool,oué comme ça on utilise moins de memoire,okkkkk.
et a propos les explicationslà c bon j'ai pas compris les decalages et tout.merci là franchement tu m'as appris beaucoup de trucs Very Happy je te remercie enormement.
il me reste une petite question c quoi le pipe "|"??ca sert a quoi en C??moi je connais en shell le pipe c pour deriger la sortie standard d'une commande vers l'entrée d'une autre commande,c pa la meme chose???
merci de nouveau Smile

moudhafer
Entier Naturel
Entier Naturel

Masculin
Nombre de messages : 58
Age : 28
Localisation : france
Réputation : 0
Points : 2832
Date d'inscription : 26/05/2010

Revenir en haut Aller en bas

Re: Exercice : Pas de chiffres qui se répètent

Message par Timon le Sam 10 Juil - 1:02

moudhafer a écrit:il me reste une petite question c quoi le pipe "|"??
C'est l'opérateur OU binaire.
Code:
0011 | 1001 = 1011
A ne pas confondre avec l'opérateur OU logique.
Code:
0011 || 1001 = 0001 (vrai)
(idem pour & et &&)

Timon
Entier Naturel
Entier Naturel

Masculin
Nombre de messages : 61
Localisation : France
Réputation : 0
Points : 3630
Date d'inscription : 14/01/2008

Feuille de personnage
Capacité linguistique:
1000/1000  (1000/1000)

http://tm.timon.free.fr

Revenir en haut Aller en bas

Re: Exercice : Pas de chiffres qui se répètent

Message par moudhafer le Dim 11 Juil - 14:23

ah ouééé je suis con :p

moudhafer
Entier Naturel
Entier Naturel

Masculin
Nombre de messages : 58
Age : 28
Localisation : france
Réputation : 0
Points : 2832
Date d'inscription : 26/05/2010

Revenir en haut Aller en bas

Re: Exercice : Pas de chiffres qui se répètent

Message par Napoléon le Lun 12 Juil - 21:01

bravo !!! très instructive la discussion.

_________________
Nabil - tunis
خير الناس أنفعهم للناس
avatar
Napoléon
Admin
Admin

Masculin
Nombre de messages : 2934
Localisation : Tunisie
Réputation : 122
Points : 5340
Date d'inscription : 19/03/2007

Feuille de personnage
Capacité linguistique:
999/1000  (999/1000)

http://infomath.online-talk.net

Revenir en haut Aller en bas

Re: Exercice : Pas de chiffres qui se répètent

Message par Napoléon le Lun 12 Juil - 21:39

La question qui se pose maintenant, y-a-t-il encore mieux que la solution donnée par Timon ?!

_________________
Nabil - tunis
خير الناس أنفعهم للناس
avatar
Napoléon
Admin
Admin

Masculin
Nombre de messages : 2934
Localisation : Tunisie
Réputation : 122
Points : 5340
Date d'inscription : 19/03/2007

Feuille de personnage
Capacité linguistique:
999/1000  (999/1000)

http://infomath.online-talk.net

Revenir en haut Aller en bas

Re: Exercice : Pas de chiffres qui se répètent

Message par Contenu sponsorisé


Contenu sponsorisé


Revenir en haut Aller en bas

Voir le sujet précédent Voir le sujet suivant Revenir en haut

- Sujets similaires

 
Permission de ce forum:
Vous ne pouvez pas répondre aux sujets dans ce forum