IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Python Discussion :

Trouver la plus grande puissance k de 2 tel que N ≥ 2k


Sujet :

Python

  1. #1
    Invité
    Invité(e)
    Par défaut Trouver la plus grande puissance k de 2 tel que N ≥ 2k
    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?
    Dernière modification par Invité ; 04/12/2019 à 22h33.

  2. #2
    Membre émérite

    Homme Profil pro
    Ingénieur calcul scientifique
    Inscrit en
    Mars 2013
    Messages
    1 229
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Alpes Maritimes (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Ingénieur calcul scientifique

    Informations forums :
    Inscription : Mars 2013
    Messages : 1 229
    Points : 2 328
    Points
    2 328
    Par défaut
    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 ...

  3. #3
    Invité
    Invité(e)
    Par défaut Oups
    Ah oui pardon c’est N>=2puissance k

  4. #4
    Expert éminent sénior
    Homme Profil pro
    Architecte technique retraité
    Inscrit en
    Juin 2008
    Messages
    21 240
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Manche (Basse Normandie)

    Informations professionnelles :
    Activité : Architecte technique retraité
    Secteur : Industrie

    Informations forums :
    Inscription : Juin 2008
    Messages : 21 240
    Points : 36 696
    Points
    36 696
    Par défaut
    Salut,

    Citation Envoyé par Booldegum Voir le message
    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
    Architectures post-modernes.
    Python sur DVP c'est aussi des FAQs, des cours et tutoriels

  5. #5
    Invité
    Invité(e)
    Par défaut
    Ok je vais regarder
    Mais pouvez-vous me dire comment construire l’algorithme correspondant à la question 1 svp?

  6. #6
    Expert éminent sénior
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Février 2006
    Messages
    12 631
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Février 2006
    Messages : 12 631
    Points : 30 865
    Points
    30 865
    Billets dans le blog
    1
    Par défaut
    Bonjour
    Citation Envoyé par Booldegum Voir le message
    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.
    Mon Tutoriel sur la programmation «Python»
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site
    Et on poste ses codes entre balises [code] et [/code]

  7. #7
    Expert éminent sénior
    Homme Profil pro
    Architecte technique retraité
    Inscrit en
    Juin 2008
    Messages
    21 240
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Manche (Basse Normandie)

    Informations professionnelles :
    Activité : Architecte technique retraité
    Secteur : Industrie

    Informations forums :
    Inscription : Juin 2008
    Messages : 21 240
    Points : 36 696
    Points
    36 696
    Par défaut
    Citation Envoyé par Booldegum Voir le message
    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 log2(2**k) <= log2(N) < log2 (2**(k+1)) et donc qu'on peut trouver k via partie entière de log2(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
    Architectures post-modernes.
    Python sur DVP c'est aussi des FAQs, des cours et tutoriels

  8. #8
    Expert éminent sénior
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Février 2006
    Messages
    12 631
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Février 2006
    Messages : 12 631
    Points : 30 865
    Points
    30 865
    Billets dans le blog
    1
    Par défaut
    Citation Envoyé par wiztricks Voir le message
    Les mathématiques nous disent aussi que log2(2**k) <= log2(N) < log2 (2**(k+1)) et donc qu'on peut trouver k via partie entière de log2(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...
    Mon Tutoriel sur la programmation «Python»
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site
    Et on poste ses codes entre balises [code] et [/code]

  9. #9
    Invité
    Invité(e)
    Par défaut
    Je m'étais trompé lors de mon premier message, N de doit pas être inférieur à 2k, il doit être supérieur à 2k.
    J'ai corrigé le post. Merci beaucoup pour votre aide!

  10. #10
    Expert éminent sénior
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Février 2006
    Messages
    12 631
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Février 2006
    Messages : 12 631
    Points : 30 865
    Points
    30 865
    Billets dans le blog
    1
    Par défaut
    Hé bien tu reprends mon algorithme et tu remplaces "donner k" par "donner k-1".
    Mon Tutoriel sur la programmation «Python»
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site
    Et on poste ses codes entre balises [code] et [/code]

  11. #11
    Invité
    Invité(e)
    Par défaut OK
    D'accord je vais essayer et je vous enverrais mon algorithme pour que vous me dites ce que vous en pensez

  12. #12
    Invité
    Invité(e)
    Par défaut
    J'ai réussi à faire un algorithme mais le problème c'est qu'il me donne la puissance juste supérieure à N . J'aimerais qu'il me donne la puissance la plus proche de N mais qu'elle soit inférieure ou égale à N. Je n'arrive pas à comprendre comment faire...

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
     
    def puissance():
      k=0
      N=213
      while 2**k<=N:
        k=k+1
     
      print("La puissance de 2 la plus proche de N est 2 puissance", k)
     
    print(puissance())

  13. #13
    Membre émérite

    Homme Profil pro
    Ingénieur calcul scientifique
    Inscrit en
    Mars 2013
    Messages
    1 229
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Alpes Maritimes (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Ingénieur calcul scientifique

    Informations forums :
    Inscription : Mars 2013
    Messages : 1 229
    Points : 2 328
    Points
    2 328
    Par défaut
    Primo, votre fonction devrait être plutot comme ça, sinon inutile de faire une fonction ...
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
     
    def puissance(N):
      k=0
      while 2**k<=N:
        k=k+1
     
      return k
     
    resultat = puissance(213)
    print("La puissance de 2 la plus proche de N est 2 puissance", resultat)
    Secondo, prenez un nombre simple, genre 5, et dérouler votre algorithme à la main. Prenez une feuille de papier et écrivez ce que votre machine fait, à chaque itération.
    Voyez que la valeur qui va être retourner c'est la puissance de 2 qui est juste après votre nombre. Car il faut bien dépasser le nombre N, pour savoir qu'avant on a eu la puissance qu'il nous fallait (sinon comment savoir que c'est la plus grande?). Donc le résultat qui vous intéresse n'est pas le k actuel, mais le k de l'itération précédente.

  14. #14
    Invité
    Invité(e)
    Par défaut
    Rebonjour, j'ai réussi à répondre à la question 1) en prenant comme exemple le code proposé par lg_53 (merci )
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
     
    def puissance(N):
      k=0
      while 2**k<=N:
        k=k+1
     
      return k-1
     
     
     
     
    print("La puissance de 2 la plus proche de N est 2 puissance", puissance(213))
    Pour la question 2), je pense qu'il faut soustraire 2**7 à 213 puis trouver la valeur la plus proche du résultat (je ne sais pas si j'explique bien, le mieux c'est montrer mon calcul) et continuer de cette façon jusqu'à ce que la somme entre parenthèse soit le plus proche de 213:
    213-128= 85 (valeur proche 2**6)
    213-(128+64)=21(valeur proche 2**7)
    213-(128+64+16)=5(valeur proche 2**2)
    213-(128+64+16+4)=1(valeur proche 2**0)
    Je n'ai pas les connaissances pour le coder et l'associer à ma première fonction mais je pense que mon raisonnement est bon...

  15. #15
    Membre émérite

    Homme Profil pro
    Ingénieur calcul scientifique
    Inscrit en
    Mars 2013
    Messages
    1 229
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Alpes Maritimes (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Ingénieur calcul scientifique

    Informations forums :
    Inscription : Mars 2013
    Messages : 1 229
    Points : 2 328
    Points
    2 328
    Par défaut
    Bon, on avance !
    Il y a des manières plus optimales de codé cette première fonction, comme il vous l'a été déjà suggérer précédemment dans ce post, mais vous avez déjà qqch qui fonctionne et c'est déjà une bonne chose.

    Pour la 2ieme question alors oui vous pouvez procédez comme vous dites (même si là aussi, ce n'est pas optimal).

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    def somme_puissance_de_2(N):
        puissance_max = puissance(N) ## vous reutilisez votre fonction
        liste_des_puissance = []
        ### puis là votre algo où vous allez successivement soustraire ce qu'il faut, en partant de 2^puissance_max, jusqu'à 2^0, et faire des append à la liste quand la puissance est dans la somme.
     
         return liste_des_puissance
     
    print( somme_puissance_de_2(N) )
    Faudra ensuite juste faire un petit traitement pour afficher le résultat avec une jolie phrase, plutot que la liste brute, mais chaque chose en son temps

  16. #16
    Invité
    Invité(e)
    Par défaut
    D'accord donc si je comprends bien, je dois faire un tableau et y entrer toutes les valeurs?

  17. #17
    Expert éminent sénior
    Homme Profil pro
    Architecte technique retraité
    Inscrit en
    Juin 2008
    Messages
    21 240
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Manche (Basse Normandie)

    Informations professionnelles :
    Activité : Architecte technique retraité
    Secteur : Industrie

    Informations forums :
    Inscription : Juin 2008
    Messages : 21 240
    Points : 36 696
    Points
    36 696
    Par défaut
    Salut,

    Citation Envoyé par Booldegum Voir le message
    Je n'ai pas les connaissances pour le coder et l'associer à ma première fonction mais je pense que mon raisonnement est bon...
    Votre raisonnement est bon et si vous relisez transformer votre idée:
    213-128= 85 (valeur proche 2**6)
    213-(128+64)=21(valeur proche 2**7)
    213-(128+64+16)=5(valeur proche 2**2)
    213-(128+64+16+4)=1(valeur proche 2**0)
    en code, c'est juste faire une boucle avec des variables qui vont évoluer à chaque itération.
    Donc vous avez les connaissances pour proposer un premier code.

    - W
    Architectures post-modernes.
    Python sur DVP c'est aussi des FAQs, des cours et tutoriels

  18. #18
    Invité
    Invité(e)
    Par défaut
    Très bien merci ! Je vais essayer et je vous tiendrait au courant

  19. #19
    Membre émérite

    Homme Profil pro
    Ingénieur calcul scientifique
    Inscrit en
    Mars 2013
    Messages
    1 229
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Alpes Maritimes (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Ingénieur calcul scientifique

    Informations forums :
    Inscription : Mars 2013
    Messages : 1 229
    Points : 2 328
    Points
    2 328
    Par défaut
    213-128= 85 (128= 2**7, j'ajoutes donc 7 à la liste)
    85 - 64 = 21 (64= 2**6, j'ajoutes donc 6 à la liste)
    2**5 = 32, qui est plus grand que 21. donc je ne fais rien
    2**4 = 16, je fais donc 21-16 = 5, et j'ajoutes 4 à la liste des puissances
    2**3= 8, c'est plus grand que 5, je ne fais rien
    2**2=4, plus petit que 5, donc je fais 5-4 = 1, et j'ajoutes 2 à ma liste des puissances
    2**1=2, plus grand que 1 qui me reste, donc je ne fais rien
    enfin, 2**0=1 ce qui me reste. J'ajoutes donc 0 à ma liste des puissance et l'algo est fini

    Il va renvoyer donc la liste des puissances :
    [7,6,4,2,0]

    Comprendre donc 213 = 2^7 + 2^6 + 2^4 + 2^2 + 2^0

  20. #20
    Invité
    Invité(e)
    Par défaut
    Bonjour
    Comment faire pour que mon algorithme envoie une donnée dans le tableau (en me basant sur le code de lg_53)?

+ Répondre à la discussion
Cette discussion est résolue.
Page 1 sur 2 12 DernièreDernière

Discussions similaires

  1. Réponses: 2
    Dernier message: 13/12/2010, 19h18
  2. Besoin d'aide pour optimiser un algorithme
    Par predat dans le forum Général Python
    Réponses: 5
    Dernier message: 21/08/2010, 02h29
  3. Besoin d'aide pour un petit Algorithme
    Par arnolem dans le forum Requêtes
    Réponses: 1
    Dernier message: 04/08/2010, 00h51
  4. [AIDE] besoin d'aide pour réaliser un algorithme
    Par quaresma dans le forum Algorithmes et structures de données
    Réponses: 40
    Dernier message: 18/01/2008, 10h35
  5. Besoin d'aide pour algorithme de traitement d'images
    Par Zenman94 dans le forum Algorithmes et structures de données
    Réponses: 13
    Dernier message: 07/04/2005, 15h31

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo