comparaison en chiffre

Version imprimable

Voir 40 message(s) de cette discussion en une page

11/10/2006, 20h13
bonomsoleil

comparaison en chiffre

Bonsoir Tous le monde !

J'ai un probleme qui me tourmente vraiment :? le prof nous a donne un petit programme bizzare, je peux le resumer ainsi :
un programme qui compare un nombre ( de 1 a 5 chiffres) dans un rang de 1 a 32000. Si ce nombre comporte le chiffre 3 il est imprime, sinon il ne l'est pas.
Peut etre que ca vous parait "bete" mais je n'arrive pas a resoudre ce probleme :aie:

Merci d'avance
11/10/2006, 20h17
®om

Je dirais, une boucle en 5 itérations maxi qui divise par 10 à cq étape et qui regarde si le modulo 10 du résultat vaut 3...
11/10/2006, 20h21
homeostasie

Je ne vois pas très bien ou se situe la question...;) Le prof t'a demandé de faire ce programme?

Si c'est le cas, deux méthodes me viennent à l'esprit rapidement:
-> Convertir ton nombre sous forme d'une chaine de caractères puis comparer chaque caractère au caractère 3.

-> Sinon utiliser les opérations de décalage sur ton nombre puis faire un masque de bits avec la valeur 3.
11/10/2006, 20h24
Graffito

Bonsoir,

ou sprintf dans un char[6] puis strtok du caractère "3".
11/10/2006, 20h25
®om

Citation:

Envoyé par homeostasie

-> Sinon utiliser les opérations de décalage sur ton nombre puis faire un masque de bits avec la valeur 3.

Les décalages c'est juste pour les représentations en base 2 (ou puissances de 2). Là il veut un 3 dans une représentation en base 10...
11/10/2006, 20h36
homeostasie

Citation:

Envoyé par ®om

Les décalages c'est juste pour les représentations en base 2 (ou puissances de 2). Là il veut un 3 dans une représentation en base 10...

Ouhla en effet, ou ais je la tête...:roll: Sorry!
11/10/2006, 21h04
Gruik

Citation:

Envoyé par Graffito

Bonsoir,

ou sprintf dans un char[6] puis strtok du caractère "3".

strchr(), encore plus simple

Un moyen tordu de répondre à la question...

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdlib.h>
#include <stdio.h>
 
int main(int argc, char** argv)
{
  int i;
  for (i = 1; i < argc; ++i)
  {
    char* end;
    unsigned long n = strtol(argv[i], &end, 16);
    if (*end != '\0') {
      printf("%s is not a number\n", argv[i]);
    } else {
      n -= 0x33333;
      if (((n - 0x11111) & 0x88888 & ~n) != 0) {
        printf("%s\n", argv[i]);
      }
    }
  }
  return 0;
}

11/10/2006, 21h32
bonomsoleil

Citation:

n -= 0x33333;
if (((n - 0x11111) & 0x88888 & ~n) != 0)
printf("%s\n", argv[i]);

Quel est le role exacte de ce code ?
Le main ne necessite pas un return ?
11/10/2006, 21h38
Jean-Marc.Bourguet

Citation:

Envoyé par bonomsoleil

Quel est le role exacte de ce code ?

Chercher des 3 dans une représentation hexadécimale limitée à 5 caractères.

Citation:

Le main ne necessite pas un return ?

Corrigé.
11/10/2006, 21h39
Gruik

Houla :mrgreen:
Et ça marche si n < 0x33333?
11/10/2006, 21h50
Jean-Marc.Bourguet

Citation:

Envoyé par Gruik

Houla :mrgreen:
Et ça marche si n < 0x33333?

Pourquoi ça ne marcherait pas?
11/10/2006, 21h59
bonomsoleil

merci :D
11/10/2006, 22h40
Gruik

