{"id":16564,"date":"2022-08-19T17:43:53","date_gmt":"2022-08-19T16:43:53","guid":{"rendered":"https:\/\/complex-systems-ai.com\/?page_id=16564"},"modified":"2024-02-11T15:46:31","modified_gmt":"2024-02-11T14:46:31","slug":"ex-diviser-pour-regner","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/es\/algoritmico\/ejercicios-corregidos-algoritmo-divide-y-venceras\/","title":{"rendered":"22 Ejercicios corregidos Algoritmo divide y vencer\u00e1s"},"content":{"rendered":"\t\t<div data-elementor-type=\"wp-page\" data-elementor-id=\"16564\" class=\"elementor elementor-16564\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-13c3fdc elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"13c3fdc\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-ef22e19\" data-id=\"ef22e19\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-f50af7e elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"f50af7e\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/algorithmique\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Algorithmique<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-be52ea7\" data-id=\"be52ea7\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-95fcbdb elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"95fcbdb\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Page d'accueil<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-236a3ce\" data-id=\"236a3ce\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-447994b elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"447994b\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/en.wikipedia.org\/wiki\/Algorithm\" target=\"_blank\" rel=\"noopener\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Wiki<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-46c8ccf elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"46c8ccf\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-6392f6b\" data-id=\"6392f6b\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-541411d elementor-widget elementor-widget-heading\" data-id=\"541411d\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_82_2 counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<div class=\"ez-toc-title-container\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Contenus<\/p>\n<span class=\"ez-toc-title-toggle\"><a href=\"#\" class=\"ez-toc-pull-right ez-toc-btn ez-toc-btn-xs ez-toc-btn-default ez-toc-toggle\" aria-label=\"Alternar tabla de contenidos\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewBox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewBox=\"0 0 24 24\" version=\"1.2\" baseProfile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n<nav><ul class='ez-toc-list ez-toc-list-level-1 ' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/ejercicios-corregidos-algoritmo-divide-y-venceras\/#Exercices-corriges-avec-algorithme-en-diviser-pour-regner\" >Exercices corrig\u00e9s avec algorithme en diviser pour r\u00e9gner<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/ejercicios-corregidos-algoritmo-divide-y-venceras\/#Exercice-1\" >Exercice 1<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/ejercicios-corregidos-algoritmo-divide-y-venceras\/#Exercice-2\" >Exercice 2<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/ejercicios-corregidos-algoritmo-divide-y-venceras\/#Exercice-3\" >Exercice 3<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/ejercicios-corregidos-algoritmo-divide-y-venceras\/#Exercice-4\" >Exercice 4<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-6\" href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/ejercicios-corregidos-algoritmo-divide-y-venceras\/#Exercice-5\" >Exercice 5<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-7\" href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/ejercicios-corregidos-algoritmo-divide-y-venceras\/#Exercice-6\" >Exercice 6<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-8\" href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/ejercicios-corregidos-algoritmo-divide-y-venceras\/#Exercice-7\" >Exercice 7<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-9\" href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/ejercicios-corregidos-algoritmo-divide-y-venceras\/#Exercice-8\" >Exercice 8<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-10\" href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/ejercicios-corregidos-algoritmo-divide-y-venceras\/#Exercice-9\" >Exercice 9<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-11\" href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/ejercicios-corregidos-algoritmo-divide-y-venceras\/#Exercice-10\" >Exercice 10<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-12\" href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/ejercicios-corregidos-algoritmo-divide-y-venceras\/#Exercice-11\" >Exercice 11<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-13\" href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/ejercicios-corregidos-algoritmo-divide-y-venceras\/#Exercice-12\" >Exercice 12<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-14\" href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/ejercicios-corregidos-algoritmo-divide-y-venceras\/#Exercice-13\" >Exercice 13<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-15\" href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/ejercicios-corregidos-algoritmo-divide-y-venceras\/#Exercice-14\" >Exercice 14<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-16\" href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/ejercicios-corregidos-algoritmo-divide-y-venceras\/#Exercice-15\" >Exercice 15<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-17\" href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/ejercicios-corregidos-algoritmo-divide-y-venceras\/#Exercice-16\" >Exercice 16<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-18\" href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/ejercicios-corregidos-algoritmo-divide-y-venceras\/#Exercice-17\" >Exercice 17<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-19\" href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/ejercicios-corregidos-algoritmo-divide-y-venceras\/#Exercice-18\" >Exercice 18<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-20\" href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/ejercicios-corregidos-algoritmo-divide-y-venceras\/#Exercice-19\" >Exercice 19<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-21\" href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/ejercicios-corregidos-algoritmo-divide-y-venceras\/#Exercice-20\" >Exercice 20<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-22\" href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/ejercicios-corregidos-algoritmo-divide-y-venceras\/#Exercice-21\" >Exercice 21<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-23\" href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/ejercicios-corregidos-algoritmo-divide-y-venceras\/#Exercice-22\" >Exercice 22<\/a><\/li><\/ul><\/nav><\/div>\n<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercices-corriges-avec-algorithme-en-diviser-pour-regner\"><\/span>Exercices corrig\u00e9s avec algorithme en diviser pour r\u00e9gner<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-d898bf1 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"d898bf1\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-aafc40e\" data-id=\"aafc40e\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-545833e elementor-widget elementor-widget-text-editor\" data-id=\"545833e\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>Les exercices corrig\u00e9s suivants concernent la cr\u00e9ation d&rsquo;algorithme selon la structure du <a href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/divide-y-venceras\/\">diviser pour r\u00e9gner<\/a> (divide&amp;conquer). Les algorithmes de type dichotomie seront aussi \u00e9tudi\u00e9s.<\/p>\n<p><img decoding=\"async\" class=\"aligncenter wp-image-11096 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/09\/cropped-Capture.png\" alt=\"diviser pour r\u00e9gner\" width=\"97\" height=\"97\" title=\"\"><\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-6ece53c elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"6ece53c\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-a1e933b\" data-id=\"a1e933b\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-452c5c8 elementor-widget elementor-widget-heading\" data-id=\"452c5c8\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-1\"><\/span>Exercice 1<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-f211516 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"f211516\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-1014b3c\" data-id=\"1014b3c\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-3af6f58 elementor-widget elementor-widget-text-editor\" data-id=\"3af6f58\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p><span style=\"font-weight: 400;\">On va jouer au jeu du \u201cplus petit, plus grand\u201d. Le but est de deviner un nombre compris entre 1 et n (entier). On consid\u00e8re que l\u2019algorithme prend en entr\u00e9e la valeur de n et du nombre x \u00e0 deviner, et qu\u2019il retourne le nombre de coup pour trouver ce nombre.<\/span><\/p><p><span style=\"font-weight: 400;\">a &#8211; R\u00e9exprimez le probl\u00e8me de fa\u00e7on plus formel.<\/span><\/p><p><span style=\"font-weight: 400;\">b &#8211; Ecrire l\u2019algorithme it\u00e9ratif r\u00e9solvant ce probl\u00e8me.<\/span><\/p><p><span style=\"font-weight: 400;\">c &#8211; Ecrire l\u2019algorithme <a href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/programacion-recursiva\/\">r\u00e9cursif<\/a> r\u00e9solvant ce probl\u00e8me.<\/span><\/p><p><span style=\"font-weight: 400;\">d &#8211; Comparer les complexit\u00e9s.<\/span><\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-334afbb elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"334afbb\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-cbf18e5\" data-id=\"cbf18e5\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-03b6944 elementor-widget elementor-widget-toggle\" data-id=\"03b6944\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-3891\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-3891\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-3891\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-3891\"><p><span style=\"font-weight: 400;\">a &#8211; Le probl\u00e8me pourrait se r\u00e9\u00e9crire comme suit : Etant donn\u00e9 un tableau tri\u00e9 par ordre croissant d\u2019entiers, comment d\u00e9terminer si un \u00e9l\u00e9ment appartient ou pas \u00e0 ce tableau ? Le principe est bien connu : on compare l\u2019\u00e9l\u00e9ment recherch\u00e9 \u00e0 l\u2019\u00e9l\u00e9ment m\u00e9dian, et le cas \u00e9ch\u00e9ant on r\u00e9p\u00e8te la recherche dans la partie gauche ou droite du tableau.<\/span><\/p><p><img decoding=\"async\" class=\"alignnone wp-image-16570 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo67.png\" alt=\"algorithme recherche dichotomique\" width=\"388\" height=\"92\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo67.png 388w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo67-300x71.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo67-18x4.png 18w\" sizes=\"(max-width: 388px) 100vw, 388px\" \/><\/p><p><span style=\"font-weight: 400;\">b &#8211;\u00a0<\/span><span style=\"font-weight: 400;\">L\u2019algorithme it\u00e9ratif est le suivant :<\/span><\/p><p><img fetchpriority=\"high\" decoding=\"async\" class=\"alignnone wp-image-16571 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo68.png\" alt=\"algorithme recherche dichotomique\" width=\"361\" height=\"369\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo68.png 361w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo68-293x300.png 293w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo68-12x12.png 12w\" sizes=\"(max-width: 361px) 100vw, 361px\" \/><\/p><p><span style=\"font-weight: 400;\">Puisque le tableau est coup\u00e9 \u00e0 chaque fois en deux, on parcourera au plus log n \u00e9l\u00e9ment avant de trouver le bon ou de savoir qu\u2019il n\u2019existe pas. La <a href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/complejidad-en-el-tiempo\/\">complexit\u00e9<\/a> est donc O(log n)<\/span><\/p><p><span style=\"font-weight: 400;\">c &#8211;\u00a0<\/span><span style=\"font-weight: 400;\">Par d\u00e9faut la r\u00e9ponse de l\u2019algorithme est faux, sauf s\u2019il y a un vrai qui est retourn\u00e9e ce qui donnera dans le main puis la m\u00e9thode :<\/span><\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-16572 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo69.png\" alt=\"algorithme recherche dichotomique\" width=\"730\" height=\"547\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo69.png 730w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo69-300x225.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo69-16x12.png 16w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo69-600x450.png 600w\" sizes=\"(max-width: 730px) 100vw, 730px\" \/><\/p><p><span style=\"font-weight: 400;\">Puisque le fonctionnement est exactement le m\u00eame que l\u2019algorithme it\u00e9ratif, on se doute que la complexit\u00e9 est la m\u00eame.<\/span><\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-0a0f31c elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"0a0f31c\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-7832835\" data-id=\"7832835\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-24d37a3 elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"24d37a3\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-b63a933 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"b63a933\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-a3f95c3\" data-id=\"a3f95c3\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-0d6c5db elementor-widget elementor-widget-heading\" data-id=\"0d6c5db\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-2\"><\/span>Exercice 2<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-f4655b3 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"f4655b3\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-82405a2\" data-id=\"82405a2\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-232748e elementor-widget elementor-widget-text-editor\" data-id=\"232748e\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p><span style=\"font-weight: 400;\">On cherche la somme d\u2019un tableau B de n \u00e9l\u00e9ments entiers.<\/span><\/p><p><span style=\"font-weight: 400;\">1 &#8211; \u00c9crivez un algorithme de type diviser-pour-r\u00e9gner qui r\u00e9sout ce probl\u00e8me.<\/span><\/p><p><span style=\"font-weight: 400;\">2 &#8211; Analysez sa complexit\u00e9 et faire l\u2019arbre d\u2019appels pour le tableau [3,4,2,3,4].<\/span><\/p><p><span style=\"font-weight: 400;\">3 &#8211; Comparez-la avec un algorithme it\u00e9ratif que vous d\u00e9crirez<\/span><\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-6978b14 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"6978b14\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-19a0653\" data-id=\"19a0653\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-1f8d4d4 elementor-widget elementor-widget-toggle\" data-id=\"1f8d4d4\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-3301\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-3301\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-3301\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-3301\"><p><span style=\"font-weight: 400;\">On d\u00e9finit la fonction Sum(B,i,j) qui est la somme des \u00e9l\u00e9ments de B entre les positions i et j. Ainsi la valeur recherch\u00e9e est Sum(B,1,n). On va calculer Sum(B,i,j) en d\u00e9coupant le tableau B[i..j] en deux moiti\u00e9s ; calculant les sommes pour chaque moiti\u00e9 ; et additionnant ces deux sommes. Ceci donne le code suivant :<\/span><\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-16573 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo70.png\" alt=\"algorithme r\u00e9cursif somme tableau\" width=\"295\" height=\"249\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo70.png 295w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo70-14x12.png 14w\" sizes=\"(max-width: 295px) 100vw, 295px\" \/><\/p><p><span style=\"font-weight: 400;\">Pour la complexit\u00e9, vu qu\u2019on n\u2019a pas encore vu le Master Theorem on va se servir de l\u2019arbre d\u2019appels :<\/span><\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-16574 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo71.png\" alt=\"algorithme r\u00e9cursif somme tableau\" width=\"650\" height=\"390\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo71.png 650w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo71-300x180.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo71-18x12.png 18w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo71-600x360.png 600w\" sizes=\"(max-width: 650px) 100vw, 650px\" \/><\/p><p><span style=\"font-weight: 400;\">On comprend que l\u2019on coupe en deux \u00e0 chaque fois le tableau. Le calcul est simple, donc la complexit\u00e9 ne d\u00e9pend que de la profondeur de l\u2019arbre p tel que 2^<\/span><span style=\"font-weight: 400;\">p<\/span><span style=\"font-weight: 400;\"> &gt; n (taille du tableau) d\u2019o\u00f9 p &gt; log n et une complexit\u00e9 en O(log n).<\/span><\/p><p><span style=\"font-weight: 400;\">L\u2019algorithme it\u00e9ratif est le suivant :<\/span><\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-16575 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo72.png\" alt=\"algorithme r\u00e9cursif somme tableau\" width=\"194\" height=\"207\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo72.png 194w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo72-11x12.png 11w\" sizes=\"(max-width: 194px) 100vw, 194px\" \/><\/p><p><span style=\"font-weight: 400;\">Ici la complexit\u00e9 est de O(n).<\/span><\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-0585396 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"0585396\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-0b83d57\" data-id=\"0b83d57\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-80d5bed elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"80d5bed\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-2105cfe elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"2105cfe\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-00072ae\" data-id=\"00072ae\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-c34181e elementor-widget elementor-widget-heading\" data-id=\"c34181e\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-3\"><\/span>Exercice 3<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-5c4c0a8 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"5c4c0a8\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-aa79b05\" data-id=\"aa79b05\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-4c8c4d5 elementor-widget elementor-widget-text-editor\" data-id=\"4c8c4d5\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p><span style=\"font-weight: 400;\">On dit qu\u2019un tableau a un \u00e9l\u00e9ment majoritaire si une valeur du tableau est pr\u00e9sent au moins n\/2 fois sur n \u00e9l\u00e9ments.<\/span><\/p><p><span style=\"font-weight: 400;\">1 &#8211; Proposer un algorithme it\u00e9ratif pour r\u00e9soudre ce probl\u00e8me.<\/span><\/p><p><span style=\"font-weight: 400;\">2 &#8211; Proposer une m\u00e9thode pour r\u00e9soudre ce probl\u00e8me en diviser pour r\u00e9gner.<\/span><\/p><p><span style=\"font-weight: 400;\">3 &#8211; Ecrire la m\u00e9thode d\u00e9crite par un algorithme.<\/span><\/p><p>Modifier votre algorithme en tenant compte des propri\u00e9t\u00e9s suivantes :<\/p><ul><li>si une seule des moiti\u00e9s fournit un majoritaire, seul cet \u00e9l\u00e9ment peut \u00eatre majoritaire dans le tableau complet.<\/li><li>si les deux appels r\u00e9cursifs fournissent des majoritaires, qu&rsquo;ils sont diff\u00e9rents, avec un nombre d&rsquo;occurrences diff\u00e9rent : le seul qui puisse \u00eatre majoritaire est celui qui a la plus grand nombre d&rsquo;occurrences.<\/li><li>dans le cas o\u00f9 n est une puissance de 2, et donc les moiti\u00e9s toujours de taille \u00e9gale, s&rsquo;il y a deux majoritaires diff\u00e9rents avec le m\u00eame nombre d&rsquo;occurrences, alors il ne peut y avoir de majoritaire dans le tableau complet.<\/li><\/ul>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-838a586 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"838a586\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-cc50116\" data-id=\"cc50116\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-74a1a55 elementor-widget elementor-widget-toggle\" data-id=\"74a1a55\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-1221\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-1221\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-1221\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-1221\"><p><span style=\"font-weight: 400;\">1 &#8211; On compte le nombre d\u2019occurrence de chaque \u00e9l\u00e9ment (pas besoin de compter vers la gauche car s\u2019il existe alors il a d\u00e9j\u00e0 \u00e9t\u00e9 compt\u00e9 auparavant). Pour la premi\u00e8re boucle, on aurait pu s\u2019arr\u00eater \u00e0 n\/2 + 1 car m\u00eame si tous les \u00e9l\u00e9ments suivant \u00e9taient identique il ne serait tout de m\u00eame pas majoritaire.<\/span><\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-16577 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo73.png\" alt=\"algorithme r\u00e9cursif majoritaire\" width=\"381\" height=\"228\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo73.png 381w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo73-300x180.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo73-18x12.png 18w\" sizes=\"(max-width: 381px) 100vw, 381px\" \/><\/p><p><span style=\"font-weight: 400;\">2 &#8211; On va partir du principe de diviser pour r\u00e9gner :<\/span><\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-16578 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo74.png\" alt=\"algorithme r\u00e9cursif majoritaire\" width=\"366\" height=\"85\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo74.png 366w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo74-300x70.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo74-18x4.png 18w\" sizes=\"(max-width: 366px) 100vw, 366px\" \/><\/p><p><span style=\"font-weight: 400;\">S&rsquo;il existe un \u00e9l\u00e9ment majoritaire x dans E, alors x est majoritaire dans au moins une des deux listes E1 et E2 (en effet si x non majoritaire dans E1, ni dans E2, alors dans E, nombre de x \u2264 n\/4 + n\/4 = n\/2).<\/span><\/p><p><span style=\"font-weight: 400;\">Le principe de la r\u00e9cursion est alors le suivant : calculer les \u00e9l\u00e9ments majoritaires de E1 et de E2 (s&rsquo;ils existent) avec le nombre total d&rsquo;occurrences de chacun et en d\u00e9duire si l&rsquo;un des deux est majoritaire dans E.<\/span><\/p><p><span style=\"font-weight: 400;\">L&rsquo;algorithme suivant Majoritaire(i, j) renvoie un couple qui vaut (x, cx) si x est majoritaire dans le sous-tableau E[i..j] avec cx occurrences et qui vaut (\u2212, 0) s&rsquo;il n&rsquo;y a pas de majoritaire dans E[i..j], l&rsquo;appel initial \u00e9tant Majoritaire(1, n). La fonction Occurence(x, i, j) calcule le nombre d&rsquo;occurrences de x dans le sous-tableau E[i..j].<\/span><\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-16579 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo75.png\" alt=\"algorithme r\u00e9cursif majoritaire\" width=\"424\" height=\"410\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo75.png 424w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo75-300x290.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo75-12x12.png 12w\" sizes=\"(max-width: 424px) 100vw, 424px\" \/><\/p><p><span style=\"font-weight: 400;\">Il n\u2019est pas si facile \u00e0 comprendre, prenons un exemple d\u2019un tableau de 8 \u00e9l\u00e9ments avec 5 \u00e9l\u00e9ments identiques pour bien comprendre son fonctionnement.<\/span><\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-16580 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo76.png\" alt=\"algorithme r\u00e9cursif majoritaire\" width=\"705\" height=\"383\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo76.png 705w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo76-300x163.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo76-18x10.png 18w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo76-600x326.png 600w\" sizes=\"(max-width: 705px) 100vw, 705px\" \/><\/p><p>Voici l&rsquo;algorithme majoritaire en tenant compte des nouvelles propri\u00e9t\u00e9s :<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-19200 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/majoritaire.png\" alt=\"majoritaire diviser pour r\u00e9gner\" width=\"517\" height=\"491\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/majoritaire.png 517w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/majoritaire-300x285.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/majoritaire-13x12.png 13w\" sizes=\"(max-width: 517px) 100vw, 517px\" \/><\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-f694764 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"f694764\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-131c8c4\" data-id=\"131c8c4\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-baf1be7 elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"baf1be7\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-73d04cd elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"73d04cd\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-b0d8a2c\" data-id=\"b0d8a2c\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-48887c8 elementor-widget elementor-widget-heading\" data-id=\"48887c8\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-4\"><\/span>Exercice 4<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-72af1f8 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"72af1f8\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-a7937a5\" data-id=\"a7937a5\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-e04ed29 elementor-widget elementor-widget-text-editor\" data-id=\"e04ed29\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p><span style=\"font-weight: 400;\">1 &#8211; Proposer un algorithme en diviser pour r\u00e9gner cherchant le minimum d\u2019un tableau.<\/span><\/p><p><span style=\"font-weight: 400;\">2 &#8211; De m\u00eame avec le maximum.<\/span><\/p><p><span style=\"font-weight: 400;\">3 &#8211; De m\u00eame en recherchant \u00e0 la fois le minimum et le maximum.<\/span><\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-ec20f86 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"ec20f86\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-d8e3241\" data-id=\"d8e3241\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-fc21ffa elementor-widget elementor-widget-toggle\" data-id=\"fc21ffa\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-2641\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-2641\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-2641\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-2641\"><p><span style=\"font-weight: 400;\">Je vais donner directement la r\u00e9ponse \u00e0 la question 3 puisqu\u2019elle contient la r\u00e9ponse aux deux pr\u00e9c\u00e9dentes. Dans cette m\u00e9thode, il faut retenir les positions dans le tableau ainsi que la valeur de min et max.<\/span><\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-19194 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/minmax-1.png\" alt=\"min max divide and conquer\" width=\"705\" height=\"342\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/minmax-1.png 705w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/minmax-1-300x146.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/minmax-1-18x9.png 18w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/minmax-1-600x291.png 600w\" sizes=\"(max-width: 705px) 100vw, 705px\" \/><\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-8a56cd7 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"8a56cd7\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-9fc35d1\" data-id=\"9fc35d1\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-642b2b3 elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"642b2b3\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-41be1a7 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"41be1a7\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-e454857\" data-id=\"e454857\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-5cc3c4e elementor-widget elementor-widget-heading\" data-id=\"5cc3c4e\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-5\"><\/span>Exercice 5<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-5e58853 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"5e58853\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-97d28fb\" data-id=\"97d28fb\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-74a38a6 elementor-widget elementor-widget-text-editor\" data-id=\"74a38a6\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>Voici la formule du produit matricielle :<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-16566 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo64.png\" alt=\"produit matriciel\" width=\"555\" height=\"204\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo64.png 555w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo64-300x110.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo64-18x7.png 18w\" sizes=\"(max-width: 555px) 100vw, 555px\" \/><\/p><p><span style=\"font-weight: 400;\">1 &#8211; Proposer un algorithme it\u00e9ratif et en donner la complexit\u00e9.<\/span><\/p><p><span style=\"font-weight: 400;\">Pour d\u00e9composer une matrice en dichotomie, il faut le faire \u00e0 la fois sur les lignes et sur les colonnes, donc en 4 parties comme le sch\u00e9ma suivant :<\/span><\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-19360 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/strassen.png\" alt=\"strassen\" width=\"495\" height=\"134\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/strassen.png 495w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/strassen-300x81.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/strassen-18x5.png 18w\" sizes=\"(max-width: 495px) 100vw, 495px\" \/><\/p><p><span style=\"font-weight: 400;\">Chaque \u00e9l\u00e9ment est une matrice carr\u00e9e. Notons r=ae+bg, s=af+bh, t=ce+dg et u=cf+dh.<\/span><\/p><p><span style=\"font-weight: 400;\">2 &#8211; Strassen a trouv\u00e9 une m\u00e9thode pour encore r\u00e9duire le nombre de calcul. Il propose de calculer r, s, t, u en utilisant une combinaison lin\u00e9aire (addition ou soustraction) des matrices suivantes :<\/span><\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-16569 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo66.png\" alt=\"algorithme de Strassen\" width=\"497\" height=\"146\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo66.png 497w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo66-300x88.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo66-18x5.png 18w\" sizes=\"(max-width: 497px) 100vw, 497px\" \/><\/p><p><span style=\"font-weight: 400;\">Exprimer r, s, t, u en fonction des pi.<\/span><\/p><p><span style=\"font-weight: 400;\">3 &#8211; Proposer un algorithme r\u00e9cursif bas\u00e9 sur les calculs de Strassen pour le produit matricielle.<\/span><\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-4f5654d elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"4f5654d\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-a1e94d7\" data-id=\"a1e94d7\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-f3d8efb elementor-widget elementor-widget-toggle\" data-id=\"f3d8efb\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-2551\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-2551\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-2551\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-2551\"><p><span style=\"font-weight: 400;\">1 &#8211; On remarque dans la formule qu\u2019il va falloir faire trois boucles en fonction de i, j et k.\u00a0<\/span><\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-16582 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo78.png\" alt=\"algorithme produit matricielle\" width=\"527\" height=\"303\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo78.png 527w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo78-300x172.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo78-18x10.png 18w\" sizes=\"(max-width: 527px) 100vw, 527px\" \/><\/p><p><span style=\"font-weight: 400;\">Au plus profond des structures \u00e0 it\u00e9rations, il y a trois boucles de 1 \u00e0 n imbriqu\u00e9es, donc une complexit\u00e9 en O(n^<\/span><span style=\"font-weight: 400;\">3<\/span><span style=\"font-weight: 400;\">)<\/span><\/p><p><span style=\"font-weight: 400;\">2 &#8211; Cela donne les relations lin\u00e9aires suivantes :<\/span><\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-16584 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo80.png\" alt=\"algorithme de strassen\" width=\"577\" height=\"118\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo80.png 577w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo80-300x61.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo80-18x4.png 18w\" sizes=\"(max-width: 577px) 100vw, 577px\" \/><\/p><p><span style=\"font-weight: 400;\">3 &#8211; L\u2019algorithme en diviser pour r\u00e9gner est le suivant :<\/span><\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-16585 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo81.png\" alt=\"algorithme de strassen\" width=\"890\" height=\"593\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo81.png 890w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo81-300x200.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo81-768x512.png 768w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo81-18x12.png 18w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo81-700x465.png 700w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/08\/algo81-600x400.png 600w\" sizes=\"(max-width: 890px) 100vw, 890px\" \/><\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-5ff1a15 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"5ff1a15\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-81c70a7\" data-id=\"81c70a7\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-d1ed4db elementor-widget elementor-widget-heading\" data-id=\"d1ed4db\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-6\"><\/span>Exercice 6<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-3a431d3 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"3a431d3\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-8db9fd8\" data-id=\"8db9fd8\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-fd48a30 elementor-widget elementor-widget-text-editor\" data-id=\"fd48a30\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>\u00c9crivez un\u00a0<a href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/pseudo-lenguaje-y-diagrama-de-flujo\/\">pseudo-code<\/a>\u00a0pour un\u00a0algorithme\u00a0Diviser pour R\u00e9gner permettant de trouver la position du plus grand \u00e9l\u00e9ment dans un tableau de nombres. \u00c9crivez un pseudo-code pour un algorithme de force brute, comparez avec le pr\u00e9c\u00e9dent. Montrez un <a href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/arboles-y-arboles\/\">arbre<\/a> du processus de l\u2019algorithme diviser pour mieux r\u00e9gner. Quel est le niveau maximal de l\u2019arborescence pour les nombres\u00a0?<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-8e439c5 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"8e439c5\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-fc19f65\" data-id=\"fc19f65\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-6967a00 elementor-widget elementor-widget-toggle\" data-id=\"6967a00\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-1101\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-1101\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-1101\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-1101\"><p><img loading=\"lazy\" decoding=\"async\" class=\"jetpack-lazy-image jetpack-lazy-image--handled wp-image-11032 size-full alignnone\" title=\"Corrected Exercises: Algorithms 1\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image42.png\" alt=\"diviser pour r\u00e9gner programmation dynamique exercices corrig\u00e9s\" width=\"522\" height=\"209\" data-recalc-dims=\"1\" data-lazy-loaded=\"1\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image42.png 522w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image42-300x120.png 300w\" sizes=\"(max-width: 522px) 100vw, 522px\" \/><\/p><p>L\u2019algorithme de force brute est trivial : une boucle.<\/p><p>A chaque niveau l, l\u2019arbre binaire complet est compos\u00e9 de 2^(l-1) feuille. Donc le total des sommets est 2^l -1. Soit l le niveau de l\u2019arbre, donc l=sup(log_2 (n)).<\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-b1786fd elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"b1786fd\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-c8ecb4e\" data-id=\"c8ecb4e\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-82d261e elementor-widget elementor-widget-heading\" data-id=\"82d261e\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-7\"><\/span>Exercice 7<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-8ea7e5f elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"8ea7e5f\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-a226d1b\" data-id=\"a226d1b\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-52caf9a elementor-widget elementor-widget-text-editor\" data-id=\"52caf9a\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>\u00c9crivez un pseudo-code pour un algorithme de division pour r\u00e9gner pour le probl\u00e8me d\u2019exponentiation du calcul de a^n o\u00f9 a&gt;0 et n est un entier positif. \u00c9crivez un pseudo-code pour un algorithme de force brute, comparez avec le pr\u00e9c\u00e9dent. Montrez un arbre du processus de l\u2019algorithme diviser pour mieux r\u00e9gner. Quel est le niveau maximum de l\u2019arbre pour n non donn\u00e9 ? V\u00e9rifier la\u00a0<a href=\"https:\/\/complex-systems-ai.com\/algorithmique\/terminaison-et-correction\/\">terminaison<\/a>, l\u2019exactitude et l\u2019exhaustivit\u00e9.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-38e1e34 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"38e1e34\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-7998a31\" data-id=\"7998a31\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-480be0f elementor-widget elementor-widget-toggle\" data-id=\"480be0f\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-7551\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-7551\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-7551\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-7551\"><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-11033 size-full jetpack-lazy-image jetpack-lazy-image--handled\" title=\"Diviser Pour R\u00e9gner Et Programmation Dynamique Diviser Pour R\u00e9gner\" src=\"https:\/\/i0.wp.com\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Capture-1-e1605195942759.png?resize=691%2C420&amp;ssl=1\" alt=\"diviser pour r\u00e9gner programmation dynamique exercices corrig\u00e9s\" width=\"691\" height=\"420\" data-recalc-dims=\"1\" data-lazy-loaded=\"1\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Capture-1-e1605195942759.png 691w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Capture-1-e1605195942759-300x182.png 300w\" sizes=\"(max-width: 691px) 100vw, 691px\" \/><\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-cf2ead1 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"cf2ead1\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-5e59b7c\" data-id=\"5e59b7c\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-51076db elementor-widget elementor-widget-heading\" data-id=\"51076db\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-8\"><\/span>Exercice 8<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-6ffc1dd elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"6ffc1dd\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-2e92ccc\" data-id=\"2e92ccc\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-a2cbc4e elementor-widget elementor-widget-text-editor\" data-id=\"a2cbc4e\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>Pour multiplier deux nombres entiers de n chiffres, une m\u00e9thode na\u00efve consiste \u00e0 multiplier chaque chiffre du premier nombre par chaque chiffre du second, et de faire les bons d\u00e9calages et les bonnes sommes. Le temps de calcul est alors en O(n\u00b2).<\/p><p>L\u2019algorithme de Karatsuba utilise le principe que le calcul utilis\u00e9 dans cette approche na\u00efve :<\/p><p>(a \u00d7 10^k+ b)(c \u00d7 10k+ d) = ac \u00d7 10^2k+ (ad + bc) \u00d7 10^k+ bd<\/p><p>n\u00e9cessitant quatre produits (ac, ad, bc et bd) peut \u00eatre fait avec seulement trois produits en regroupant les calculs sous la forme suivante :<\/p><p>(a \u00d7 10^k + b)(c \u00d7 10^k + d) = ac \u00d7 10^2k + (ac + bd \u2212 (a \u2212 b)(c \u2212 d)) \u00d7 10^k + bd<\/p><p>Certes des soustractions ont \u00e9t\u00e9 introduites, mais seulement trois produits de grands nombres sont maintenant n\u00e9cessaires : ac, bd et (a \u2212 b)(c \u2212 d).<\/p><p>Comme les additions et les soustractions sont peu co\u00fbteuses (n\u00e9gligeables par rapport aux multiplications), nous allons gagner en temps de calcul. Pour information la multiplication par une puissance de la base de calcul correspond \u00e0 un d\u00e9calage de chiffre et est tr\u00e8s rapide \u00e0 ex\u00e9cuter sur une machine.<\/p><p>\u00c9crire le code de la fonction karatsuba() permettant de multiplier deux grands nombres entiers de n chiffres selon ce principe.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-826c6b0 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"826c6b0\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-e4104ee\" data-id=\"e4104ee\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-2f69e82 elementor-widget elementor-widget-toggle\" data-id=\"2f69e82\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-4971\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-4971\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-4971\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-4971\"><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-19198 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/karatsuba.png\" alt=\"karatsuba algorithm\" width=\"686\" height=\"276\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/karatsuba.png 686w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/karatsuba-300x121.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/karatsuba-18x7.png 18w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/karatsuba-600x241.png 600w\" sizes=\"(max-width: 686px) 100vw, 686px\" \/><\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-f39c88c elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"f39c88c\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-16f2cd4\" data-id=\"16f2cd4\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-8cc7509 elementor-widget elementor-widget-heading\" data-id=\"8cc7509\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-9\"><\/span>Exercice 9<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-1ed62d0 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"1ed62d0\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-82b079e\" data-id=\"82b079e\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-760c345 elementor-widget elementor-widget-text-editor\" data-id=\"760c345\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>Etant donn\u00e9 un ensemble de points r\u00e9els, trouver la distance minimale entre deux points en utilisant un algorithme de type Diviser pour r\u00e9gner. Pour cela on utilisera la distance Euclidienne entre deux points.<\/p><p>La solution \u00e9vidente est de r\u00e9aliser une matrice de distance entre chaque pair de points. L&rsquo;algorithme de diviser pour r\u00e9gner coupe l&rsquo;espace r\u00e9cursivement en 2 blocs et regarde la distance minimale dans chaque blocs. De plus, il faut ensuite regarder la plus petite distance entre points de deux blocs diff\u00e9rents.<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-19204 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/mindistance.png\" alt=\"min distance diviser pour r\u00e9gner\" width=\"631\" height=\"400\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/mindistance.png 631w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/mindistance-300x190.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/mindistance-18x12.png 18w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/mindistance-600x380.png 600w\" sizes=\"(max-width: 631px) 100vw, 631px\" \/><\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-2dc88c7 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"2dc88c7\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-0bc4844\" data-id=\"0bc4844\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-a660d02 elementor-widget elementor-widget-toggle\" data-id=\"a660d02\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-1741\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-1741\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-1741\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-1741\"><p>Solution diviser-pour-r\u00e9gner<br \/>\u2014 Trier les points relativement \u00e0 leurs coordonn\u00e9es x.<br \/>\u2014 Diviser les points en deux groupes : la moiti\u00e9 gauche et la moiti\u00e9 droite.<br \/>\u2014 Utiliser la r\u00e9cursion pour trouver dg, la distance min entre les points de<br \/>gauche.<br \/>\u2014 Utiliser la r\u00e9cursion pour trouver dd, la distance min entre les points de droite.<br \/>\u2014 La solution optimale est :<br \/>\u00a0 \u00a0 \u00a0\u2014 soit dg,<br \/>\u00a0 \u00a0 \u00a0\u2014 soit dd,<br \/>\u00a0 \u00a0 \u00a0\u2014 soit la distance entre deux points A et B tels que A est dans la partie<br \/>gauche et B est dans la partie droite.<\/p><p>Soit midx la coordonn\u00e9e x du point le plus \u00e0 droite parmi les points de gauche. On\u00a0remarque que dans le troisi\u00e8me cas cit\u00e9 ci-dessus, les deux points A et B se situent\u00a0dans une fine bande de largeur min(dg, dd), centr\u00e9e en midx.<\/p><p>On remarque dans la bande centrale, deux points situ\u00e9es du m\u00eame c\u00f4t\u00e9 de la<br \/>fronti\u00e8re midx sont au moins \u00e0 distance d l\u2019un de l\u2019autre. On exploite cette information de la mani\u00e8re suivante :<\/p><p>\u2014 On commence par trier tous les points pr\u00e9sents dans la bande centrale en fonction de leur coordonn\u00e9e y.<\/p><p><span style=\"color: var( --e-global-color-text ); font-family: var( --e-global-typography-text-font-family ), Sans-serif; font-weight: var( --e-global-typography-text-font-weight ); font-size: 1.125rem;\">\u2014<\/span><span style=\"color: var( --e-global-color-text ); font-family: var( --e-global-typography-text-font-family ), Sans-serif; font-weight: var( --e-global-typography-text-font-weight ); font-size: 1.125rem;\">\u00a0<\/span>Pour chaque point A dans la bande centrale, on regarde la distance qui le s\u00e9pare des points se trouvant dans son rayon.<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-19206 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/mindistance2.png\" alt=\"min distance diviser pour r\u00e9gner\" width=\"581\" height=\"688\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/mindistance2.png 581w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/mindistance2-253x300.png 253w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/mindistance2-10x12.png 10w\" sizes=\"(max-width: 581px) 100vw, 581px\" \/><\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-bf32222 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"bf32222\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-4f49b47\" data-id=\"4f49b47\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-fc2fff3 elementor-widget elementor-widget-heading\" data-id=\"fc2fff3\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-10\"><\/span>Exercice 10<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-eb9525d elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"eb9525d\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-0773f62\" data-id=\"0773f62\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-e97c548 elementor-widget elementor-widget-text-editor\" data-id=\"e97c548\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>On s\u2019int\u00e9resse dans cet exercice \u00e0 la complexit\u00e9 dans le pire des cas et en nombre de comparaisons\u00a0des algorithmes.<\/p><p>1. Pour rechercher le plus grand et deuxi\u00e8me plus grand \u00e9l\u00e9ment de n entiers, donner un algorithme\u00a0na\u00eff et sa complexit\u00e9.<\/p><p>2. Pour am\u00e9liorer les performances, on se propose d\u2019envisager la solution consistant \u00e0 calculer le\u00a0maximum selon le principe de Diviser pour R\u00e9gner<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-9af0344 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"9af0344\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-39d50fb\" data-id=\"39d50fb\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-1fd2acf elementor-widget elementor-widget-toggle\" data-id=\"1fd2acf\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-3331\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-3331\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-3331\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-3331\"><p>1.<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-19211 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/doublemax.png\" alt=\"double max\" width=\"379\" height=\"234\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/doublemax.png 379w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/doublemax-300x185.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/doublemax-18x12.png 18w\" sizes=\"(max-width: 379px) 100vw, 379px\" \/><\/p><p>2.<\/p><p>Le principe est assez simple puisque cela est proche de l&rsquo;algorithme Merge Sort. Lors du r\u00e8gne, un tuple de deux \u00e9l\u00e9ments est remont\u00e9 (max1, max2) ou max1 &gt; max2. Le r\u00e8gne consiste \u00e0 comparer les tuples gauche et droit et de retourner les deux plus grands. Ainsi, chaque branche retournera les deux plus grands de son sous-tableau jusqu&rsquo;\u00e0 obtenir les deux plus grands du tableau dans son enti\u00e8ret\u00e9.<\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-e37ff89 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"e37ff89\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-dd64540\" data-id=\"dd64540\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-e784b59 elementor-widget elementor-widget-heading\" data-id=\"e784b59\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-11\"><\/span>Exercice 11<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-bdbc3b2 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"bdbc3b2\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-875535b\" data-id=\"875535b\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-862a9d7 elementor-widget elementor-widget-text-editor\" data-id=\"862a9d7\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>\u00c9tant donn\u00e9 un tableau d&rsquo;entiers, trouvez la somme maximale parmi tous les sous-tableaux possibles. Les sous-tableaux doivent occuper des positions cons\u00e9cutives dans le tableau d&rsquo;origine.<\/p><p>Entr\u00e9e : nombres[] = [2, -4, <strong>1, 9, -6, 7<\/strong>, -3]<\/p><p>Sortie : la somme maximale du sous-tableau est de 11 (marqu\u00e9e en <strong>gras<\/strong>)<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-1aa4ddb elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"1aa4ddb\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-023d2cf\" data-id=\"023d2cf\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-97b01da elementor-widget elementor-widget-toggle\" data-id=\"97b01da\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-1591\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-1591\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-1591\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-1591\"><p>L&rsquo;id\u00e9e est d&rsquo;utiliser la technique Divide and Conquer pour trouver la somme maximale des sous-tableaux. L&rsquo;algorithme fonctionne comme suit:<\/p><ol><li>Divisez le tableau en deux sous-tableaux \u00e9gaux.<\/li><li>Calculer r\u00e9cursivement la somme maximale des sous-tableaux pour le sous-tableau gauche,<\/li><li>Calculer r\u00e9cursivement la somme maximale des sous-tableaux pour le sous-tableau droit,<\/li><li>Trouvez la somme maximale du sous-tableau qui traverse l&rsquo;\u00e9l\u00e9ment du milieu.<\/li><li>Renvoie le maximum des trois sommes ci-dessus.<\/li><\/ol><table class=\"c-table\"><tbody><tr class=\"c-row\"><td class=\"c-nums \" data-settings=\"show\"><div class=\"c-nums-content\"><div class=\"c-num\" data-line=\"c-6362a665943fe624866205-1\">1<\/div><div class=\"c-num\" data-line=\"c-6362a665943fe624866205-2\">2<\/div><div class=\"c-num\" data-line=\"c-6362a665943fe624866205-3\">3<\/div><div class=\"c-num\" data-line=\"c-6362a665943fe624866205-4\">4<\/div><div class=\"c-num\" data-line=\"c-6362a665943fe624866205-5\">5<\/div><div class=\"c-num\" data-line=\"c-6362a665943fe624866205-6\">6<\/div><div class=\"c-num\" data-line=\"c-6362a665943fe624866205-7\">7<\/div><div class=\"c-num\" data-line=\"c-6362a665943fe624866205-8\">8<\/div><div class=\"c-num\" data-line=\"c-6362a665943fe624866205-9\">9<\/div><div class=\"c-num\" data-line=\"c-6362a665943fe624866205-10\">10<\/div><div class=\"c-num\" data-line=\"c-6362a665943fe624866205-11\">11<\/div><div class=\"c-num\" data-line=\"c-6362a665943fe624866205-12\">12<\/div><div class=\"c-num\" data-line=\"c-6362a665943fe624866205-13\">13<\/div><div class=\"c-num\" data-line=\"c-6362a665943fe624866205-14\">14<\/div><div class=\"c-num\" data-line=\"c-6362a665943fe624866205-15\">15<\/div><div class=\"c-num\" data-line=\"c-6362a665943fe624866205-16\">16<\/div><div class=\"c-num\" data-line=\"c-6362a665943fe624866205-17\">17<\/div><div class=\"c-num\" data-line=\"c-6362a665943fe624866205-18\">18<\/div><div class=\"c-num\" data-line=\"c-6362a665943fe624866205-19\">19<\/div><div class=\"c-num\" data-line=\"c-6362a665943fe624866205-20\">20<\/div><div class=\"c-num\" data-line=\"c-6362a665943fe624866205-21\">21<\/div><div class=\"c-num\" data-line=\"c-6362a665943fe624866205-22\">22<\/div><div class=\"c-num\" data-line=\"c-6362a665943fe624866205-23\">23<\/div><div class=\"c-num\" data-line=\"c-6362a665943fe624866205-24\">24<\/div><div class=\"c-num\" data-line=\"c-6362a665943fe624866205-25\">25<\/div><div class=\"c-num\" data-line=\"c-6362a665943fe624866205-26\">26<\/div><div class=\"c-num\" data-line=\"c-6362a665943fe624866205-27\">27<\/div><div class=\"c-num\" data-line=\"c-6362a665943fe624866205-28\">28<\/div><div class=\"c-num\" data-line=\"c-6362a665943fe624866205-29\">29<\/div><div class=\"c-num\" data-line=\"c-6362a665943fe624866205-30\">30<\/div><div class=\"c-num\" data-line=\"c-6362a665943fe624866205-31\">31<\/div><div class=\"c-num\" data-line=\"c-6362a665943fe624866205-32\">32<\/div><div class=\"c-num\" data-line=\"c-6362a665943fe624866205-33\">33<\/div><div class=\"c-num\" data-line=\"c-6362a665943fe624866205-34\">34<\/div><div class=\"c-num\" data-line=\"c-6362a665943fe624866205-35\">35<\/div><div class=\"c-num\" data-line=\"c-6362a665943fe624866205-36\">36<\/div><div class=\"c-num\" data-line=\"c-6362a665943fe624866205-37\">37<\/div><div class=\"c-num\" data-line=\"c-6362a665943fe624866205-38\">38<\/div><div class=\"c-num\" data-line=\"c-6362a665943fe624866205-39\">39<\/div><div class=\"c-num\" data-line=\"c-6362a665943fe624866205-40\">40<\/div><div class=\"c-num\" data-line=\"c-6362a665943fe624866205-41\">41<\/div><div class=\"c-num\" data-line=\"c-6362a665943fe624866205-42\">42<\/div><div class=\"c-num\" data-line=\"c-6362a665943fe624866205-43\">43<\/div><div class=\"c-num\" data-line=\"c-6362a665943fe624866205-44\">44<\/div><div class=\"c-num\" data-line=\"c-6362a665943fe624866205-45\">45<\/div><div class=\"c-num\" data-line=\"c-6362a665943fe624866205-46\">46<\/div><div class=\"c-num\" data-line=\"c-6362a665943fe624866205-47\">47<\/div><div class=\"c-num\" data-line=\"c-6362a665943fe624866205-48\">48<\/div><div class=\"c-num\" data-line=\"c-6362a665943fe624866205-49\">49<\/div><div class=\"c-num\" data-line=\"c-6362a665943fe624866205-50\">50<\/div><div class=\"c-num\" data-line=\"c-6362a665943fe624866205-51\">51<\/div><div class=\"c-num\" data-line=\"c-6362a665943fe624866205-52\">52<\/div><div class=\"c-num\" data-line=\"c-6362a665943fe624866205-53\">53<\/div><div class=\"c-num\" data-line=\"c-6362a665943fe624866205-54\">54<\/div><div class=\"c-num\" data-line=\"c-6362a665943fe624866205-55\">55<\/div><div class=\"c-num\" data-line=\"c-6362a665943fe624866205-56\">56<\/div><div class=\"c-num\" data-line=\"c-6362a665943fe624866205-57\">57<\/div><div class=\"c-num\" data-line=\"c-6362a665943fe624866205-58\">58<\/div><div class=\"c-num\" data-line=\"c-6362a665943fe624866205-59\">59<\/div><div class=\"c-num\" data-line=\"c-6362a665943fe624866205-60\">60<\/div><div class=\"c-num\" data-line=\"c-6362a665943fe624866205-61\">61<\/div><div class=\"c-num\" data-line=\"c-6362a665943fe624866205-62\">62<\/div><\/div><\/td><td class=\"c-code\"><div class=\"c-pre\"><div id=\"c-6362a665943fe624866205-1\" class=\"c-line\"><span class=\"c-p\" data-no-translation=\"\">#include &lt;stdio.h&gt;<\/span><\/div><div id=\"c-6362a665943fe624866205-2\" class=\"c-line\"><span class=\"c-p\" data-no-translation=\"\">#include &lt;limits.h&gt;<\/span><\/div><div id=\"c-6362a665943fe624866205-3\" class=\"c-line\">\u00a0<\/div><div id=\"c-6362a665943fe624866205-4\" class=\"c-line\"><span class=\"c-c\">\/\/ Utility function to find the maximum of two numbers<\/span><\/div><div id=\"c-6362a665943fe624866205-5\" class=\"c-line\"><span class=\"c-t\" data-no-translation=\"\">int<\/span> <span class=\"c-e\" data-no-translation=\"\">max<\/span><span class=\"c-sy\" data-no-translation=\"\">(<\/span><span class=\"c-t\" data-no-translation=\"\">int<\/span> <span class=\"c-v\" data-no-translation=\"\">x<\/span><span class=\"c-sy\" data-no-translation=\"\">,<\/span> <span class=\"c-t\" data-no-translation=\"\">int<\/span> <span class=\"c-v\" data-no-translation=\"\">y<\/span><span class=\"c-sy\" data-no-translation=\"\">)<\/span> <span class=\"c-sy\" data-no-translation=\"\">{<\/span><\/div><div id=\"c-6362a665943fe624866205-6\" class=\"c-line\"><span class=\"c-h\" data-no-translation=\"\">\u00a0\u00a0\u00a0\u00a0<\/span><span class=\"c-st\" data-no-translation=\"\">return<\/span> <span class=\"c-sy\" data-no-translation=\"\">(<\/span><span class=\"c-v\" data-no-translation=\"\">x<\/span> <span class=\"c-o\" data-no-translation=\"\">&gt;<\/span> <span class=\"c-v\" data-no-translation=\"\">y<\/span><span class=\"c-sy\" data-no-translation=\"\">)<\/span> <span class=\"c-sy\" data-no-translation=\"\">?<\/span> <span class=\"c-v\" data-no-translation=\"\">x<\/span> <span class=\"c-o\" data-no-translation=\"\">:<\/span> <span class=\"c-v\" data-no-translation=\"\">y<\/span><span class=\"c-sy\" data-no-translation=\"\">;<\/span><\/div><div id=\"c-6362a665943fe624866205-7\" class=\"c-line\"><span class=\"c-sy\" data-no-translation=\"\">}<\/span><\/div><div id=\"c-6362a665943fe624866205-8\" class=\"c-line\">\u00a0<\/div><div id=\"c-6362a665943fe624866205-9\" class=\"c-line\"><span class=\"c-c\">\/\/ Function to find the maximum subarray sum using divide-and-conquer<\/span><\/div><div id=\"c-6362a665943fe624866205-10\" class=\"c-line\"><span class=\"c-t\" data-no-translation=\"\">int<\/span> <span class=\"c-e\" data-no-translation=\"\">maximum_sum<\/span><span class=\"c-sy\" data-no-translation=\"\">(<\/span><span class=\"c-t\" data-no-translation=\"\">int<\/span> <span class=\"c-v\" data-no-translation=\"\">nums<\/span><span class=\"c-sy\" data-no-translation=\"\">[<\/span><span class=\"c-sy\" data-no-translation=\"\">]<\/span><span class=\"c-sy\" data-no-translation=\"\">,<\/span> <span class=\"c-t\" data-no-translation=\"\">int<\/span> <span class=\"c-v\" data-no-translation=\"\">low<\/span><span class=\"c-sy\" data-no-translation=\"\">,<\/span> <span class=\"c-t\" data-no-translation=\"\">int<\/span> <span class=\"c-v\" data-no-translation=\"\">high<\/span><span class=\"c-sy\" data-no-translation=\"\">)<\/span><\/div><div id=\"c-6362a665943fe624866205-11\" class=\"c-line\"><span class=\"c-sy\" data-no-translation=\"\">{<\/span><\/div><div id=\"c-6362a665943fe624866205-12\" class=\"c-line\"><span class=\"c-h\" data-no-translation=\"\">\u00a0\u00a0\u00a0\u00a0<\/span><span class=\"c-c\">\/\/ If the array contains 0 or 1 element<\/span><\/div><div id=\"c-6362a665943fe624866205-13\" class=\"c-line\"><span class=\"c-h\" data-no-translation=\"\">\u00a0\u00a0\u00a0\u00a0<\/span><span class=\"c-st\" data-no-translation=\"\">if<\/span> <span class=\"c-sy\" data-no-translation=\"\">(<\/span><span class=\"c-v\" data-no-translation=\"\">high<\/span> <span class=\"c-o\" data-no-translation=\"\">&lt;=<\/span> <span class=\"c-v\" data-no-translation=\"\">low<\/span><span class=\"c-sy\" data-no-translation=\"\">)<\/span> <span class=\"c-sy\" data-no-translation=\"\">{<\/span><\/div><div id=\"c-6362a665943fe624866205-14\" class=\"c-line\"><span class=\"c-h\" data-no-translation=\"\">\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/span><span class=\"c-st\" data-no-translation=\"\">return<\/span> <span class=\"c-v\" data-no-translation=\"\">nums<\/span><span class=\"c-sy\" data-no-translation=\"\">[<\/span><span class=\"c-v\" data-no-translation=\"\">low<\/span><span class=\"c-sy\" data-no-translation=\"\">]<\/span><span class=\"c-sy\" data-no-translation=\"\">;<\/span><\/div><div id=\"c-6362a665943fe624866205-15\" class=\"c-line\"><span class=\"c-h\" data-no-translation=\"\">\u00a0\u00a0\u00a0\u00a0<\/span><span class=\"c-sy\" data-no-translation=\"\">}<\/span><\/div><div id=\"c-6362a665943fe624866205-16\" class=\"c-line\">\u00a0<\/div><div id=\"c-6362a665943fe624866205-17\" class=\"c-line\"><span class=\"c-h\" data-no-translation=\"\">\u00a0\u00a0\u00a0\u00a0<\/span><span class=\"c-c\">\/\/ Find the middle array element<\/span><\/div><div id=\"c-6362a665943fe624866205-18\" class=\"c-line\"><span class=\"c-h\" data-no-translation=\"\">\u00a0\u00a0\u00a0\u00a0<\/span><span class=\"c-t\" data-no-translation=\"\">int<\/span> <span class=\"c-v\" data-no-translation=\"\">mid<\/span> <span class=\"c-o\" data-no-translation=\"\">=<\/span> <span class=\"c-sy\" data-no-translation=\"\">(<\/span><span class=\"c-v\" data-no-translation=\"\">low<\/span> <span class=\"c-o\" data-no-translation=\"\">+<\/span> <span class=\"c-v\" data-no-translation=\"\">high<\/span><span class=\"c-sy\" data-no-translation=\"\">)<\/span> <span class=\"c-o\" data-no-translation=\"\">\/<\/span> <span class=\"c-cn\" data-no-translation=\"\">2<\/span><span class=\"c-sy\" data-no-translation=\"\">;<\/span><\/div><div id=\"c-6362a665943fe624866205-19\" class=\"c-line\">\u00a0<\/div><div id=\"c-6362a665943fe624866205-20\" class=\"c-line\"><span class=\"c-h\" data-no-translation=\"\">\u00a0\u00a0\u00a0\u00a0<\/span><span class=\"c-c\">\/\/ Find maximum subarray sum for the left subarray,<\/span><\/div><div id=\"c-6362a665943fe624866205-21\" class=\"c-line\"><span class=\"c-h\" data-no-translation=\"\">\u00a0\u00a0\u00a0\u00a0<\/span><span class=\"c-c\">\/\/ including the middle element<\/span><\/div><div id=\"c-6362a665943fe624866205-22\" class=\"c-line\"><span class=\"c-h\" data-no-translation=\"\">\u00a0\u00a0\u00a0\u00a0<\/span><span class=\"c-t\" data-no-translation=\"\">int<\/span> <span class=\"c-v\" data-no-translation=\"\">left_max<\/span> <span class=\"c-o\" data-no-translation=\"\">=<\/span> <span class=\"c-v\" data-no-translation=\"\">INT_MIN<\/span><span class=\"c-sy\" data-no-translation=\"\">;<\/span><\/div><div id=\"c-6362a665943fe624866205-23\" class=\"c-line\"><span class=\"c-h\" data-no-translation=\"\">\u00a0\u00a0\u00a0\u00a0<\/span><span class=\"c-t\" data-no-translation=\"\">int<\/span> <span class=\"c-v\" data-no-translation=\"\">sum<\/span> <span class=\"c-o\" data-no-translation=\"\">=<\/span> <span class=\"c-cn\" data-no-translation=\"\">0<\/span><span class=\"c-sy\" data-no-translation=\"\">;<\/span><\/div><div id=\"c-6362a665943fe624866205-24\" class=\"c-line\"><span class=\"c-h\" data-no-translation=\"\">\u00a0\u00a0\u00a0\u00a0<\/span><span class=\"c-st\" data-no-translation=\"\">for<\/span> <span class=\"c-sy\" data-no-translation=\"\">(<\/span><span class=\"c-t\" data-no-translation=\"\">int<\/span> <span class=\"c-v\" data-no-translation=\"\">i<\/span> <span class=\"c-o\" data-no-translation=\"\">=<\/span> <span class=\"c-v\" data-no-translation=\"\">mid<\/span><span class=\"c-sy\" data-no-translation=\"\">;<\/span> <span class=\"c-v\" data-no-translation=\"\">i<\/span> <span class=\"c-o\" data-no-translation=\"\">&gt;=<\/span> <span class=\"c-v\" data-no-translation=\"\">low<\/span><span class=\"c-sy\" data-no-translation=\"\">;<\/span> <span class=\"c-v\" data-no-translation=\"\">i<\/span><span class=\"c-o\" data-no-translation=\"\">&#8212;<\/span><span class=\"c-sy\" data-no-translation=\"\">)<\/span><\/div><div id=\"c-6362a665943fe624866205-25\" class=\"c-line\"><span class=\"c-h\" data-no-translation=\"\">\u00a0\u00a0\u00a0\u00a0<\/span><span class=\"c-sy\" data-no-translation=\"\">{<\/span><\/div><div id=\"c-6362a665943fe624866205-26\" class=\"c-line\"><span class=\"c-h\" data-no-translation=\"\">\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/span><span class=\"c-v\" data-no-translation=\"\">sum<\/span> <span class=\"c-o\" data-no-translation=\"\">+=<\/span> <span class=\"c-v\" data-no-translation=\"\">nums<\/span><span class=\"c-sy\" data-no-translation=\"\">[<\/span><span class=\"c-v\" data-no-translation=\"\">i<\/span><span class=\"c-sy\" data-no-translation=\"\">]<\/span><span class=\"c-sy\" data-no-translation=\"\">;<\/span><\/div><div id=\"c-6362a665943fe624866205-27\" class=\"c-line\"><span class=\"c-h\" data-no-translation=\"\">\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/span><span class=\"c-st\" data-no-translation=\"\">if<\/span> <span class=\"c-sy\" data-no-translation=\"\">(<\/span><span class=\"c-v\" data-no-translation=\"\">sum<\/span> <span class=\"c-o\" data-no-translation=\"\">&gt;<\/span> <span class=\"c-v\" data-no-translation=\"\">left_max<\/span><span class=\"c-sy\" data-no-translation=\"\">)<\/span> <span class=\"c-sy\" data-no-translation=\"\">{<\/span><\/div><div id=\"c-6362a665943fe624866205-28\" class=\"c-line\"><span class=\"c-h\" data-no-translation=\"\">\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/span><span class=\"c-v\" data-no-translation=\"\">left_max<\/span> <span class=\"c-o\" data-no-translation=\"\">=<\/span> <span class=\"c-v\" data-no-translation=\"\">sum<\/span><span class=\"c-sy\" data-no-translation=\"\">;<\/span><\/div><div id=\"c-6362a665943fe624866205-29\" class=\"c-line\"><span class=\"c-h\" data-no-translation=\"\">\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/span><span class=\"c-sy\" data-no-translation=\"\">}<\/span><\/div><div id=\"c-6362a665943fe624866205-30\" class=\"c-line\"><span class=\"c-h\" data-no-translation=\"\">\u00a0\u00a0\u00a0\u00a0<\/span><span class=\"c-sy\" data-no-translation=\"\">}<\/span><\/div><div id=\"c-6362a665943fe624866205-31\" class=\"c-line\">\u00a0<\/div><div id=\"c-6362a665943fe624866205-32\" class=\"c-line\"><span class=\"c-h\" data-no-translation=\"\">\u00a0\u00a0\u00a0\u00a0<\/span><span class=\"c-c\">\/\/ Find maximum subarray sum for the right subarray,<\/span><\/div><div id=\"c-6362a665943fe624866205-33\" class=\"c-line\"><span class=\"c-h\" data-no-translation=\"\">\u00a0\u00a0\u00a0\u00a0<\/span><span class=\"c-c\">\/\/ excluding the middle element<\/span><\/div><div id=\"c-6362a665943fe624866205-34\" class=\"c-line\"><span class=\"c-h\" data-no-translation=\"\">\u00a0\u00a0\u00a0\u00a0<\/span><span class=\"c-t\" data-no-translation=\"\">int<\/span> <span class=\"c-v\" data-no-translation=\"\">right_max<\/span> <span class=\"c-o\" data-no-translation=\"\">=<\/span> <span class=\"c-v\" data-no-translation=\"\">INT_MIN<\/span><span class=\"c-sy\" data-no-translation=\"\">;<\/span><\/div><div id=\"c-6362a665943fe624866205-35\" class=\"c-line\"><span class=\"c-h\" data-no-translation=\"\">\u00a0\u00a0\u00a0\u00a0<\/span><span class=\"c-v\" data-no-translation=\"\">sum<\/span> <span class=\"c-o\" data-no-translation=\"\">=<\/span> <span class=\"c-cn\" data-no-translation=\"\">0<\/span><span class=\"c-sy\" data-no-translation=\"\">;<\/span><span class=\"c-h\" data-no-translation=\"\">\u00a0\u00a0\u00a0\u00a0<\/span><span class=\"c-c\">\/\/ reset sum to 0<\/span><\/div><div id=\"c-6362a665943fe624866205-36\" class=\"c-line\"><span class=\"c-h\" data-no-translation=\"\">\u00a0\u00a0\u00a0\u00a0<\/span><span class=\"c-st\" data-no-translation=\"\">for<\/span> <span class=\"c-sy\" data-no-translation=\"\">(<\/span><span class=\"c-t\" data-no-translation=\"\">int<\/span> <span class=\"c-v\" data-no-translation=\"\">i<\/span> <span class=\"c-o\" data-no-translation=\"\">=<\/span> <span class=\"c-v\" data-no-translation=\"\">mid<\/span> <span class=\"c-o\" data-no-translation=\"\">+<\/span> <span class=\"c-cn\" data-no-translation=\"\">1<\/span><span class=\"c-sy\" data-no-translation=\"\">;<\/span> <span class=\"c-v\" data-no-translation=\"\">i<\/span> <span class=\"c-o\" data-no-translation=\"\">&lt;=<\/span> <span class=\"c-v\" data-no-translation=\"\">high<\/span><span class=\"c-sy\" data-no-translation=\"\">;<\/span> <span class=\"c-v\" data-no-translation=\"\">i<\/span><span class=\"c-o\" data-no-translation=\"\">++<\/span><span class=\"c-sy\" data-no-translation=\"\">)<\/span><\/div><div id=\"c-6362a665943fe624866205-37\" class=\"c-line\"><span class=\"c-h\" data-no-translation=\"\">\u00a0\u00a0\u00a0\u00a0<\/span><span class=\"c-sy\" data-no-translation=\"\">{<\/span><\/div><div id=\"c-6362a665943fe624866205-38\" class=\"c-line\"><span class=\"c-h\" data-no-translation=\"\">\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/span><span class=\"c-v\" data-no-translation=\"\">sum<\/span> <span class=\"c-o\" data-no-translation=\"\">+=<\/span> <span class=\"c-v\" data-no-translation=\"\">nums<\/span><span class=\"c-sy\" data-no-translation=\"\">[<\/span><span class=\"c-v\" data-no-translation=\"\">i<\/span><span class=\"c-sy\" data-no-translation=\"\">]<\/span><span class=\"c-sy\" data-no-translation=\"\">;<\/span><\/div><div id=\"c-6362a665943fe624866205-39\" class=\"c-line\"><span class=\"c-h\" data-no-translation=\"\">\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/span><span class=\"c-st\" data-no-translation=\"\">if<\/span> <span class=\"c-sy\" data-no-translation=\"\">(<\/span><span class=\"c-v\" data-no-translation=\"\">sum<\/span> <span class=\"c-o\" data-no-translation=\"\">&gt;<\/span> <span class=\"c-v\" data-no-translation=\"\">right_max<\/span><span class=\"c-sy\" data-no-translation=\"\">)<\/span> <span class=\"c-sy\" data-no-translation=\"\">{<\/span><\/div><div id=\"c-6362a665943fe624866205-40\" class=\"c-line\"><span class=\"c-h\" data-no-translation=\"\">\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/span><span class=\"c-v\" data-no-translation=\"\">right_max<\/span> <span class=\"c-o\" data-no-translation=\"\">=<\/span> <span class=\"c-v\" data-no-translation=\"\">sum<\/span><span class=\"c-sy\" data-no-translation=\"\">;<\/span><\/div><div id=\"c-6362a665943fe624866205-41\" class=\"c-line\"><span class=\"c-h\" data-no-translation=\"\">\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/span><span class=\"c-sy\" data-no-translation=\"\">}<\/span><\/div><div id=\"c-6362a665943fe624866205-42\" class=\"c-line\"><span class=\"c-h\" data-no-translation=\"\">\u00a0\u00a0\u00a0\u00a0<\/span><span class=\"c-sy\" data-no-translation=\"\">}<\/span><\/div><div id=\"c-6362a665943fe624866205-43\" class=\"c-line\">\u00a0<\/div><div id=\"c-6362a665943fe624866205-44\" class=\"c-line\"><span class=\"c-h\" data-no-translation=\"\">\u00a0\u00a0\u00a0\u00a0<\/span><span class=\"c-c\">\/\/ Recursively find the maximum subarray sum for the left<\/span><\/div><div id=\"c-6362a665943fe624866205-45\" class=\"c-line\"><span class=\"c-h\" data-no-translation=\"\">\u00a0\u00a0\u00a0\u00a0<\/span><span class=\"c-c\">\/\/ and right subarray, and take maximum<\/span><\/div><div id=\"c-6362a665943fe624866205-46\" class=\"c-line\"><span class=\"c-h\" data-no-translation=\"\">\u00a0\u00a0\u00a0\u00a0<\/span><span class=\"c-t\" data-no-translation=\"\">int<\/span> <span class=\"c-v\" data-no-translation=\"\">max_left_right<\/span> <span class=\"c-o\" data-no-translation=\"\">=<\/span> <span class=\"c-e\" data-no-translation=\"\">max<\/span><span class=\"c-sy\" data-no-translation=\"\">(<\/span><span class=\"c-e\" data-no-translation=\"\">maximum_sum<\/span><span class=\"c-sy\" data-no-translation=\"\">(<\/span><span class=\"c-v\" data-no-translation=\"\">nums<\/span><span class=\"c-sy\" data-no-translation=\"\">,<\/span> <span class=\"c-v\" data-no-translation=\"\">low<\/span><span class=\"c-sy\" data-no-translation=\"\">,<\/span> <span class=\"c-v\" data-no-translation=\"\">mid<\/span><span class=\"c-sy\" data-no-translation=\"\">)<\/span><span class=\"c-sy\" data-no-translation=\"\">,<\/span><\/div><div id=\"c-6362a665943fe624866205-47\" class=\"c-line\"><span class=\"c-h\" data-no-translation=\"\">\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/span><span class=\"c-e\" data-no-translation=\"\">maximum_sum<\/span><span class=\"c-sy\" data-no-translation=\"\">(<\/span><span class=\"c-v\" data-no-translation=\"\">nums<\/span><span class=\"c-sy\" data-no-translation=\"\">,<\/span> <span class=\"c-v\" data-no-translation=\"\">mid<\/span> <span class=\"c-o\" data-no-translation=\"\">+<\/span> <span class=\"c-cn\" data-no-translation=\"\">1<\/span><span class=\"c-sy\" data-no-translation=\"\">,<\/span> <span class=\"c-v\" data-no-translation=\"\">high<\/span><span class=\"c-sy\" data-no-translation=\"\">)<\/span><span class=\"c-sy\" data-no-translation=\"\">)<\/span><span class=\"c-sy\" data-no-translation=\"\">;<\/span><\/div><div id=\"c-6362a665943fe624866205-48\" class=\"c-line\">\u00a0<\/div><div id=\"c-6362a665943fe624866205-49\" class=\"c-line\"><span class=\"c-h\" data-no-translation=\"\">\u00a0\u00a0\u00a0\u00a0<\/span><span class=\"c-c\">\/\/ return the maximum of the three<\/span><\/div><div id=\"c-6362a665943fe624866205-50\" class=\"c-line\"><span class=\"c-h\" data-no-translation=\"\">\u00a0\u00a0\u00a0\u00a0<\/span><span class=\"c-st\" data-no-translation=\"\">return<\/span> <span class=\"c-e\" data-no-translation=\"\">max<\/span><span class=\"c-sy\" data-no-translation=\"\">(<\/span><span class=\"c-v\" data-no-translation=\"\">max_left_right<\/span><span class=\"c-sy\" data-no-translation=\"\">,<\/span> <span class=\"c-v\" data-no-translation=\"\">left_max<\/span> <span class=\"c-o\" data-no-translation=\"\">+<\/span> <span class=\"c-v\" data-no-translation=\"\">right_max<\/span><span class=\"c-sy\" data-no-translation=\"\">)<\/span><span class=\"c-sy\" data-no-translation=\"\">;<\/span><\/div><div id=\"c-6362a665943fe624866205-51\" class=\"c-line\"><span class=\"c-sy\" data-no-translation=\"\">}<\/span><\/div><div id=\"c-6362a665943fe624866205-52\" class=\"c-line\">\u00a0<\/div><div id=\"c-6362a665943fe624866205-53\" class=\"c-line\"><span class=\"c-t\" data-no-translation=\"\">int<\/span> <span class=\"c-e\" data-no-translation=\"\">main<\/span><span class=\"c-sy\" data-no-translation=\"\">(<\/span><span class=\"c-t\" data-no-translation=\"\">void<\/span><span class=\"c-sy\" data-no-translation=\"\">)<\/span><\/div><div id=\"c-6362a665943fe624866205-54\" class=\"c-line\"><span class=\"c-sy\" data-no-translation=\"\">{<\/span><\/div><div id=\"c-6362a665943fe624866205-55\" class=\"c-line\"><span class=\"c-h\" data-no-translation=\"\">\u00a0\u00a0\u00a0\u00a0<\/span><span class=\"c-t\" data-no-translation=\"\">int<\/span> <span class=\"c-v\" data-no-translation=\"\">arr<\/span><span class=\"c-sy\" data-no-translation=\"\">[<\/span><span class=\"c-sy\" data-no-translation=\"\">]<\/span> <span class=\"c-o\" data-no-translation=\"\">=<\/span> <span class=\"c-sy\" data-no-translation=\"\">{<\/span> <span class=\"c-cn\" data-no-translation=\"\">2<\/span><span class=\"c-sy\" data-no-translation=\"\">,<\/span> <span class=\"c-o\" data-no-translation=\"\">&#8211;<\/span><span class=\"c-cn\" data-no-translation=\"\">4<\/span><span class=\"c-sy\" data-no-translation=\"\">,<\/span> <span class=\"c-cn\" data-no-translation=\"\">1<\/span><span class=\"c-sy\" data-no-translation=\"\">,<\/span> <span class=\"c-cn\" data-no-translation=\"\">9<\/span><span class=\"c-sy\" data-no-translation=\"\">,<\/span> <span class=\"c-o\" data-no-translation=\"\">&#8211;<\/span><span class=\"c-cn\" data-no-translation=\"\">6<\/span><span class=\"c-sy\" data-no-translation=\"\">,<\/span> <span class=\"c-cn\" data-no-translation=\"\">7<\/span><span class=\"c-sy\" data-no-translation=\"\">,<\/span> <span class=\"c-o\" data-no-translation=\"\">&#8211;<\/span><span class=\"c-cn\" data-no-translation=\"\">3<\/span> <span class=\"c-sy\" data-no-translation=\"\">}<\/span><span class=\"c-sy\" data-no-translation=\"\">;<\/span><\/div><div id=\"c-6362a665943fe624866205-56\" class=\"c-line\"><span class=\"c-h\" data-no-translation=\"\">\u00a0\u00a0\u00a0\u00a0<\/span><span class=\"c-t\" data-no-translation=\"\">int<\/span> <span class=\"c-v\" data-no-translation=\"\">n<\/span> <span class=\"c-o\" data-no-translation=\"\">=<\/span> <span class=\"c-r\" data-no-translation=\"\">sizeof<\/span><span class=\"c-sy\" data-no-translation=\"\">(<\/span><span class=\"c-v\" data-no-translation=\"\">arr<\/span><span class=\"c-sy\" data-no-translation=\"\">)<\/span> <span class=\"c-o\" data-no-translation=\"\">\/<\/span> <span class=\"c-r\" data-no-translation=\"\">sizeof<\/span><span class=\"c-sy\" data-no-translation=\"\">(<\/span><span class=\"c-v\" data-no-translation=\"\">arr<\/span><span class=\"c-sy\" data-no-translation=\"\">[<\/span><span class=\"c-cn\" data-no-translation=\"\">0<\/span><span class=\"c-sy\" data-no-translation=\"\">]<\/span><span class=\"c-sy\" data-no-translation=\"\">)<\/span><span class=\"c-sy\" data-no-translation=\"\">;<\/span><\/div><div id=\"c-6362a665943fe624866205-57\" class=\"c-line\">\u00a0<\/div><div id=\"c-6362a665943fe624866205-58\" class=\"c-line\"><span class=\"c-h\" data-no-translation=\"\">\u00a0\u00a0\u00a0\u00a0<\/span><span class=\"c-r\" data-no-translation=\"\">printf<\/span><span class=\"c-sy\" data-no-translation=\"\">(<\/span><span class=\"c-s\" data-no-translation=\"\">\u00ab\u00a0The maximum sum of the subarray is %d\u00a0\u00bb<\/span><span class=\"c-sy\" data-no-translation=\"\">,<\/span><\/div><div id=\"c-6362a665943fe624866205-59\" class=\"c-line\"><span class=\"c-h\" data-no-translation=\"\">\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/span><span class=\"c-e\" data-no-translation=\"\">maximum_sum<\/span><span class=\"c-sy\" data-no-translation=\"\">(<\/span><span class=\"c-v\" data-no-translation=\"\">arr<\/span><span class=\"c-sy\" data-no-translation=\"\">,<\/span> <span class=\"c-cn\" data-no-translation=\"\">0<\/span><span class=\"c-sy\" data-no-translation=\"\">,<\/span> <span class=\"c-v\" data-no-translation=\"\">n<\/span> <span class=\"c-o\" data-no-translation=\"\">&#8211;<\/span> <span class=\"c-cn\" data-no-translation=\"\">1<\/span><span class=\"c-sy\" data-no-translation=\"\">)<\/span><span class=\"c-sy\" data-no-translation=\"\">)<\/span><span class=\"c-sy\" data-no-translation=\"\">;<\/span><\/div><div id=\"c-6362a665943fe624866205-60\" class=\"c-line\">\u00a0<\/div><div id=\"c-6362a665943fe624866205-61\" class=\"c-line\"><span class=\"c-h\" data-no-translation=\"\">\u00a0\u00a0\u00a0\u00a0<\/span><span class=\"c-st\" data-no-translation=\"\">return<\/span> <span class=\"c-cn\" data-no-translation=\"\">0<\/span><span class=\"c-sy\" data-no-translation=\"\">;<\/span><\/div><div id=\"c-6362a665943fe624866205-62\" class=\"c-line\"><span class=\"c-sy\" data-no-translation=\"\">}<\/span><\/div><\/div><\/td><\/tr><\/tbody><\/table><p>Nous pouvons facilement r\u00e9soudre ce probl\u00e8me en temps lin\u00e9aire en utilisant l&rsquo;algorithme de Kadane. L&rsquo;id\u00e9e est de maintenir un sous-tableau maximum (somme positive) \u00ab se terminant \u00bb \u00e0 chaque index du tableau donn\u00e9. Ce sous-tableau est soit vide (auquel cas sa somme est nulle) soit constitu\u00e9 d&rsquo;un \u00e9l\u00e9ment de plus que le sous-tableau maximum se terminant \u00e0 l&rsquo;indice pr\u00e9c\u00e9dent.<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-19234 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/kadane.png\" alt=\"algorithme kadanes\" width=\"688\" height=\"573\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/kadane.png 688w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/kadane-300x250.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/kadane-14x12.png 14w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/kadane-600x500.png 600w\" sizes=\"(max-width: 688px) 100vw, 688px\" \/><\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-f48080f elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"f48080f\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-d1339d3\" data-id=\"d1339d3\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-3075239 elementor-widget elementor-widget-heading\" data-id=\"3075239\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-12\"><\/span>Exercice 12<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-e8cf0f8 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"e8cf0f8\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-fe34891\" data-id=\"fe34891\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-c52cbf7 elementor-widget elementor-widget-text-editor\" data-id=\"c52cbf7\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>\u00c9tant donn\u00e9 un tableau d&rsquo;entiers, trouvez l&rsquo;\u00e9l\u00e9ment de pic qu&rsquo;il contient. Un \u00e9l\u00e9ment de pic est un \u00e9l\u00e9ment sup\u00e9rieur \u00e0 ses voisins. Il peut y avoir plusieurs \u00e9l\u00e9ments de pic dans un tableau et la solution doit signaler tout \u00e9l\u00e9ment de pic.<\/p><p>Un \u00e9l\u00e9ment A[i] d&rsquo;un tableau A est un \u00e9l\u00e9ment de pic s&rsquo;il n&rsquo;est pas plus petit que son ou ses voisins.<br \/>A[i-1] &lt;= A[i] &gt;= A[i+1] pour 0 &lt; i &lt; n-1<br \/>A[i-1] &lt;= A[i] si je = n \u2013 1<br \/>A[i] &gt;= A[i+1] si je = 0<\/p><p>Par exemple,<br \/>Entr\u00e9e : [8, 9, 10, 2, 5, 6]<br \/>Sortie : l&rsquo;\u00e9l\u00e9ment de pic est 10 (ou 6)<\/p><p><br \/>Entr\u00e9e : [8, 9, 10, 12, 15]<br \/>Sortie : l&rsquo;\u00e9l\u00e9ment de pic est 15<\/p><p><br \/>Entr\u00e9e : [10, 8, 6, 5, 3, 2]<br \/>Sortie : l&rsquo;\u00e9l\u00e9ment de pic est 10<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-d070a6e elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"d070a6e\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-dc4f160\" data-id=\"dc4f160\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-7e373e5 elementor-widget elementor-widget-toggle\" data-id=\"7e373e5\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-1321\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-1321\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-1321\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-1321\"><p>Une solution na\u00efve serait de tester tous les \u00e9l\u00e9ments pour le pic en ex\u00e9cutant une recherche lin\u00e9aire sur le tableau et de renvoyer l&rsquo;\u00e9l\u00e9ment le plus grand que ses voisins. Deux cas particuliers doivent \u00eatre trait\u00e9s. Si le tableau est tri\u00e9 par ordre d\u00e9croissant, son \u00e9l\u00e9ment de pic est le premier \u00e9l\u00e9ment. Si le tableau est tri\u00e9 par ordre croissant, l&rsquo;\u00e9l\u00e9ment de pic est le dernier. Le probl\u00e8me avec cette approche est que sa complexit\u00e9 temporelle dans le pire des cas est O(n), o\u00f9 n est la taille de l&rsquo;entr\u00e9e.<\/p><p>Nous pouvons facilement r\u00e9soudre ce probl\u00e8me en temps O(log(n)) en utilisant une id\u00e9e similaire \u00e0 l&rsquo;algorithme de recherche binaire. L&rsquo;id\u00e9e est de calculer l&rsquo;indice m\u00e9dian, et si l&rsquo;\u00e9l\u00e9ment du milieu est sup\u00e9rieur \u00e0 ses deux voisins, renvoyez l&rsquo;\u00e9l\u00e9ment car il s&rsquo;agit d&rsquo;un pic. Si le voisin droit de l&rsquo;index m\u00e9dian est sup\u00e9rieur \u00e0 l&rsquo;\u00e9l\u00e9ment du milieu, recherchez de mani\u00e8re r\u00e9cursive le pic sur le c\u00f4t\u00e9 droit du tableau. Si le voisin gauche de l&rsquo;index m\u00e9dian est sup\u00e9rieur \u00e0 l&rsquo;\u00e9l\u00e9ment du milieu, recherchez de mani\u00e8re r\u00e9cursive le pic dans le c\u00f4t\u00e9 gauche du tableau.<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-19236 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/picelement.png\" alt=\"pic \u00e9l\u00e9ment diviser pour r\u00e9gner\" width=\"727\" height=\"691\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/picelement.png 727w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/picelement-300x285.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/picelement-13x12.png 13w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/picelement-600x570.png 600w\" sizes=\"(max-width: 727px) 100vw, 727px\" \/><\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-4320699 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"4320699\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-fd3aa62\" data-id=\"fd3aa62\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-0a2eb87 elementor-widget elementor-widget-heading\" data-id=\"0a2eb87\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-13\"><\/span>Exercice 13<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-c7d5d4f elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"c7d5d4f\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-81653fe\" data-id=\"81653fe\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-ab1e541 elementor-widget elementor-widget-text-editor\" data-id=\"ab1e541\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>\u00c9tant donn\u00e9 un tableau tri\u00e9 avec \u00e9ventuellement des \u00e9l\u00e9ments en double, la t\u00e2che consiste \u00e0 trouver les index des premi\u00e8re et derni\u00e8re occurrences d&rsquo;un \u00e9l\u00e9ment x dans le tableau donn\u00e9.<\/p><p>Exemples:<\/p><p>Entr\u00e9e : tab[] = {1, 3, 5, 5, 5, 5, 67, 123, 125}, x = 5<br \/>Sortie : Premi\u00e8re occurrence = 2<br \/>Derni\u00e8re occurrence = 5<\/p><p>Entr\u00e9e : tab[] = {1, 3, 5, 5, 5, 5, 7, 123, 125 }, x = 7<br \/>Sortie : Premi\u00e8re occurrence = 6<br \/>Derni\u00e8re occurrence = 6<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-a1b3d5e elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"a1b3d5e\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-b249989\" data-id=\"b249989\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-bf50b3b elementor-widget elementor-widget-toggle\" data-id=\"bf50b3b\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-2001\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-2001\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-2001\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-2001\"><p>L&rsquo;id\u00e9e pour r\u00e9soudre ce probl\u00e8me est d&rsquo;it\u00e9rer sur les \u00e9l\u00e9ments d&rsquo;un tableau donn\u00e9 et de v\u00e9rifier les \u00e9l\u00e9ments donn\u00e9s dans un tableau\u00a0et de garder une trace de la premi\u00e8re et de la derni\u00e8re occurrence de l&rsquo;index de l&rsquo;\u00e9l\u00e9ment trouv\u00e9.<\/p><p>Ex\u00e9cutez une boucle for et for i = 0 to n-1<br \/>Prendre premier = -1 et dernier = -1<br \/>Lorsque nous trouvons un \u00e9l\u00e9ment pour la premi\u00e8re fois, nous mettons d&rsquo;abord \u00e0 jour = i<br \/>Nous mettons toujours \u00e0 jour last=i chaque fois que nous trouvons l&rsquo;\u00e9l\u00e9ment.<br \/>Nous imprimons en premier et en dernier.<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-19241 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/occurence.png\" alt=\"trouver occurence\" width=\"389\" height=\"574\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/occurence.png 389w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/occurence-203x300.png 203w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/occurence-8x12.png 8w\" sizes=\"(max-width: 389px) 100vw, 389px\" \/><\/p><p>Une approche efficace utilisant la recherche binaire\u00a0:<\/p><p>1. Pour la premi\u00e8re occurrence d&rsquo;un nombre<\/p><p>a) Si (\u00e9lev\u00e9 &gt;= faible)<br \/>b) Calculer moyen = faible + (\u00e9lev\u00e9 \u2013 faible)\/2\u00a0;<br \/>c) Si ((milieu == 0 || x &gt; arr[milieu-1]) &amp;&amp; arr[milieu] == x)<br \/>retour milieu;<br \/>d) Sinon si (x &gt; arr[moyen])<br \/>retourner premier(arr, (moyen + 1), haut, x, n);<br \/>e) Sinon<br \/>return first(arr, low, (mid -1), x, n);<br \/>f) Sinon retourner -1\u00a0;<\/p><p>2. Pour la derni\u00e8re occurrence d&rsquo;un nombre<\/p><p>a) si (haut &gt;= bas)<br \/>b) calculer moyen = faible + (\u00e9lev\u00e9 \u2013 faible)\/2\u00a0;<br \/>c)if( ( milieu == n-1 || x &lt; arr[milieu+1]) &amp;&amp; arr[milieu] == x )<br \/>retour milieu;<br \/>d) sinon si(x &lt; arr[milieu])<br \/>return last(arr, low, (mid -1), x, n);<br \/>e) d&rsquo;autre<br \/>return last(arr, (mid + 1), high, x, n);<br \/>f) sinon retourner -1\u00a0;<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-19242 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/occurence2.png\" alt=\"trouver occurence\" width=\"516\" height=\"686\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/occurence2.png 516w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/occurence2-226x300.png 226w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/occurence2-9x12.png 9w\" sizes=\"(max-width: 516px) 100vw, 516px\" \/><\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-8063df0 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"8063df0\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-b31f3a5\" data-id=\"b31f3a5\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-5fc7992 elementor-widget elementor-widget-heading\" data-id=\"5fc7992\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-14\"><\/span>Exercice 14<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-7d00fa1 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"7d00fa1\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-8feaffb\" data-id=\"8feaffb\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-a9a07ee elementor-widget elementor-widget-text-editor\" data-id=\"a9a07ee\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>\u00c9tant donn\u00e9 n b\u00e2timents rectangulaires dans une ville en 2 dimensions, calcule la ligne d&rsquo;horizon de ces b\u00e2timents, en \u00e9liminant les lignes cach\u00e9es. La t\u00e2che principale consiste \u00e0 visualiser les b\u00e2timents d&rsquo;un c\u00f4t\u00e9 et \u00e0 supprimer toutes les sections non visibles.<\/p><p>Tous les b\u00e2timents partagent un fond commun et chaque b\u00e2timent est repr\u00e9sent\u00e9 par un triplet (gauche, ht, droite)<\/p><p>&lsquo;gauche&rsquo; : est la coordonn\u00e9e x du c\u00f4t\u00e9 gauche (ou du mur).<br \/>&lsquo;right&rsquo; : est la coordonn\u00e9e x du c\u00f4t\u00e9 droit<br \/>\u2018ht\u2019 : est la hauteur du b\u00e2timent.<br \/>Une ligne d&rsquo;horizon est un ensemble de bandes rectangulaires. Une bande rectangulaire est repr\u00e9sent\u00e9e par une paire (gauche, ht) o\u00f9 gauche est la coordonn\u00e9e x du c\u00f4t\u00e9 gauche de la bande et ht est la hauteur de la bande.<\/p><p>Exemples:<\/p><p>Entr\u00e9e\u00a0: tableau de b\u00e2timents<br \/>{ (1, 11, 5), (2, 6, 7), (3, 13, 9), (12, 7, 16), (14, 3, 25),<br \/>(19, 18, 22), (23, 13, 29), (24, 4, 28) }<\/p><p>Sortie\u00a0: Skyline (un ensemble de bandes rectangulaires)<br \/>Une bande a la coordonn\u00e9e x du c\u00f4t\u00e9 gauche et de la hauteur<br \/>(1, 11), (3, 13), (9, 0), (12, 7), (16, 3), (19, 18),<br \/>(22, 3), (25, 0)<\/p><p>L&rsquo;image ci-dessous est pour l&rsquo;entr\u00e9e 1\u00a0:<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-19247 size-medium\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/SkyLineProblem-300x192.png\" alt=\"SkyLine Problem\" width=\"300\" height=\"192\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/SkyLineProblem-300x192.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/SkyLineProblem-18x12.png 18w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/SkyLineProblem.png 331w\" sizes=\"(max-width: 300px) 100vw, 300px\" \/><\/p><p>Nous pouvons trouver Skyline en temps \u0398(nLogn) en utilisant Divide and Conquer. L&rsquo;id\u00e9e est similaire \u00e0 Merge Sort, diviser l&rsquo;ensemble donn\u00e9 de b\u00e2timents en deux sous-ensembles. Construisez r\u00e9cursivement l&rsquo;horizon pour deux moiti\u00e9s et fusionnez enfin les deux horizons.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-b83a2b7 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"b83a2b7\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-351afab\" data-id=\"351afab\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-c64c4d2 elementor-widget elementor-widget-toggle\" data-id=\"c64c4d2\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-2071\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-2071\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-2071\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-2071\"><p>L&rsquo;id\u00e9e est similaire \u00e0 la fusion du tri par fusion, commencez par les premi\u00e8res bandes de deux horizons, comparez les coordonn\u00e9es x. Choisissez la bande avec la plus petite coordonn\u00e9e x et ajoutez-la au r\u00e9sultat. La hauteur de la bande ajout\u00e9e est consid\u00e9r\u00e9e comme le maximum des hauteurs actuelles de skyline1 et skyline2.<\/p><p>La hauteur de la nouvelle bande est toujours obtenue en prenant au maximum les suivants<\/p><p>(a) Hauteur actuelle de skyline1, dites &lsquo;h1&rsquo;.<br \/>(b) Hauteur actuelle de skyline2, dites &lsquo;h2&rsquo;<\/p><p>h1 et h2 sont initialis\u00e9s \u00e0 0. h1 est mis \u00e0 jour lorsqu&rsquo;une bande de SkyLine1 est ajout\u00e9e au r\u00e9sultat et h2 est mis \u00e0 jour lorsqu&rsquo;une bande de SkyLine2 est ajout\u00e9e.<br \/><br \/>Skyline1 = {(1, 11), (3, 13), (9, 0), (12, 7), (16, 0)}<br \/>Skyline2 = {(14, 3), (19, 18), (22, 3), (23, 13), (29, 0)}<br \/>R\u00e9sultat = {}<br \/>h1 = 0, h2 = 0<br \/><br \/>Comparez (1, 11) et (14, 3). \u00c9tant donn\u00e9 que la premi\u00e8re bande a un x gauche plus petit, ajoutez-le au r\u00e9sultat et incr\u00e9mentez l&rsquo;index pour Skyline1.<br \/>h1 = 11, nouvelle hauteur = max(11, 0)<br \/>R\u00e9sultat = {(1, 11)}<\/p><p>Comparez (3, 13) et (14, 3). \u00c9tant donn\u00e9 que la premi\u00e8re bande a un x gauche plus petit, ajoutez-le au r\u00e9sultat et incr\u00e9mentez l&rsquo;index pour Skyline1<br \/>h1 = 13, nouvelle hauteur = max(13, 0)<br \/>R\u00e9sultat = {(1, 11), (3, 13)}<br \/><br \/>De m\u00eame (9, 0) et (12, 7) sont additionn\u00e9s.<br \/>h1 = 7, nouvelle hauteur = max(7, 0) = 7<br \/>R\u00e9sultat = {(1, 11), (3, 13), (9, 0), (12, 7)}<\/p><p>Comparez (16, 0) et (14, 3). \u00c9tant donn\u00e9 que la deuxi\u00e8me bande a un x gauche plus petit, elle est ajout\u00e9e au r\u00e9sultat.<br \/>h2 = 3, nouvelle hauteur = max(7, 3) = 7<br \/>R\u00e9sultat = {(1, 11), (3, 13), (9, 0), (12, 7), (14, 7)}<\/p><p>Comparez (16, 0) et (19, 18). Puisque la premi\u00e8re bande a un x gauche plus petit, elle est ajout\u00e9e au r\u00e9sultat.<br \/>h1 = 0, nouvelle hauteur = max(0, 3) = 3<br \/>R\u00e9sultat = {(1, 11), (3, 13), (9, 0), (12, 7), (14, 7), (16, 3)}<\/p><p>Puisque Skyline1 n&rsquo;a plus d&rsquo;\u00e9l\u00e9ments, tous les \u00e9l\u00e9ments restants de Skyline2 sont ajout\u00e9s<br \/>R\u00e9sultat = {(1, 11), (3, 13), (9, 0), (12, 7), (14, 7), (16, 3),<br \/>(19, 18), (22, 3), (23, 13), (29, 0)}<\/p><p>Une observation concernant la sortie ci-dessus est que la bande (14, 7) est redondante (il existe d\u00e9j\u00e0 une bande de m\u00eame hauteur). Nous supprimons tous les \u00e9l\u00e9ments redondants<br \/>bandes.<br \/>R\u00e9sultat = {(1, 11), (3, 13), (9, 0), (12, 7), (16, 3), (19, 18),<br \/>(22, 3), (23, 13), (29, 0)}<\/p><p>Dans le code ci-dessous, la redondance est g\u00e9r\u00e9e en n&rsquo;ajoutant pas de bande si la bande pr\u00e9c\u00e9dente dans le r\u00e9sultat a la m\u00eame hauteur.<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-19248 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/skyline.png\" alt=\"skyline diviser pour r\u00e9gner\" width=\"753\" height=\"690\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/skyline.png 753w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/skyline-300x275.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/skyline-13x12.png 13w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/skyline-600x550.png 600w\" sizes=\"(max-width: 753px) 100vw, 753px\" \/><\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-19249 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/skyline2.png\" alt=\"skyline diviser pour r\u00e9gner\" width=\"778\" height=\"641\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/skyline2.png 778w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/skyline2-300x247.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/skyline2-768x633.png 768w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/skyline2-15x12.png 15w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/skyline2-600x494.png 600w\" sizes=\"(max-width: 778px) 100vw, 778px\" \/><\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-e3692cf elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"e3692cf\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-a2aaf7e\" data-id=\"a2aaf7e\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-f1248ab elementor-widget elementor-widget-heading\" data-id=\"f1248ab\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-15\"><\/span>Exercice 15<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-da20c97 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"da20c97\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-7c92446\" data-id=\"7c92446\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-d80f3ad elementor-widget elementor-widget-text-editor\" data-id=\"d80f3ad\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>\u00c9tant donn\u00e9 un tableau de citations d&rsquo;entiers o\u00f9 citations[i] est le nombre de citations qu&rsquo;un chercheur a re\u00e7ues pour son i\u00e8me article et les citations sont tri\u00e9es par ordre croissant, retournez calculer l&rsquo;index h du chercheur.<\/p><p>Selon la d\u00e9finition de h-index sur Wikipedia : un scientifique a un index h si h de ses n articles ont au moins h citations chacun, et les autres n \u2212 h articles n&rsquo;ont pas plus de h citations chacun.<\/p><p>S&rsquo;il existe plusieurs valeurs possibles pour h, la valeur maximale est prise comme indice h.<\/p><p>Entr\u00e9e : citations = [0,1,3,5,6]<br \/>Sortie\u00a0: 3<br \/>Explication : [0,1,3,5,6] signifie que le chercheur a 5 articles au total et chacun d&rsquo;eux a re\u00e7u respectivement 0, 1, 3, 5, 6 citations.<\/p><p>\u00c9tant donn\u00e9 que le chercheur a 3 articles avec au moins 3 citations chacun et les deux autres avec pas plus de 3 citations chacun, leur h-index est de 3.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-d3d0f12 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"d3d0f12\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-cfb4c70\" data-id=\"cfb4c70\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-ea0f453 elementor-widget elementor-widget-toggle\" data-id=\"ea0f453\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-2451\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-2451\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-2451\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-2451\"><p>Juste une recherche binaire, \u00e0 chaque fois v\u00e9rifier les citations[mid]<\/p><p>cas 1 : citations[mid] == len-mid, alors cela signifie qu&rsquo;il y a des citations[mid] articles qui ont au moins citations[mid] citations.<\/p><p>cas 2 : citations[mid] &gt; len-mid, alors cela signifie qu&rsquo;il y a des citations[mid] articles qui ont plus de citations[mid] citations, donc nous devrions continuer \u00e0 chercher dans la moiti\u00e9 gauche<\/p><p>cas 3 : citations[mid] &lt; len-mid, il faut continuer la recherche dans la partie droite<\/p><p>Apr\u00e8s it\u00e9ration, il est garanti que right+1 est celui que nous devons trouver (c&rsquo;est-\u00e0-dire que len-(right+1) papiers a au moins len-(righ+1) citations)<\/p><p>L&rsquo;algorithme suivant est \u00e9crit sous forme it\u00e9rative mais c&rsquo;est bien du Diviser pour R\u00e9gner :<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-19250 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/Hindex.png\" alt=\"H-index diviser pour r\u00e9gner\" width=\"473\" height=\"310\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/Hindex.png 473w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/Hindex-300x197.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/Hindex-18x12.png 18w\" sizes=\"(max-width: 473px) 100vw, 473px\" \/><\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-b8b318b elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"b8b318b\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-4a24b56\" data-id=\"4a24b56\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-3efec76 elementor-widget elementor-widget-heading\" data-id=\"3efec76\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-16\"><\/span>Exercice 16<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-11e21a5 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"11e21a5\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-c77b27a\" data-id=\"c77b27a\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-02efd28 elementor-widget elementor-widget-text-editor\" data-id=\"02efd28\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>Dans le probl\u00e8me \u00ab Koko Eating Bananas \u00bb, on nous donne un tableau de taille n qui contient le nombre de bananes dans chaque tas. En une heure, Koko peut manger au maximum\u00a0K\u00a0bananes. Si le tas contient moins de K bananes, dans ce cas si Koko termine toutes les bananes de ce tas, elle ne peut pas commencer \u00e0 manger des bananes d&rsquo;un autre tas dans la m\u00eame heure.<\/p><p>Koko veut manger toutes les bananes en H heures. Nous sommes cens\u00e9s trouver la valeur minimale de K.<\/p><p><span class=\"enlighter-text\">piles = <\/span><span class=\"enlighter-g1\">[<\/span><span class=\"enlighter-n1\">30<\/span><span class=\"enlighter-text\">,<\/span><span class=\"enlighter-n1\">11<\/span><span class=\"enlighter-text\">,<\/span><span class=\"enlighter-n1\">23<\/span><span class=\"enlighter-text\">,<\/span><span class=\"enlighter-n1\">4<\/span><span class=\"enlighter-text\">,<\/span><span class=\"enlighter-n1\">20<\/span><span class=\"enlighter-g1\">]<\/span><span class=\"enlighter-text\">, H = <\/span><span class=\"enlighter-n1\">6. Ici la r\u00e9ponse est 23.<\/span><\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-19251 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/banana.webp\" alt=\"\" width=\"566\" height=\"333\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/banana.webp 566w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/banana-300x177.webp 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/banana-18x12.webp 18w\" sizes=\"(max-width: 566px) 100vw, 566px\" \/><\/p><p>Koko mangera des bananes de cette mani\u00e8re pour manger toutes les bananes en 6 heures :<\/p><p>Premi\u00e8re heure : 23<\/p><p>Deuxi\u00e8me heure\u00a0: 7<\/p><p>Troisi\u00e8me heure : 11<\/p><p>Quatri\u00e8me heure\u00a0: 23<\/p><p>Cinqui\u00e8me heure\u00a0: 4<\/p><p>Sixi\u00e8me heure\u00a0: 20<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-c802667 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"c802667\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-ce0e10f\" data-id=\"ce0e10f\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-3db5fea elementor-widget elementor-widget-toggle\" data-id=\"3db5fea\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-6471\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-6471\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-6471\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-6471\"><p>La premi\u00e8re et la plus importante chose pour r\u00e9soudre ce probl\u00e8me est de faire ressortir des observations. Voici quelques observations pour notre intervalle de recherche\u00a0:<\/p><p>Koko doit manger au moins une banane par heure. C&rsquo;est donc la valeur minimale de K. nommons-le comme Start<\/p><p>Nous pouvons limiter le nombre maximum de bananes que Koko peut manger en une heure au nombre maximum de bananes dans un tas parmi tous les tas. Il s&rsquo;agit donc de la valeur maximale de K. Appelons-la End.<\/p><p>Nous avons maintenant notre intervalle de recherche. Supposons que la taille de l&rsquo;intervalle soit Longueur et que le nombre de piles soit n. L&rsquo;approche na\u00efve pourrait \u00eatre de v\u00e9rifier chaque valeur dans l&rsquo;intervalle. si pour cette valeur de K Koko peut manger toutes les bananes en heure H avec succ\u00e8s, choisissez le minimum d&rsquo;entre elles. La complexit\u00e9 temporelle pour l&rsquo;approche na\u00efve sera Longueur*n dans le pire des cas.<\/p><p>Nous pouvons am\u00e9liorer la complexit\u00e9 temporelle en utilisant la recherche binaire \u00e0 la place de la recherche lin\u00e9aire. L&rsquo;algorithme est \u00e9crit en it\u00e9ratif mais il s&rsquo;agit bien d&rsquo;une approche Diviser pour R\u00e9gner<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-19252 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/banana2.png\" alt=\"\" width=\"611\" height=\"362\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/banana2.png 611w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/banana2-300x178.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/banana2-18x12.png 18w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/banana2-445x265.png 445w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/banana2-600x355.png 600w\" sizes=\"(max-width: 611px) 100vw, 611px\" \/><\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-f2763a4 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"f2763a4\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-855a927\" data-id=\"855a927\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-916ad6b elementor-widget elementor-widget-heading\" data-id=\"916ad6b\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-17\"><\/span>Exercice 17<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-223ebdd elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"223ebdd\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-da59354\" data-id=\"da59354\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-0d58c2e elementor-widget elementor-widget-text-editor\" data-id=\"0d58c2e\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>\u00c9tant donn\u00e9 un tableau tri\u00e9 d&rsquo;entiers distincts non n\u00e9gatifs, trouvez le plus petit \u00e9l\u00e9ment non n\u00e9gatif manquant dans celui-ci.<\/p><p>Par exemple,<\/p><p>Entr\u00e9e : nombres[] = [0, 1, 2, 6, 9, 11, 15]<br \/>R\u00e9sultat : Le plus petit \u00e9l\u00e9ment manquant est 3<br \/><br \/><br \/>Entr\u00e9e : nombres[] = [1, 2, 3, 4, 6, 9, 11, 15]<br \/>Sortie\u00a0: le plus petit \u00e9l\u00e9ment manquant est 0<br \/><br \/><br \/>Entr\u00e9e : nombres[] = [0, 1, 2, 3, 4, 5, 6]<br \/>R\u00e9sultat : Le plus petit \u00e9l\u00e9ment manquant est 7<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-32468fd elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"32468fd\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-6d91b69\" data-id=\"6d91b69\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-ec507a4 elementor-widget elementor-widget-toggle\" data-id=\"ec507a4\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-2471\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-2471\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-2471\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-2471\"><p>Une solution na\u00efve consisterait \u00e0 ex\u00e9cuter une recherche lin\u00e9aire sur le tableau et \u00e0 renvoyer le premier index, qui ne correspond pas \u00e0 sa valeur. Si aucune discordance ne se produit, renvoyez la taille du tableau. Le probl\u00e8me avec cette approche est que sa complexit\u00e9 temporelle dans le pire des cas est O(n), o\u00f9 n est la taille de l&rsquo;entr\u00e9e. Cette solution ne profite pas non plus du fait que l&rsquo;entr\u00e9e est tri\u00e9e.<\/p><p>Nous pouvons facilement r\u00e9soudre ce probl\u00e8me en temps O(log(n)) en modifiant l&rsquo;algorithme de recherche binaire (\u00e9quivalent au Diviser pour R\u00e9gner). L&rsquo;id\u00e9e est de comparer l&rsquo;indice m\u00e9dian avec l&rsquo;\u00e9l\u00e9ment m\u00e9dian. Si les deux sont identiques, alors la non-concordance se trouve dans le bon sous-tableau ; sinon, il se trouve dans le sous-tableau de gauche. Donc, nous \u00e9cartons une moiti\u00e9 en cons\u00e9quence et revenons pour l&rsquo;autre.<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-19257 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/missing.png\" alt=\"plus petit \u00e9l\u00e9ment manquant\" width=\"593\" height=\"515\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/missing.png 593w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/missing-300x261.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/missing-14x12.png 14w\" sizes=\"(max-width: 593px) 100vw, 593px\" \/><\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-4ce6625 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"4ce6625\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-d4e2ed9\" data-id=\"d4e2ed9\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-3554efc elementor-widget elementor-widget-heading\" data-id=\"3554efc\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-18\"><\/span>Exercice 18<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-27ac47a elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"27ac47a\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-9be4f2f\" data-id=\"9be4f2f\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-d21d956 elementor-widget elementor-widget-text-editor\" data-id=\"d21d956\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>\u00c9tant donn\u00e9 un tableau d&rsquo;entiers nums et un entier k, renvoie le k\u00e8me plus grand \u00e9l\u00e9ment du tableau.<\/p><p>Notez qu&rsquo;il s&rsquo;agit du k\u00e8me \u00e9l\u00e9ment le plus grand dans l&rsquo;ordre tri\u00e9, et non du k\u00e8me \u00e9l\u00e9ment distinct.<\/p><p>Vous devez le r\u00e9soudre en complexit\u00e9 temporelle O(nlogn).<\/p><p>Exemple 1:<\/p><p>Entr\u00e9e : nombres = [3,2,1,5,6,4], k = 2<br \/>Sortie\u00a0: 5<\/p><p>Exemple 2 :<\/p><p>Entr\u00e9e : nombres = [3,2,3,1,2,4,5,5,6], k = 4<br \/>Sortie\u00a0: 4<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-500a87a elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"500a87a\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-aeea083\" data-id=\"aeea083\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-2dd2509 elementor-widget elementor-widget-toggle\" data-id=\"2dd2509\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-4801\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-4801\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-4801\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-4801\"><p>Pour r\u00e9soudre ce probl\u00e8me il faut aller au plus simple. Trier le tableau en O(nlogn) puis le parcourir du plus grand au plus petit. Un compteur s&rsquo;incr\u00e9mente d\u00e8s qu&rsquo;on change de nombre, on retourne le nombre du k-i\u00e8me changement.<\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-3e88bce elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"3e88bce\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-f967b80\" data-id=\"f967b80\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-0b96297 elementor-widget elementor-widget-heading\" data-id=\"0b96297\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-19\"><\/span>Exercice 19<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-b898228 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"b898228\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-ff4b062\" data-id=\"ff4b062\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-d0bd68d elementor-widget elementor-widget-text-editor\" data-id=\"d0bd68d\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>\u00c9tant donn\u00e9 un tableau d&rsquo;entiers nums, renvoyer un tableau d&rsquo;entiers counts o\u00f9 counts[i] est le nombre d&rsquo;\u00e9l\u00e9ments plus petits \u00e0 droite de nums[i].<\/p><p>Entr\u00e9e : nombres = [5,2,6,1]<br \/>Sortie\u00a0: [2,1,1,0]<\/p><p>Explication:<br \/>\u00c0 droite de 5, il y a 2 \u00e9l\u00e9ments plus petits (2 et 1).<br \/>A droite de 2, il n&rsquo;y a qu&rsquo;un seul \u00e9l\u00e9ment plus petit (1).<br \/>\u00c0 droite de 6, il y a 1 \u00e9l\u00e9ment plus petit (1).<br \/>\u00c0 droite de 1, il y a 0 \u00e9l\u00e9ment plus petit.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-7fd763f elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"7fd763f\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-dc6ea2a\" data-id=\"dc6ea2a\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-a82faf2 elementor-widget elementor-widget-toggle\" data-id=\"a82faf2\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-1761\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-1761\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-1761\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-1761\"><p>Les plus petits nombres \u00e0 droite d&rsquo;un nombre sont exactement ceux qui sautent de sa droite \u00e0 sa gauche lors d&rsquo;un tri stable. Je fais donc un tri par fusion avec un suivi suppl\u00e9mentaire de ces sauts de droite \u00e0 gauche. Voici les algorithmes sous leur forme it\u00e9rative.<\/p><p>On trie les paires (index, valeur). La valeur est utilis\u00e9e pour le tri et l&rsquo;index est utilis\u00e9 pour le suivi des sauts.<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-19258 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/smallersort.png\" alt=\"\" width=\"500\" height=\"362\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/smallersort.png 500w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/smallersort-300x217.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/smallersort-18x12.png 18w\" sizes=\"(max-width: 500px) 100vw, 500px\" \/><\/p><p>Vous pouvez \u00e9galement trier uniquement les index et rechercher les chiffres r\u00e9els pour les comparaisons \u00e0 la vol\u00e9e. Peut-\u00eatre un peu plus facile \u00e0 comprendre et \u00e0 porter dans d&rsquo;autres langues\u00a0:<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-19259 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/smallersort2.png\" alt=\"\" width=\"543\" height=\"358\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/smallersort2.png 543w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/smallersort2-300x198.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/smallersort2-18x12.png 18w\" sizes=\"(max-width: 543px) 100vw, 543px\" \/><\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-3521db3 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"3521db3\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-24ed4f2\" data-id=\"24ed4f2\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-f1e4e90 elementor-widget elementor-widget-heading\" data-id=\"f1e4e90\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-20\"><\/span>Exercice 20<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-cbbf663 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"cbbf663\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-2a4a805\" data-id=\"2a4a805\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-a6ec082 elementor-widget elementor-widget-text-editor\" data-id=\"a6ec082\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>\u00c9tant donn\u00e9 deux tableaux tri\u00e9s nums1 et nums2 de taille m et n respectivement, renvoie la m\u00e9diane des deux tableaux tri\u00e9s.<\/p><p>La complexit\u00e9 globale du temps d&rsquo;ex\u00e9cution doit \u00eatre O(log (m+n)).<\/p><p>Exemple 1:<\/p><p>Entr\u00e9e\u00a0: nums1 = [1,3], nums2 = [2]<br \/>Sortie : 2.00000<br \/>Explication : tableau fusionn\u00e9 = [1,2,3] et la m\u00e9diane est 2.<\/p><p>Exemple 2\u00a0:<\/p><p>Entr\u00e9e\u00a0: nums1 = [1,2], nums2 = [3,4]<br \/>Sortie : 2.50000<br \/>Explication : tableau fusionn\u00e9 = [1,2,3,4] et la m\u00e9diane est (2 + 3) \/ 2 = 2,5.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-4758eb7 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"4758eb7\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-1c4f260\" data-id=\"1c4f260\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-74e330c elementor-widget elementor-widget-toggle\" data-id=\"74e330c\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-1221\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-1221\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-1221\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-1221\"><p>Voyons d&rsquo;abord le concept de &lsquo;M\u00c9DIAN&rsquo; d&rsquo;une mani\u00e8re un peu non conventionnelle. C&rsquo;est-\u00e0-dire:<\/p><p>\u00ab\u00a0si nous coupons le tableau tri\u00e9 en deux moiti\u00e9s de LONGUEURS \u00c9GALES, alors la m\u00e9diane est la MOYENNE DE Max(lower_half) et Min(upper_half), c&rsquo;est-\u00e0-dire les deux nombres imm\u00e9diatement \u00e0 c\u00f4t\u00e9 de la coupe\u00a0\u00bb.<\/p><p>Par exemple, pour [2 3 5 7], on fait la coupure entre 3 et 5 :<br \/>[2 3 \/ 5 7]<br \/>alors la m\u00e9diane = (3+5)\/2.<\/p><p>Voici l&rsquo;algorithme en Diviser pour R\u00e9gner :<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-19269 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/median.png\" alt=\"\" width=\"519\" height=\"393\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/median.png 519w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/median-300x227.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/median-16x12.png 16w\" sizes=\"(max-width: 519px) 100vw, 519px\" \/><\/p><p>trouver le ki\u00e8me \u00e9l\u00e9ment dans les deux tableaux tri\u00e9s : A[aMid] &lt;= B[bMid], x\u00a0: mi-longueur de a, y\u00a0: mi-longueur de b, alors on peut savoir<\/p><p>(1) il y aura au moins (x + 1 + y) \u00e9l\u00e9ments avant bMid<br \/>(2) il y aura au moins (m &#8211; x &#8211; 1 + n &#8211; y) = m + n &#8211; (x + y +1) \u00e9l\u00e9ments apr\u00e8s aMid<\/p><p>Donc<\/p><p>si k &lt;= x + y + 1, trouver le k\u00e8me \u00e9l\u00e9ment dans a et b, mais sans tenir compte de bMid et de son suffixe<\/p><p>si k &gt; x + y + 1, trouver le k &#8211; (x + 1) \u00e8me \u00e9l\u00e9ment dans a et b, mais sans consid\u00e9rer aMid et son pr\u00e9fixe<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-19270 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/median2.png\" alt=\"\" width=\"571\" height=\"474\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/median2.png 571w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/median2-300x249.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/median2-14x12.png 14w\" sizes=\"(max-width: 571px) 100vw, 571px\" \/><\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-7a160c9 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"7a160c9\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-142c8e9\" data-id=\"142c8e9\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-0521c2d elementor-widget elementor-widget-heading\" data-id=\"0521c2d\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-21\"><\/span>Exercice 21<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-b0ebb6b elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"b0ebb6b\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-5ae18a0\" data-id=\"5ae18a0\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-f160694 elementor-widget elementor-widget-text-editor\" data-id=\"f160694\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>Votre t\u00e2che consiste \u00e0 calculer a^b mod 1337 o\u00f9 a est un entier positif et b est un entier positif extr\u00eamement grand donn\u00e9 sous la forme d&rsquo;un tableau.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-b679070 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"b679070\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-8a832d4\" data-id=\"8a832d4\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-35f8d2e elementor-widget elementor-widget-toggle\" data-id=\"35f8d2e\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-5651\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-5651\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-5651\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-5651\"><p>Une connaissance : ab % k = (a%k)(b%k)%k<\/p><p>Puisque la puissance ici est un tableau, nous ferions mieux de la g\u00e9rer chiffre par chiffre. Un constat :<\/p><p>a^1234567 % k = (a^1234560 % k) * (a^7 % k) % k = (a^123456 % k)^10 % k * (a^7 % k) % k<\/p><p>\u00c7a vous para\u00eet compliqu\u00e9 ? Permettez-moi de le dire autrement:<\/p><p>Supposons que f(a, b) calcule a^b % k\u00a0; Traduisez ensuite la formule ci-dessus en utilisant f :<\/p><p>f(a,1234567) = f(a, 1234560) * f(a, 7) % k = f(f(a, 123456),10) * f(a,7)%k\u00a0;<\/p><p>Mise en \u0153uvre de cette id\u00e9e :<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-19264 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/superpow.png\" alt=\"superpow\" width=\"529\" height=\"429\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/superpow.png 529w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/superpow-300x243.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/superpow-15x12.png 15w\" sizes=\"(max-width: 529px) 100vw, 529px\" \/><\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-df96c9d elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"df96c9d\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-604814d\" data-id=\"604814d\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-9fa3bbd elementor-widget elementor-widget-heading\" data-id=\"9fa3bbd\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-22\"><\/span>Exercice 22<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-ac7dc17 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"ac7dc17\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-67810e1\" data-id=\"67810e1\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-e754742 elementor-widget elementor-widget-text-editor\" data-id=\"e754742\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>Pour calculer l\u2019aire sous la courbe, il est possible d\u2019encadrer la courbe par un rectangle et d\u2019en d\u00e9duire que l\u2019aire de la courbe est dans l\u2019ordre de grandeur de l\u2019aire du rectangle.<\/p><p>La m\u00e9thode des rectangles est une m\u00e9thode <a href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/\">algorithmique<\/a> qui permet d\u2019obtenir un encadrement d\u2019une int\u00e9grale. Pour rappel ; une fonction positive sur un intervalle [a,b], \u00e0 pour int\u00e9grale sur cet intervalle l\u2019aire sous la courbe repr\u00e9sentative de f et l\u2019axe des abscisses.<\/p><p>Dans l\u2019algorithme Diviser pour R\u00e9gner, on subdivise l\u2019intervalle [a,b] en n intervalles de largueur inf\u00e9rieur \u00e0 un seuil k (k \u00e9tant la pr\u00e9cision de calcul de l\u2019int\u00e9gral).<\/p><p>Soit I le milieu d\u2019un intervalle, l\u2019aire sous la courbe dans cet intervalle est donc \u00e9gale au rectangle dont la hauteur est d\u00e9finie par f(I). L\u2019aire dans l\u2019intervalle d\u2019origine est donc \u00e9gale \u00e0 la somme de toutes les aires subdivis\u00e9es.<\/p><p>Il est aussi possible d&rsquo;encadrer l&rsquo;aire sous la courbe en consid\u00e9rant qu&rsquo;elle est de m\u00eame grandeur que la somme des rectangles de hauteur f(a) et de m\u00eame grandeur que la somme des rectangles de hauteur f(b).<\/p><p>Une troisi\u00e8me m\u00e9thode existe pour simuler l&rsquo;aire sous la courbe : la m\u00e9thode des trap\u00e8zes.\u00a0<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-19271 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/trapeze.png\" alt=\"\" width=\"428\" height=\"332\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/trapeze.png 428w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/trapeze-300x233.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/trapeze-15x12.png 15w\" sizes=\"(max-width: 428px) 100vw, 428px\" \/><\/p><p>Pour calculer la surface du trap\u00e8ze ABED, on fait la somme des aires du rectangle ABCD et du triangle\u00a0rectangle BEC. L\u2019aire du trap\u00e8ze est une repr\u00e9sentation de l\u2019aire sous la courbe dans l\u2019intervalle [a,b].<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-76f6ed7 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"76f6ed7\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-23ab924\" data-id=\"23ab924\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-127e950 elementor-widget elementor-widget-toggle\" data-id=\"127e950\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-1931\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-1931\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-1931\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-1931\"><p>Les algorithmes sont tr\u00e8s simple. Tant que la taille seuil n&rsquo;est pas atteinte, on renvoie methode(a, (a+b)\/2, fonction) + methode ((a+b)\/2, b, fonction).<\/p><p>Ce calcul permet de sommer les parties gauche et droite de la diviser de l&rsquo;intervalle. Une fois le seuil atteint, la m\u00e9thode renvoie le calcul de l&rsquo;aire correspondant \u00e0 l&rsquo;\u00e9nonc\u00e9 \u00e9tudi\u00e9.<\/p><p>Pour les rectangles dit \u00e0 droite nous aurons comme somme totale :<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-19272 \" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/rectangle.png\" alt=\"m\u00e9thode des rectangles\" width=\"300\" height=\"237\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/rectangle.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/rectangle-15x12.png 15w\" sizes=\"(max-width: 300px) 100vw, 300px\" \/><\/p><p>Pour les rectangles dit \u00e0 gauche nous aurons comme somme totale :<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-19273 size-medium\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/rectangle2-300x205.png\" alt=\"m\u00e9thode des rectangles\" width=\"300\" height=\"205\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/rectangle2-300x205.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/rectangle2-18x12.png 18w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/rectangle2.png 304w\" sizes=\"(max-width: 300px) 100vw, 300px\" \/><\/p><p>Pour la m\u00e9thode des trap\u00e8zes, le calcul de chaque sous-intervalle est donn\u00e9 par la formule suivante :<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-19274 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/trapeze.jpg\" alt=\"\" width=\"605\" height=\"139\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/trapeze.jpg 605w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/trapeze-300x69.jpg 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/trapeze-18x4.jpg 18w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/12\/trapeze-600x138.jpg 600w\" sizes=\"(max-width: 605px) 100vw, 605px\" \/><\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<\/div>\n\t\t","protected":false},"excerpt":{"rendered":"<p>Algorithms Wiki home page Ejercicios corregidos con algoritmo en divide y vencer\u00e1s Los siguientes ejercicios corregidos se relacionan con la creaci\u00f3n de algoritmo seg\u00fan la estructura de divide \u2026 <\/p>","protected":false},"author":1,"featured_media":0,"parent":1062,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-16564","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/16564","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/comments?post=16564"}],"version-history":[{"count":70,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/16564\/revisions"}],"predecessor-version":[{"id":20236,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/16564\/revisions\/20236"}],"up":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/1062"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/media?parent=16564"}],"curies":[{"name":"gracias","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}