Fibonacci

Mérciii Xavie mais j'avais un probleme au niveau de la locaion , c'est reglé , mércii bp , mércii.. *!!

le probleme s'es réglé , mais mon probleme c'est que le programme éfféctue au moin (2 a la puissaance n/2 )/2 concatenations , et moi je veux un programme qui n'éffectue q'au plus 'n' concaténations , comment j peux faire , et qué ce que je devrai changé , peut etre la solution itertive ou bién quoi , et merci bién , merci..

C'est vrai que la chaîne va être de plus en plus longue, mais ce sera toujours mieux d'en avoir maximum trois (on ne doit pas pouvoir faire beaucoup mieux) qu'en avoir fibo(n).
On sera rapidement limité en n mais l'optimisation a justement pour but de pouvoir augmenter n, même si ce n'est qu'un petit peu.

Sur ma machine j'ai fait quelques tests, et le malloc de concaténation plante à n=35 pour la méthode récursive, et n=44 pour la méthode itérative... Ce n'est pas sensiblement mieux mais c'est déjà ça ;-)

ah bon , passe Moi alos comment t'as fait pénétrer le malloc a ton programme , et aussi comment ça marche la méthode itértive stp é mérciii d'avance...

"Passe moi", "Passe moi"...
Ce n'est pas parce que je l'ai fait dans mon coin que ça doit t'empêcher de la trouver par toi même !

Le malloc je m'en sers pour la concaténation, vu que la taille de la chaîne augmente très rapidement, un char[100] est dépassé dès n=12, il faut donc t'arranger pour allouer dynamiquement l'espace nécessaire pour ton char*
Pour la méthode itérative tu en trouveras plein sur le forum, le principe est toujours le même, tu pars de fibo_0 et fibo_1, puis tu calcules fibo_2, fibo_3, ... fibo_n avec une petite boucle.

Idée intéressante (en théorie du moins). En pratique on ne gagnera que 2 itérations puisqu'au lieu d'avoir trois chaînes on en aura deux et que l'espace mémoire va quand même être limité, c'est surtout au niveau de la consommation de ressources pour l'allocation mémoire que l'on y gagnerai.

Calculer la taille du bloc final est "facile", il suffit de calculer la valeur du Nè terme de la suite de Fibonacci (donc 100000 sera dépassé pour n>25) et il serait alors préférable de stocker les valeurs de cette suite pour s'en servir comme "indices" lors des copies des blocs (et ainsi savoir quel est le pointeur destination de la copie)

Par contre je n'ai pas compris d'où sors ton 'ABB' dans ton code, de plus tu notes 01, 02, 03, est-ce des valeurs octales ?

Une seule chaine en fait, puisqu'on copie n-2 à partir du début de l'unique chaine...
Et pour ABB, c'est que je partais de f(1) = A et f(2) = B donc f(3) = AB et f(4) = ABB, oui, c'est peut-être pas ce qui est demandé !

Et bien sûr les valeurs affichées ne sont pas en octal, qui n'a aucun intérêt pour moi, mais bien en décimal, c'est juste que j'ai toujours tendance à ajouter un zéro devant les décimaux, sans que je m'explique vraiment pourquoi !
Je crois que c'est dû à l'assembleur, où il est important de faire ressortir les nombres, et il n'y a pas de variation de couleur...

Et je ne comprend pas bien ce que tu veux dire sur les indices de copie ?
Car la chaine est constituée pas-à-pas, sans qu'aucun caractère ne soit copié deux fois, je ne vois pas trop comment faire mieux...

Après j'ai bien pensé à un autre principe, qui consisterait à retenir les tailles de chaines et ensuite reconstituer à la demande, mais c'est beaucoup plus compliqué, et pas spécialement à la portée d'un débutant...

En fait si f(3)=f(1)+f(2)="A"+"B"="AB", on devrait avoir avoir f(4)=f(2)+f(3)="BAB" et non pas "ABB"

Pour mes indices, ce que je remarque c'est que pour tout k>2, les fibo(k) derniers caractères de fibo_ab(n) sont exactement la chaîne fibo_ab(k). Du coup je peux me servir des indices fibo(k) pour construire par copie les fibo_ab(k+2)... Enfin c'est sur cette idée que je partais ;-)

En C, ça donnerait à peu près ceci (je raccourci ^^)

int* fibo = fibonacci(n); // fibo[0]=fibo[1]=1, fibo[k]=fibo[k-2]+fibo[k-1]
char* str = malloc(fibo[n]+1);

str[fibo[n]-2]='a';
str[fibo[n]-1]='b';
str[fibo[n]-0]='\0';

for (i=3; i<=n; i++)
    strncpy(str+(fibo[n]-fibo[i]),str+(fibo[n]-fibo[i-2]),fibo[i-2]);

Alors que moi je voyais ça à l'envers, en copiant fibo(k-2) devant fibo(k-1) pour avoir fibo(k)

-------A   
-------B   
------AB   
-----BAB   
---ABBAB   
BABABBAB   

Ce qui revient au même effectivement, ta méthode ayant l'avantage de garder l'ordre voulu !
En tous cas dans un sens comme dans l'autre, la méthode est fonctionnelle...
Mais je ne vois pas trop l'intérêt du résultat, difficile à visualiser et pas très pratique non plus pour effectuer des calculs.
De plus on pourrait pousser la méthode dans ses retranchements en passant au binaire, ce qui diviserait par 8 la taille de la chaine (A = 0 et B = 1)...

Evidemment en passant binaire cela permettrait de diviser l'espace mémoire alloué, mais on se retrouve à devoir utiliser des opérateurs bit-a-bit et j'avoue ne pas les connaître suffisamment pour pouvoir faire des copies propres, d'autant que les opérateurs de déplacement se contrôlent surement avec des int, or ce sont eux qui vont désormais déborder à cause de la croissance exponentielle.

Le problème est très scolaire, mais son optimisation l'est un peu moins ^^

Hé bien, pour info, en binaire non optimisé ça donnerais ça, sommairement toujours :

var  
  N1, N2, N3 : Integer;  
  Bloc : Array[0..100000] of Byte;  
  Count1, Count2 : integer;  

  Bloc[0]:= $6;
  N1:= 02;  
  N2:= 03;  

  FillChar(Bloc, SizeOf(Bloc), 0); 

  For Count1:= 0 to 20 do  
  begin  
    For Count2:= 0 to N1-01 do  
    If Boolean(((Bloc[Count2 shr  03]) shr (Count2 and 07)) and 01) then 
    Inc(Bloc[(Count2 + N2) shr  03]) , 01 shl ((Count2 + N2) and 07); 

    N3:= N1 + N2;  
    N1:= N2;  
    N2:= N3;  
  end;  

Il serais évidement possible de copier 32 bits d'un seul coup pour dupliquer les chaines, en plus compliqué...

Même en mettant 8 bits par byte, tes 100 000 cases ça fait un peu petit. Peut-être que le Pascal ne te permet pas de faire plus ? Il faudrait que je regarde ce que ça donne avec les bits en C.
Pour l'instant avec 1 octets par caractère, j'atteint n=44 (soit 1,13 milliards de caractères) et ça plante à n=45 (1,84 milliards), en divisant par 8 l'espace, ça permettrait d'atteindre n=48 (7,78 milliards)

Après pour faire plus (est-ce vraiment utile ?) il faudrait faire de la manipulation de fichiers, ce sera certes plus long, mais on soulagera la mémoire vive au détriment de la mémoire physique.
Mais il ne faut pas rêver, on n'ira pas beaucoup plus loin :p