Palindrome - Binaire

Bonjour voilà le but de l'exercice : il demande à l'utilisateur de saisir un nombre, mon algo est censé calculer l'équivalent binaire pour chaque nombre entre 1 et ce nombre, puis de déterminer pour chaque conversion binaire si celle-ci est un palindrome : 1001 est un palindrome et pour chaque binaire déterminé comme palindrome, faire la somme de chaque nombre(non binaire donc).

ex : ou ent est égal à 5 : 1=1

3=11

5=101

1+3+5=9

Voilà pour que ce soit clair, parceque j'étais pas sur que ça soit bien expliqué !

Voilà mon 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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

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




int main(void)
{

    int i=1;
    int j=1;
    char reste[256]="";
    char result[256]="";
    int ent=0;
    char result2[256]={};
    int longueur = strlen(result);
    int resultMul=1;

    printf("Saisir un nombre: ");
    scanf("%d", &ent);
    while(i<ent){
        while(i != 0){
            sprintf(reste, "%d", j%2);
            strcat(result, reste);
            i=i/2;
            printf("Binaire de %d: %s \n", i, result );
            result2[i] += result[longueur-i-1];
            printf("%s", result2);
            if(strcmp(result, result2) ==0){
                printf("Le Binaire de %d est un palindrome", i);
                resultMul += i;
                i++;
            }



    }

    return 0;
        }
}

J'ai essayé avec plusieurs combinaisons et généralement soit je tombe sur une boucle infinie :

1
2

Saisir un nombre: 5
Binaire de 0: 11111111111111111111111111111111111111 etc etc

ou je tombe sur :

1
2

Saisir un nombre: 5
Binaire de 0: 1

Salut,

premièrement, tu utilises la fonction strlen sur une chaîne vide. Le résultat sera donc chaque fois 0. Deuxièmement, la raison pour laquelle tu as une boucle infinie est parce que ta condition est mauvaise. En réalité, tu as deux boucles imbriquées mais qui fonctionnent toutes les deux sur la même variable. Cela veut dire que tu rentres dans la 1e boucle avec une certaine valeur pour i, que tu entres dans la 2nde avec la même valeur, mais dans cette seconde boucle, tu modifies i jusqu'à ce qu'il soit égale à 0. De là, tu recommences la première boucle. Mais donc à chaque fois que tu rentres dans la seconde boucle, ton i sera le même.

Il y a également plus simple pour déterminer la version binaire du nombre : en utilisant (var & (1 << b)) >> b, tu obtiens 1 ou 0 selon la valeur du bème bit. Dès lors, si tu sais qu'un int est codé sur 32 bits, tu peux utiliser le code suivant :

 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

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

void binary(const int n, char *str)
{
    int b = 32-1;
    int nb_bits;
    /* d'abord ignorer les premiers '0' */
    while(!(n & (1 << b)) && b >= 0)
        --b;
    nb_bits = b;  /* déterminer le nombre de bits significatifs */
    for(; b >= 0; --b)
        str[nb_bits-b] = ((n & (1 << b)) >> b) + '0';  /* transforme 1 ou 0 en '1' ou '0' */
    str[nb_bits+1] = '\0';  /* caractère de fin de chaîne */
}

int main(void)
{
    char str[33];  /* 32 bits + 1 pour le \0 final */
    binary(255, str);
    puts(str);
    binary(458659475, str);
    puts(str);
    return EXIT_SUCCESS;
}

Je te laisse déjà cela, essaye de t'occuper des palindromes.

EDIT : j'ai changé le code : j'avais oublié un +1 dans la ligne str[nb_bits+1] = '\0'; /* caractère de fin de chaîne */.

Merci pour ta réponse par contre j'ai pas trop compris les lignes :

pourquoi int b=32-1

while(!(n & (1 << b)) && b >= 0) =

C'est tant que l'inverse de (n et 1<<b) ET b>=0 (à quoi correspond 1<<b ?)

–b c'est une décrémentation de b du coup ?

Question sûrement bête mais on est pas obligé d'initialiser une variable dans une boucle for en c? ( genre for(i=0 ; i<..; i++) )

Ton code me parait plus compliqué !

Re,

