{"cells": [{"cell_type": "markdown", "metadata": {}, "source": ["# 1A.1 - Variables, boucles, tests (correction)\n", "\n", "Boucles, tests, correction."]}, {"cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [{"data": {"text/html": ["Plan\n", "
run previous cell, wait for 2 seconds
\n", ""], "text/plain": [""]}, "execution_count": 2, "metadata": {}, "output_type": "execute_result"}], "source": ["from jyquickhelper import add_notebook_menu\n", "add_notebook_menu()"]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Partie 3 : boucles (exercice)"]}, {"cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["4\n", "1\n", "3\n", "2\n"]}], "source": ["l = [ 4, 3, 0, 2, 1 ]\n", "i = 0\n", "while l[i] != 0 :\n", " i = l[i]\n", " print (i) # que vaut l[i] \u00e0 la fin ?"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Cet exercice montre une fa\u00e7on curieuse de se d\u00e9placer dans un tableau puisqu'on commence \u00e0 la premi\u00e8re position puis on va la position indiqu\u00e9 par le premier \u00e9l\u00e9ment du tableau et ainsi de suite. On s'arr\u00eate quand on tombe sur la valeur z\u00e9ro."]}, {"cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [{"data": {"image/png": "iVBORw0KGgoAAAANSUhEUgAAAeoAAAEPCAIAAAAChhBcAAAAAXNSR0IArs4c6QAAAARnQU1BAACx\njwv8YQUAAAAJcEhZcwAADsMAAA7DAcdvqGQAACqLSURBVHhe7Z39bxTZnt7zr2V1syutskp0V/kh\nm+xklBESIiJLiAi6CAmJsEJIDAlZhIIYHLNmfY0MeAEHC8fBMjIwIONl8NLTfqFpu/3+7sYvuMcw\neTyn7jdnTneVq7uqq+pUPR89P4C7+u2pU8/5nlOnqv/Jz4QQQiyE8U0IIVbC+CaEECthfBNCiJUw\nvgkhxEoY34QQYiWMb0IIsRLGNyGEWAnjmxBCrITxTQghVsL4JoQQK2F8E0KIlTC+CSHEShjfhBBi\nJYxvQgixEsY3IYRYCeObEEKshPFNCCFWwvgmTWGxXIFm1j7lZjehoWJ5YHQNevBm6e7rRejawAx0\n5UnpXHdR16l77491jNXUoZv5f3P9naEjt0ZlgxOdE/pL4cXVu0Atg7PqfbvfLuNjjExvFpd38Amd\nj0uIhTC+iV8kjlUWqyCWCFax+3VLzojX5OtwW17lPr5I67M5fKn+/Bq+I74pvvJO5bPz/QlJGIxv\nss/W7p6KZpXLbS/mbA/lEIWvf/LOxKXeqfbv5/tyq6jc17d/cowjJD4Y31nBLaCZzo3pm9Yf0bdd\n7it1vFpAtT6+sF3e2XO8JiQSGN9po7L3pbT6aXiy3DOygoxGzYjKEVljpA/VDB26mT/dVUC/2Dm0\n8HxiAzvC2SuENAHGt8WsbFbyc1uophEWV/unzz78cOTWqBEoVLxCx3nmfqH12Rwq9OLyzt7nL87O\nIyQwjG872Nrdw/AcSd3+/TwK6hOdE5zxsFFf3ciduvf++tOZ3ncr6Hp5XpQEgfGdRFBW/1D62DOy\ngqrtXHeRNXWKdfLOxOW+Uvfb5ZHpTXTSTgsgxAeM7/iZ39h9Wdh48GbpypPS6a5COuapD7fl1Vrs\nsw8/oAc6/6io1l+3vdhfmQf15VYxmIByvywMFxWWttWa8WrVTDd0dbJBcXlHfyn1+krIR/W+qHwx\nfMGnSuY5W9TmsGioWGaUkwNhfEdNZe8LUqY/v4ajFCFS81KUZAr9CiIPHQzi+Gr/NHIQaaiughme\n3F8ljX7IuhV12B3I/fzcllrMjm+EEY9ak3P89jg6IcOEKHXmfqHj1QLGYZxjITVhfDcdlFGItp6R\nFUQeaquvbiR0zvrIrVF8vAs9k6iRVXWsLl1BKKPCdb5MJsHXH5nehCHqxMPJO1GfeECbQZRjp2B3\noL9xPhbJPIzv8EGthKO9a3gJhzrKVeNQjFE1A3p8YX+ywvnoxDdxZTreBSMD7D7sOK5jyTiM73DA\nwfx8YqPtxVwS6uuj7WM4wlVGD46v5+e2Ml4+R4Zk+vWnMxG0hG9af0TP0Z9f4xVD2YTx3TjF5R0c\nqFf7p+MqsQ+35TGmvvJk/8I/fBIEx/zGLiuy5IB9oc5ztD6bO91VaF55jn4CHXbPyAr76UzB+K6D\nyt6X3Oz+rMiFnsnoTzme6Jy4+Hj/thsDo/uXaHNlgnUgzUurnzAeUmetm7TECFU/migv+MwCjO+D\nKSxtP3izH9mRnbDCG+EgRFl99/Xiy8IGKjiesEolCFnsX3TJ5x8VQ0/z47fH8cr5uS3nzUjqYHzX\nZmbtU19u9VLvVARVNka+COur/dPdb5eHJ8vzG7vOhyBZArU5BlWqUAg3yo/cGr3+dGZkmqtW0gbj\n+/+zvv3TwOjatYGZo+3NncvGwSn3wUBpz4OKGCDKc7ObGHud6y6GOOZDw0Pzxis7b0Msh/G9fway\nc2jhROeE0dZD1OG2vJq2xkiZk5KkLtQZFzRRdPlhLWU51jHWNbzE85y2k934zs9ttb2Ya1Khfehm\nHkNgHCHDk2Xe2p+ExU7l8w+ljx2v9qPcaHKN6fyj4uD4Osd/lpKt+EYzHZnevP50phkXQx+/PY6R\naV9uFeW8836ENA3Uzv35NeRv8NmVb1p/xEExvrDtvDSxhEzEN1J7qFi+2j8d7hkhjGRRBKkbDLHE\nJnGBkhwV9JUnpeDN+0TnxIM3nFSxhpTHd35uC2VFiKmNyD778EPX8BLvPkGSBhrk8GQ5+OASjfxC\nz+TziQ228ISTzvheLFfuvl4M8WLIk3cmUGXz3m/EFtSpneO3x42WXJeO3BpFpcIr8hNLquJ77/OX\nl4UNFA5GK2xMSP9rAzOoQTgxQuyluLyDUgb1h9G8/evrllzL4CxXTCWQlMQ3yu2OVwvBf5Xm0M38\n5b5SX251Zo2NlaSKwtJ267O5IPMqKIwwAHVejiQA6+M7N7t5qXcq4HrYo+1j6rI01O/O6xKSRip7\n+yPUi48bP2RQyPfn1zgtngRsjW+0nsHx9VP33httqy7xphAks6xv/9T9drnhSRWMdDuHFjivGC/2\nxTeCu2dkJcg8CUIfLY+rswkBQSZVvm7JXRuY4aEUFzbFd8DgRqHRNbzEG0IRUk3ASZVLvVMM8eix\nI773Pn8ZGF1rLLhRVrS9mEOJ4bwWIcSd9e2fHrxZauxYQyXO8ihKLIjvkenNBua4May78qQ0PFnm\n2UhC6gVHTWPnllC8tz6b45x4NCQ6vss7exiUGe3jQJ3onOh+u8xrDQgJjlrZZRxiBwrF093Xi/xB\nqGaT3Ph+Wdio63QKun20M97LmJDQmd/YRU1d772xDt3Mo5DiEsPmkcT4Rqd9ua9kNAUPfdP6Y9uL\nOU66EdJUcGB2Ddc9LY7tB0bXOIfZDBIX3+ML2/7vVYLunWM0QqIE1TTiuN5p8eO3xzGedl6ChESy\n4vvBmyWf65YY3ITEy8j05rnuonFgeuvsww+8HUWIJCW+MbZqGZw1dnZNId+xJc9MEpIE6l0YhuO3\nc2iBE+KhkIj4Rnb7nOy++HiKvTchSeNlYaOum9NiY+S+82TSKPHHt8/sPtYxxlUlhCQWHMj1Xlt3\ntX+aw+ggxB/fHa8WjJ1ardZnc/ydBEKSj7qzxaGbfpf8Ysv+/JrzZFInMcc3umtjdxo63JbnLYYJ\nsYut3b27rxf9/0ghT2k2RpzxvbJZ8d7B2Kn81VRCLGV9+6e2F34v9uEpzQaIM74vPva6GPdyX4lL\n/QmxHZTVqMOMo9tNx2+P8/77/oktvocny8ae09UyOMvsJiQ19OfXfE6IqzKch78fYotvjx8UxkPc\neYSkjPLO3tX+aeNgd9OZ+4XFMidODyCe+F7ZrLhdXYnRExeZEJJWcrObJzp9/ULbN60/Do6vO08j\ntYgnvnvfrRi7SsTF3YSkm8rel7uvF32e0kTBznrOjXji+/rTGWMnKV3uKzlbEEJSzczap/OPfN0y\n5eSdCd5PtCbxxLfbbuM9yQjJFIPj635u63/oJq//qEE88e12ewT+IiUhWWNls+KzDL/7etF5DvmF\neOLb7dwFh0iEZJPut8tuyxl0Xeqd4lS4EE98u90mmOctCcksxeUdP4tSTncV+FPICsY3ISQpoLJu\nfTZnxEK1jnWM8R4pIJ74dlu9z1OXhJDnExsH3u4KG7Daiye+rw3UXjg4MMpbRxJCfi6tfjrw9x++\nupHLeMEXT3y3fz9v7Akl3vmXEKLYqXy+1Ot1Vzso4wkeT3zffb1o7AYlLgwihOgc+HMuWU7weOL7\nwZslYx8oMb6JXVT2vhSXdxAfaNLXn86c6y6e7ioc6xg72j6mmjT+gf/ij3ioZXC2++3y8GSZp93q\noi+36r2mMLMJHk98u/3IztX+aWcL8vPP8xu7udnNH0ofYVfvuxX0bW0v5q4NzFx8PIUsgE7emUA0\nKOl34/y6JSd/P357XG18/lERz8Ur4HX682uD4+t4cUQP12A1APK3Z2TlQs+k/x+UMYT9deVJCTuC\nP0jiB/R53lZnM8HjiW+3m32fuV9wtsgSO5XPpdVPQ8UySrPWZ3MIBWSud7kRrnBgnLr3/lLvVPv3\n86h0RqY3mSnVlHf2nk9soAuUyjosneicgPPop/lbMx4Ulra9fwcZh0zWLqyPJ75RvBjWKx1uyztb\npBSUuuML26h8UQJjqIHuqq5f5o5SOBgQK6j0UbCj9seBgb2Wwfuw4ysjtbGnDH+aIQybYDjXw7mB\nqsL7uh4UIji+nK0zQDzxjUPC8F20tbvnbJQKUFYjrFFbnX9U9PlrIwkXjh9UoCjSi8s7zpdMKSi3\nu4aXYulfMRjCaMz5HEQDBZB3gmN/ZefUQjzxDdJ61yo0LxRrqFjPPvzQ8MSoLUKHdKFnEiOJkenN\nNN2JAj3T9aczPm9I3TydvDMxMLrGX54yODDBkS0ZOaMTW3y7/Vgass/Zwh5UZLcMznq3qnp1tH3s\nXHfxypMSqt3OoQVUgjiY8UbqlONiuSKqnqrGR9I3wCAAz3pZ2MArIG0xGsBrYhec7ir4uV2nH311\nI3fmfqHj1cIPpY/2RvnwZNnn3e8iE8Ko990Kp8V1DkxwHDhZ6PZii2+3OxsgpJwtkg0OJ5Sc+BbB\nI1tmmfFqPSMramFZlIfr1u4eBj3oGGC+mpEPmOkS5bDIlqOovLN3ua9kfBE/QpGOjhDjLdl36C+l\n+lP9qJyaRlGPYVkDdT36cry4ek0CYKz3vBZqFGfT9BJbfKOtG3YrJXztIOrc/vzapd6pxiZGcNye\nuvceMYFoS/gaD8l0taIZodPYLDB6AlT6CK8k148YlNR7ZgL7UfVPDXwvPAVjFCR+vX0/Ovg0TVIF\nBD2l92Fo41C+LmKLb7e1gzgqnC2SxPzG7t3Xi6e76l5+gLzGs3DUIfSLyzu2D+hQoiKIEVsYnNbb\ngWF79M2D4+uJCiCUxm7zeNVSXRG+ghTXwcEHQNtAj+6zJD/WMcalKUJ+bsvDNzQ5jHucTdNIbPGN\nntPwWpScwxtphRoZhafxCb2FHgiFFQ7yFOS1B/hq+IK971YQynVVkTjerjwpofyM1xy8Oz68z07o\n5J0JtISmDiDQJXQOLfgcBLR/P5/k0UyUvCxsfOV+kQSKJ2e7NBJbfAO3lhr72nsc2KgxL/VO+SyI\nIBXZeFbKFj76B+mjzt+6rSmq1tH2MRTysdRH6Jh9LuW++HgqygaJ9vPgja/ViugyM7XG2QN0e4Y5\nunBUOtv9GhQfI9N2j2PijG+324nhkHa2iBxk0N3Xiz4nedH9qNmAzEa2G4vlysDo/hkCn/0fSqRm\n17Y66J4PHFHhk7c+m4trBTGs6BlZOdZxwOWdqDqzea8PA+xQjxkwowAvLG0j7lWRgZ7S+audxBnf\n8E53WXSuu+hsESEoZDCi9xiFibDjMXTNzVqzpiJGEEOofdDJ+ZkTONyWx3EV4rSyG/g8xlsbQsWd\nhFPKaGDdb5e9u0C02H7eZvmX4ZRHb4ejNT+3hfGxccMDt8LcFuKMbySmbqUI7TXKQgx14ql7743P\nUC2MVbuGl/hjyo0BnzFQvf505sCRDfb+tYEZDGydZzYECn8crs5/fg12ovGOutCFJG25AkYAB7ZP\nlOrO1hkGbcatq3Mry2w/sRlnfOOQdrPb7dgLERXcB07UIm7QaQdMEyLA9uHJ/fMKBw50sE3DtqtX\nwDDOmLZGNMvrVwtVOYo4Z9MkAdPuvl70dowJDtDxG7Z4y/bTv3HGN8ABZhiqhDGjs0UT8BPc6Feu\nPClZdNWJdSAokTgH1pWI1AZGPPor4C0wRsZ+xGjPrVxAJ538i2IKS9veK3w6h2I7aZQEsIv7cquG\nJx461jHmPNNaYo5vt1PG5x81a/ob5Zj3GaGj7WMYX0cwA0sUSCVktEdpiYeuP52pa49U72L01m7z\nNt+0/ojP4Dwz2aBabBmcNT6/LowUnU0zA1JbzcvVe6nwhZ5J5yWsJeb4RpganirhiA19GLtYrrit\ndVHCUOBlYYPldiwgnTteea16RuGMMZnPvXPgmg1d1i3e8F4n19SRa3JAT9ZYaotan1nf1cUc39gH\nbtdNhHg+He+Cgtpt4AwFmWYlIYI91ftuxeP05umugp895T++0TCc51iF2z0nIJQ+ti9n9gM68sbu\nUSNKwdmCmOMbuK3iamD+BAe/8y8NlHUn77jOGDK4Ewj2Iw4ttxBHPB14zaHP+D7aPmbvLJlHgqMg\nxVjT2S69BEzw2C8PDE788T1UrH3zk3rnT7Z29050Thi3g8DB6Xa2B90DgzvJYIfefb3oNp2C3eqx\n+/xX3xiTtQzOWroedGB0DYeJ8Y2UztwvZGEaMEiCp2ARcPzxjTIqlPkT7Az1rGsDMyr33bIbNVfq\nb0WWGhDiqLVrhhSSF/nlbPdrDlwPagivj1Ggjd354Pi68V1EGZkEbyzBsced59tM/PEN3OZPzj78\n4GzhA9Td8kSUbGi71dmNfdbxaoG33LSO8YVttyWG6K2rd6jbglQPoW1Ymnfo3ozvooTuLa6L/iOm\ngQQ/eWfCebLNJCK+3eZPIP/3xvS+IgNCjR/B1UCkSeAQffCm9vlnHIrGFHa98X3k1qi9p/vgjNsv\nBJ25n+b77enUm+CXeqecZ9pMIuLbY/4Ex6Gz0UH0vnM9kwPh+OTt2VLA/Mbu6Vp3XcdIS0/wuuIb\nGZfYH83wSXlnz7ibh8j223r4p64Ex5DFeZrNJCK+wZUnrr77nJG8+3rReKIuhLuzHbEcHKWttX5p\nT09w//HdMjiLF1TPshq7fv+kSfhP8L7cqvMcm0lKfCOjDX9FPoc5158ecLsD9BDGEJvYy/OJjeoR\nGxJcnbX2E98eZz4txe2OH9kpwIHPBE/HPGpS4ht4XBLppwD3eLro0M18pppyuhlf2K5OcHUl9IG/\nf3asY8zGdSbeoDqpeW6griUAKcBPgqejkktQfOtLRwz5uYTnwBvwf3Uj1zm04H25B7EL1FDVCd4z\nsuJ95zmEe1p/YaPtRY1pJcj2yf168U5wtBlnO8tJUHwDjzHv4Pi6s5EL3ldqoAPIyCKqrFGd4Oin\nv3Ufit19vZiOye6auBXgGVkDruOR4Kn5AcxkxbfbHaygw2157/FOzVYLHbk1emD0E6t5WTDXjNa8\nVhN/TP5dYYNT87xupk5gCkjwmtNoV56UnC0sJ1nxDTxuAI3a3K1u2ql8NjaGUIW1DM7yhyizwIEn\nrtGuUnCRtB8wHDG+u1Lot/C0AiRD9bRqam6Mnrj4dvsFNSWMhmom+GK5YmyJ8REXemcHHKUeF8pf\n7Z/O1KW2Na3I7En76gRPzT0zEhffoOboT4TRUPUsinHFfM/ISornN0lNas68YQSWwSX/NcciGfwl\nB8FIcFt+neNAkhjf8NrtEjIlBDTaon49vcx+cnF3ljFm3r5uyehtEvrza7oPStm5gL4meoKnZkI1\nifENcNShbpKWV1P6jfb7cqsYMGbhLvXEg4HRX8XWic5x54GMUVr9pPugdMz+n3YMiErww2155//2\n03h8/9P/9F1T9Wd/3WO0P0N/eubvZeM//l37Hx1vkf9S2dRvTtzUW8hfXHtrbJAR/ea/tOk+KP3r\n/xmbG9Ekhh/90X/+X//ifK/xx7ikbAlCcuMb+u23T40mqOuPf/d7Y3uKQmTrjQSBbmyQDd3QTRBV\nbRaRIksMu6RsCULQ+DbaRzZFKyCaIKIVImUFE8OQbksQGN8hiFZANEFEK0TKCiaGId2WIDC+QxCt\ngGiCiFaIlBVMDEO6LUFgfIcgWgHRBBGtECkrmBiGdFuCwPgOQbQCogkiWiFSVjAxDOm2BIHxHYJo\nBUQTRLRCpKxgYhjSbQkC4zsE0QqIJohohUhZwcQwpNsSBMZ3CKIVEE0Q0QqRsoKJYUi3JQiM7xBE\nKyCaIKIVImUFE8OQbksQGN8hiFZANEFEK0TKCiaGId2WIDC+QxCtgGiCiFaIlBVMDEO6LUFgfIcg\nWgHRBBGtECkrmBiGdFuCwPgOQbQCogkiWiFSVjAxDOm2BIHxHYJoBUQTRLRCpKxgYhjSbQkC4zsE\n0QqIJohohUhZwcQwpNsSBMZ3CKIVEE0Q0QqRsoKJYUi3JQiM7xBEKyCaIKIVImUFE8OQbksQGN8h\niFZANEFEK0TKCiaGId2WIDC+QxCtgGiCiFaIlBVMDEO6LUFgfIcgWgHRBBGtECkrmBiGdFuCwPgO\nQbQCogkiWiFSVjAxDOm2BIHxHYJoBUQTRLRCpKxgYhjSbQkC4zsE0QqIJohohUhZwcQwpNsSBMZ3\nCKIVEE0Q0QqRsoKJYUi3JQiM7xBEKyCaIKIVImUFE8OQbksQGN8hiFZANEFEK0TKCiaGId2WIDC+\nQxCtgGiCiFaIlBVMDEO6LUFgfIcgWgHRBBGtECkrmBiGdFuCwPgOQbQCogkiWiFSVjAxDOm2BIHx\nHYJoBUQTRLRCpKxgYhjSbQkC4zsE0QqIJohohUhZwcQwpNsSBMZ3CKIVEE0Q0QqRsoKJYUi3JQiM\n7xBEKyCaIKIVImUFE8OQbksQGN8hiFZANEFEK0TKCiaGId2WIDC+QxCtgGiCiFaIlBVMDEO6LUGw\nPr7/6vdjc+u76iPt/vS5992KsUEEissKfHd838mVnY+f9sQB/DdTJij97fO58YXtJPgAxWhF1/Ai\nfFjZrCgfAI6OwfF1NBVjy2ikrFCfJEZbRLACbQMfBs3DeChK6bYEwfr4/seZTecD/cLrYtnYIALF\nYgWySTXEmuAAjviIjas94GsisJyvXQXCK/rkisWKv/m/Jem9qsFD2MB4SgRSVqjPEIstorMPP0id\nB/BvY4MopdsSBLvjG7vE+TR/IDvxrb4vDkvkOHzAX1QxLpkecQONqz2gjJLvKwmFIlQqUPxDNo5G\nsVihsgl7H4dAzfaAf8TVk6kPEIstSlJ0C4zv2HaGSB262DFSf2UnvvGt0SiNP0KIMGUFiLLgisUE\nxJP6ptVHI6JKqlFsZjzaVMViBY4FjESrA/pvn88pEwA2MB5ttpQV6t1jsUUvutEekA/q34zvGHaG\nLmmX2CWyV7IT3x6S9hqlG7GYIAGt6k1DqMHVo9jMeKipSlp7kAFKxD5Aygr17rHYIt9d9W0SGozv\nmNuoCik1JGR864rFjehNkHGGx6EoQ+aa+d4kJbY9AOOhZktZod46FlsQ3+i0kNrqv4xvh1h2hkhG\nzWpczPjWJRVHzdmVJil6E/zsdBmIRDl/krT2kOX4RretTygxvh1i2RkiNWqWwSDjW4TGmpGSU6JZ\naqtqycKkKBtGotoDJEcHGobxULOlrFDvngRbGN8OMe4MaY5y3DK+RXIWFzW48VBTFb0JfuJbGgZs\nMR5qnhLVHiBpEtFnlrJCvXsSbGF8O8S1M6S61HcA4xu2dA0vSqLhH/qYMQJFb4L6psBjgY00jCgP\n1yS0B5E+Got4BQ6krFDvngRbGN8Oce0MGQ7rB20241tfIyh8/GUluLFlBIreBOcLe87nxnK4xtUe\nakoODYR4xD06pKxQHyAJtjC+HWLZGWf/cJ2OMRZmfOvgQK25BLipit4E59syvt2F40VK7xgPDfUB\nkmAL49shlp2h1lSgRRon5bIZ34bQNJHacriiDE/3qUv1NYHxd10Zj298a/X1o7/0VElZoT5DEmxh\nfDtEvzPE+uqMZnyLUJJLgkd50EZvgvqOAA3DeEg0OL6utslgfMs0I9qDx+mBpkpZoT5GEmxhfDtE\nvzNUKYG2WD0twPjWJW0UdA0vGo82SdGboBaPAo/4loaBLDMeap6S0B7kwggQWRuolrJCfYwk2ML4\ndoh4Z0hzrHlejvFtSArwyAyJ3gTVnQM/8R1lw4i9PcjdAkCUl25VS1mhPknstkCMb4eId4aMBH0S\n5arniK3wI4m2FMe3n/uU+Yn40BVve9Bnz6Jc7V5Tygr1YeK1RYnx7RDxzpBJTJ9k+TINSCYWUhzf\nMiDz6KrVBogz4+9NVYztIVHZDSkr1OeJ0RYR49shCTtDFMsYWZQoKyBZXgkiO2cVvQn616y5SlLy\nPeIgi6s9wAS5y3m88SRSVqiPFJctuhjfDknYGaKsxTfyCHJb2S0zBlG20VjaA0xQ37Q6oGGODEGi\nXEAJxWKFnt34h1vbiFjKCvWpYrHFEOPbIQk7Q5S1+FYBjWEyYkvWFeCIxb/lGMajUS4Xi6U9IJdl\nrmByZUe+L3yQ7I7+3F0sVkhPhi+ekOyGlBXqg8ViiyHGt0MSdoYoa/GNeJLYqglCPMrshuJqD/ia\nktTVxLLuInorJJUOBM3GeG5TpaxQbx29LZDPc2YRtxPdliCkJL5lJ2XkcIVQYfW+W0HNJeU2QJDp\n9XiUirE9wArsd5kyAvDkH2c2I54zEUVvhT4K8YbxXRPGd3ZFKyCaIKIVImUFE8OQbksQGN8hiFZA\nNEFEK0TKCiaGId2WIDC+QxCtgGiCiFaIlBVMDEO6LUFgfIcgWgHRBBGtECkrmBiGdFuCwPgOQbQC\nogkiWiFSVjAxDOm2BIHxHYJoBUQTRLRCpKxgYhjSbQkC4zsE0QqIJohohUhZwcQwpNsSBMZ3CKIV\nEE0Q0QqRsoKJYUi3JQiM7xBEKyCaIKIVImUFE8OQbksQGN8hiFZANEFEK0TKCiaGId2WIDC+QxCt\ngGiCiFaIlBVMDEO6LUFgfIcgWgHRBBGtECkrmBiGdFuCwPgOQbQCogkiWiFSVjAxDOm2BIHxHYJo\nBUQTRLRCpKxgYhjSbQkC4zsE0QqIJohohUhZwcQwpNsSBMZ3CKIVEE0Q0QqRsoKJYUi3JQiM7xBE\nKyCaIKIVImUFE8OQbksQGN8hiFZANEFEK0TKCiaGId2WIDC+QxCtgGiCiFaIlBVMDEO6LUFgfIcg\nWgHRBBGtECkrmBiGdFuCwPgOQbQCogkiWiFSVjAxDOm2BIHxHYJoBUQTRLRCpKxgYhjSbQkC4zsE\n0QqIJohohUhZwcQwpNsSBMZ3CKIVEE0Q0QqRsoKJYUi3JQiM7xBEKyCaIKIVImUFE8OQbksQGN8h\niFZANEFEK0TKCiaGId2WIDC+QxCtgGiCiFaIlBVMDEO6LUFgfIcgWgHRBBGtECkrmBiGdFuCwPgO\nQbQCogkiWiFSVjAxDOm2BIHxHYJoBUQTRLRCpKxgYhjSbQkC4zsE0QqIJohohUhZwcQwpNsSBMZ3\nCKIVEE0Q0QqRsoKJYUi3JQiM7xBEKyCaIKIVImUFE8OQbksQgsY3lTzd+JNTt//sr3v+/L89+4tr\nb9FW/tnJv6vahqKiExOjppQtQWB8p0p//u1TFdm6fvvtgLEZRUWpJCQGapp/9T9e/fbbp//yQt8/\n/6//+0/PdP3Jqd//5sRNY7MopWwJQuPxTRLI5b4pI7uVrj+dqex9cTYiaQf7erFcKSxt52Y3B8fX\n+/Nrw5Nl57GsAhOMgwK61DvlPGwnjO9UMVQsGw1UdLqrML6w7WxHLGTv834ol1Y/IZSfT2wMjK7d\nfb3Y8Wrh2sAMYuhcd/FE58SxjjFjv0Nft+TmN3adV8kqZ+4XDFugthdzzsN2wvhOFTjC/8PfjRpt\nVBfK8PXtn5ytiQ0gqRHKX93IGbvSv7rfLjuvlVV6RlYMT5QwNHG2sBPGd9r4h8mPRhs19Jff5RDi\nLMdsAV3yyTsTxk70r1P33uMVnNfKJDNrnzD+MGyB8MedymdnIzthfKcQ7wJc6d9+9+53d9+/mcr6\nlKgVjExvGrvPp1CzF5d3nFfJJMjumhNK0NX+aWcja2F8p5DOoQWjpXro37f+eKm3NLmS6YM8+Vx5\nUjJ2nB+1fz/vPD+TFJa2j9yqXcocbsuXd/ac7ayF8Z1CUHAZjdWP0KCvPpmeXvvkvApJEiublZoz\nAB46fns8y8uNcrOb37T+aHgiGiqmYdzJ+E4nOHSN9upTf/ld7lx3sfvtMifHkwZKaWNneQv55Twz\nY6DTglceJ3uvDcw4m1oO4zud1DV/4qZjHWNo6IPj61ysEiN7n78MT5YvPq69ot9N15+mJKHqBZ2W\nd+1yonNia9f6aRMF4zudNDZ/4iE0elQ0yJHUNP0kA5NhdcerBYyE6p0zgY62j2VwN+Ertz6bM6ww\ndPbhhxRMeQuM79TS8PzJgUKUoyrvy61mfFVDiGC8X1ja7n23gqr51L33huH16mVhw3ndbIDgvvt6\n8dDNvOGDofOPiravFDRgfKeWUOZPDtRXN3KIm6v9091vl38ofUxTadM89j5/Ka1+QsgidK48KQVZ\n1l0t2y8ErwufwQ1d7iulb/074zu1hD5/4lNHbo1e6JlsezGHWnJkepPz5qisEdZDxTJ6OIQ1ersG\n5kN8CkG2sllx3jjV+A9uVBjYMpXXLjG+00xd8yfIlH/3nfnHUPRN64+nuwqo0DEg6M+vIdPnN3ZT\neTgtlivqLlFdw0vXBmbOPvzgtu44oNw6gL7cqvNR0kthafv60xmfXSA6yxRP8TG+00y9S82Ujt+e\nONrelNAxdLR9DAGHUS2ORtRHqNYRfIg/1KrJLCGRzjNr+3eMelnYv2MUMrrj1QIK6jP3C/guxrdr\nhpBZ8Ap59Hxiw3gIOtdddD5oGsEgBs2j5p2nagpeYbiTyipBYHynmfzcltGm/es//n7sb55M//f/\nM9Wk+tGPDrflj3WMIZUu9U6hmEXEo7pEbioNT5aRpEpINGSrksf8+/r2T7IZJE+H8GrqZdGL4I1a\nn83hHfHWGDfgM3hcABKB8O7nH+0vxtfXk+Cz6dsgrdC1OI+lC4zV0E2iMejf11soC9Lqhg7jO+VU\nV4VqKsP4o4cQHPdeL/79P+zP2zZvNQtlCH3G1f5p9CVuY3+MUfQrUx68WXIeSAsYgWF8U+86HGyf\njisq/cD4TjltL361EhbZjZIcI0qUM/rfDxSS4uLjKYxel8oVHB5qSbKfE0eUT6GjxSADgYVxgM8F\nPLJzkVmpmSXACKlnZAXlszjjU5kKbgXjO+Xo8ycqu50Hfv75h9LHugakShikI2UGRtfUkhIMbHHM\ndA4t4I/RzP+mQ7ARcYMBDapm/3ltsLW7d+TWKHrWwpL1P8SBhoShBoZ6+pDCpzIY3ArGd/pRqWpk\nt2Kn8rkvt9rwuuPTXQUEt/4jPggU/Lc/v4byHIGOV27gaEyfELIoJ68NzCCsETQhTsvCantvK1jZ\n+zIyvdn6bK6xSTk0LbQxvILzctmD8Z1+MMSumd06yFxUgigJjSPEp/bvVtg/7XZ3FBRWqPTRTyDT\nsRmCLK11OmIaXdrlvhI87xlZQVKXVj8hpBwjmkOzXz900B7QGC4+nkKzNAz0KfiMtpSRFe4eML7T\nD0bW3tktIHxRHgbM1hOdEy2Ds88nNmpGubD3+QsO49zsJjJu4JefbUTk6Ys9kla2o2/Dp8JnwydE\nJ6QWOyKj1WLHxXIl3WvUAoIBByIbJULAhUxn7hdguHU9VpNgfBMTxBAGpIinhosjkc8od2On8hmx\niL4HxTsiHl0LErNzaP/HeZUwdkaYKuG9EK+QW/ej8lcJo3V5IoQ4ltdEWYd3wdu9LGwgl1E+4zM4\nH4jUQ1iRDWGfYr+n+AKcxmB8E1dQ46A0RrQ1PKmiC/Ha+myuP7/GgzCtoMFgqIcRCdpM8MiG8CIY\nk/kcO2YQxjc5GFTBGLGi1A0lxyHU9WcffsCRiQp3nr8LYTPojNElo2M+de99WPNdh9vyGPxhCMj5\nKG8Y36QOkOMI3GsDM6HUVqJDN/MXH091vFoYGF1D+Zayu3qmifLOXm52s/fdCrpedMDBp9d0YXzW\n/v08Xp+p7RPGN2kQ5GzX8JL/e1DUpWMdYwh0HMwM9BhRy0D7cqsI63PdxQauEjhQGM9d6JlEf8BB\nWAMwvklQUJENjq+HNd3pJgT65b4SKnQM1fNzW42dCyUeqPWdqrJGpDZ1b6pz2sOTZXbMQWB8kzBR\niw2uDcwgbY0jNnRh5H7q3ntkeufQAvoP1ImNXbuYQVY2KyPTm9hTGN9EdnVVwGVIpBrGN2kWi+XK\nwOhaNFEuOnQzjzBC8ajWZeMDoKIsrX7S79WXEZCSxeUdVLiIabXa8lx38fjt8bDOP/sR+lfU8kPF\nMiO7GTC+SRSg3MMxjFoPCRLu+S7/wvuiAESyI8iQKQj3/vwaikEbF3dX9r7gAxeWtvHhMfJAQOPr\nyE1u0V/GddHT4bb9s9DqxlsZ7DIjhvFNYgBxGfpqs1CEiEf2nbm/f2nllSclpCHG+0hGCBGJWl7F\nPTSztp/4ogaiCgWp/gqolNUr412gnpH9245D+AyQukAJdsUYzTWFWp5rQOOC8U1iBoVkfm4LaYWg\nRG7yJrQJ15E//JapugKLi/xihPFNEgfK0h9KHxnoSZCENQYf4wvbnA9JFIxvYgEIdGOlRJTn3zIi\nWcmjVmcyrJMP45vYymK5IuuULz6eOtHJe4v7lZHUXEdvKYxvkioQQ4Wl7erVcnEtd4lRxhpKxHRm\n11CmFcY3yQqILYSXWtqBmh2JJivt1B3GLZqQQTTjA599+EGtg2z/fl4FtFoYM7+xyztiZwHGNyG/\nYrFcUSkPDY6vS9ZDKGORlZf7Skh8VdQjQ3X5PMt65Nao8USUyeo11Z3H0a+od0Qi4wOoO4+rXOZP\nzBCB8U0IIVbC+CaEECthfBNCiJUwvgkhxEoY34QQYiWMb0IIsRLGNyGEWAnjmxBCrITxTQghVsL4\nJoQQK2F8E0KIlTC+CSHEShjfhBBiJYxvQgixEsY3IYRYCeObEEKshPFNCCFWwvgmhBArYXwTQoiV\nML4JIcRKGN+EEGIljG9CCLESxjchhFgJ45sQQizk55//HxHi4p0gouesAAAAAElFTkSuQmCC\n", "text/plain": [""]}, "execution_count": 4, "metadata": {}, "output_type": "execute_result"}], "source": ["from IPython.display import Image\n", "Image(\"td2_1.png\")"]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Partie 5 : recherche non dichotomique (exercice)\n", "\n", "Il n'y a pas d'autres moyens que de passer tous les \u00e9l\u00e9ments en revue et de conserver la position du premier \u00e9l\u00e9ment dans la liste qui v\u00e9rifie le crit\u00e8re de recherche."]}, {"cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["3\n"]}], "source": ["l = [ 3, 6, 2 , 7, 9 ]\n", "x = 7\n", "\n", "for i,v in enumerate(l) :\n", " if v == x :\n", " position = i\n", "\n", "print ( position )"]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Partie 6 : recherche dichotomique (exercice)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["La recherche dichotomique s'applique uniquement sur un tableau tri\u00e9e. A chaque it\u00e9ration, on vise le milieu du tableau pour savoir dans quelle moiti\u00e9 chercher."]}, {"cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["3\n"]}], "source": ["l = [2, 3, 6, 7, 9]\n", "# si la liste n'est pas tri\u00e9e, il faut \u00e9crire : \n", "l.sort ()\n", "x = 7\n", "\n", "a = 0\n", "b = len(l)-1\n", "while a <= b :\n", " m = (a+b)//2 # ne pas oublier // sinon la division est r\u00e9elle\n", " if l[m] == x : \n", " position = m # ligne A\n", " break # pas la peine de continuer, on quitte la boucle\n", " elif l[m] < x :\n", " a = m+1\n", " else :\n", " b = m-1\n", "\n", "print ( position )"]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Partie 7 : pour aller plus loin (exercice)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Lorsque l'\u00e9l\u00e9ment \u00e0 chercher n'est pas dans la liste, cela d\u00e9clenche une erreur :"]}, {"cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["None\n"]}], "source": ["l = [2, 3, 6, 7, 9]\n", "l.sort ()\n", "x = 5\n", "\n", "position = -1\n", "\n", "a = 0\n", "b = len(l)-1\n", "while a <= b :\n", " m = (a+b)//2\n", " if l[m] == x : \n", " position = m\n", " break \n", " elif l[m] < x :\n", " a = m+1\n", " else :\n", " b = m-1\n", "\n", "print ( position )"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Le programme affiche ``None`` qui \u00e9tait la valeur par d\u00e9faut de la variable position. La boucle n'a pas chang\u00e9 le contenu de la variable. Donc, lorsque ``position==-1``, cela veut dire que le r\u00e9sultat n'a pas \u00e9t\u00e9 trouv\u00e9.\n", "\n", "**Co\u00fbt**\n", "\n", "Comme \u00e0 chaque it\u00e9ration, on divise la taille du probl\u00e8me par deux, on est s\u00fbr que l'algorithme a trouv\u00e9 la r\u00e9ponse lorsque $\\frac{n}{2^k} < 1$ o\u00f9 $n$ est le nombre d'\u00e9l\u00e9ments du tableau et $k$ le nombre d'it\u00e9rations. Par cons\u00e9quent, $k \\sim \\ln_2 n$. On note cela $O(\\ln_2 n)$. Le programme suivant v\u00e9rifie cela :"]}, {"cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["k= 0 x= 298775 it\u00e9ration= 20 log2(len(l))= 19.931568569324174\n", "k= 1 x= 941582 it\u00e9ration= 19 log2(len(l))= 19.931568569324174\n", "k= 2 x= 74686 it\u00e9ration= 20 log2(len(l))= 19.931568569324174\n", "k= 3 x= 274574 it\u00e9ration= 20 log2(len(l))= 19.931568569324174\n", "k= 4 x= 573574 it\u00e9ration= 20 log2(len(l))= 19.931568569324174\n", "k= 5 x= 351579 it\u00e9ration= 18 log2(len(l))= 19.931568569324174\n", "k= 6 x= 414944 it\u00e9ration= 20 log2(len(l))= 19.931568569324174\n", "k= 7 x= 556908 it\u00e9ration= 20 log2(len(l))= 19.931568569324174\n", "k= 8 x= 894863 it\u00e9ration= 19 log2(len(l))= 19.931568569324174\n", "k= 9 x= 651824 it\u00e9ration= 20 log2(len(l))= 19.931568569324174\n"]}], "source": ["import random, math\n", "l = list(range(0,1000000))\n", "\n", "for k in range(0,10):\n", " x = random.randint(0,l[-1])\n", " \n", " iter = 0\n", " a = 0\n", " b = len(l)-1\n", " while a <= b :\n", " iter += 1\n", " m = (a+b)//2\n", " if l[m] == x : \n", " position = m\n", " break \n", " elif l[m] < x :\n", " a = m+1\n", " else :\n", " b = m-1\n", " \n", " print (\"k=\",k, \"x=\", x, \"it\u00e9ration=\", iter, \" log2(len(l))=\", math.log(len(l))/math.log(2))"]}, {"cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [], "source": []}], "metadata": {"kernelspec": {"display_name": "Python 3", "language": "python", "name": "python3"}, "language_info": {"codemirror_mode": {"name": "ipython", "version": 3}, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.6.1"}}, "nbformat": 4, "nbformat_minor": 2}