Une petite application de la dynamic programming

Soyez le premier à donner votre avis sur cette source.

Snippet vu 7 700 fois - Téléchargée 35 fois

Contenu du snippet

Ceci est un exemple simple de programmation dynamique appliquée au calcul d'une suite de fibonacci du genre Un = Un-1 +Un-2

Source / Exemple :


using System;

namespace fibo_dp
{
	/// <summary>
	/// Summary description for Class1.
	/// </summary>
	class Class1
	{
		public static int[] G=new int[50000];
		public static Int32 CalcFibo(int i)
		{
			switch (i)
			{
				case 1:
				case 0:
				case 2:
					return 1;
				   
				default:
					return CalcFibo(i-1)+CalcFibo(i-2);

				   
			}
		}
		public static Int32 CalcFiboDp(int i)
	    { 
			
			if (G[i]!=0) 
				return G[i];
			else
			{
				G[i]=CalcFiboDp(i-1) + CalcFiboDp(i-2);
				return G[i];
			}

	}
		
		/// <summary>
		/// The main entry point for the application.
		/// </summary>
		[STAThread]
		static void Main(string[] args)
		{
			//
			// TODO: Add code to start application here
			//
			
			for (int n=0;n<50000;n++)
			{
				G[n]=0;
			}
			G[0]=0;G[1]=1;G[2]=1;
            if (args.Length==0)
			{
				Console.WriteLine("Give me number");
				return;
			}
			if (args.Length==1)
				Console.WriteLine( CalcFibo((Convert.ToInt16(args[0]))));
			else
				if (args.Length==2)
			{
				Console.WriteLine(CalcFiboDp(Convert.ToInt16(args[0])));
			}

		}
	}
}

A voir également

Ajouter un commentaire

Commentaires

Messages postés
1221
Date d'inscription
jeudi 23 août 2001
Statut
Membre
Dernière intervention
9 septembre 2018

Ok, tu as raison. Du reste, le terme de programmation dynamique est assez général, il aurait fallut que les auteurs de cette théorie trouve plutot un adjectif pour indiquer un certain type de récursivité efficace, mais c'est vrai que tu n'y es pour rien :-)
Messages postés
34
Date d'inscription
vendredi 22 mars 2002
Statut
Membre
Dernière intervention
2 mai 2006

en fait ce dont tu parles si je comprends bien c de la compilation dynamique de code ,une technique de c# et d'autres compilateurs qui te permet d'ecrire du code a posteriori. Un exemple simple d'une fonction de calcul dont tu fournis le corps mais pas le contenu. Contenu que tu peux fournir après et le faire executer.Ce genre de chose se fait avec le namespace Microsoft.CsharpCompiler je crois bien.
Messages postés
34
Date d'inscription
vendredi 22 mars 2002
Statut
Membre
Dernière intervention
2 mai 2006

eh bien mon petit père je crois que tu n'as pas assez revisé les cours maths.En effet la dp s'apparente un peu a la recursitité :-) mais c pas tout a fait la meme chose parceque en dp par souci d'optimisation on evite de calculer les resultats intermediaires pour plus de rapidité. Voici un link http://docs.happycoders.org/orgadoc/computer_science_theory/dynamic_programming/prog-dynamique.pdf

ou tu pourras avoir quelques petites explanations sur la dp.
Salut
Messages postés
1221
Date d'inscription
jeudi 23 août 2001
Statut
Membre
Dernière intervention
9 septembre 2018

Hum, tu confonds avec la récursivité ! pour moi la prog. dyn., c'est la capacité à compiler du code pendant l'execution, mais bon...

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.