Je me suis occupé du palindrome, par contre j'ai une erreur et la j'avoue je sais pas d'ou elle sort

 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
27
28
29
30
31
32
33
34
35
36
37

#include <stdlib.h>
#include <string.h>
void binary(const int n, char *str)
{
    int b = 32-1;
    int nb_bits;
    /* d'abord ignorer les premiers '0' */
    while(!(n & (1 << b)) && b >= 0)
        --b;
    nb_bits = b;  /* déterminer le nombre de bits significatifs */
    for(; b >= 0; --b)
        str[nb_bits-b] = ((n & (1 << b)) >> b) + '0';  /* transforme 1 ou 0 en '1' ou '0' */
    str[nb_bits] = '\0';  /* caractère de fin de chaîne */
}

int main(void)
{
    char str[33];  /* 32 bits + 1 pour le \0 final */
    int i;
    char result[33];
    int somme=0;
    binary(255, str);
    puts(str);
    int longueur=strlen(str);
    //binary(458659475, str);
    //puts(str);

    for(i=0 ; i<longueur ; i++)
        result[i] += str[longueur-i-1];
        printf("%s \n", result);
    if(strcmp(result,str) ==0 )
        printf("C'est un palindrome \n");
    else
        printf("Ce n'est pas un palindrome \n");

    return EXIT_SUCCESS;
}

En erreur j'ai ça :

1
2
3
4

root@Max:~/Bureau/C# ./a.out
1111111
2111111 
Ce n'est pas un palindrome 

La ça m'échappe d'ou il sort le 2 lol, c'est bizarre vu que je n'ai aucun 2 dans l'autre chaîne.

Hey, les opérateurs << et >> sont ce que l'on appelle des shifts bitwise. Cela veut dire que tu prends un nombre en binaire (par exemple $159_{10} = 10011111_2$), et tu le décales d'un certain nombre de bits. Donc v << b correspond à la valeur de la variable v décalée b fois vers la gauche (par exemple si v = 159, alors v << 3 == 100 11111000, ce qui vaut 1272). De manière similaire, l'opérateur dans l'autre sens décale vers la droite (par exemple si v = 159, alors v >> 3 == 00010011, ce qui vaut 19).

L'opérateur binaire & représente un ET logique de table de vérité :

Cela veut dire que si tu as deux variables a et b, quand tu fais a & b, tu obtiens une variable (ou du moins un résultat) correspondant à tous les bits valant 1 à la fois dans la variable a et à la fois dans la variable b.

On peut donc en comprendre que lorsque l'on fait v & (1 << b), on calcule d'abord (1 << b) ce qui correspond (en binaire) à un '1' et b '0' derrière (par exemple 1 << 0 == 1, 1 << 1 == 10, 1 << 2 == 100, etc.) La suite, c'est de prendre les bits valant 1 à la fois dans v et dans (1 << b). Or, dans 1 << b, il n'y a qu'un seul bit valant '1', et c'est le « premier ». Donc quand tu fais v & (1 << b), tu as pour résulta un nombre valant '0' sur tous ses bits sauf le bième (en partant du bit de poids faible, et donc de la droite — du moins dans l'écriture —). Ce nombre résultant vaut donc 0 si le bième bit de v vaut 0 et vaut (1 << b) si le bième bit de v vaut '1'.

Pour finir, on sait qu'en ASCII, le caractère '1' suit directement le caractère '0' (qui ont pour code respectif 49 et 48). Donc on veut obtenir uniquement comme résultat 1 ou 0. On refait donc un shift de b bits, mais dans l'autre sens cette fois-ci. Cela donne donc (v & (1 << b)) >> b.

PS : et pour la condition du while, on veut d'abord ignorer tous les caractères valant '0' a début du nombre. Donc tant que (n & (1 << b)) >> b vaut 0, on décrémente b pour passer au bit suivant.

Pour le palindrome, je répondrai plus tard, quand j'aurai le temps de m'y pencher un peu plus.

Écriture binaire

Pour l'initialisation en C, non : tu as trois zones séparées dans une boucle for en C.

1
2
3
4

for(/*zone d'initialisation*/; /*zone de condition de boucle*/; /*zone du pas d'incrément*/)
{
    /*...*/
}

Cependant, tu peux compléter celles que tu veux. Soit 0, soit 1, soit 2 soit 3.

La raison pour laquelle je n'ai rien mis dans l'initialisation, c'est parce que mon b est déjà initialisé.

Sinon, mon code t'a l'air un peu compliqué parce que les opérateurs bit-à-bit et les shifts s'utilisent assez rarement. Mais il est très important d'en comprendre le fonctionnement en C.

PS : pour la valeur initiale de b (à savoir 32-1 == 31), c'est simplement parce que je ne veux pas que b commence à 0 vu que je veux commencer à traiter le nombre par la gauche. Donc il faut que b ait la valeur du nombre tel que 1 << b représente un nombre avec un '1' en premier bit et que des 0 le suivant donc celui-ci pour un nombre sur 32 bits :

1

10000000 00000000 00000000 00000000

On constate que ce nombre fait en effet 32 bits (découpé en 4 octets de 8 bits). Donc de combien de bits faut-il décaler le '1' ? De 31 bits.

Il y a une manière un peu plus générale de faire cela (je n'ai traité que le cas des nombres sur 32 bits pour ne pas compliquer mon post). L'opérateur sizeof(ma_variable) te donne le nombre d'octets utilisés pour stocker ma_variable en mémoire. Et donc tu peux remplacer le int b = 32-1; par int b = sizeof(n)*8 - 1; mais ce n'est qu'un détail.

Palindromes

Premièrement, pourquoi utiliser l'opérateur += pour créer ta seconde chaîne ? À priori, vu que tu initialises ton tableau avec des zéros, ça devrait fonctionner,¹ mais c'est un drôle de choix. Il serait intuitivement bien plus logique (et plus performant mais là de manière imperceptible) d'utiliser une simple assignation.

Sinon, comme ça je dirais que ton problème vient de ce que l'on oublie toujours en C quand on manipule des chaînes de caractères, à savoir le '\0' final.

Ah oui effectivement c'était bien ça le soucis ! Merci !

Du coup il faut que je fasse, pour que ça calcul les binaires de i jusqu'à un nombre donné par l"utilisateur n puis ensuite faire la somme des nombres i qui sont des palindromes en binaire

Je te laisse faire ça. N'oublie pas de mettre en résolu une fois le problème réglé.

J'ai relu plusieurs les explications que tu m'as donné sur les bits shift mais je me perds un peu,

str[nb_bits-b] = ((n & (1 << b)) >> b) + '0'; / transforme 1 ou 0 en '1' ou '0' /

Pourquoi +'0' ? il est censé transformer en '1' Ou '0'?

Le + '0', ça sert juste à transformer le nombre en un chiffre affichable pour printf

Un nombre affichable pour printf ? je pige pas sans ça il est pas affichable ?

Si. Mais pour faire court, en informatique, tout est représenté par des nombres. Mais ces nombres ont un sens différent en fonction de l'utilisation (en particulier, en fonction du type de variable). Par exemple, la valeur $32$ (qui s'écrit 00100000 en binaire) peut valoir le nombre 32 si ta variable est un int mais peut représenter également le caractère espace (' ') si c'est un caractère (char).

Quand dans mon code je fais + '0', c'est pour passer d'un nombre qui est contenu dans un entier (et qui est entre 0 et 9 compris) en un nombre représentant un caractère ASCII particulier. Et ce caractère ASCII c'est le caractère affichable '1' ou le caractère affichable '0'.

Pour plus de détails sur l'ASCII, voir ce lien : http://www.asciitable.com. Tu peux bien y voir qu'en effet, le caractère qui te permet d'afficher un '0' à l'écran n'est pas le caractère de code binaire 0 mais bien le caractère de code binaire 48.

Une bonne manière d'en comprendre la différence est de comprendre et puis lancer ce très court code :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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

int main(void)
{
    int i = 0;
    for(; i < 128; ++i)
        printf("valeur entière : %03d  --  caractère représenté : %c\n", i, i);
    return EXIT_SUCCESS;
}

En faisant cela, tu te rends également compte que certains codes binaires ne représentent pas de caractères affichables à proprement parlé (car ils ne s'affichent pas tels quels) mais permettent de structurer une communication, un fichier, un texte, etc.