Suite de Robinson

Version imprimable

19/02/2008, 13h10
JetliMohamed

Suite de Robinson

Je suis intéressé bien de cet exercice SVP Aide-moi!!!

La suite de Robinson défini par :
Ui = a
Ui+1 = apparition de chaque chiffre dans apparait dans UI
Exemple :
Si U0 = 1 et n=6 alors

U1 = 11 car "1 se répète 1 fois dans U0"
U2 = 21 car "1 se répète 2 fois dans U1"
U3 = 1211 car "2 se répète 1 fois et 1 se répète 1 fois dans U2"
U4 = 3112 car "1 se répète 3 fois et 2 se répète 1 fois dans U3"
U5 =132112 car"3 se répète 1 fois et 1 se répète 2 et 2 se répète 1 fois dans U4 ".
U6 = 311322

Question :
1. Quel est l'ordre de récurence de cette suite?
2.Ecrire un analyse et un algorithme qui permet de calculer et d'afficher un terme d'indice (n) de cette suite.

Jetli.:: cet exercice est un ex de mon devoire de controle !!!!
19/02/2008, 13h54
krachik

Bonjour
Cet exercice me rappelle un enigme comme quoi il faut completer la suite :mouarf:.

Bon revenons à cet exercice donc. et comme tu le sais forcement ce n'est pas parce que ça fait parti de ton devoir de controle(que tu as peut etre deja fait ou peut etre pas ) qu'on va te filer une correction toute faite.
Alors proposes et ensuite on vera si tout le monde est d'accord ;)
Cordialement.
20/02/2008, 09h05
JetliMohamed
Bonjour, ce qui est plus intéressant que l'algorithme, c'est l'idée, alors voilà mon idée pour cet exercice : :yaisse2:
- 1- On va lire (a) le premier terme, c'est l'initiation de notre suite.
  {La lecture du premier terme est une chaîne directement puis on fait un test si il est valeur ou non (répéter lire(a) val(a,x,e) jusqu'a (e=0 )
  * e est l'erreur de conversion.
- 2- On va lire (n) le nombre de termes de la suite.
- 3- Un appel à la fonction compter qui calcule l'apparition de chaque chiffre de la chaîne.
- 4- Concaténons le nombre d'apparitions avec le chiffre compté dans une chaîne jusqu'à obtenir toutes les apparitions et les chiffres de Ui-1 dans une nouvelle chaîne.
  ==>Ici mon idée a deux autres sous-idées :
  - 4.1-Pour sauvegarder cette chaîne, on la met dans un tableau de taille (n);
    Enfin on affiche chaque fois le tableau comme résultat final.
  - 4.2 -Mais j'ai une autre idée plus correcte : c'est d'afficher la chaîne directement et on travaille avec cette chaîne pour la deuxième opération. Sauvegardons le nouveau résultat dans une autre auxiliaire et cette fois on affiche l'auxiliaire.
    Initialisons la première à vide etc... jusqu'à obtenir le nombre de termes final (n). :?
Merci, j'espère bien que vous m'aiderez et proposerez d'autre idées plus optimales que la mienne.

Jetli.::

Bonjour
Je suis d'accord sur certains points et je dirai que pendant la concatenation comme tu le vois ça serait plus simple d'utiliser une chaine.

Citation:

Envoyé par JetliMohamed

4- Concaténons le nombre d'apparitions avec le chiffre compté dans une chaîne jusqu'à obtenir toutes les apparitions et les chiffres de Ui-1 dans une nouvelle chaîne.

ça va être quand même peu un lourd de faire ça à chaque fois sur chaque bout de la chaine .Moi je proposerai juste de déterminer le nombre maximum contenu dans la chaine et comme ça on fera une concatenation avec une boucle partant de 1 jusqu'a ce nombreMax ; et en tout deux boucles "for" seraient suffisantes
En plus chez toi je ne vois pas intervenir le nombre de terme de la suite introduit
On supose que l'algo ne tient pas compte des contrôles :P et je suppose aussi que je dispose des fonctions suivantes
Code:

1 2 3 ---->nbOccurence(String,Char) :Integer Calcule le nombre d''occurence d''un caractere dans la chaine ---->chMax (String) :Integer Renvoie le chiffre Maximum contenu dans cette serie de chiffres
1. On lit le premier terme(U0) et on le converti bien sûr en chaine
2. On lit le nombre de terme de la suite
3. On fait un parcours de 1 jusqu'au nombre de terme , et à chaque fois on calcule le Chiffre Max de la chaine pour en faire un parcours allant de 1 jusqu'a ce nombre .Ensuite il suffit de faire une concatenation avec le nombre d'occurence de chaque chiffre+chiffre tout en prenant soin de rajouter la chaine precedemment concatenée a la nouvelle (attention dans la seconde boucle)
4. Ne pas oublier les initialisations comme tu l'a dis en mettant la suite à vide avant le prochaine coup de boucle(la premiere boucle

---------
Bon je crois que tout ça doit être un peu confus dès que j'ai un papier+stylo à portée de main je te remet ça au propre bien ecrit en algo :P
@+

21/02/2008, 12h51
JetliMohamed

Bonjours mon ami Krachik,

Citation:

Krachik dit : pour en faire un parcours allant de 1 jusqu'a ce nombre .Ensuite il suffit de faire une concatenation avec le nombre
d'occurencede chaque chiffre+chiffre

Ce que je comprend pas c'est de quoi s'agit il le deuxième parcours

Citation:

pour en faire un parcours allant de 1 jusqu'a ce nombre

Je sais que ce nombre est le chiffreMax mais quel est la résultat de cette opération :(.
SVP je suis interresser bien de votre algorithme. Merci!!!!!:king:
Jetli.::

Bonjour
Désolé pour le retard.
En fait ce que je disais par cette fonction chMax :il consiste à trouver le chiffre le plus grand contenu dans cette serie de suite comme ça on es sûr d'avoir le nombre exact de chiffre contenu dans la serie sans doublons:P
Exemple : U4 = 3112 le chiffre maxi dans cette serie est 3: et deduction les chiffres dans la serie seront 1 ,2 ,3 sans doublons. Mon but en faisant cette fonction etait de d'eviter d'avoir par exemple :
U4 = 3112 et U5=13212112 (ne pas répeter le comptage c'est a dire une fois qu'un chiffre apparu à été compté ne plus le toucher au prochain comptage)
Mais en y pensant la ,je vois plus simple :Il suffit de traiter le chaine precedente de serie en y renvoyant une chaine où on aura plus de doublons
exemple U4 =3112 apres traitement on devrai avoir U4'= 312 ,Donc ce qu'on aura à faire c'est juste compter le nombre d'apparition de chaque chiffre de U4' dans U4 +chaque chiffre de U4'

En gros la fonction qui devra nous renvoyer notre suite sera de ce genre qui prendra en entrée le premier terme de la suite (premier) et le nombre de terme de la suite(n)
Code:

1 2 3 4 5 6 7 8 9 10 11 12 Suite <--------"" chConverti<---------ChaineConvertEnttoString(premier); POUR i allant de 1 à n FAIRE chSansDoublons <----- ElimDoublons(chConverti) POUR j allant de 1 à longeur(chSansDoublons) FAIRE Suite<--- Suite + nbOccur(chConverti,chSansDoublons[j])+chSansDoublons[j] Fin Pour Afficher Suite chConverti< ---- Suite //Affecter la suite pour une nouvelle action Suite <-----"" //Liberer la suite pour une nouvelle concat FinPour
Alors il faut ecrire :
1.La fonction qui renvoie la nouvelle chaine sans doubon(ElimDoublons)
2.La fonction pour le nombre d'occurence (nbOccur);

Il ne reste plus qu'a ecrire tout ça 8-). Dans ton algo pour le traitement que je fais dans ma seconde boucle ça va etre plus lourd sans fonctions adequates .
Cordialement

22/02/2008, 16h41
JetliMohamed

Bonjours Karchik,
J'ai compris bien votre idée car elle est presque comme la mienne mais celle ci est plus courte merci bien une seconde pour ecrire les fonctions de vos appelle
élimination de redandance et le comptage d'occurence.
Jetli.:: merci @+

Re-Slt,
Voila ma fonction qui ne s'arrete pas je sais ou est la faute lol.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
uses wincrt;
var
ch:string;
function elimdoub(x:string):string ;
var
cpt,i,j:integer;
c:char;
begin
for j:=1 to length (x) do
begin
     i:=1 ; c:= x[j];
     repeat
           if x[i] = c then
           begin
           cpt := cpt+1;
           i:=i+1;
 
           if cpt>=2 then
           begin
           delete (x,i-1,1);
           end
           else
           begin
           i:= i+1;
           end;
           end;
     until i = length(x);
end;
 
elimdoub := x;
end;
{PP}
Begin
writeln('Entrer un chaine de caractère');
readln(ch);
ch:=  elimdoub(ch);
writeln(ch);
end.

Krachik SVP corrige la
j'attend vite vite vite lool.

23/02/2008, 01h59
krachik

Bonjour
je crois qu' on ne sait pas bien compris ,quand j'ai dit " proposes et on vera si tout le monde est d'accord" ,ça ne veut pas dire que "proposes sans avoir pris le temps de bien réfléchir à ce que tu allais faire" ;).
Il ne faut pas se précipiter sur les choses et fournir un code que toi meme tu ne comprendras pas

Citation:

Voila ma fonction qui ne s'arrete pas je sais ou est la faute lol.

Alors je crois que tu devrais reprendre ton code apres avoir etabli un bon algo,et quand tu le reprendras penses à bien indenter ton code proprement ;)
-regardes bien les tests et les actions que tu fais dans ta fonction
-C'est quoi l'idée que tu essais de traduiire 8-)
Cordialement.+
24/02/2008, 05h24
droggo
Gio,

Ce que tu présentes dans ton 1er message n'est pas la suite de Robinson :

- Cette suite s'initialise avec 0 (éventuellement avec une autre valeur, mais ce n'est plus la suite de Robinson au sens strict)

et surtout,

- le terme (n+1) affiche , le nombre d'occurence de chaque chiffre présent dans le terme (n), dans l'ordre 9 à 0, sans tenir compte des chiffres n'apparaissant pas dans ce terme (n).

De cela, il ressort que la "vraie" suite de Robinson est
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 0 10 1110 3110 132110 13123110 23124110 1413223110 1423224110 2413323110 1433223110 1433223110 1433223110 1433223110
On voit qu'elle finit rapidement par boucler sur la même chaîne.

et si on veut initialiser avec 1, on obtiendra
Code:

1 2 3 4 5 6 7 1 11 21 1211 1231 131221 132231
qui finira également par un chaîne constante. Ce n'est pas vrai pour toute valeur initiale, mais elle finira toujours soit par être constante, soit par osciller entre 2 ou 3 valeurs.

Citation:

Envoyé par droggo

et si on veut initialiser avec 1, on obtiendra[.........]
qui finira également par un chaîne constante. Ce n'est pas vrai pour toute valeur initiale, mais elle finira toujours soit par être constante, soit par osciller entre 2 ou 3 valeurs.

