Recherche des nombres chanceux selon stanislaw ulam

Commenter

Contenu du snippet

Programme permettant d'afficher les nombres chanceux selon Stanislaw Ulam (cf http://fr.wikipedia.org/wiki/Nombre_chanceux )

On utilise ici un vector de booléens contenant "true" si le nombre est chanceux, et "false" sinon.
On élimine donc les nombres au fur et à mesure en les mettant à "false", on affiche enfin uniquement les indices du tableau pour lesquels on a "true".

Je n'ai pas grand chose à y ajouter, ce que je pense pouvoir tenter d'expliquer est dans les commentaires !

Source / Exemple : 


#include<iostream>
#include<iomanip>
using namespace std;

//
//Fonction qui renvoie l'indice du prochain élément 
//du tableau qui vaut 'true', càd le prochain entier
//encore actuellement "chanceux" ou 0 s'il n'y a pas
//de prochain nombre inférieur à la limite.
///////////////////////////////////////////////////
int prochainVrai( bool *tab, int n, int taille )
{
	for ( int i=n+1; i<taille; i++)
		if ( tab[i] )
			return i;
	return 0;
}

//
//Recherche et affichage des nombres 
//chanceux inférieurs à "limite"
////////////////////////////////////
void chanceux( int limite )
{
	bool tab[limite+1];
	int pas=1, tmp, cpt;
	
	//traitement de la première étape, on élimine les nombres impairs
	for (int i =0; i<=limite; i++)
		tab[i]=( i%2 != 0 );
	
	//chaque itération de cette boucle représente une étape,
	//on itère donc jusqu'à ce qu'il n'y ait plus
	//de nombres inférieurs à la limite
	while ( (pas=prochainVrai(tab,pas,limite+1)) != 0 )
	{		
		tmp=0;
		cpt=0;
		
		//suppression des nombres correspondant à l'étape en cours
		while ( (tmp=prochainVrai(tab,tmp,limite+1)) != 0)
		{	
			cpt++;	
			
			if (cpt == pas)
			{	
				tab[tmp]=false;
				cpt=0;
			} 
		}
	}
	
	// affichage des nombres chanceux	
	for(int i=1; i<=limite; i++)
		if ( tab[i] )
			cout << setw(7) << i << endl;
}

int main()
{
	int lim= -1;
	
	while ( lim < 0 )
	{	
		cout << "Entrez la limite de recherche des nombres chanceux : ";	
		cin >> lim;
	}
	
	chanceux(lim);
	
	return 0;
}

Conclusion :


Si vous y voyez des améliorations possibles, je suis intéressé :-)

A voir également

S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.