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)

[Flodelarab]

il te faudrat envoyer environ 800sms

Non ! Il faudra 6554 sms, comme expliqué plus haut.

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

Dans le but de ?...

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

Que veut dire "manipuler", concrètement ?


Il faudra que tu finisses par lire nos messages, si tu veux de l'aide.

[tbc92]

J'ai l'impression qu'il y a un quiproquo sur le nombre de générations.
Ce que j'appelle génération, c'est ce qu'on appelle génération en généalogie. Dans ton dessin par exemple, il y a 3 générations.
Et dans un octet, tu as 8 bits, tu peux stocker 8 générations.
Si je comprend bien ta question, tu veux pouvoir traiter 8388608 générations. Il te faut donc 8388608/8 octets. Et puisque chaque SMS est limité à 160 octets, on arrive au nombre de 8388608/8/160 = 6554 SMS ( je fais confiance au calcul de Flodelarab, l'ordre de grandeur est celui-là.)

Et malheureusement, pas de compression envisageable.

[monpoto2]

Merci la famille pour vos intervention brillante
pour être encore plus clair, voici quelques point caractéristiques du système sous forme de questionnaire:

A quoi correspond ce nombre que tu veux transmettre ? : Ce nombre doit correspondre à la position ou numéro d'un élément dans l'arbre binaire

Est-il le fruit d'un calcul ? : Surement Le système A doit fournir ce nombre

Est-ce que le système B peut être capable de refaire ce calcul ? : Non

Est-ce que le système B a nécessairement besoin de connaître ce chiffre et pourquoi ? : Oui, le système a besoin de ce nombre pour recalculer le chemin de parcours

Est-ce qu'au lieu d'utiliser des SMS, tu pourrais utiliser de la data pour transmettre 1mo ? Il faut nécessairement passer par SMS

Combien pèse ton arbre entier avec les données s'il y a autant d'élément dedans ? l'arbre est variable , mini (2^8388608+1)+1 nœuds

soit au degré minimal de 1Mo

Pourquoi est-il partagé sur les deux systèmes ? : Les deux systèmes sont indépendantes

Est-ce que c'était juste un arbre théorique avec lequel tu espérais réduire la taille de donnée à envoyer ? : Oui, les données à envoyer sont énormes donc nous avons trouvé une manière de les organiser dans un arbre, la réussite de ce projet serait donc que le système A calcule la position des données dans l'arbre, envoie cette position au Système B qui va à son tour parcourir l'arbre et retrouver l’élément de départ. Le système B régénère cet élément et active une action du central radioactive.

[Flodelarab]

Et malheureusement, pas de compression envisageable.

C'est le drame.

Un caractère est codé sur combien d'octets ?

Je me réponds à moi-même. Je viens de vérifier sur wikipedia, c'est 8 bits pour 140 caractères ou 160 caractères ASCII (donc 7 bits)
Donc le tarif vient de monter à 7490 sms.
Désolé.

Ce n'est pas impossible. Il reste à voir si c'est acceptable.

[anapurna]

Merci la famille pour vos intervention brillante
pour être encore plus clair, voici quelques point caractéristiques du système sous forme de questionnaire:

A quoi correspond ce nombre que tu veux transmettre ? : Ce nombre doit correspondre à la position ou numéro d'un élément dans l'arbre binaire //Ok

Est-il le fruit d'un calcul ? : Surement Le système A doit fournir ce nombre

Est-ce que le système B peut être capable de refaire ce calcul ? : Non // Pourquoi ?

Est-ce que le système B a nécessairement besoin de connaître ce chiffre et pourquoi ? : Oui, le système a besoin de ce nombre pour recalculer le chemin de parcours
//Ok donc il recalcul

Est-ce qu'au lieu d'utiliser des SMS, tu pourrais utiliser de la data pour transmettre 1mo ? Il faut nécessairement passer par SMS
//Ok

Combien pèse ton arbre entier avec les données s'il y a autant d'élément dedans ? l'arbre est variable , mini (2^8388608+1)+1 nœuds
//Ok as tu besoin de passer que son indice ?
soit au degré minimal de 1Mo

Pourquoi est-il partagé sur les deux systèmes ? : Les deux systèmes sont indépendantes

Est-ce que c'était juste un arbre théorique avec lequel tu espérais réduire la taille de donnée à envoyer ? : Oui, les données à envoyer sont énormes donc nous avons trouvé une manière de les organiser dans un arbre, la réussite de ce projet serait donc que le système A calcule la position des données dans l'arbre, envoie cette position au Système B qui va à son tour parcourir l'arbre et retrouver l’élément de départ. Le système B régénère cet élément et active une action du central radioactive.

bin en faite tu donne toi même la solution pourquoi ne pas donner ton nombre en puissance de 2 afin que le système B puissent le reconstruire a l'arrivée

[bifur]

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

Dans le but de ?...

tout simplement dans le but de pouvoir travailler sur des entiers du nombre de bit nécessaire, c'est pas parce qu'on as une machine 32bits que l'on ne peut pas travailler sur du 64bit, c'est juste plus compliqué ici c'est pour travailler sur des mot de 8388608bit

par contre j'ai l'impression que certain n'ont pas comprit que:
le numéros = le chemin entre la personne de ce numéros dans l'arbre et la base de l'arbre

il faut les lire différament c'est tout, n'importe que microprocesseur sera capable de retrouver le "chemin" si on lui donne le nombre (même un humain pourrrait le "lire" si on lui écrivait en binaire

[kolodz]

Bonjour,

J'avoue ne pas bien comprendre quel domaine métier peu demander de travailler sur un arbre binaire à 1 000 000+ niveau.
Cela indique un problème de conception grave au niveau de l'application ou une mauvaise compréhension du problème de base.
Si on suppose que ton arbre binaire représente, les parents d'une personnes. A partir d'un certains point la personne d'origine n'est plus intéressant à partir d'un certains point. Car la modélisation sera fausse... (Il y a des personnes en doublons et donc leurs parents aussi...)
Par exemple, si tu prends l'arbre généalogique d'un personne sur 30 générations, la ligne n=30 est supposé contenir 1 073 741 824 personnes or la population mondial en 1300 est estimé à 429 000 000.

C'est un exemple idiot, mais qui sous-ligne le fait qu'il n'est pas envisageable de travail avec le même point de référence ayant une profondeur non fixe.
Il serai préférable d'avoir un point de référence variable...


Pour ce qui est de la partie purement technique :
Au degré n = 8388608 :
Il est nécessaire d'avoir 8388608 bit pour mémorisé le nombre en mémoire.
Soit 1 048 576 octet (1 octet = 8 bits)
Soit 1 024 Ko
Soit 1 Mo

De même, pour obtenir le "type" en position 0<X<N, il suffit de lire le bit à la position correspondant.
Exemple :
En reprenant l'exemple :

9 = 1001 => Soit Père(n=1), Père(n=2)
8 = 1001 => Soit Père(n=1), Père(n=2)
10 = 1010 =>Soit Père(n=1), Mère(n=2)
11 = 1011 =>Soit Père(n=1), Mère(n=2)
12 = 1100 => Soit Mère(n=1), Père(n=2)
13 = 1101 => Soit Mère(n=1), Père(n=2)
14 = 1110 => Soit Mère(n=1), Mère(n=2)
15 = 1111 => Soit Mère(n=1), Mère(n=2)

Je te laisse faire la correspondance entre la position du bit et le degré dans ton arbre...

il est possible de divisé l'arbre en plusieurs partie.
Par exemple pour un arbre à 6 "degré" :
L'id de par personne sera "42" en binaire : 101010
On peut découpé l'arbre en 3 groupe de 2 génération et avoir 2-2-2 (10-10-10)
Soit 3 fois Mère-Père...

A ce niveau là, il est possible de transmettre uniquement une partie de l'arbre. Et dire pour la génération X à Y l'enchainement est ...

Cordialement,
Patrick Kolodziejczyk.

[monpoto2]

il est possible de divisé l'arbre en plusieurs partie.
Par exemple pour un arbre à 6 "degré" :
L'id de par personne sera "42" en binaire : 101010
On peut découpé l'arbre en 3 groupe de 2 génération et avoir 2-2-2 (10-10-10)
Soit 3 fois Mère-Père...

A ce niveau là, il est possible de transmettre uniquement une partie de l'arbre. Et dire pour la génération X à Y l'enchainement est ...

Pourriez- vous donnez plus de détails de votre idée en couleur rouge.

[kolodz]

Pour "l'idée", c'est assez simple.
Si on reprend votre exemple :

Si on considère l'ID 12.
Le chemin est le même si on cumul l'arbre d'ID2 sur l'arbre d'ID6.
Du coup, il est totalement possible de dire que du rang 1 à 2 on a l'arbre ID6 et que le rang 3 correspond à l'arbre ID2.

Sachant que dans la représentation que vous avez, en binaire :
Si on a un 1, cela indique qu'on a un nœud "Droit/Mère"
Si on a un 0, cela indique un nœud "Gauche/Père"

Si vous ne comprenez pas, le mieux est d'apprendre la représentation binaire et et à quoi correspond un encodage
Voici une vidéo qui explique globalement le principe d'encodage :

Le première exemple est pratiquement ce que tu cherche...

Cordialement,
Patrick Kolodziejczyk.

[DonQuiche]

Le problème est mal posé. Oublions l'arbre.

Ces données ne sont stockées nulle part car il n'y aurait pas assez d'espace sur Terre. En revanche il est possible que le système A choisisse une combinaison précise parmi au moins 2^8388608 possibles. Votre "arbre" n'est donc qu'une convention d'encodage de la solution. Convention manifestement insuffisante pour vos besoins car elle impose trop de SMS.

Le système B peut-il vraiment recevoir n'importe laquelle des 2^8388608 possibilités ? Si oui, alors le design désiré est impossible en pratique (trop de SMS). Le mieux qu'il soit possible de faire dans ce cas est d'envoyer certaines données et de laisser B refaire une partie du calcul.

SI vraiment la tâche te semble possible, c'est sans doute qu'il y a en fait bien moins de combinaisons possibles en pratique. Voilà ce que tu dois creuser. Pur t'indiquer ton chemin je détaille les trois croisements sur ta route et non pas les trois mille pavés.

[monpoto2]

Pour "l'idée", c'est assez simple.
Si on reprend votre exemple :

Si on considère l'ID 12.
Le chemin est le même si on cumul l'arbre d'ID2 sur l'arbre d'ID6.
Du coup, il est totalement possible de dire que du rang 1 à 2 on a l'arbre ID6 et que le rang 3 correspond à l'arbre ID2.

Sachant que dans la représentation que vous avez, en binaire :
Si on a un 1, cela indique qu'on a un nœud "Droit/Mère"
Si on a un 0, cela indique un nœud "Gauche/Père"

Bien cette partie a l'air très intéressantes : veillez développer un peu plus , j'allais dire plus d'exemple, un raisonnement mathématique sera encore plus la bienvenue.

Si on considère l'ID 12.
Le chemin est le même si on cumul l'arbre d'ID2 sur l'arbre d'ID6.
Du coup, il est totalement possible de dire que du rang 1 à 2 on a l'arbre ID6 et que le rang 3 correspond à l'arbre ID2.

Sachant que dans la représentation que vous avez, en binaire :
Si on a un 1, cela indique qu'on a un nœud "Droit/Mère"
Si on a un 0, cela indique un nœud "Gauche/Père"

Pour la vidéo je vais jeté un coup d’œil

A mi chemin pour la recherche de solutions à mon problème de taille, je tiens à vous remercier tous pour l'énergie que vous accordez à ce sujet. Je remercie également l’équipe de developpez.com.
Sachez que tous vos suggestions et explication sont soigneusement noté en les étudiants cas par cas.

Je sais que grace à vous je trouverai mon mot final d'ici la fin de la semaine.Merci

[souviron34]

J'avoue ne pas bien comprendre quel domaine métier peu demander de travailler sur un arbre binaire à 1 000 000+ niveau.
Cela indique un problème de conception grave au niveau de l'application ou une mauvaise compréhension du problème de base.
Si on suppose que ton arbre binaire représente, les parents d'une personnes. A partir d'un certains point la personne d'origine n'est plus intéressant à partir d'un certains point. Car la modélisation sera fausse... (Il y a des personnes en doublons et donc leurs parents aussi...)
Par exemple, si tu prends l'arbre généalogique d'un personne sur 30 générations, la ligne n=30 est supposé contenir 1 073 741 824 personnes or la population mondial en 1300 est estimé à 429 000 000.

C'est un exemple idiot, mais qui sous-ligne le fait qu'il n'est pas envisageable de travail avec le même point de référence ayant une profondeur non fixe.
Il serai préférable d'avoir un point de référence variable...

Pour abonder dans le sens de Patrick, un petit calcul d'ordre de grandeur..

L'un des plus ancien hominidé connu est Lucy (paléoanthropologie) qui a vécu il y a 3 ou 4 millions d'années.

Si on admet une vision "jeune" d'une génération, on peut dire que chaque génération donne naissance à une nouvelle tous les 15 ans.

Depuis donc Lucy, il y a eu 266 667 générations. Soit 2¹⁸...

Et on est très large là... (puisque les premiers humains nous ressemblant semblent avoir entre 200 000 ans et 2.8 millions d'années)..

Donc pour tout humain d'aujourd'hui on devrait remonter au maximum à 2¹⁸ générations..


D'autre part, l'arbre ne peut pas croître indéfiniment vers le passé.. : comme on vient de le dire, on part de 0 il y a X millions d'années pour augmenter... Donc réciproquement à partir d'aujourd'hui on ne croît pas indéfiniment vers le passé....

On a donc un arbre qui commence par croître puis par se réduire..


Et si je reprend l'exemple de Patrick : en 1300, cela fait 700 ans.. Soit 46 générations... soit 2⁵.. Avec 2 parents, cela signifie que tout humain d'aujourd'hui aurait 2 millions de parents... sur 46 niveaux...

On est loin des chiffres sur lesquels tu nous demandes de travailler..

[monpoto2]

bin en faite tu donne toi même la solution pourquoi ne pas donner ton nombre en puissance de 2 afin que le système B puissent le reconstruire a l'arrivée

SVP détaille moi cette partie , elle est extrêmement importante et intéressant. Au lieu d'envoyer un nombre on peut envoyer au Système B, une puissance de 2. génial !!!! détails SVP.

[DonQuiche]

SVP détaille moi cette partie , elle est extrêmement importante et intéressant. Au lieu d'envoyer un nombre on peut envoyer au Système B, une puissance de 2. génial !!!! détails SVP.

Tu pars du nombre 0 et à chaque embranchement tu multiplies le précédent nombre par 2 et tu ajoutes 0 pour le choix gauche ou 1 pour le choix droite. Gauche-gauche-gauche donne 000, gauche-droite-gauche donne 010, etc.

Mais avec tes 8388608 embranchements il te faudrait 8388608 bits. Donc beaucoup trop de SMS comme tout le monde te l'a dit. Et il est impossible de compresser davantage (premier théorème de Shannon).


Voilà pourquoi je t'ai dit plus haut que tel quel ton problème était insoluble. Tu ne peux pas compresser davantage, il faut absolument que tu trouves un moyen de ne transmettre qu'une partie de l'information. Ou abandonner les SMS.