Exercice sur l'exponentiation rapide

Version imprimable

02/11/2019, 17h03
wafzy

Exercice sur l'exponentiation rapide

bonjour tout le monde, je suis nouvelle dans le forum et j'ai une petite question en espérant que quelqu'un pourrait m'aider :
je suis entrain de réviser mes examens et je fais des exercices supplémentaire donné par mon prof et je beug sur une question
- il faut écrire un algo qui prend en entrée un entier et qui stocke dans un tableau sa décomposition en base 2 , je n'arrive pas à comprendre comment on pourrais faire cela ?
merci en avance
02/11/2019, 17h40
joel.drigo

Salut,

La décomposition en base 2 permet de déterminer les nombres d'une écriture binaire du nombre.
Un nombre entier, par exemple, 42, peut s'écrire en base 2 : 101010.

Mathématiquement, cela signifie qu'on peut écrire :

0×2⁰+1×2¹+0×2²+1×2³+0×2⁴+1×2⁵ =
0 + 2 + 0 + 8 + 0 + 32 = 42

Tout comme d'ailleurs 42, en base 10, peut s'écrire 2×10⁰+4×10¹, soit 2 + 40.

Remarque bien que les puissances correspondent à la position du chiffre dans le nombre (en partant de la fin) et que le multiplicateur est la valeur du chiffre.

Ce que tu dois faire c'est donc retrouver quels 0 et 1 il faut pour représenter un nombre saisi au clavier.

