Apprendre Maple Index du Forum Apprendre Maple
Site dédié au logiciel de calcul formel Maple
 
  Page d'accueilPage d'accueil   FAQFAQ    RechercherRechercher    Liste des MembresListe des Membres    Groupes d'utilisateursGroupes d'utilisateurs 
S'enregistrerS'enregistrer    ProfilProfil   Se connecter pour vérifier ses messages privésSe connecter pour vérifier ses messages privés   ConnexionConnexion 

Décomposition d'un nombre en somme de puissance de 2
Aller à la page 1, 2  Suivante
 
Poster un nouveau sujet   Répondre au sujet    Apprendre Maple Index du Forum -> Programmation
Voir le sujet précédent :: Voir le sujet suivant  
Auteur Message
Guimzo



Inscrit le: 02 Juin 2012
Messages: 209

MessagePosté le: 26 Oct 2014 10:47    Sujet du message: Décomposition d'un nombre en somme de puissance de 2 Répondre en citant

Bonjour,

Je cherche à fabriquer une séquence qui pour un nombre n donné donnerait sous forme détaillée, la liste ordonnée de la somme des puissances de 2 qui compose ce nombre n :

Exemple :

n = 17
res : = [2^4+2^0]

Autre exemple :

n=13
res:= [2^3+2^2+2^0]

Donc le résultat est ordonné.

