Discussion :

[simpatico]

bonjour tout le monde.
je voudrais générer tous les nombres codés sur n bits avec une fonction recursive. si quelqu'un a une idée n'hesitez pas à me donner un coup de main.
NB: il se peut résouder ce probleme en utilisant n boucles for mais la complexité augmente. je cherche une solution optimale avec une fonction récursive.
merci d'avance de votre aide.

[fregolo52]

tu fais une fonction avec 2 int en paramètre.
le 1er est le nombre, le 2e est la position du bit.

PS : quoi que ... je n'ai peut-être rien compris au problème.

[bpy1401]

bonjour simpatico

je voudrais générer tous les nombres codés sur n bits avec une fonction recursive

je ne vois pas en quoi la récursivité va nous aider la dedans. juste une boucle for ferait l'affaire.

[Climoo]

Perso avec des boucles, je vois pas bien comment faire (mais peut être n'ai-je pas bien tout compris non plus).
Pour ce qui est de la complexité, c'est forcément exponentiel je pense, car la taille de la sortie est exponentielle.
Par exemple, les entiers codés sur 4 bits, il y en 2^4.
Donc nécessairement...

Voilà un pseudo code qui pourra te mettre sur la voie...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
Fonction nbits(entier n) 
	Si (n = 1) 
		renvoyer {'1', '0'}
	Sinon
                resultatmoins1 = nbits( n - 1)
                resultat = {}
                Pour chaque nombre m dans resultatsmoins1
                      resultat = resultat U { concat('0', m) }
                      resultat = resultat U { concat('1', m) }
	        Fpour
                renvoyer resultat
	Fsi
FinFonction

Le U, c'est pour l'union...
Théoriquement, ça marche... Cela dit, le résultat sera pas trié (t'auras pas les nombres du plus petit au plus grand).

[matafan]

Avec une boule :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
for (i = 0; i < (1 << n); i++) {
        /* ... */
}

Dans cette boucle i prend successivement toutes les valeurs qu'on peut représenter sur n bits

[Obsidian]

Dans cette boucle i prend successivement toutes les valeurs qu'on peut représenter sur n bits

Tu peux enlever le mouarf, je pense. Ce sont effectivement la définition la plus exacte et la meilleure approche à donner.

[Climoo]

Héhé, je n'y avais pas pensé. C'était pourtant si simple
Le posteur aura néanmoins le plaisir de découvrir une fonction récursive pas efficace