J'aimerais bien savoir comment t'es arrivé à ce calcul (à part si c'est trop long à expliquer)

Citation:

Pourquoi ça ne marcherait pas?

Dans ce cas, n fait un tour de modulo de l'unsigned long, j'ai du mal à croire que ça produise un resultat interessant pour le probleme
12/10/2006, 07h28
Jean-Marc.Bourguet

Citation:

Envoyé par Gruik

J'aimerais bien savoir comment t'es arrivé à ce calcul (à part si c'est trop long à expliquer)

Je n'ai pas inventé l'astuce moi-même, je suis tombé sur un programme qui l'utilisait (pour vérifier si un byte était à 0 dans un mot). Je n'ai pas le temps d'expliquer maintenant. Si dans quelques jours je ne l'ai pas fait, relance-moi par email.

Citation:

Dans ce cas, n fait un tour de modulo de l'unsigned long, j'ai du mal à croire que ça produise un resultat interessant pour le probleme

C'est justement à cause du module que ça marche.
12/10/2006, 13h04
diogene
Si bonomsoleil utilise la solution de Jean-Marc, le prof va avoir une crise cardiaque ! Peut-être qq chose de plus simple du genre :
Code:

1 2 3 int i = n; while(i!=0 && i%10!=3 && i%10!=-3) i/=10; if (i!=0) printf("%d ",n);
lui préserverait la santé

Comment ça marche

Grâce à Dark_Ebola qui m'a relancé, voici comment ceci fonctionne:
Citation:
Envoyé par Jean-Marc.Bourguet
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include <stdlib.h> #include <stdio.h> int main(int argc, char** argv) { int i; for (i = 1; i < argc; ++i) { char* end; unsigned long n = strtol(argv[i], &end, 16); if (*end != '\0') { printf("%s is not a number\n", argv[i]); } else { n -= 0x33333; if (((n - 0x11111) & 0x88888 & ~n) != 0) { printf("%s\n", argv[i]); } } } return 0; }
Premièrement, j'évalue le nombre décimal en prétendant qu'il est en hexadécimal. Donc, j'ai en fait du BCD (décimal codé binaire). L'objectif est de trouver les 3. Ce qui va mettre des 0 (en décimal codé binaire) aux endroits où il y avait des trois et (bug, Gruik avait raison, il y a des problèmes) aussi où il y avait des quatre suivis d'un chiffre inférieur à 3.

Il faut donc savoir s'il y a un ou des 0. En soustrayant 0x11111 les 0 deviennent des 0xF, en prenant un et logique avec 0x88888 on se retrouve avec 0x8 là ou il y avait des 9, A, B, C, D, E, F, 0. En faisant un et logique avec ~n, on n'a plus des 0x8 que là où il y avait des 0 (il y a un autre cas quand il y a eu une retenue, mais ici s'il y a retenue ça veut dire qu'il y avait un 0 avant, donc pas de problème).

Le truc peut être employé pour chercher s'il y a au moins un octet à 0 dans un mot:

Code:

(n - ((unsigned) -1)/255) & ((unsigned) -1)/255*128) & ~n

(unsigned) -1)/255 va donner 0x01010101 avec des unsigned de 32 bits et 0x0101010101010101 avec des unsigned de 64 bits. Ça ne marche que pour des multiples de 8 bits.

23/10/2006, 19h05
Emmanuel Delahaye

Citation:

Envoyé par bonomsoleil

J'ai un probleme qui me tourmente vraiment :? le prof nous a donne un petit programme bizzare, je peux le resumer ainsi :
un programme qui compare un nombre ( de 1 a 5 chiffres) dans un rang de 1 a 32000. Si ce nombre comporte le chiffre 3 il est imprime, sinon il ne l'est pas.
Peut etre que ca vous parait "bete" mais je n'arrive pas a resoudre ce probleme

Ben, 3 chiffres (significatifs, je suppose), en décimal, ça veut dire de 100 à 999 inclus ? Non ?

C'est un peu 'brute force' comme méthode, mais ça répond à la question...
25/10/2006, 03h50
koala01

Salut,

Citation:

Envoyé par Emmanuel Delahaye

Ben, 3 chiffres (significatifs, je suppose), en décimal, ça veut dire de 100 à 999 inclus ? Non ?

C'est un peu 'brute force' comme méthode, mais ça répond à la question...

J'ai l'impression que tu confond...
Il ne veut pas trois chiffres significatifs, mais voir apparaitre, dans la notation décimale, le chiffre trois au moins une fois... 3,103,13,30,31333...

Selon moi, et bien que la solution de Jean-Marc présente un intéret certain (quoi que, effectivement, le prof risque d'en faire un infarctus ;):D) le plus facile est de transformer le nombre en chaine, puis d'en tester chaque caractère jusqu'à ce qu'on en trouve un qui corresponde à notre souhait...

D'ailleurs, quand on y pense bien, rien ne nous oblige à travailler réellement avec le type "entier" (meme si on y pense tout de suite quand on parle de nombres)...

Traitons ce nombre directement comme une chaine, saisissons le en tant que chaine, et non en tant qu'entier... et testons chaque caractère de la chaine pour savoir s'il entre dans les conditions pour etre affiché... Apres tout, rien dans l'énoncé ne stipule qu'une opération arithmétique quelconque ne sera effectuée dessus... et, au pire, il sera toujours temps de le convertir en entier s'il advient qu'il est nécessaire d'effectuer un calcul avec ;)

La "loi du moindre effort", ca dit quelque chose à quelqu'un? :D

Si l'on part sur ce que j'ai exposé dans mon message précédent, voici un code "tout simple" qui fonctionne ;)

La convertions en entier, outre le fait qu'elle prépare à un éventuel calcul, permet ici de vérifier que l'on est bien dans les limites imposées ;)

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int main()
{
    //comptons large... 10 caractères effectifs, ca semble pas mal ;)
    char nombre[11];
    int verif;
    int affiche=0;
    int cpt=0;
    printf("Intrudisez un nombre entre 1 et 31000\n");
    fgets(nombre,10,stdin);
    //autant vérifier la validité de l'introduction ici
    verif=atoi(nombre);
    if(verif<1 || verif>31000)
        affiche=2;
    while(cpt<6 && affiche==0)
    {
        //si on trouve un '3' dans la  chaine, c'est bon ;)
        if(nombre[cpt]=='3')
            affiche=1;
        cpt++;
    }
    if(affiche==1)
        printf("%d",nombre);
    if(affiche==2)
        printf("la valeur introduite n'est pas valable");
    return 0;
}

Voir 40 message(s) de cette discussion en une page