Écrire une réponse @ Prise2Tete

Forum dédié aux énigmes et à toutes formes de jeux de logique.	Déconnexion
Tu n'es pas identifié sur Prise2tete : s'identifier. Accueil Forum	[+]

	Forum » Enigmes Mathématiques » Décomposition en somme d'entiers Écrire une réponse Attention : Aucun indice ou demande d'aide concernant les énigmes de Prise2Tete n'est accepté sur le forum ! Rends-toi sur le cercle des sages si tu as besoin d'aide ! Tout nouveau message ou sujet ne respectant pas cette règle sera supprimé, merci. Rédige ton message Nom Courriel \| \| \| \| Upload \| Aide Message [quote=MthS-MlndN]Alleluyah Wikipedia : [url]http://fr.wikipedia.org/wiki/Partition_d'un_entier[/url] [latex]E_k^n = E_{k-1}^{n-1} + E_k^{n-k}[/latex] Autrement dit : soit on prend une partition de [latex]n-1[/latex] déjà trouvée, on rajoute [latex]+1[/latex] à la fin, et basta (pour trouver toutes les partitions de [latex]n[/latex] dans lesquelles [latex]1[/latex] est présent au moins une fois, ça j'y avais pensé), soit on prend une partition de [latex]n-k[/latex] à [latex]k[/latex] éléments et on ajoute [latex]1[/latex] à chaque nombre (pour obtenir toutes les partitions dont chaque élément vaut au moins 2, et c'est ça que je n'avais pas trouvé :D) Bon. Un tableau de 1000x1000 éléments ajouté au programme. L'integer(8) ne suffit plus (il y a d'énormes dépassements de capacités) alors je suis passé en real : [code] program decompo2 implicit none integer :: n, i real(8) :: decompo_cont2, ndec(1000), ndecdetaille(1000,1000) !!! On traite tous les cas séparément : n peut être décomposé en des sommes de 1 à n/2 éléments, !!! et le plus grand élément d'une somme sera toujours inférieur ou égal à n. ndecdetaille(:,:) = 0. ndec(:) = 0. !!! Chaque nombre a une et une seule partition en 1 entier ndecdetaille(:,1) = 1. ndec(1) = 0. do n=2, 1000 !!! On initialise avec les solutions du type 1+"une solution déjà trouvée" !!! (la seule solution à n entiers en fait partie) do i=2, n ndecdetaille(n,i) = ndecdetaille(n-1,i-1) end do !!! On ajoute les décompositions de n composées uniquement d'entiers !!! supérieurs ou égaux à 2 do i=2,n/2 ndecdetaille(n,i) = ndecdetaille(n,i) + ndecdetaille(n-i,i) end do do i=1,n ndec(n) = ndec(n) + ndecdetaille(n,i) end do print, 'Le nombre ', n, ' peut etre decompose de ', & ndec(n), 'facons différentes.' end do end program[/code] Résultat affiché à la 1000° itération (quasi-instantanément) : [b]Le nombre 1000 peut etre decompose de 2.40614678640326198E+031 facons différentes.[/b] Tu m'étonnes que j'avais un dépassement de capacité :lol: On peut aller plus loin. Résultat obtenu en trois/quatre secondes : [b]Le nombre 10000 peut etre decompose de 3.61672513256361863E+106 facons différentes.[/b] Ca change de la complexité exponentielle du début ! Merci Nicouj pour ce problème (le genre de problèmes que j'adore : de l'algorithmique, des astuces algébriques à fouiller, comment transformer un calcul horrible en une somme à la "triangle de Pascal" en étant astucieux...). Un régal :)[/quote] Options Ne pas convertir les émoticônes sur ce message Sécurité Répondez à la devinette suivante : Le père de toto a trois fils : Pif, Paf et ?* Retour Résumé de la discussion Nicouj 25-10-2010 14:26:19 Le problème est de compter le nombre de décompositions d'un entier en somme d'entiers strictement positifs modulo associativité/commutativité. Par exemple pour le nombre 5 il existe 7 décompositions : 5 4+1 3+2 3+1+1 2+2+1 2+1+1+1 1+1+1+1+1 Combien en existe t-il de décompositions pour les nombres suivants : - 10 (à la main) - 100 (à la machine) - 1000 (à la machine mais en faisant gaffe) ~~Réponse pour 1000~~ : (je viens de m'apercevoir que la boite de réponse tronque la solution car il y a trop de chiffres >< Du coup je laisse la case réponse pour 10 : Pied de page des forums P2T basé sur PunBB Screenshots par Robothumb © Copyright 2002–2005 Rickard Andersson
Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact