fusion de deux nombres entiers...

Le
Jean-Francois Ortolo
Bonjour

Soient $n1 et $n2 deux nombres entiers, dont on sait que $n1 < $n2

Le problème, est de restituer la théorique bonne valeur de ces deux
nombres, sachant que s'ils sont différents, c'est que des chiffres
parasites se sont glissés dans l'un des deux nombres ( ou les deux ).

Je commence avec deux nombres, je continuerai avec plus que deux
nombres, car je dispose d'un certain nombre de nombres ( sic ) qui
devraient être égaux, mais le parasitage fait que, parfois, il ne le
sont pas.

Il est sûr que le parasitage ne consiste que dans l'ajout de chiffres
supplémentaires dans certains nombres, sans altération de l'ordre des
chiffres composant le nombre de départ ( non parasité ). Il n'y a jamais
de retrait de chiffres à cause du parasitage.

Donc, l'algorithme pour restituer le nombre réel, est évident: fusion
dans l'ordre de tous les nombres, pour ne retenir que les chiffres
appartenant à tous les nombres sans exception, tout en respectant
l'ordre. C'est donc un algorithme de fusion.

Pour se limiter à simplement deux nombres au départ, et sachant que
si $n1 == $n2, on retient $n1, on suppose donc, que $n1 < $n2.

Ma question est: Y a-t-il moyen d'opérer cete fusion, avec une
expression régulière ( Posix de préférence ), et une instruction de type
str_replace() ou, plus probablement: ereg_replace() ?

Comme $n1 < $n2, je pense que l'expression régulière pourrait être
déduite de $n1 ?

Merci beaucoup à vous pour vos réponses à ce problème, probablement
classique en PHP.

Bien à vous.

Amicalement.

Jean-François Ortolo


PS Je sais bien comment faire une fusion de deux chaînes de
caractères ( c'est cet algorithme-là que je veux implémenter ), mais je
cherche essentiellement à réduire le coût en durée d'exécution, donc à
utiliser une expression régulière et une instruction de remplacement, au
lieu de traiter chaque caractère ( chiffres ) les uns après les autres.

Les chiffres parasites peuvent être situés n'importe où dans les
nombres de départ.

--
Visitez mon site gratuit donnant des Statistiques
et des Historiques Graphiques sur les Courses de Chevaux:
http://www.ortolojf-courses.com
Vidéos High-Tech et Jeu Vidéo
Téléchargements
Vos réponses Page 1 / 2
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
Jean-Francois Ortolo
Le #6204
Jean-Francois Ortolo wrote:
Bonjour



PS Je sais bien comment faire une fusion de deux chaînes de
caractères ( c'est cet algorithme-là que je veux implémenter ), mais je
cherche essentiellement à réduire le coût en durée d'exécution, donc à
utiliser une expression régulière et une instruction de remplacement, au
lieu de traiter chaque caractère ( chiffres ) les uns après les autres.

Les chiffres parasites peuvent être situés n'importe où dans les
nombres de départ.



Attention

Il s'agit bien d'un algorithme de fusion - dans l'ordre - mais en ne
retenant que les chiffres rencontrés dans tous les nombres analysés.

--
Visitez mon site gratuit donnant des Statistiques
et des Historiques Graphiques sur les Courses de Chevaux:
http://www.ortolojf-courses.com

Olivier Miakinen
Le #6205

Soient $n1 et $n2 deux nombres entiers, dont on sait que $n1 < $n2

Le problème, est de restituer la théorique bonne valeur de ces deux
nombres, sachant que s'ils sont différents, c'est que des chiffres
parasites se sont glissés dans l'un des deux nombres ( ou les deux ).


Je crois avoir fini par comprendre (en lisant la suite) ce que tu
cherches à faire. Mais avoue que ce n'est pas très facile avec ce début
puisque tu commences par dire qu'ils sont différents avant d'expliquer
que s'ils sont différents c'est une erreur...

Note que donner quelques exemples bien choisis aurait pu aider, aussi.

Je commence avec deux nombres, je continuerai avec plus que deux
nombres, car je dispose d'un certain nombre de nombres ( sic ) qui
devraient être égaux, mais le parasitage fait que, parfois, il ne le
sont pas.

Il est sûr que le parasitage ne consiste que dans l'ajout de chiffres
supplémentaires dans certains nombres, sans altération de l'ordre des
chiffres composant le nombre de départ ( non parasité ). Il n'y a jamais
de retrait de chiffres à cause du parasitage.

Donc, l'algorithme pour restituer le nombre réel, est évident: fusion
dans l'ordre de tous les nombres, pour ne retenir que les chiffres
appartenant à tous les nombres sans exception, tout en respectant
l'ordre. C'est donc un algorithme de fusion.


Euh... évident ?

$n1 = 11145999
$n2 = 11154999
résultat = 1114999 ? 1115999 ? 111999 ?

Pour se limiter à simplement deux nombres au départ, et sachant que
si $n1 == $n2, on retient $n1, on suppose donc, que $n1 < $n2.

Ma question est: Y a-t-il moyen d'opérer cete fusion, avec une
expression régulière ( Posix de préférence ), et une instruction de type
str_replace() ou, plus probablement: ereg_replace() ?


Je pense que ça doit pouvoir se faire avec un unique preg_replace(), je
vais y réfléchir. En revanche je ne vois pas comment on pourrait le
faire avec les expressions régulières de type Posix vu qu'il faudra
utiliser des références internes à la recherche, ce qui ne doit pas
exister dans les ereg Posix.

Comme $n1 < $n2, je pense que l'expression régulière pourrait être
déduite de $n1 ?


Ah, tu veux dire créer une regexp à partir de $n1, à appliquer sur $n2 ?
Moi j'aurais pensé utiliser une expression fixe sur "$n1|$n2" ("|" étant
un caractère quelconque autre qu'un chiffre).

Merci beaucoup à vous pour vos réponses à ce problème, probablement
classique en PHP.


:-D

Le « probablement » me semble excessivement optimiste.

PS Je sais bien comment faire une fusion de deux chaînes de
caractères ( c'est cet algorithme-là que je veux implémenter ), mais je
cherche essentiellement à réduire le coût en durée d'exécution, donc à
utiliser une expression régulière et une instruction de remplacement, au
lieu de traiter chaque caractère ( chiffres ) les uns après les autres.


Si tu veux améliorer les performances, c'est une raison supplémentaire
pour utiliser preg_xxx plutôt que ereg_xxx (fût-ce avec une expression
identique).

Les chiffres parasites peuvent être situés n'importe où dans les
nombres de départ.


D'où ma question à propos de 11145999 et 11154999. À la limite,
qu'est-ce qui nous empêche de penser que le nombre de départ était
1199 auquel a été ajouté 1459 dans un cas et 1549 dans l'autres ?

Jean-Francois Ortolo
Le #5655
Olivier Miakinen wrote:

Donc, l'algorithme pour restituer le nombre réel, est évident: fusion
dans l'ordre de tous les nombres, pour ne retenir que les chiffres
appartenant à tous les nombres sans exception, tout en respectant
l'ordre. C'est donc un algorithme de fusion.



Euh... évident ?

$n1 = 11145999
$n2 = 11154999
résultat = 1114999 ? 1115999 ? 111999 ?



Compte tenu du fait que le parasitage est très aléatoire, et ne
concerne que 83 lignes sur un total de plus de 100000 lignes non
parasitées, et que les nombres à comparer sont situés à des lignes
contigûes les unes des autres, on considère qu'il y a une probabilité
nulle, pour que ce type de parasitage double ( très peu probable deux
fois contigüe, et de manière aussi directionnelle... pour appeler les
choses comme ça ), se passe réellement.

En fait, il y a déjà une faible probabilité, pour que sur les deux
nombres, les deux soient parasités, mais je suis quand même obligé de
tenir compte de cette très faible probabilité. Autrement, il suffirait
de prendre le nombre le plus petit.


Je pense que ça doit pouvoir se faire avec un unique preg_replace(), je
vais y réfléchir. En revanche je ne vois pas comment on pourrait le
faire avec les expressions régulières de type Posix vu qu'il faudra
utiliser des références internes à la recherche, ce qui ne doit pas
exister dans les ereg Posix.


Comme $n1 < $n2, je pense que l'expression régulière pourrait être
déduite de $n1 ?



Ah, tu veux dire créer une regexp à partir de $n1, à appliquer sur $n2 ?
Moi j'aurais pensé utiliser une expression fixe sur "$n1|$n2" ("|" étant
un caractère quelconque autre qu'un chiffre).



Oui, effectivement.

Histoire, si $n1 = 123 et $n2 = 81426834 on a $n1 < $n2

$expr = "^[^1]*1[^2]*2[^3]*3[0-9]*$"; // Expression déduite de $n1
$n = ereg_replace($expr, $n1, $n2);
if($n == $n1)
$nombre = $n; // résultat trouvé


Je reconnais que c'est stupide, celà ne marche que si $n1 est le
nombre à chercher, et si donc l'un des deux nombres n'est pas parasité.

Si les deux nombres sont parasités, j'ai besoin de quelque chose de
plus compliqué.


D'où ma question à propos de 11145999 et 11154999. À la limite,
qu'est-ce qui nous empêche de penser que le nombre de départ était
1199 auquel a été ajouté 1459 dans un cas et 1549 dans l'autres ?



Non, parce que le faible pourcentage de lignes parasitées, et le
caractère très très aléatoire du parasitage, font qu'il est certain que
le même parasitage, ne se reproduira pas deux fois de suite.

Les chiffres ajoutés par le parasitage, peuvent être n'importe quels
chiffres, en relativement faible nombre ( moins de 8 chiffres en plus
admettons ), il est possible de rencontrer relativement souvent les
quatres chiffres parasites 2000 à la suite, ou le chiffre 8 répété ou
non. Sinon, tout autre chiffre peut participer à un parasitage.

Attention: Il y a un plus, c'est que les nombres à trouver, sont
nécessairement inférieurs à 100, c'est à dire à un ou deux chiffres.

Merci beaucoup pour votre aide.

Jean-François Ortolo

--
Visitez mon site gratuit donnant des Statistiques
et des Historiques Graphiques sur les Courses de Chevaux:
http://www.ortolojf-courses.com


Olivier Miakinen
Le #5652

Compte tenu du fait que le parasitage est très aléatoire, et ne
concerne que 83 lignes sur un total de plus de 100000 lignes non
parasitées, [...]

Les chiffres ajoutés par le parasitage, peuvent être n'importe quels
chiffres, en relativement faible nombre ( moins de 8 chiffres en plus
admettons ), il est possible de rencontrer relativement souvent les
quatres chiffres parasites 2000 à la suite, ou le chiffre 8 répété ou
non. Sinon, tout autre chiffre peut participer à un parasitage.

Attention: Il y a un plus, c'est que les nombres à trouver, sont
nécessairement inférieurs à 100, c'est à dire à un ou deux chiffres.


Moi y en a rien comprendre du tout. Tu as 100 000 lignes contenant un
nombre d'un ou deux chiffres, ce nombre devant être identique partout
sauf sur 83 lignes, où ce nombre de deux chiffres peut être parasité par
un nombre de plus de 4 chiffres ? C'est bien ça ?

Si ce n'est pas ça, donne-nous un exemple *concret*. Par exemple, si
c'est bien ce que j'ai compris :

<début des 100 000 lignes>
37
37
37
...
37
320007 (1re erreur)
37
...
37
8838887888 (2e erreur)
37
...
37
37
37
337 (83e erreur)
<fin des 100 000 lignes>

Mickael Wolff
Le #5649
Bonjour

Soient $n1 et $n2 deux nombres entiers, dont on sait que $n1 < $n2



Ton histoire « confusionne » mon esprit. Comment sont représentés tes
chiffres ? Est-ce que tu travaille sur des entiers ou flottants
processeurs, ou sur leur représentation sous forme de chaine ?

Qu'est-ce qu'un parasitage dans ce cas précis ? Comment l'obtiens-tu ?

Si c'est un problème algorithmique connu, désolé pour la pollution,
j'ai beaucoup trop de lacunes en algorithmie. Sinon, bah, qu'on
m'explique :)

Bonne journée !

PS.: Et si vous êtes en France, voir en Alsace, faites comme moi :
sortez, fait beau ! Alors bonne balades ;)

Note au modérateur : je suis désolé pour l'encodage, mon client st
pourtant bien configuré. J'essaierai d'être vigilant à ce propos.
--
Mickaël Wolff aka Lupus Michaelis
http://lupusmic.org

Jean-Francois Ortolo
Le #5646
Mickael Wolff wrote:

Ton histoire « confusionne » mon esprit. Comment sont représentés tes
chiffres ? Est-ce que tu travaille sur des entiers ou flottants
processeurs, ou sur leur représentation sous forme de chaine ?



Evidemment, les entiers sont sous forme de chaînes de caractères.

Qu'est-ce qu'un parasitage dans ce cas précis ? Comment l'obtiens-tu ?



J'ai déjà décrit ce type de parasitage dans des précédents messages.

En gros: Parasitage == ajout de n'importe quels chiffres à n'importe
quel endroit de la chaîne de caractères composant le nombre entier. Le
nombre de chiffres ajoutés, dans le cas de parasitage, peut aller,
mettons, de 1 chiffre ajouté à 8 chiffres ajoutés.

Un parasitage ne peut pas consister dans le retrait d'un ni de
plusieurs chiffres, du nombre initial. Seuls des ajouts de chiffres sont
possibles ( à l'exclusion d'autre chose que des chiffres ).

Les codes de début de ligne $an$mois$jour$reunion$course avec chacune
des variables sur 2 chiffres, ne sont jamais parasités. Les nombres
entiers ( dont on suppose, pour la clarté de l'exposé du problème,
qu'ils sont situés après un caractère t ( tabulation ) situé lui-même
après le code, à raison d'un nombre entier par ligne, ces nombres
entiers donc, sont les seuls tokens, susceptibles d'être parasités.

Se reporter à mon précédent message juste au dessus à droite, pour
plus de détails.

Si c'est un problème algorithmique connu, désolé pour la pollution,
j'ai beaucoup trop de lacunes en algorithmie. Sinon, bah, qu'on
m'explique :)



Apparemment, d'après Monsieur Miakinen, ce n'est pas un problème
algorithmique courant en PHP.

Bonne journée !



Merci beaucoup.

Bien à vous.

Amicalement.

Jean-François Ortolo

--
Visitez mon site gratuit donnant des Statistiques
et des Historiques Graphiques sur les Courses de Chevaux:
http://www.ortolojf-courses.com

Olivier Miakinen
Le #5104

Se reporter à mon précédent message juste au dessus à droite, pour
plus de détails.


« Juste au dessus à droite » ? :-D

Pour que cette indication serve à quelque chose, il faudrait que Mickael
utilise le même nouvelleur que toi, configuré de la même manière, et
avec les mêmes articles téléchargés et affichés ! Cela fait beaucoup
trop de « si ».

Apparemment, d'après Monsieur Miakinen, ce n'est pas un problème
algorithmique courant en PHP.


Disons plus modestement que je n'ai encore jamais rencontré ce problème,
pas plus en PHP qu'ailleurs.


Tiens, une petite question au passage. Hier, tu écrivais :

PS Pour donner un exemple concret, voici ce à quoi pourrait ressembler
le fichier, nonobstant le problème du formattage:

0709010101 57 nombre à trouver: 57
0709010101 578
0709010101 957
0709010102 98 nombre à trouver: 98
0709010102 986
0709020101 5462 nombre à trouver: 56
0709020101 65361
0709020102 etc....

[...]

Le nombre de lignes parasitées ( 83 ), correspond au nombre de
lignes, où figurent des numéros de chevaux > 27


Les numéros 57, 98 et 56 de ton exemple sont tous supérieurs à 27.
Alors ? Parasités ou pas ?

Etienne SOBOLE
Le #5101
Y a t-il une longeure maximale pour les chaine de chiffre???

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
Matthieu Moy
Le #5102
Olivier Miakinen

Se reporter à mon précédent message juste au dessus à droite, pour
plus de détails.


« Juste au dessus à droite » ? :-D

Pour que cette indication serve à quelque chose, il faudrait que Mickael
utilise le même nouvelleur que toi, configuré de la même manière, et
avec les mêmes articles téléchargés et affichés ! Cela fait beaucoup
trop de « si ».


Il « faudrait », ou il « suffirait » ?

--
Matthieu


Etienne SOBOLE
Le #5103
Bon une petite recherche et j'ai trouvé...

cela s'apparente aux algorithmes qui recherchent les différences entre deux
chaines de caractères.
En gros ca te dit tous les changements à réaliser pour passer d'une chaine à
l'autre.
Dans ton cas il suffit d'ignorer les changements puisque si tu enleves les
caractères insérés, supprimés, ou deplacés il devrait te rester les
caractère en commun.

Donc faut aller voir du cote de la Distance de Levenshtein
Le tres excellent Wikipédia te donnera ca.
http://fr.wikipedia.org/wiki/Distance_de_Levenshtein

puis cap sur les implémentations
http://en.wikibooks.org/wiki/Algorithm_implementation/Strings/Levenshtein_distance

ou tu trouvera celle du PHP
qui au passage te dis que Levenshtein existe nativement en PHP
http://fr3.php.net/manual/fr/function.levenshtein.php

enfin tu recherches le post de dinesh AT dinsoft DOT net sur la meme page et
tu trouves à peu de chose prêt ton bonheur... Il y a sans doute une tite
adaptation à faire pour ton cas précis, mais c'est sans doute par là qu'il
faut chercher....

Tiens nous au courrant.

A+
Etienne
Publicité
Poster une réponse
Anonyme