{"id":2381,"date":"2020-05-07T11:43:59","date_gmt":"2020-05-07T09:43:59","guid":{"rendered":"https:\/\/www.mathweb.fr\/euclide\/?page_id=2381"},"modified":"2023-04-16T16:18:17","modified_gmt":"2023-04-16T14:18:17","slug":"python-diviser-pour-regner","status":"publish","type":"page","link":"https:\/\/www.mathweb.fr\/euclide\/python-diviser-pour-regner\/","title":{"rendered":"Diviser pour r\u00e9gner en Python"},"content":{"rendered":"\n

La m\u00e9thode du \u00ab\u00a0Diviser pour r\u00e9gner\u00a0\u00bb est un paradigme de programmation imagin\u00e9 pour am\u00e9liorer la complexit\u00e9 d’un programme. Regardons ce que cela donne en Python.<\/p>\n\n\n\n

\"Diviser
Diviser pour r\u00e9gner en Python<\/figcaption><\/figure><\/div>\n\n\n\n
\nhttps:\/\/www.mathweb.fr\/euclide\/produit\/python-en-mathematiques-au-lycee\/\n<\/div><\/figure>\n\n\n\n

Le principe du \u00ab\u00a0diviser pour r\u00e9gner\u00a0\u00bb en Python<\/h2>\n\n\n\n

On souhaite calculer \\(N=7^{52}\\). La m\u00e9thode basique consiste \u00e0 multiplier le nombre 7 par lui-m\u00eame 52 fois… Ce qui n’est pas tr\u00e8s rapide !<\/p>\n\n\n\n

L’id\u00e9e consiste donc \u00e0 diviser le probl\u00e8me en 2 : on va calculer \\( 7^{26} \\times 7^{26}\\), c’est-\u00e0-dire \\((7^{26})^2\\). L\u00e0, il n’y a plus que 26 + 1 op\u00e9rations (26 multiplications pour calculer \\(7^{26}\\), et une derni\u00e8re pour faire le carr\u00e9 du r\u00e9sultat.<\/p>\n\n\n\n

On recommence ensuite avec \\(7^{26}\\) : on le calcule en faisant \\( (7^{13})^2 \\). \\(N\\) se calcule alors en 13+1+1 op\u00e9rations au lieu de 52 initialement.<\/p>\n\n\n\n

On ne s’arr\u00eate pas l\u00e0, bien entendu : on continue tant que l’on peut utiliser ce principe :$$\\begin{align}N & = 7^{52}\\\\&= (7^{26})^2\\\\&= \\big((7^{13})^2\\big)^2\\\\&=\\big[[(7^6)^2\\times7]^2\\big]^2\\\\&=\\big[[\\big((7^3)^2\\big)^2\\times7]^2\\big]^2\\\\&=\\big[[\\big((7^2\\times7)^2\\big)^2\\times7]^2\\big]^2 \\end{align}$$<\/p>\n\n\n\n

Le principe est, vous l’avez peut-\u00eatre remarqu\u00e9, r\u00e9cursif.<\/p>\n\n\n\n

Impl\u00e9mentation en Python du \u00ab\u00a0diviser pour r\u00e9gner\u00a0\u00bb<\/h2>\n\n\n\n

Nous allons \u00e9crire une fonction \u00ab\u00a0puissance(x,n)\u00a0\u00bb bas\u00e9e sur ce paradigme, o\u00f9 x<\/em> et n<\/em> sont deux entiers (positif pour n<\/em>). Pour cela, nous allons prendre en compte que:$$\\begin{cases}x^0 = 0& \\\\x^n = (x^2)^{n\/2} & \\text{ si }n\\text{ est pair}\\\\x^n = x(x^2)^{(n-1)\/2} & \\text{ si }n\\text{ est impair} \\end{cases}$$Cela donne alors la fonction suivante (exponentiation rapide):<\/p>\n\n\n\n

def puissance(x,n):\n    if n == 0:\n        return 1\n    elif n%2 == 0:\n        return puissance(x*x , n\/2)\n    else:\n        return x * puissance(x*x , (n-1)\/2)\n    \n\nprint(puissance(2,9))<\/pre>\n\n\n\n
Complexit\u00e9<\/h2>\n\n\n\n
Notons \\(C(n)\\) la complexit\u00e9 de la fonction \u00ab\u00a0puissance(n)\u00a0\u00bb.  Comme nous divisons en deux le probl\u00e8me \u00e0 chaque appel de la fonction, on peut estimer que : $$C(n) = a C(n\/2) + f(n)$$o\u00f9 \\(f(n)\\) est la complexit\u00e9 totale due au partage et \u00e0 la recombinaison, et o\u00f9:<\/p>\n\n\n\n