Discussion :

[Invité]

Bonjour,j'ai fait un devoir de mathématiques où l'on me demandait de créer un algorithme.
Voici l'énoncé :
1.On se donne un entier naturel N. Écrire un algorithme qui donne la plus grande puissance k de 2 tel que
N ≥ 2k . Tester votre algorithme sur N = 213.
2.Utiliser votre algorithme pour écrire N = 213 comme une somme de puissance de 2.

Voici mon code:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def puissance():
  N=float(input("Donnez un entier naturel: "))
  n=2
  k=100
  p=N/2
  m=2
  j=100
 
  if N<n**k :
    while n**k>=N:
      k=k-1
 
    while m**j>=p:
      j=j-1
 
    print("La puissance de 2 la plus proche de N est", n,"puissance", k,"qui est égale à: ", n**k)
    print("La somme de puissance de 2 la plus proche de N est: ", m,"puissance ", j,"plus", m,"puissance ", j," qui est égale à: ", m**j+m**j)
 
print(puissance())

J'ai eu un zéro à cet exercice. On m'a dit que ce n'était pas un algorithme.
Pouvez-vous m'expliquer ce qu'est un algorithme, comment en créer un et, si possible, me donner un exemple d'algorithme correspondant à l'exercice svp?

Mon code ne répond-t-il pas à la question?

[lg_53]

Non ca ne répond pas aux questions.

Essayez de proposer qqch pour résoudre correctement la question 1) déjà.
Car là en l'état si je rentre l'entier qui vaut 2^101 par exemple, votre fonction ne fera rien du tout ...

Ensuite vous avez du mal recopier l'énoncé, car
"la plus grande puissance k, tel N ≤ 2^k"
1) manque la puissance là à mon avis, comme je l'ai indiqué ici
2) ca doit etre la plus petite (ou alors il faut tourner l'inégalité dans l'autre sens) car sinon la réponse c'est juste k = + infini, indépendamment de la valeur N entrée ...

[Invité]

Ah oui pardon c’est N>=2puissance k

[wiztricks]

Salut,

Mon code ne répond-t-il pas à la question?

Lisez tout l'énoncé: Comment s'écrit 213 sous la forme d'une somme de puissances de 2?
128 + 64 + 16 + 4 + 1...
Et comme les ordinateurs représentent les nombres tels que 213 sous forme binaire (la somme de puissances de deux) vous pouvez le vérifier via:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
>>> bin(213)
'0b11010101'

Et comme on veut fabriquer un algorithme qui aide à traiter la question 2, votre fonction puissance doit avoir n en paramètre et retourner le k qui va bien histoire d'itérer sur les restes successifs.
note: chercher un peu sur Internet comment on passe de base 10 en base 2.

- W

[Invité]

Ok je vais regarder
Mais pouvez-vous me dire comment construire l’algorithme correspondant à la question 1 svp?

[Sve@r]

Bonjour

Mais pouvez-vous me dire comment construire l’algorithme correspondant à la question 1 svp?
1.On se donne un entier naturel N. Écrire un algorithme qui donne la plus grande puissance k de 2 tel que N ≤ 2k

Je ne connais pas exactement la syntaxe exacte dédié aux algorithmes mais généralement elle ressemble à ceci

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
mettre 0 dans k
tant que 2 puissance k <= N faire
    mettre k+1 dans k
fin faire
donner k

Ensuite, transcrire l'algorithme en C, C++, basic, assembleur, cobol, brainfuck, Python c'est autre chose. D'ailleurs ta question n'a rien à voir avec Python et aurait plutôt sa place dans la section "algo" du forum.

[wiztricks]

Ok je vais regarder
Mais pouvez-vous me dire comment construire l’algorithme correspondant à la question 1 svp?

Pour chercher k tel que 2**(k) <= N < 2**k+1, je commence avec N = 20 (par exemple) et je regarde:

• est ce que 2**0 > 10, non, je continue
• est ce que 2**1 > 10, non, je continue
• est ce que 2**2 > 10, toujours pas, je continue
• est ce que 2**3 > 10, toujours pas, je continue
• est ce que 2**4 > 10, Yes.

Donc 2**3 < 10 <= 2**4 et k = 3.

Après je réfléchis à ce que j'ai fait: à chaque itération on multiplie la puissance de 2 initiale par 2. Ce qui revient à partir de p = 1 et ré-écrire:

• est ce que p > 10, non, je continue avec p = 2*p
• est ce que p > 10, non, je continue avec p = 2*p
• est ce que p > 10, toujours pas, je continue avec p = 2*p
• est ce que p > 10, toujours pas, je continue avec p = 2*p
• est ce que p > 10, Yes.

Et le k là dedans est juste le compteur du nombre d'itérations.

Et maintenant qu'on a un algorithme(*) qui semble fonctionner sur le papier, vous pouvez essayer de le coder (le ré-écrire en Python).

(*) On part des mathématiques qui disent que la suite 2**k est monotone croissante, ce qui veut dire que quelque soit N il existe un k tel que 2**k <= N < 2**(k+1). L'algorithme, c'est juste traduire ces théorèmes pour trouver ce "k" par une méthode itérative.

Les mathématiques nous disent aussi que log₂(2**k) <= log₂(N) < log₂ (2**(k+1)) et donc qu'on peut trouver k via partie entière de log₂(N).
Mais ce n'est pas un algorithme car si on relit la définition de Wikipédia:

un algorithme est un calcul (« arithmos » en grec), qui est tellement long et difficile à faire à la main qu'il en devient douloureux : « algos » signifie douleur en grec : un algorithme est un calcul pénible à faire à la main.

- W

[Sve@r]

Les mathématiques nous disent aussi que log₂(2**k) <= log₂(N) < log₂ (2**(k+1)) et donc qu'on peut trouver k via partie entière de log₂(N).
Mais ce n'est pas un algorithme car si on relit la définition de Wikipédia:

un algorithme est un calcul (« arithmos » en grec), qui est tellement long et difficile à faire à la main qu'il en devient douloureux : « algos » signifie douleur en grec : un algorithme est un calcul pénible à faire à la main.

Me semble que calculer un log à la main sera probablement particulièrement pénible...

[Invité]

Je m'étais trompé lors de mon premier message, N de doit pas être inférieur à 2^k, il doit être supérieur à 2^k.
J'ai corrigé le post. Merci beaucoup pour votre aide!