Discussion :

[monpoto2]

Bonjour la mifa,

Me Voici enfin dans la communauté,

Chers ingénieurs, depuis 3 mois, je bosse sur l'algorithme me permettra de parcourir et traiter les arbres binaires, mais ... vrai vrai là je suis fatigué. J'ai tout fais en vain.Mais ma conscience me dit qu'il doit nécessairement exister une méthode ou une manière de le faire.

Voici mon problème mes gares:

D'abord primo, ce n'est pas un exercice, c'est un projet perso que je doit valider (une sorte d'un défi dans mon entreprise).

Secondo, je vais essayer de m'expliquer aussi mieux pour être plus clair.

Tertio, je suis débutant dans le traitement des arbres binaires et qu'après mes recherches et analyse des différentes méthodes de parcours des arbres, j'ai finalement opter la méthode ci-dessous pour mon problème.

Mon algo consiste à retrouver le numéro d'un élément de l'arbre à une grande profondeur(le défi ici est de réduire le numéro de cet élément à cette profondeur aussi petite que possible c'est à dire pas question de traiter les nombres à millions de chiffre) et d'appliquer la méthode de parité pour descendre jusqu'à la racine.

En analysant l'arbre ci-dessus et par construction, on peut dire : il y a 2^n ascendants au degré n.


Par construction de l'arbre, à partir du degré 1 (racine), les pères ont un numéro pair et les mères un numéros impair.

par construction, le numéro de tout ascendant est 2p.

De façon général, si p est pair, le descendant porte le numero p/2, et si p est impair, le descendant porte le numero (p-1)/2

Dans mes recherches j'aurais appris qu'on peut retrouver le chemins d'un ascendants( élément de l'arbre) en connaissant sa position(son numero).

Exemple le degré 9 comporte 512 ascendants (2^9). Si on se positionne sur l'ascendant portant le numéro 612. on peut parcourir le chemin suivant:

Voici mes limites dans mon algo.

Je doit traiter les données au degré n=8388608 donc j'ai affaire à 2^8388608 ascendants au degré 8388608 portant donc des numéros aussi grand.

Question:

- Comment traiter ses données aussi grand facilement ( existe-t-il une astuce de transformer ces nombres en des valeurs plus petites) ?

- Existe-t-il des formules mathématiques plus simples pour la résolution ?

PS : Vos explications, astuces, formules mathématiques, algo me fairons plaisir.

Esperant vous avoir mieux expliquer mon problèmes, je suis à vous la communauté !!!!

[bifur]

si j'ai bien comprit on a affaire a des nombres stoké sur 1Mo (ce qui commence a faire)

pour commencer je dirait qu'en regardant le bit de poid fort de ton nombre tu obtient le rang (ex: 612 donne en binaire 1001100100, le bit a 1 le plus élevé est le 9eme)
ensuite je dirait q'il te suffit de regarder l'état du bit de poids faible pour voir si c'est un homme ou une femme
ensuite tu recule d'un rang juste en supprimant le bit de poid faible
et en dernier je dirait que tu peut compter le nombre d'homme (les zéro) et les femme (les un) entre benjamin et l'ascendant 612 en tronquant le bit de poid fort (ex: 612 donne en binaire une fois le bit de poid fort tronqué 001100100 soit 6 zéro et 3 un, 6 hommes et 3 femmes)

je ne comprend pas bien ce que tu souhaite faire comme traitement a tes données ?

[monpoto2]

Au fait, il s'agit de trouver le numéro d'un élément au degré n. Cela j'arrive à le prouver théoriquement et pratiquement.

Ici le seul souci est que ce nombre devient trop grand au degré n supérieur ( n > 2^32) puisque à ce degré on a affaire à (2^8388608+1)-1 nœuds. ce qui donne des grands nombres à quelques millions de chiffres

Or mon boulot consiste à permettre que le système A calcule la position de l'élément E de l'arbre connaissant évidemment le chemin pour atteindre E et ensuite envoie cette position au système B via GSM( maxi 160 caractères). Le système B doit être capable de retrouver le chemin en analysant bien sûr le numéro de l’élément E reçu.

voilà, c'est tout mon système !!!! qui m'arrache les cheveux.

Avec des données plus petites de l’élément E dans l'arbre (degré n <= 23), cela est possible aussi théorique que pratique.

Si nous prenons comme exemple l'arbre cité dans le post :
Le système A après calcul doit envoyer 612 comme position de l’élément au Système B. Le système B doit à son tour analyser le nombre 612 reçu et retrouver le chemin à parcours dans son arbre.
Pour faire simple c'est comme les système A envoie au système B un nombre qu'il doit analyser et retrouver le chemin à parcourir (001100100 soit 6 zéro et 3 un, 6 hommes et 3 femmes).

NB : Système A et Système B sont indépendants

[Flodelarab]

Bonjour

Un caractère est codé sur combien d'octets ?
Si c'est 1 octet, ne cherche pas, tu ne trouveras pas.

Car 160 caractères * 8 bits = 1280 bits.

Or ton "ordre" est le nombre de bits dont tu as besoin. Ici 8388608.

Comme 8388608>1280, ton objectif est impossible.

Sinon, il faudrait que chaque caractère soit codé sur 6553 octets.... ce qui me parait tout aussi impossible.

[anapurna]

salut

comment charge tu ton arbre ?
comme te l'as dis bifur en regardant la structure de ton nombre tu peut connaitre son identité l'identité de ses parent et ainsi de suite

un nombre est constitué d'une multitude de 0 ou de 1 et au miracle c'est information corresponde a une puissance de deux sur chaque rang
ce qui comme tu le comprendra correspond exactement a la structure de ton arbre

si la capacité de ton chiffre dépasse le int64 (9223372036854775807)
soit tu en envois deux consécutivement et tu change un peu le protocole de communication entre les deux machine
soit il va falloir trouver un moyen de compression

[bifur]

il faudrait créer un nouveau type de variable en mémoire
par exemple:

octet 0: bit 0 à 7
octet 1: bit 8 à 15
....
octet n: bit n*8 à n*8+7

et ensuite créer un programme capable de manipuler ces variables


pour ce qui est de la transmission par sms, avec juste un sms c'est impossible, mais par contre tu peut fractionner celuis ci en plusieurs morceaux et les envoyer un par un par smsmais la il te faudrat envoyer environ 800sms (long et couteux)