É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 » A vous de payer - suite (3/7) É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=scarta]Voici, non pas le programme lui-même, mais les détails de l'algorithme utilisé. Pour réaliser un programme qui va trouver les solutions, l'idée est simple: - on construit une fonction F:N->N qui à un entier N représentant le cardinal d'un ensemble fait correspondre une valeur M qui est la somme minimale nécéssaire pour trouver un nombre dans cet ensemble - cette fonction est construite valeur par valeur. La première valeur est bien entendu F(1) = 0; car pour un nombre unique, il ne faut poser aucune question pour le trouver :) - pour un nombre N quelconque, et en supposant que toutes les valeurs de F inférieures à N ont déjà été calculées, on calcule le F(N) comme étant le minimum de l'expression MAX(F(A)+7, F(N-A)+3); A étant un entier compris entre 1 et N-1 Cependant, deux problèmes se posent: la gestion de la mémoire et le temps de calcul. [b]Gestion de la mémoire[/b] Pour représenter cette fonction F, la manière la plus naturelle serait d'utiliser un tableau, noté valeurs[]. on aurait alors valeurs[N] = F(N+1) (les indices d'unt tableau de taille T sont compris entre 0 et T-1) Le problème, c'est que 10^16 c'est beaucoup. Un tableau d'entiers (32 bits) à 10^16 entrées ferait une taille d'environ 37252903 Go (ça fait beaucoup de RAM) On peut cependant contourner ce problème facilement: en effet, on remarque que les valeurs changent assez peu souvent. Du coup, on utilise 2 tableaux notés clefs[] et valeurs[]. i étant un entier, on note Clefs(i) le plus petit entier pour lequel il faudrait au minimum Valeurs(i) euros. Autrement dit, F(Clefs(i)) = Valeurs(i). Avec cette implémentation, on peut calculer F(N) de la manière suivante: fonction F(entier N) renvoyant un entier: boucle pour i allant du dernier indice de Clefs jusqu'à 0 en décroissant si Clefs(i) <= N; renvoyer Valeurs(i) fin de la boucle renvoyer 0 (au cas où) fin de fonction Explications: Tous les nombres compris entre Clefs(i) (inclu) et Clefs[i+1] (exclu) ont pour image par F Valeurs(i); on par donc de la dernière clef et on remonte jusqu'à la première clef inférieure à N (la clef suivante est donc nécessairement supérieure à N); et on renvoie la valeur associée. [b]Gestion du temps de calcul[/b] Pour calculer F de cette manière, supposons qu'un millionième de seconde suffise pour trouver une valeur de N, il nous faudrait l'équivalent de 317 années de calcul. De plus, plus N est grand, plus le minimum est à calculer sur un nombre important de valeurs (et donc plus le temps nécessaire pour trouver F(N) est grand aussi). Voyons quelles optimisations on peut apporter au système. On remarque tout d'abord que F est croissante (résultat trivial étant donné que s'il faut X euros pour un ensemble de cardinal N, il faut aussi au moins X euros pour un ensemble de cardinal plus grand que N). [u][i]Optimisation n°1[/i][/u] Lorsqu'on calcule le minimum; on calcule en général toutes les valeurs une par une et on stocke la plus petite qu'on ait vu. Dans notre cas, si une de ces valeurs vaut F(N-1) alors inutile d'aller plus loin. En effet, on ne peut pas trouver moins car F est croissante. [u][i]Optimisation n°2[/i][/u] Au lieu de faire croître A entre 1 et N-1 on va le faire décroître de N. Ca ne change pas grand chose en théorie... Sauf que pour plusieurs (beaucoup) valeurs consécutives de A, on a un F(A) constant (cf. la gestion de mémoire) Du coup, si j'ai déjà calculé la valeur MAX(F(A+1)+3, F(N-A-1)+7) et que F(A) = F(A+1) il est inutile de calculer MAX(F(A)+3, F(N-A)+7) En effet, F est croissante donc F(N-A-1) <= F(N-A); du coup le MAX calculé en A sera soit égal, soit supérieur à celui calculé en A+1. Comme on cherche le plus petit des maximums, inutile de calculer ceux dont on sait à l'avance qu'ils seront plus grands. Comme on stocke dans Clefs[] les valeurs de N où F(N) change, il suffit de prendre les valeurs Clefs(i)-1, qui est la plus grande valeur telle à image par F constante. Autrement dit, on ne va pas calculer notre minimum sur toutes les valeurs de A, uniquement sur celles telles que F(A) < F(A+1), c'est à dire les plus grandes valeurs pour une même image. Seulement voilà, ces deux optimisations sont bien jolies mais elles ne font qu'accélerer le calcul de F(N): on est toujours obligé de faire le calcul 10^16 fois pour l'instant. Il faudrait donner un coup de boost au calcul, et déterminer que F(N+1) = F(N) en avance de phase quand c'est possible. Pour celà, on va s'inspirer de l'optimisation 2 [u][i]Optimisation n°3[/i][/u] Quand j'ai fini de calculer F(N), j'ai trouvé un A tel que: - MAX(F(A)+3;F(N-A)+7) est minimal - F(A) < F(A+1), cf. l'optimisation n°2 Pour N+1, on est en droit de se demander si la même valeur de A donnerait directement le même résultat. Et la réponse est: pas toujours ^^ Ceci dit, si jamais F(N+1-A) = F(N-A), alors la réponse est oui. En effet, on a alors MAX(F(A)+3; F(N-A)+7) = MAX(F(A)+3; F(N+1-A)+7). Comme le premier est minimal dans le cas N; le second aussi dans le cas N+1 (F est croissante, on ne pourra pas trouver moins). Du coup, une fois que j'ai calculé F(N) pour un minimum obtenu avec une valeur A, je peux passer toutes les valeurs de N jusqu'à N' tel que f(N'-A) > f(N-A). On va donc chercher la première clef K supérieure à N-A et reprendre à N=K+A. On saute ainsi de nombreuses valeurs de N pour lesquelles F(N) est constante. Attention, ça ne signifie pas que la valeur calculée suivante sera différente, elle pourra être identique pour une autre valeur de A. Quoi qu'il en soit, même après avoir calculé cette nouvelle image de F on réappliquera cette optimisation. Avec ces trois modifications, le programme calcule toutes les valeurs où l'image par F change, sur tous les entiers de 64 bits (inférieurs à 2^64 = 1,8E19) en moins d'une seconde.[/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 : Pim, Pam et ? Retour Résumé de la discussion dhrm77 02-11-2011 18:08:38 Comme cette énigme est apparement trop simple pour certains, je vous propose une petite complication: 2 mathematiciens (A et B) jouent au probleme suivant: A choisit mentalement un nombre X dans l'ensembre {1,....,10000000000000000}. B qui cherche à découvrir X, peut choisir un sous-ensemble E de {1,....,10000000000000000} et demander si X appartient à E ou non. - Si la réponse de A est Oui, B doit payer 7 euros. - Si la réponse de A est Non, B doit payer 3 euros. Quel est la somme minimale nécessaire que B doit posséder au départ pour être assuré de trouver X ? Et bien sur, quelles sont donc les étapes? Edit: Pour ceux qui n'ont pas les moyens d'aller jusqu'a 10^16, donnez la solution pour un ensemble de depart de 2277444446 nombres. Pour les étapes, il suffit d'expliquer un peu et de donner quelques nombres clef, pour que je vois si vous avez la bonne réponse. 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