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

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 ni + ni -
@+

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

on est occupé par la révision, pas de vacances

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 a écrit:NB: l'algo proposé est ecrit en C,nn?en C il n'y a pas le type bool

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.

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

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).

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!!!

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 ?

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

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
par contre si tu peux expliquer un peu ton code s'il te plait

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

Qu'est-ce qui ne te semble pas clair à part ça ?

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 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

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 &&)

ah ouééé je suis con :p

bravo !!! très instructive la discussion.

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