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
Posté par Ontologia (site web personnel) .
Étiquettes :
aucune
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.