Voici ce que j'ai déjà fait, mais je pense que c'est vraiment pas bon : (


n:=n:
Res:=a:
do res: =[ round(log2(n)) - n] while a>0 ; end do: print("res:=a");
Revenir en haut de page
Voir le profil de l'utilisateur Envoyer un message privé
Guimzo



Inscrit le: 02 Juin 2012
Messages: 209

MessagePosté le: 28 Oct 2014 15:42    Sujet du message: Répondre en citant

Bonjour,

Zozo si tu es dans les parages, pourrais-tu m'aider s'il te plaît, je crois que ALS est en vacances jusqu'au 4 novembre...

Voici ce que j'ai refait :

=====================

restart;
Decomposition := proc (n)
local a, b, c :
a := evalf(log[2](n)):
b := floor(a):
c := n-2^b:
if c = 0 then print(Decomposition = 2 puissance(b)):
end if:
end proc:
Decomposition(128);

=====================

La séquence est un début ; je pense qu'il manque l'instruction "ELSE" quand c>0, mais je ne vois pas comment l'introduire et comment rappeler l'ensemble des puissances en résultat...?
Donc du coup ça ne fonctionne que quand n est lui même de la forme 2^n, ce qui revient à calculer tout simplement 2^n...
Revenir en haut de page
Voir le profil de l'utilisateur Envoyer un message privé
Guimzo



Inscrit le: 02 Juin 2012
Messages: 209

MessagePosté le: 29 Oct 2014 12:45    Sujet du message: Répondre en citant

Bonjour,

Voici une formulation possible pour une séquence de décomposition en somme de puissance de 2 d'un nombre ; formulation avec l'aide d'un internaute @Tryss :

====================

restart;
Dec := proc (n)
local a, b, c;
c := n;
while 0 < c do a := log[2](c);
b := floor(a); printf("2^%d ", b);
c := c-2^b end do end proc;
Dec(291)

=====================

Alors Maple renvoie éffectivement les différentes puissances de 2 qui composent un nombre n donné, mais il reste finalement à inclure ces résultats dans une liste ordonnée c'est à dire avec l'outil "Convert(a,set)...
Revenir en haut de page
Voir le profil de l'utilisateur Envoyer un message privé
zozo



Inscrit le: 03 Jan 2013
Messages: 125

MessagePosté le: 01 Nov 2014 17:02    Sujet du message: Répondre en citant

Algorithme pour décomposer a en base b :

Code:

> DECOMPOSITION:=proc(a::nonnegint, b::posint)
> local d,q;
>    d := NULL;
>    q := a;
>    while q > 0 do
>       d :=  (q mod b), d;
>       q := floor(q / b);
>   od:
>    return [d]
> end proc:

> DECOMPOSITION(255,2);

                       [1, 1, 1, 1, 1, 1, 1, 1]

> DECOMPOSITION(1002,2);

                    [1, 1, 1, 1, 1, 0, 1, 0, 1, 0]


Revenir en haut de page
Voir le profil de l'utilisateur Envoyer un message privé
Guimzo



Inscrit le: 02 Juin 2012
Messages: 209

MessagePosté le: 02 Nov 2014 15:29    Sujet du message: Répondre en citant

zozo a écrit:
Algorithme pour décomposer a en base b :

Code:

> DECOMPOSITION:=proc(a::nonnegint, b::posint)
> local d,q;
>    d := NULL;
>    q := a;
>    while q > 0 do
>       d :=  (q mod b), d;
>       q := floor(q / b);
>   od:
>    return [d]
> end proc:

> DECOMPOSITION(255,2);

                       [1, 1, 1, 1, 1, 1, 1, 1]

> DECOMPOSITION(1002,2);

                    [1, 1, 1, 1, 1, 0, 1, 0, 1, 0]





Bonjour Zozo,

Merci pour ton aide ; mais comment avoir ce nombre directement sous forme de somme de puissance de 2 : tel que

255 = [2^7, 2^6 ,2^5 ,2^4, 2^3, 2^2 ,2^1, 2^0]

1002 = [2^9, 2^8, 2^7, 2^6, 2^5, 2^3, 2^1]
Revenir en haut de page
Voir le profil de l'utilisateur Envoyer un message privé
zozo



Inscrit le: 03 Jan 2013
Messages: 125

MessagePosté le: 02 Nov 2014 16:01    Sujet du message: Répondre en citant

Code:

DECOMPOSITION:=proc(a::nonnegint, b::posint)
>  local d,q,k;
>     d := NULL;
>     q := a;
>     k :=-1;
>     while q > 0 do
>        k:=k+1:
>        if (q mod b)>0 then d :=  (q mod b)*cat(b,`^`,k), d fi;
>        q := floor(q / b);
>    od:
>     return [d]
>  end proc:



> DECOMPOSITION(255,2);
> DECOMPOSITION(1002,2);

               [2^7, 2^6, 2^5, 2^4, 2^3, 2^2, 2^1, 2^0]


                 [2^9, 2^8, 2^7, 2^6, 2^5, 2^3, 2^1]

> DECOMPOSITION(2014,5);

                      [3 5^4, 5^3, 2 5^1, 4 5^0]

Revenir en haut de page
Voir le profil de l'utilisateur Envoyer un message privé
Guimzo



Inscrit le: 02 Juin 2012
Messages: 209

MessagePosté le: 02 Nov 2014 17:59    Sujet du message: Répondre en citant

Bonjour Zozo,

Excellent ton programme, merci beaucoup
Ce programme je devais l'inclure en fait dans une séquence de factorisation, que j'ai fait, mais si tu peux regarder s'il te plaît où ça cloche, plus précisément au niveau du "CHOOSE" qui a du mal quand on lui demande de combiner beaucoup d'éléments d'un ensemble pourtant =(n-1) éléments.

C'est à dire quand je fais un
"
a:[seq(2**n,n=0..164)]:
with(combinat):
b := choose(a, 164);"

ça prend du temps alors que c'est simplement une combinaison de 164 éléments pris dans 165 éléments : et donc qu'il n'y à que C(164,165)= 165 possibilités.

Comment améliorer le programme, pour éviter que Maple rame, parce qu'il ne semble pas reconnaître que C(164,165) = 165.....??

Voilà la sequence entière :


=====================================

restart;
Digits := 1000;
p := 2537;
length(p);
a := [seq(2^n, n = 0 .. 5)];
with(combinat);
b := choose(a, 4);
N := nops(b);
with(ListTools);
c := {seq(convert(b[i], `+`), i = 1 .. N)};
s := seq(p/r, r = c);
select(proc (x) options operator, arrow; type(x, posint) end proc, [s]);

=======================================

Donc là, il n'y aucun probléme avec un "choose(a,4)" mais des que je demande à Maple un choose(a,164), en ayant pris le soin de faire monter "n" à 165 ; là Maple rame, alors qu'il n'y à pourtant moins de 200 possibilités...??
Revenir en haut de page
Voir le profil de l'utilisateur Envoyer un message privé
ALS



Inscrit le: 11 Sep 2006
Messages: 647

MessagePosté le: 03 Nov 2014 7:37    Sujet du message: Répondre en citant

Bonjour,
très rapidement, voici ce que l'on peut écrire:

Code:

> a:=[seq(2**n,n=0..164)]:
 
> b:=[seq(subsop(165-k=NULL,a),k=0..164)];
Revenir en haut de page
Voir le profil de l'utilisateur Envoyer un message privé
Guimzo



Inscrit le: 02 Juin 2012
Messages: 209

MessagePosté le: 03 Nov 2014 12:04    Sujet du message: Répondre en citant

Bonjour ALS,

J'espère que vous avez passé de bonnes vacances, il me tardait de vous revoir sur le forum : ) Mais comme vous m'aviez dit le 4 novembre j'attendais encore : )
Je pense que vous seriez plutôt fier de "votre élève", j'ai fait la séquence tout seul, avec tout ce que vous m'avez déjà appris : )
Merci pour la séquence je vais l'essayer de suite : )
À bientôt : )
Revenir en haut de page
Voir le profil de l'utilisateur Envoyer un message privé
Guimzo