Il suffit de remarquer que on peut écrire la première expression : n + 2 fois quelque chose. Puisqu'on a que des puissances de 2 : on peut diviser toutes l'expression, sauf le premier terme (puissance 0), par 2. une somme de a_i×2^j avec j de 1 à n donne 2 × ( une somme de a_i×2^j avec j de 0 à n-1.

En gros, chaque fois que tu divises par 2, tu obtiens un résultat et un reste. En observant ce que tu peux obtenir, en essayant avec différents nombres, tu devrais pouvoir trouver l'algorithme en question.

Ça va sans dire, mais ça va mieux en le visualisant

Apprendre en ligne : Les bases décimale, binaire et hexadécimale

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
Simulation :
 
42 : 2 = 21 reste 0 (20 =  0)
21 : 2 = 10 reste 1 (21 =  2)
10 : 2 =  5 reste 0 (22 =  4)
 5 : 2 =  2 reste 1 (23 =  8)
 2 : 2 =  1 reste 0 (24 =  2)
            reste 1 (25 = 32)
                    ________
                          42
 
 E -> [E]ntier
 I -> [I]ndice courant 
 R -> [R]este
 
                     .---------------------.
                     |       E  = ?        |    -> [E]ntier = Saisie d’un entier
              D_PROG |       T  = occ * 16 |    -> Déclaration [T]able de 16 occurrences initialisées à zéro
                     |       E :: 65535    |    -> Test [E]ntier (maximum)
            > 65535  .----------+----------. <= 65535
           .-------------------<?>-------------------.
           |                              .----------+----------.
           |                     D_DIV    |        I = 16       |  -> Initialisation indice I
           |                              .----------+----------.
           |                                         |-------------------.
           |                              .----------+----------.        |  E=42/2   E=21/2   E=10/2   E=5/2    E=2/2
.----------+----------.                   |        E = E / 2    |        |  R=0      R=1      R=0      R=1      R=0
|       MESSAGE       |          T_DIV    |     T(I) = R        |        |  T(16)=0  T(15)=1  T(14)=0  T(13)=1  T(12)=0
.----------+----------.                   |        I = I - 1    |        |  I=15     I=14     I=13     I=12     I=11
           |                              |        E :: 1       |        |  E=21     E=10     E=5      E=2      E=1
           |                              .----------+----------. E > 1  |
           |                                        <?>------------------.
           |                              .----------+----------.
           |                     F_DIV    |     T(I) = E        |                                                         T(11)=1
           |                              .----------+----------.
           .--------------------+--------------------.
                     .----------+----------.
              F_PROG |          Ø          |
                     .---------------------.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
 
bin[] est un tableau
dec est le nombre à transcrire entre 0 et 255 (8 bits)
Pour x = 1 à 8
    a = dec / 2
    Si partie entière de "a" * 2 = dec alors bin(x) = 0
    Si partie entière de "a" * 2 <> dec alors bin(x) = 1
   dec = partie entière de "a"
x suivant
Pour x = 1 à 8
   Ecrire bin(x) + espace
x suivant

J'ai bon ?

Citation:

Envoyé par valentin03

J'ai bon ?

A part que le nombre est à l'envers (il suffirait de boucler de 8 à 1 au lieu de 1 à 9 pour obtenir le nombre dans le bon sens), et qu'il faut bien interpréter "Si partie entière de "a" * 2" comme "Si (partie entière de "a") * 2" et non "Si partie entière de ("a" * 2) ", et dans les conditions indiquées, oui c'et bon.

J'aurais fait, sans utiliser autre chose que des int, (avec des index de tableau de 0 à L exclu :
Code:

1 2 3 4 5 6 7 8 9 bin[] est un tableau de taille L n est un nombre i <- L tant que n>0 i <- i-1 si i<0 lancer Overflow error (nombre tenant sur plus de L bits) bin[i] = reste de la division entière de n par 2 (n modulo 2) n = division entière de n par 2 fin tant que

Citation:
Envoyé par joel.drigo
A part que le nombre est à l'envers (il suffirait de boucler de 8 à 1 au lieu de 1 à 9 pour obtenir le nombre dans le bon sens), et qu'il faut bien interpréter "Si partie entière de "a" * 2" comme "Si (partie entière de "a") * 2" et non "Si partie entière de ("a" * 2) ", et dans les conditions indiquées, oui c'et bon.

J'aurais fait, sans utiliser autre chose que des int, (avec des index de tableau de 0 à L exclu :
Code:

1 2 3 4 5 6 7 8 9 bin[] est un tableau de taille L n est un nombre i <- L tant que n>0 i <- i-1 si i<0 lancer Overflow error (nombre tenant sur plus de L bits) bin[i] = reste de la division entière de n par 2 (n modulo 2) n = division entière de n par 2 fin tant que
Merci pour la précision et les parenthèses, ça peut servir.

14/11/2019, 16h35
Invité

Citation:

Envoyé par joel.drigo

A part que le nombre est à l'envers (il suffirait de boucler de 8 à 1 au lieu de 1 à 9 pour obtenir le nombre dans le bon sens)

D'où mon initialisation "I = 16" et ma décrémentation "I = I - 1" dans mon organigramme.

Pourquoi 16 et un entier maximum de 65535 ? Pour rester cohérent avec l'exemple du site Apprendre en ligne : Les bases décimale, binaire et hexadécimale.

… Mais c'est génial, cette balise "SPOILER" ! Je ne connaissais pas ! Elle n'est pas proposée dans la construction d'un message ! Ça change tout ! Merci de me l'avoir fait découvrir.
14/11/2019, 17h38
joel.drigo
Citation:

Envoyé par IFA2377

… Mais c'est génial, cette balise "SPOILER" ! Je ne connaissais pas ! Elle n'est pas proposée dans la construction d'un message ! Ça change tout ! Merci de me l'avoir fait découvrir.

Y'a pas de quoi :) Y'en a d'autres comme ça qui ne sont pas disponibles par un bouton de l'éditeur de messages. Comme [PRE] par exemple que tu aurais pu utiliser pour ton organigramme, pour ne pas avoir des numéros de lignes et une éventuellement coloration syntaxique forcément inadéquate).
```
          │
┌─────────┴─────────┐
│non proportionnelle│
└───────────────────┘
```
ou encore une que j'aime bien, [noparse], qui permet de désactiver localement les automatismes de conversion de présentation, comme ici :

Citation:

Pour cacher une partie de votre message utilisez la balise [spoiler]. Par exemple :

[spoiler]Votre message à cacher[/spoiler]

ou encore de mélanger des smileys et des textes qui sont compris comme des smileys mais qu'on ne veut pas qu'ils le soient

Citation:

;) et ;) sont dans un bateau...

[EDIT]J'allais oublier aussi la balise [LATEX] qui peut avoir son utilité :

Je balise !

Uniquement entre les balises "PRE" et "/PRE"

Ma police de caractère Courrier new est respectée et mes caractères semi-graphiques s'affichent correctement, sauf que le texte déborde du cadre :

Simulation :

42 : 2 = 21 reste 0 (20 =  0)
21 : 2 = 10 reste 1 (21 =  2)
10 : 2 =  5 reste 0 (22 =  4)
 5 : 2 =  2 reste 1 (23 =  8)
 2 : 2 =  1 reste 0 (24 =  2)
            reste 1 (25 = 32)
                    ________
                          42

 E -> [E]ntier
 I -> [I]ndice courant 
 R -> [R]este

                     ┌─────────────────────┐
                     │       E  = ?        │    ─> [E]ntier = Saisie d’un entier
              D_PROG │       T  = occ * 16 │    ─> Déclaration [T]able de 16 occurrences initialisées à zéro
                     │       E :: 65535    │    ─> Test [E]ntier (maximum)
            > 65535  └──────────┬──────────┘ <= 65535
           ┌───────────────────<?>───────────────────┐
           │                              ┌──────────┴──────────┐
           │                     D_DIV    │        I = 16       │  ─> Initialisation indice I
           │                              └──────────┬──────────┘
           │                                         ├───────────────────┐
           │                              ┌──────────┴──────────┐        │  E=42/2   E=21/2   E=10/2   E=5/2    E=2/2
┌──────────┴──────────┐                   │        E = E / 2    │        │  R=0      R=1      R=0      R=1      R=0
│       MESSAGE       │          T_DIV    │     T(I) = R        │        │  T(16)=0  T(15)=1  T(14)=0  T(13)=1  T(12)=0
└──────────┬──────────┘                   │        I = I ─ 1    │        │  I=15     I=14     I=13     I=12     I=11
           │                              │        E :: 1       │        │  E=21     E=10     E=5      E=2      E=1
           │                              └──────────┬──────────┘ E > 1  │
           │                                        <?>──────────────────┘
           │                              ┌──────────┴──────────┐
           │                     F_DIV    │     T(I) = E        │                                                         T(11)=1
           │                              └──────────┬──────────┘
           └────────────────────┬────────────────────┘
                     ┌──────────┴──────────┐
              F_PROG │          Ø          │
                     └─────────────────────┘

Ci-dessous, entre les balises [CODE][PRE] et [/PRE][/CODE]

Ma police de caractère Courrier new est respectée et mes caractères semi-graphiques s'affichent correctement.

Ce n'est pas du tout le cas si je ne mets pas les balises [PRE][/PRE]. Bizarre, non ?

Le FORUM ALGO est le seul forum où un texte entre des balises [CODE] et [/CODE] ne reconnait pas les caractères semi-graphiques. J'ai déjà signalé ce problème. C'est pourtant le forum pour lequel ce serait nécessaire.

Quelques caractères semi-graphiques entre balises [CODE] et [/CODE], ça donne :

Code:

1
2
3
4
 
                    ┌──────────┴──────────┐
              F_PROG │          Ø          │
                     └─────────────────────┘

Sinon, entre les balises [CODE][PRE] et [/PRE][/CODE], ça se passe bien... pour les caractères semi-graphiques. Le choix est donc pas de N° de ligne et pas de caractères semi-graphiques ou N° de ligne et affichage des caractères semi-graphiques.

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
42
Simulation :

42 : 2 = 21 reste 0 (20 =  0)
21 : 2 = 10 reste 1 (21 =  2)
10 : 2 =  5 reste 0 (22 =  4)
 5 : 2 =  2 reste 1 (23 =  8)
 2 : 2 =  1 reste 0 (24 =  2)
            reste 1 (25 = 32)
                    ________
                          42

 E -> [E]ntier
 I -> [I]ndice courant 
 R -> [R]este

                     ┌─────────────────────┐
                     │       E  = ?        │    ─> [E]ntier = Saisie d’un entier
              D_PROG │       T  = occ * 16 │    ─> Déclaration [T]able de 16 occurrences initialisées à zéro
                     │       E :: 65535    │    ─> Test [E]ntier (maximum)
            > 65535  └──────────┬──────────┘ <= 65535
           ┌───────────────────<?>───────────────────┐
           │                              ┌──────────┴──────────┐
           │                     D_DIV    │        I = 16       │  ─> Initialisation indice I
           │                              └──────────┬──────────┘
           │                                         ├───────────────────┐
           │                              ┌──────────┴──────────┐        │  E=42/2   E=21/2   E=10/2   E=5/2    E=2/2
