Algorithme qui élimine les chiffre répétés

Version imprimable

Voir 40 message(s) de cette discussion en une page

27/04/2018, 01h01
pseudocode
Citation:

Envoyé par wiwaxia

Les opérations de l'arithmétique (quotient et reste de la division euclidienne) permettent probablement de définir une double suite (A_n, B_n), en partant de la puissance de dix (D₀ < 10¹⁰) immédiatement inférieure au nombre considéré (N).

Plus simplement, on peut renverser l'écriture du nombre avec des reste/divisions par 10.
```
N=2032502
 
L=0
TANT QUE N>0
   D=N-(N/10)*10    // équivalent de D = N modulo 10
   L=10*L+D
   N=N/10
FIN
 
// L=2052302
```
Il reste alors à le ré-inverser en prenant soin de supprimer les doublons (avec le principe des 10 filtres/portes expliqué ci-avant).
```
porte0=porte1=...=porte9=ouverte.

M=0
TANT QUE L>0
   D=L-(L/10)*10
   SI (D==0 et porte0==ouverte) ALORS ( M=10*M+D;  porte0=fermée;)
   SI (D==1 et porte1==ouverte) ALORS ( M=10*M+D;  porte1=fermée;)
   ...
   L=L/10
FIN
```
27/04/2018, 10h16
wiwaxia

Algorithme qui élimine les chiffre répétés
Prendre une série de 10 variables booléennes initialisées à la valeur True (chiffre non utilisé) au lieu de 10 entiers dont chacun peut passer de 1 (chiffre non utilisé) à 11, puis 11² (chiffre redoublé, donc éventualité exclue) est une solution astucieuse.

J'avais songé (sans y revenir) à une relation itérative du type B_n = F(B_n-1, c), afin d'alléger l'algorithme; le calcul de la somme est une étape lourde.

Il y a, quoi que l'on choisisse:
a) un bloc de 10 instructions semblables lié à l'impossibilité d'emploi des tableaux (contrainte incontournable);
b) deux blocs du type (WHILE ... DO), dont le plus simple correspond
- soit au renversement des chiffres (selon ce que tu proposes):
Code:

1 2 3 4 5 TANT QUE N>0 D=N-(N/10)*10 // équivalent de D = N modulo 10 L=10*L+D N=N/10 FIN
-soit à la détermination de la plus grande puissance de dix inférieure au nombre testé:

Code:

D:= 1000000000; WHILE (D>N) DO D:= D DIV 10;

C'est plus court à cet endroit, mais moins au niveau du filtre puisqu'il faut modifier le diviseur par une instruction du type

Code:

D:= D DIV 10;

Ta méthode est effectivement la plus simple.
27/04/2018, 11h29
Flodelarab

Citation:

dans le sens dextrograde

Cette discussion m'aura au moins appris 2 couples de mots: sinistrograde/dextrograde et sinistrovolubile/dextrovolubile.

Bonjour

Sans remettre en questions vos idées et suggestions j'ai du mal à comprendre le besoin d'introduire autant de complexité pour un sujet qui me parait simple à résoudre avec juste deux boucles et un compteur.

je suis pas mathématicien juste un développeur qui s’intéresse à l’algorithmie

ce code ultra simple que je viens d'écrire devrait faire le job ou alors il y a une subtilité que je ne vois pas
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 string mystring = "1023352197291078"; //-> 10235978 string outputstring=""; for (int i = mystring.Length-1; i >= 0; i--) { char chr = mystring.ElementAt(i); int cpt=0; for (int j = 0; j <i; j++) { if (chr == mystring.ElementAt(j)) cpt++; } if (cpt == 0) outputstring = chr + outputstring; } Console.WriteLine(outputstring); Console.ReadLine();

27/04/2018, 15h45
wiwaxia

Citation:

Envoyé par Flodelarab

Cette discussion m'aura au moins appris 2 couples de mots: sinistrograde/dextrograde ...

L'opposé de dextrograde est "lévograde" :D = qui progresse vers la gauche, comme les écritures sémitiques (hébreu, arabe, araméen, etc )