Allé Hop voila ce que dit mon compilateur :mouarf:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 U(1) :11 U(2) :21 U(3) :1211 U(4) :3112 U(5) :132112 U(6) :311322 U(7) :232122 U(8) :421311 U(9) :14123113 U(10) :41141223 U(11) :24312213 U(12) :32142321 U(13) :23322114 U(14) :32232114 U(15) :23322114 U(16) :32232114 U(17) :23322114 U(18) :32232114 U(19) :23322114 U(20) :32232114 U(21) :23322114 U(22) :32232114 U(23) :23322114 U(24) :32232114 U(25) :23322114 U(26) :32232114 U(27) :23322114 U(28) :32232114 U(29) :23322114 U(30) :32232114 U(31) :23322114 U(32) :32232114 U(33) :23322114 U(34) :32232114 U(35) :23322114 U(36) :32232114 ....................

24/02/2008, 12h00
M.Dlb

Pas mal ;) C'est le genre d'exos que je trouve très intéressant pour des étudiants, à la fois ludique (pour ceux qui aiment les maths) et riche en enseignement côté programmation

Fio,
Citation:
Envoyé par krachik
Allé Hop voila ce que dit mon compilateur :mouarf:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 U(1) :11 U(2) :21 U(3) :1211 U(4) :3112 U(5) :132112 U(6) :311322 U(7) :232122 U(8) :421311 U(9) :14123113 U(10) :41141223 U(11) :24312213 U(12) :32142321 U(13) :23322114 U(14) :32232114 U(15) :23322114 U(16) :32232114 U(17) :23322114 U(18) :32232114 U(19) :23322114 U(20) :32232114 U(21) :23322114 U(22) :32232114 U(23) :23322114 U(24) :32232114 U(25) :23322114 U(26) :32232114 U(27) :23322114 U(28) :32232114 U(29) :23322114 U(30) :32232114 U(31) :23322114 U(32) :32232114 U(33) :23322114 U(34) :32232114 U(35) :23322114 U(36) :32232114 ....................
Je ne dis pas le contraire.

Ce que j'ai précisé, c'est que la suite que tu obtiens n'est pas la "suite de Robinson", pour laquelle on compte le nombre d'occurrences des chiffres en tenant compte de l'orde de 9 à 0 : on compte les 9, puis les 8...

Celle que tu génères correspond à l'énoncé, et compte le nombre d'occurrences des chiffres en fonction de leur ordre de 1ère apparition dans la chaîne, ce qui est très différent, et n'est pas la suite de Robinson.
Cette suite ainsi obtenue a sûrement un nom aussi, mais je l'ignore. :)