Inscrit le: 02 Juin 2012
Messages: 209

MessagePosté le: 03 Nov 2014 12:55    Sujet du message: Répondre en citant

Re-bonjour ALS,


La ligne " b:=[seq(subsop(165-k=NULL,a),k=0..164)]; " est excellente par rapport à choose : )
Merci merci merci : )


Mais quand je veux utiliser un nombre plus petit par rapport aux combinaisons, je ne sais pas comment il faudrait faire ; je m'explique :
Par exemple, je prends le nombre 85073, je sais qu'il a que deux facteurs premiers dont 241 et 353 ; d'autre part je sais que 353 = [`2^8`+ `2^6`+`2^5`+ `2^0`]

Donc en tout, 353 = la somme de 4 puissance de 2 allant 2^0 à 2^8
Donc il me faudrait choisir 4 éléments dans 9 éléments,

Alors comment régler la séquence dans ce cas, et dans les autres cas par rapport au nombre d'éléments que je veux combiner, et du nombre d'éléments de l'ensemble où je les prends :


Voici la séquence :


==========================
restart;
Digits := 1000;
p := (85073);
length(p);
a := [seq(2^n, n = 0 .. 8 )] :
b := [seq(subsop(9-k = NULL, a), k = 0 .. 4)] :
N := nops(b):
with(ListTools):
c := {seq(convert(b[i], `+`), i = 1 .. N)};
C := nops(c);
s := seq(p/r, r = c);
select(proc (x) options operator, arrow; type(x, posint) end proc, [s]);

===================================

En fait, dans ce cas ci, vu que 353 = la somme de la combinaison de 4 puissances de 2, avec la plus haute puissance qui égal à 8; il faudrait donc, que la ligne "b" fasse comme un "choose(a,4)"....?


L'autre séquence qui marche avec choose, mais qui rame des que l'on met un grand nombre p, avec un n en conséquence :

================================

restart;
Digits := 1000;
p := 85073;
length(p);
a := [seq(2^n, n = 0 .. 8 )]:
with(combinat):
b := choose(a, 4):
N := nops(b):
with(ListTools):
c := {seq(convert(b[i], `+`), i = 1 .. N)};
C := nops(c);
s := seq(p/r, r = c):
select(proc (x) options operator, arrow; type(x, posint) end proc, [s]);

================================
Revenir en haut de page
Voir le profil de l'utilisateur Envoyer un message privé
ALS



Inscrit le: 11 Sep 2006
Messages: 647

MessagePosté le: 03 Nov 2014 14:18    Sujet du message: Répondre en citant

Ma ligne b:=[seq(subsop(N+1-k=NULL,a),k=0..N)] ne marche que pour une combinaison de N éléments parmi N+1 éléments.
Pour choisir p éléments parmi N, il faut utiliser choose quand 1<p<N.

D'autre part, convert(b[i], `+`) fait la somme de tous les éléments de b[i], c'est bien ce que vous cherchiez à faire?
Revenir en haut de page
Voir le profil de l'utilisateur Envoyer un message privé
Guimzo



Inscrit le: 02 Juin 2012
Messages: 209

MessagePosté le: 03 Nov 2014 14:28    Sujet du message: Répondre en citant

Re ALS,


Mais comment expliquer que Maple ait du mal à calculer cette séquence, alors qu'il n'y à qu'à peine une centaine de possibilités....??

================

restart; a := [seq(2^n, n = 0 .. 160)]:
with(combinat):
b := choose(a, 160);

================
Revenir en haut de page
Voir le profil de l'utilisateur Envoyer un message privé
ALS



Inscrit le: 11 Sep 2006
Messages: 647

MessagePosté le: 03 Nov 2014 14:40    Sujet du message: Répondre en citant

Effectivement, je ne me l'explique pas non plus !
Revenir en haut de page
Voir le profil de l'utilisateur Envoyer un message privé
Guimzo



Inscrit le: 02 Juin 2012
Messages: 209

MessagePosté le: 03 Nov 2014 17:12    Sujet du message: Répondre en citant

Existerait-il un moyen de contourner ce "bug" de Maple, de former des groupes de p éléments pris dans n éléments, quand le nombres n et p sont au dessus de 50....?

Sinon je vais essayer de voir dans Mathematica ce que ça donne un

"a:=[seq(n,n=1..50)] :with(combinat): b:=choose(a,48 ) ; "
Merci ALS, j'espère vous revoir bientôt s'il vous plaît, pour l'autre séquence avec les multiplications...
Revenir en haut de page
Voir le profil de l'utilisateur Envoyer un message privé
Guimzo



Inscrit le: 02 Juin 2012
Messages: 209

MessagePosté le: 14 Nov 2014 1:04    Sujet du message: Répondre en citant

Re-bonsoir ALS,


Pourriez-vous m'aider s'il vous plaît à corriger la séquence suivante :

=========================

restart;
Digits := 155;
p := 85073;
a := [seq(2^n, n = 0 .. 10)];
with(combinat);
b := choose(a, 2);
N := nops(b);
with(ListTools);
c := {seq(convert(b[i], `-`), i = 1 .. N)};
M := nops(c);
for x in c do r := (sqrt(g*g+4*p)+g)*(1/2) :
if type(r, integer) then break end if end do; print("FACTEUR r =", r);

======================================

C'est la ligne 9 que je voudrais corriger :
" c := {seq(convert(b[i], `-`), i = 1 .. N)}; "

En fait je voudrais fabriquer un ensemble "c" qui soit composé des différentes soustractions des 2 nombres qui composent les binômes (b:=choose(a,2))......?
Revenir en haut de page
Voir le profil de l'utilisateur Envoyer un message privé
Montrer les messages depuis:   
Poster un nouveau sujet   Répondre au sujet    Apprendre Maple Index du Forum -> Programmation Toutes les heures sont au format GMT + 2 Heures
Aller à la page 1, 2  Suivante
Page 1 sur 2

 
Sauter vers:  
Vous ne pouvez pas poster de nouveaux sujets dans ce forum
Vous ne pouvez pas répondre aux sujets dans ce forum
Vous ne pouvez pas éditer vos messages dans ce forum
Vous ne pouvez pas supprimer vos messages dans ce forum
Vous ne pouvez pas voter dans les sondages de ce forum


phpBB

Développé par phpBB © 2001, 2006 phpBB Group
Traduction par : phpBB-fr.com


Apprendre Maple - ©  - Alain Le Stang - Navigation optimisée pour une résolution 1024 x 768.