┌──────────┴──────────┐                   │        E = E / 2    │        │  R=0      R=1      R=0      R=1      R=0
│       MESSAGE       │          T_DIV    │     T(I) = R        │        │  T(16)=0  T(15)=1  T(14)=0  T(13)=1  T(12)=0
└──────────┬──────────┘                   │        I = I ─ 1    │        │  I=15     I=14     I=13     I=12     I=11
           │                              │        E :: 1       │        │  E=21     E=10     E=5      E=2      E=1
           │                              └──────────┬──────────┘ E > 1  │
           │                                        <?>──────────────────┘
           │                              ┌──────────┴──────────┐
           │                     F_DIV    │     T(I) = E        │                                                         T(11)=1
           │                              └──────────┬──────────┘
           └────────────────────┬────────────────────┘
                     ┌──────────┴──────────┐
              F_PROG │          Ø          │
                     └─────────────────────┘

Sinon, merci aussi pour la balise NOPARSE.

Il y a cette solution de contournement éventuellement (avec table) :

Simulation :

42 : 2 = 21 reste 0 (20 =  0)
21 : 2 = 10 reste 1 (21 =  2)
10 : 2 =  5 reste 0 (22 =  4)
 5 : 2 =  2 reste 1 (23 =  8)
 2 : 2 =  1 reste 0 (24 =  2)
            reste 1 (25 = 32)
                    ________
                          42

 E -> [E]ntier
 I -> [I]ndice courant 
 R -> [R]este

                     ┌─────────────────────┐
                     │       E  = ?        │    ─> [E]ntier = Saisie d’un entier
              D_PROG │       T  = occ * 16 │    ─> Déclaration [T]able de 16 occurrences initialisées à zéro
                     │       E :: 65535    │    ─> Test [E]ntier (maximum)
            > 65535  └──────────┬──────────┘ <= 65535
           ┌───────────────────<?>───────────────────┐
           │                              ┌──────────┴──────────┐
           │                     D_DIV    │        I = 16       │  ─> Initialisation indice I
           │                              └──────────┬──────────┘
           │                                         ├───────────────────┐
           │                              ┌──────────┴──────────┐        │  E=42/2   E=21/2   E=10/2   E=5/2    E=2/2
┌──────────┴──────────┐                   │        E = E / 2    │        │  R=0      R=1      R=0      R=1      R=0
│       MESSAGE       │          T_DIV    │     T(I) = R        │        │  T(16)=0  T(15)=1  T(14)=0  T(13)=1  T(12)=0
└──────────┬──────────┘                   │        I = I ─ 1    │        │  I=15     I=14     I=13     I=12     I=11
           │                              │        E :: 1       │        │  E=21     E=10     E=5      E=2      E=1
           │                              └──────────┬──────────┘ E > 1  │
           │                                        <?>──────────────────┘
           │                              ┌──────────┴──────────┐
           │                     F_DIV    │     T(I) = E        │                                                         T(11)=1
           │                              └──────────┬──────────┘
           └────────────────────┬────────────────────┘
                     ┌──────────┴──────────┐
              F_PROG │          Ø          │
                     └─────────────────────┘

08/12/2019, 19h48
Invité

Balise : [C=BASH]… [/C]

Bonjour,

À propos de balises, grâce à emixam16 dans une discussion, je viens d'en découvrir une nouvelle qui permet de surligner :

[C=BASH]EXEMPLE[/C]

EXEMPLE
08/12/2019, 23h09
joel.drigo

Citation:

Envoyé par IFA2377

Bonjour,

À propos de balises, grâce à emixam16 dans une discussion, je viens d'en découvrir une nouvelle qui permet de surligner :

[C=BASH]EXEMPLE[/C]

EXEMPLE

Il s'agit de la balise "code inline", le pendant de la balise "code" pour mettre du code inline. ( String s = "";, var s = '';... )
Pour surligner, utiliser la balise [highlight] : [highlight]Texte surligné[/highlight] donne Texte surligné