Générer le code binaire, par le récursif

Générer le code binaire, par le récursif - Algo - Programmation

Marsh Posté le 14-01-2004 à 22:59:41    

Bonsoir,  
 
J'ai un problème d'algo concernant une fonction capable de retourner le code binaire d'un niveau n.
Le prototype :

Code :
  1. public static String showBits(int n [, String s]);


 
L'argument s est optionel, mais le prof' nous a dit qu'on allait en avoir besoin..

Code :
  1. n=1: 0\n1\n
  2. n=2: 00\n01\n\10\n11\n
  3. etc.


Personnellement, j'ai écrit cette fonction itérative/récursive, mais qui ne fonctionne pas tout à fait correctement, ne marche que pour les niveaux 1, 2, et 3, sans passer de ligne après chaque ligne..
 

Code :
  1. public static String showBits(int n) {
  2. if (n == 1) return "0\n1\n";
  3. String s = new String();
  5. for (int i=0; i<Math.pow(2, n-1); i++) {
  6.     String lg = new String();
  7.     for (int j=0; j<n-1; j++) lg += showBits(n-1).charAt(j+2*i);
  8.     s += "0" + lg;
  9. }
  10. for (int i=0; i<Math.pow(2, n-1); i++) {
  11.     String lg = new String();
  12.     for (int j=0; j<n-1; j++) lg += showBits(n-1).charAt(j+2*i);
  13.     s += "1" + lg;
  14. }
  15. return s;
  16.     }
  18. Appel avec n=2: 00011011
  19. Appel avec n=3: 000001010011100101110111


 
Evidemment, il y a des contraintes. Il ne faut pas sauvegarder le nombre n original extérieurement à la fonction, pas de variables static, pas de méthodes complexes, et il faut bien sûr que ça soit récursif !
 
Voilà, si quelqu'un pouvait m'aider un peu..
 
Merci.


Message édité par LajioT le 14-01-2004 à 23:04:13
Reply

Marsh Posté le 14-01-2004 à 22:59:41   

Reply

Marsh Posté le 14-01-2004 à 23:03:44    

-> Cat algo

Reply

Marsh Posté le 16-01-2004 à 20:54:13    

Personne ne peut m'aider ? =(

Reply

Marsh Posté le 16-01-2004 à 21:51:35    

LajioT a écrit :

Personne ne peut m'aider ? =(


 
Voilà je l'ai fait en PHP parce que sinon je connais pas les arguments optionnels dans ton language (C++ ?) :
 

Code :
  1. function bits ($n, $s = "" ) {
  2. if ($n > 0) {
  3.  return  bits ($n - 1, $s . "0" ) . bits ($n - 1, $s . "1" );
  4. } else {
  5.  return $s;
  6. }
  7. }
  8. echo bits (5);


 
Enfin vu la taille de la fonction :D ça devrait pas être dur de le traduire  ;)  
 
voilà le résultat :
01
00011011
000001010011100101110111
0000000100100011010001010110011110001001101010111100110111101111
 
et ainsi de suite ... et ca marche bien je t'assure =)

Reply

Marsh Posté le 16-01-2004 à 22:06:07    

Ahh, yessss, ça fonctionne !  
Merci beaucoup ! ;)
 
Je te laisse trouver le langage. =)

Code :
  1. class Bits {
  2.     public static String bits(int n, String s) {
  3. return n>0 ? bits(n-1, s + "0" ) + bits(n-1, s + "1" ) : s;
  4.     }
  5.     public static void main(String[] args) {
  6. System.out.println(bits(3, "" ));
  7.     }
  8. }


Message édité par LajioT le 16-01-2004 à 22:06:27
Reply

Marsh Posté le 16-01-2004 à 22:47:06    

Tentacle a écrit :


 
Voilà je l'ai fait en PHP parce que sinon je connais pas les arguments optionnels dans ton language (C++ ?) :
 

Code :
  1. function bits ($n, $s = "" ) {
  2. if ($n > 0) {
  3.  return  bits ($n - 1, $s . "0" ) . bits ($n - 1, $s . "1" );
  4. } else {
  5.  return $s;
  6. }
  7. }
  8. echo bits (5);


 
Enfin vu la taille de la fonction :D ça devrait pas être dur de le traduire  ;)  
 
voilà le résultat :
01
00011011
000001010011100101110111
0000000100100011010001010110011110001001101010111100110111101111
 
et ainsi de suite ... et ca marche bien je t'assure =)
 

Comment t'as procédé pour pondre ça ? J'avoue que j'suis un peu sur le cul [:wam]

Reply

Marsh Posté le 16-01-2004 à 23:12:35    

y'en a, ils ont une eprom à la place du cerveau :D

Reply

Marsh Posté le 16-01-2004 à 23:54:12    

*syl* a écrit :

Comment t'as procédé pour pondre ça ? J'avoue que j'suis un peu sur le cul [:wam]


 
Heuuu en fait j'ai fait une suite ainsi
0  00  000
         001
    01  010
         011
1  10  100
         101
    11  110
         111
 
on voit que le premier chiffre se fait rajouter 0 et 1, qui eux meme se voient rajouter 0 et 1 (tiens je l'avais pas vu comme ca lol).
Et hop le résultat =) (après avoir inversé 2-3 trucs :/ )
 
Edit: Vive les alignements


Message édité par Tentacle le 16-01-2004 à 23:54:58
Reply

Marsh Posté le 16-01-2004 à 23:56:13    

LajioT a écrit :

Ahh, yessss, ça fonctionne !  
Merci beaucoup ! ;)
 
Je te laisse trouver le langage. =)

Code :
  1. class Bits {
  2.     public static String bits(int n, String s) {
  3. return n>0 ? bits(n-1, s + "0" ) + bits(n-1, s + "1" ) : s;
  4.     }
  5.     public static void main(String[] args) {
  6. System.out.println(bits(3, "" ));
  7.     }
  8. }




 
Heuuu ça me rappelle des (mauvais ?) souvenirs ... du java  :??:

Reply

Marsh Posté le 16-01-2004 à 23:57:25    

Bien vu :jap:
 

Citation :

Edit: Vive les alignements

balise fixed
 

Citation :

Heuuu ça me rappelle des (mauvais ?) souvenirs ... du java  :??:

gagné [:austiniste]


Message édité par *syl* le 16-01-2004 à 23:58:36
Reply

Marsh Posté le 16-01-2004 à 23:57:25   

Reply

Marsh Posté le 17-01-2004 à 12:51:08    

*syl* a écrit :

Bien vu :jap:
 

Citation :

Edit: Vive les alignements

balise fixed


 
Haaa merci je m'en rappellerai :jap:  
 

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed