[Fwd: Re: fusion de deux nombres entiers...]

[Jean-Francois Ortolo]

Y a t-il une longeure maximale pour les chaine de chiffre???

Il n'y a pas de longueur maximale pour les chaînes de chiffres, on
suppose simplement, que comme les nombres non parasités doivent être
inférieurs à 28 ( 2 chiffres ), et que l'on suppose qu'un vingtaine de
chiffres parasites est bien un maximum, je pense que la chaîne de
chiffres, ne dépassera pas 20 chiffres.

Je serais interessé deja par voir l'algo po rapide que tu as mis au point,
car ce n'est pas trivial comme problèmatique..
Peut etre faut-il rechercher dans les algo de traitement du signal...
Ce qui est sur c'est que c'est pas ininteressant :)
Je vais chercher. A+
Etienne

Ben...

C'est un algorithme de fusion avec sélection de tous les chiffres
appartenant à la fois aux deux nombres, dans l'ordre rencontré.

Attention, c'est important de dire, que c'est dans l'ordre rencontré,
puisque le parasitage ne va pas changer l'ordre relatif des chiffres
initiaux, entre eux.

Donc, mettons $n1 et $n2, on accède à chaque chiffre avec un indice:

$n1[0] est le premier chiffre de $n1 et $n1[strlen("$n1") - 1] est
le dernier chiffre de $n1.

Voici un algorithme que j'ai concocté, merci de m'indiquer les
erreurs qu'il contient, ou des contre-exemples qu'il ne pourrait pas
traiter.

Cette foix-ci, j'ai corrigé la dernière erreur que j'ai remarquée.

Maintenant, les boucles for s'exécutent alternativement, avec
incrémentation dans chaque boucles for, des variables $k et $l, cette
incrémentation n'a lieu qu'une fois pour chaque boucle.

Au moins une des variables $trouve1 et $trouve2 doit être à true
après les deux boucles for, sinon on sort de la boucle while(true)

En effet, si ce n'est pas le cas, c'est que le traitement est terminé.

// $n3 ou $n4 doivent contenir le résultat.
$n3 = "";
$n4 = "";

$k = 0;
$l = 0;
$o = 0;
$p = 0;
if($n1 == $n2)
$n = $n1;
else {
while(true) {
$o = $k;
$trouve1 = false;
for(; $k < strlen($n1); $k++) {
if($n1[$k] == $n2[$l]) {
$n3 .= $n1[$k];
$n4 .= $n2[$l];
$k++; // modification 1
$l++; // modification 2
$trouve1 = true;
break;
}
}

if(!$trouve1)
$k = $o;

$p = $l;
$trouve2 = false;
for(; $l < strlen($n2); $l++) {
if($n2[$l] == $n1[$k]) {
$n4 .= $n2[$l];
$n3 .= $n1[$k];
$k++; // modification 3
$l++; // modification 4
$trouve2 = true;
break;
}
}

if(!$trouve2)
$l = $p;

if((!$trouve1)&&(!$trouve2))
break;

// modification 5
// suppression des incrémentations
// des variables $k et $l.

} // fin de la boucle while(true)

// résultat
// théoriquement $n3 et $n4 sont égaux.
if(strlen($n3) > 0)
$n = 0 + $n3;
else
$n = -1; // les nombres $n1 et $n2 sont incompatibles
}


Si $trouve2 est égal à false, la boucle while reprend si $trouve1 est
égal à true. La variable $l ayant été incrémentée entre temps ( dans la
première boucle for ), le traitement continue sans boucle infinie.

Cela est rendu possible, par la condition de sortie de boucle.


Je pense, que la rapidité de cet algorithme, devrait être de l'ordre
de moins de n2(o), et le plus souvent pratiquement linéaire.


Qu'est-ce que vous pensez de cet algorithmme ?

Le problème, serait de le faire tourner dans autant de nombres $n1 et
$n2 que possible, pour en détecter les erreurs, s'il en contient.

Merci beaucoup de votre aide.

Bien à vous.

Amicalement.

Jean-François Ortolo

[Jean-Francois Ortolo]

Bonjour

Le modérateur ne m'a pas laissé inclure l'algorithme ( voir mon
précédent message ). Donc, voici ma réponse à mon précédent message.


Cà ne marche pas.

Mettons: $n1 = 1234567 , et $n2 = 612345


A ce moment-là, la première boucle for va détecter le chiffre 6 dans
$n1 , associé au chiffre 6 dans $n2. Ensuite, $trouve2 sera égal à
false ( car 7 pas trouvé dans $n2, ensuite on repart au début de la
boucle while.

Ensuite, le chiffre 1 de $n2 ne sera pas trouvé dans $n1, puisque $k
pointe sur le chiffre 7 de $n1, donc $trouve1 == false. Et puis, lors de
la deuxième boucle for, le chiffre 7 ne sera toujours pas trouvé, donc
$trouve2 == false, donc on sort de la boucle while.

Résultat: $n3 = 6 au lieu de $n3 = 12345

Le problème est compliqué, du fait que les chiffres des deux nombres,
ne sont pas en ordre croissant. L'algorithme de fusion classique est
donc inopérant.

Si je triais ces chiffres pour chaque nombres, avec un tri indirect
et une array d'indices ( de manière à retrouver l'ordre initial après ),
le problème serait de traiter les cas où il y a plusieurs chiffres égaux
successifs, dans un nombre trié ( ou dans les deux nombres ). Cà je sais
pas faire.

J'ai sous la main mon bouquin d'algorithme 'Handbook of Algorithms
and Data Structures' de Gonnet, les autres livres que j'ai, ne traitent
pas de ce problème.

Vais voir si ce livre m'apporte un début de réponse.

Bien à vous.

Amicalement.

Jean-François Ortolo