URL: https://linuxfr.org/forums/programmationautre/posts/algo-de-recherche-arborescente-en-largeur
Title: Algo de recherche arborescente en largeur
Authors: Ontologia
Date: 2004年10月06日T11:34:57+02:00
Tags: 
Score: 0
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).
</div><div class="naked_ctrl">
<form action="/index.cgi/contrast" method="get" name="gate">
<p><a href="http://altstyle.alfasado.net">AltStyle</a> によって変換されたページ <a href="httpS://linuxfr.org/forums/programmationautre/posts/algo-de-recherche-arborescente-en-largeur.md">(-&gt;オリジナル)</a>
/ <label>アドレス: <input type="text" name="naked_post_url" value="httpS://linuxfr.org/forums/programmationautre/posts/algo-de-recherche-arborescente-en-largeur.md" size="22" /></label> <label>モード: <select name="naked_post_mode">
<option value="default">デフォルト</option>
<option value="speech">音声ブラウザ</option>
<option value="ruby">ルビ付き</option>
<option value="contrast" selected="selected">配色反転</option>
<option value="larger-text">文字拡大</option>
<option value="mobile">モバイル</option>
</select>
<input type="submit" value="表示" />
</p>
</form>
</div>