Citation:

Envoyé par Flodelarab

... et sinistrovolubile/dextrovolubile.

:calim2: ? Où as-tu trouvé cela ?
27/04/2018, 16h57
Flodelarab

Citation:

Envoyé par wiwaxia

:calim2: ? Où as-tu trouvé cela ?

Je vous retourne le compliment, très cher.
"Dextrograde" n'est dans aucun dictionnaire, sérieux ou fantaisiste.
Il semblerait que ce soit une francisation d'un mot anglais qui lui même est inventé.

Citation:

Prendre une série de 10 variables booléennes initialisées à la valeur True (chiffre non utilisé) au lieu de 10 entiers dont

On peut même n'avoir qu'une variable et faire un multiplexage en base deux.
Ça tient même sur 2 octets.
2ⁱ indique la présence du chiffre i.

Citation:

j'ai du mal à comprendre le besoin d'introduire autant de complexité

Complexité ? Où ça ?
27/04/2018, 17h04
anapurna

salut

après réflexion il y a une autre solution sans connaitre à l'avance le nombre de variable a utiliser

se servir des fonctions de décalage de bit
donc plutot que de se servir de 10 variables booléennes initialisées à la valeur True
je prendrais 1 entier et utiliserais sa forme binaire

"1023352197291078" ce qui devrais nous donner comme résultats intermédiaire après traitement "1111010011000001"

il suffit de relire cet entier ce qui nous donneras
"1023352197291078"
"1111010011000001"
"1023 5 97 8"

mes deux cents ;)

Citation:

Sans remettre en questions vos idées et suggestions j'ai du mal à comprendre le besoin d'introduire autant de complexité pour un sujet qui me parait simple à résoudre avec juste deux boucles et un compteur.

nous avons déjà donné cette réponse il y a fort longtemps ... après moi je suis preneur pour d'autre solution
dans ce cas ce fut fort intéressant
je suis aussi informaticien ... et grâce à leur approche je viens de proposer une autre solution qui dans certain cas peut
être utile par exemple dans les matériel embarqué avec peu de mémoire
ou les optimisation pour le graphisme

PS : Arf grillé pff
27/04/2018, 23h56
wiwaxia

Algorithme qui élimine les chiffre répétés

Citation:

Envoyé par Flodelarab

Cette discussion m'aura au moins appris 2 couples de mots: ... sinistrovolubile/dextrovolubile.

:D Je me demandais quel pouvait être le lien avec le contenu du présent forum ...

Citation:

Envoyé par Flodelarab

... "Dextrograde" n'est dans aucun dictionnaire, sérieux ou fantaisiste.
Il semblerait que ce soit une francisation d'un mot anglais qui lui même est inventé.

J'ai lu ces termes dans un ouvrage français de linguistique, paru il y a quinze ou vingt ans; le contexte en rendait le sens si clair qu'il ne m'est jamais venu l'idée de consulter un dictionnaire - c'est désormais chose faite.
On ne les trouve en effet que dans des articles en anglais traitant des écritures méditerranéennes; cependant leur étymologie latine et leur orthographe autorisent leur passage en français, même s'il s'agit de néologismes.

Citation:

Envoyé par shaun_the_sheep

... j'ai du mal à comprendre le besoin d'introduire autant de complexité pour un sujet qui me parait simple à résoudre avec juste deux boucles et un compteur ...

Les chaînes apparaissent effectivement comme un outil approprié, comme cela avait déjà été suggéré (#13, #15); il y avait toutefois un handicap: l'obligation de ne pas utiliser les tableaux (et donc aussi les chaînes, très vraisemblablement), et de s'en tenir à des types simples de variables.

Citation:

Envoyé par shaun_the_sheep

... ce code ultra simple que je viens d'écrire ...

Il n'y a là probablement aucune pointe d'humour noir, mais ce programme (dont je ne doute pas de l''efficacité) m'a paru rien moins qu'évident ... je ne suis peut-être pas le seul dans ce cas.

Voir 40 message(s) de cette discussion en une page