É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 » Arithmétique et informatique 2 É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=rivas]Salut scarta, Merci pour cette série. 1) La chose à plus rapide à éliminer ce sont les nombres pairs (sauf 2). Ce "sauf 2" m'ennuie: cela veut dire qu'il faut faire un test supplémentaire. Mais bon on élimine tout de même la moitié des cas. Pour tester les nombres pairs il suffit de tester le bit de poids faible du nombre. J'écrirais quelque chose du genre: [code]if ((n & 1) == 0 && n != 2) return;[/code] Ce qui veut dire: si n est pair mais ne vaut pas 2 on ne continue pas l'évaluation. Il vaut mieux tester la parité en premier plutôt que l'égalité à 2, celle-ci ayant la plus forte probabilité. 2.1) On utiliser le résultat sur la congruence modulo 4 des carrés. Un carré ne peut être congru qu'à 0 ou 1 modulo 4 (0->0, 1->1, 2->0, 3->1, n+4->n). Si on considère donc les 2 derniers bits, il ne peuvent être que 00 ou 01. Le bit 1 vaut toujours 0. Il suffit donc de rajouter un test comme celui-ci au début pour éliminer la moitié des cas (nombres congrus à 2 ou 3 modulo 4): [code]if ((n & 2) != 0) return;[/code] (Le != 0 est facultatif mais c'est une bonne pratique de l'écrire) 2.2) Regardons les carrés modulo 8: 0, 1, 4, 1, 0, 1, 4, 1 Le test précédent a permis d'éliminer les congruences à 2, 3, 6 et 7 modulo 8 . On voit qu'un carré n'est jamais congru à 5 modulo 8. On peut donc aussi éliminer ces cas: [code]if ((n & 7) == 5) return;[/code] Est-ce à ça que tu pensais? 3) On se base sur l'écriture en base 2 (naturelle pour l'ordinateur) du multiplicateur. On écrit: [latex]m=\sum{a_k2^k}[/latex] donc [latex]m.n=\sum{a_k(n.2^k)}[/latex] Chaque ak est un chiffre en base 2 donc 0 ou 1. On procède par "accumulation". On part de n. Si a0 vaut 1, on ajoute n à l'accumulation. On mutiplie n par 2 et on regarde a1 cette fois. Si a1 vaut 1 on ajoute 2n à l'accumulation et on multiplie n par 2 et on continue jusqu'à avoir épuisé les ak. On a donc calculé exactement: [latex]\sum{a_k(n.2^k)}[/latex] c'est-à-dire m.n. La multiplication par 2 à chaque étape se fait par décalage à gauche d'un bit (opération élémentaire). On choisit le plus grand nombre pour faire l'accumulation et on teste les bits du plus petit, cela permet de réduire encore le nombre de passes dans la boucle. Ici on a décomposé m, la complexité maximale est donc de l'ordre de log2(m) additions et décalages. Il faut faire attention à éviter le "débordement", c'est-à-dire un résultat trop grand pour être stocké dans un entier "informatique". Voici un petit exemple de comment le faire. Pour des raisons de simplicité, je ne gère ni les signes, ni le débordement mais ce n'est pas difficile. [code]int mult(int m, int n) { int r; if (m > n) // On échange m et n si nécessaire pour travailler sur le plus petit { int tmp; tmp=m; m=n; n = tmp; } r = 0; // On met l'accumulateur à 0 while (m != 0) { if (m & 1) // Si le bit en cours d'analyse est non nul on ajoute n.2^k à l'accumulateur r += n; m >> =1; // On regarde le bit suivant de m (en fait décale m à chaque tour et on regarde toujours le bit 0) n <<= 1; // On multiple n.2^k par 2 pour passer a n.2^(k+1) } return r; }[/code] 4) On utilise la aussi la décomposition en base 2. Mais cette fois-ci du quotient avant de le connaître. :) On peut aussi dire que l'on fait exactement comme lorsque l'on pose la division de façon habituelle mais on le fait en base 2, pas 10 (ce qui oblige à bien comprendre ce que l'on fait quand on pose une division :)). En fait on multiplie n par 2 jusqu'à ce que ça ne soit plus possible (jusqu'à ce que le multiple suivant soit plus grand que m). C'était la phase d'initialisation. A partir de là on entre dans un boucle: Si on peut soustraire n.2^k à m (n.2^k est <= m), on le fait, on obtient une nouvelle valeur de m et on écrit un chiffre 1 au quotient, sinon on écrit un chiffre 0 au quotient. Dans les 2 cas, si k n'était pas déjà revenu à 0, on divise n.2^k par 2 (décalage à droite), on diminue k (pour savoir lorsqu'on doit arrêter, on peut aussi ne pas avoir besoin de k en tester n.2^k jusqu'à ce qu'il vaille le n initial) J'ecrirai l'algo en C un peu plus tard, je dois partir...[/quote] Options Ne pas convertir les émoticônes sur ce message Sécurité Répondez (numériquement) à la petite énigme suivante : Un berger a 40 moutons, ils meurent tous sauf 18, combien en reste-t-il ? Retour Résumé de la discussion scarta 12-11-2010 12:41:03 Toujours sur le même thème, voici quelques questions un peu différentes. Petite définition pour ceux qui ne connaissent pas tout ça: une fonction informatique est une liste d'instructions qui prend un ou plusieurs paramètres en entrée, et renvoie un résultat. Un peu comme en math: f(a,b,c,d)=e 1) Je souhaite écrire une fonction informatique pour savoir si un nombre est premier. Quelle instruction rapide pourrais-je écrire au début de ma fonction pour pouvoir traiter la moitié des cas très rapidement ? 2.1) Je souhaite écrire une fonction informatique pour savoir si un nombre est un carré parfait. Quelle instruction rapide pourrais-je écrire au début de ma fonction pour pouvoir traiter la moitié des cas très rapidement ? 2.2) Quelle autre instruction me permettrait d'éliminer encore plus de cas après la précédente ? 3) Je peux faire des boucles (répéter une série d'instructions plusieurs fois). Je n'ai pas le droit de faire de multiplication, comment calculer m*n ? 4) Pareil, je souhaite faire m/n (division euclidienne). 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