Salut, j'ai un petit exercice à réaliser, mais mes lacunes en maths me coutent chers :
Soit x un entier, on a x = Somme( i=0; k) bi*2^i , où bi E {-1;0;1}
Mon problème consiste à trouver, pour x fixé, une suite la plus courte possible, constituée d'additions et de soustractions.
Je m'oriente vers une recherche arborescente en largeur, ou chaque niveau correspondera a un terme en plus dans la somme.
Existe t-il une meilleur solution, ou sinon, existe t-il des règles qui permettent de limiter la taille de l'arbre et donc le temps de calcul ?
Le but, est simplement de trouver un temps de calcul raisonnable ( de qq dizièmes de secondes à qq secondes) pour des nombres d'environ 32 ou 64 bits (ce que m'offrent la plupart des langages en fait).
Forum Programmation.autre Algo de recherche arborescente en largeur
6
oct.
2004
# Demandes de précisions
Posté par Sisyphe Plâtrier . Évalué à 3.
D'autre part, si c'est un exercice de cours ou de TD, quémander la solution n'est pas forcément une bonne idée. Alors, fake ?
Sinon si "plus court" signifie que le dernier chiffre non-nul a le rang le plus faible : reste en binaire, le -1 ne sert à rien.
Si par contre "plus court" signifie le moins grand nombre de chiffres non-nuls, ce qui présente plus d'intérêt, pas encore d'idée. Sorry.
[^] # Re: Demandes de précisions
Posté par Ontologia (site web personnel) . Évalué à 1.
Non, c'est juste une question/un délire avec un copain.
Je fé un bts d'info alors je m'ennuie, voilà...
On s'occupe comme on peut hein !
plus court signifie la somme la plus courte :
60 = 4+8+16+32 = 64-4 (= 64 +(-4))
La deuxième somme est plus courte que la première.
« Il n’y a pas de choix démocratiques contre les Traités européens » - Jean-Claude Junker
# marrant, ton truc
Posté par mac_is_mac (site web personnel) . Évalué à 2.
ou le calcul de la meilleure solution pour x appelerait
le calcul de la meilleure solution pour 2^(n+1)-x et
le calcul de la meilleure solution pour x-2^n, où
2^n est la plus grande puissance de 2 inférieure ou égale à x.
(Je ne considère ici que des x positifs).
Mais c'est juste une intuit....
Tu nous tiens au courant ? Ca pourrait plaire à mes étudiants...
[^] # Re: marrant, ton truc
Posté par mac_is_mac (site web personnel) . Évalué à 4.
Ca a l'air de marcher.
function [e,t]=ecriture(x)
if (x>0) then
p=1;
while (p<x), p=2*p, end
if (x==p) then
e=[p];
t=1;
else
[f,u]=ecriture(p-x);
[g,v]=ecriture(x-p/2);
if (u<v) then e=[p -f], t=u+1
else e=[p/2 g], t=v+1, end
end
else
e=[];
t=0;
end
endfunction
Par exemple, pour 121:
[e,s]=ecriture(121)
s= 3
e=[ 128 -8 1]
[^] # Re: marrant, ton truc
Posté par Ontologia (site web personnel) . Évalué à 1.
Ce serait possible de clarifier un peu ?
merci :)
« Il n’y a pas de choix démocratiques contre les Traités européens » - Jean-Claude Junker
[^] # Re: marrant, ton truc
Posté par mac_is_mac (site web personnel) . Évalué à 2.
if condition then instruction1; instruction2; end
quand il n'y a pas de "sinon" et
if condition then instruction1; instruction2;
else instruction3; instruction4; end
quand il y en a un.
(En fait le else ferme le bloc d'instruction précédent).
Sinon, scilab est orienté liste, donc si tu fais
a=[2];
a=[ 1 a];
a=[a -a 3];
tu récupères a=[1 2 -1 -2 3]
# probleme semblable
Posté par djnet . Évalué à 1.
Mais le probleme (qui n'a pas de rapport avec linux, non ?) s'apparente à la conversion décimal -> binaire
A mon avis, il faut:
1: déterminer le signe de x, si positif, on utilisera bi = 0|1 sinon bi=0|-1;
2: y=abs(x)
2: ensuite, tu regarde si y est pair (bi=0) ou impair (bi=1/-1, cf 1: ), ca te donne bi, pour i=0
3: y=y/2; tu incrémente i et tu retourne au 2: (tant que y>0)
[^] # Re: probleme semblable
Posté par Ontologia (site web personnel) . Évalué à 1.
J'ai oublié de préciser x positif, et je cherche bien à déterminer x positif avec bi=-1|0|1
Exemple : 63 = 1+2+4+8+16+32 = 64-1 ...
« Il n’y a pas de choix démocratiques contre les Traités européens » - Jean-Claude Junker
[^] # Re: probleme semblable
Posté par djnet . Évalué à 2.
Dans ce cas, bi = 1|-1 , non ?
parce que si tu prends en compte bi=0, ton exemple n'est pas complet:
63 = 1+2+4+8+16+32 = 1*64 + 0*32 + 0*16 + 0*8 + 0*4 + 0*2 + (-1)*1
La solution que je te propose n'apporte pas la solution optimale.
Peut-etre peux-tu essayer d'optimiser celle-ci. Les suites 111 (3 '1' consecutifs) peuvent etre optimisées en 1000-1 :
exemple:
1000111010 = 1001000010 - 1000
du coup, a droite, tu a moins de '1'
cela est valable pour les suites de 3 '1' ou plus
cette transformation marche bien sur un cas, mais il faut sans doute
faire un peu de recursivite (ca complique la chose, evidemment)
Cela s'applique a quoi, ce type de pb ?
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.