forked from Open-CT/openct-tasks
81 lines
5.0 KiB
HTML
81 lines
5.0 KiB
HTML
<!doctype html>
|
|
<html>
|
|
<head>
|
|
<meta charset="utf-8">
|
|
<title>Pomme de pin</title>
|
|
<link class="module" rel="stylesheet" href="../../../_common/modules/pemFioi/taskStyles-0.1.css" id="http://www.france-ioi.org/modules/pemFioi/taskStyles-0.1.css">
|
|
<script class="module" src="../../../_common/modules/ext/jquery/1.7/jquery.min.js" id="http://code.jquery.com/jquery-1.7.1.min.js"></script>
|
|
<script class="module" type="text/javascript" src="../../../_common/modules/ext/json/json2.min.js" id="https://github.com/douglascrockford/JSON-js"></script>
|
|
<script class="remove" type="text/javascript" src="../../../_common/modules/integrationAPI.01/installationAPI.01/pemFioi/installation.js" id="http://www.france-ioi.org/modules/integrationAPI.01/installationAPI.01/pemFioi/installation.js"></script>
|
|
<script class="remove" type="text/javascript" src="../../../_common/modules/ext/jschannel/jschannel.js"></script>
|
|
<script class="proxy module" type="text/javascript" src="../../../_common/modules/integrationAPI.01/official/platform-pr.js" id="http://www.france-ioi.org/modules/integrationAPI.01/official/platform-pr.js"></script>
|
|
<script class="module" type="text/javascript" src="../../../_common/modules/pemFioi/beaver-task.js" id="http://www.france-ioi.org/modules/pemFioi/beaver-task.js"></script>
|
|
<script class="stdAnswerTypes module" type="text/javascript" src="../../../_common/modules/integrationAPI.01/installationAPI.01/pemFioi/answerTypes.js" id="http://www.france-ioi.org/modules/integrationAPI.01/installationAPI.01/pemFioi/answerTypes.js"></script>
|
|
<link class="stdAnswerTypes module" rel="stylesheet" type="text/css" href="../../../_common/modules/integrationAPI.01/installationAPI.01/pemFioi/answerTypes.css" id="http://www.france-ioi.org/modules/integrationAPI.01/installationAPI.01/pemFioi/stdAnsTypes.css" />
|
|
<script class="stdButtonsAndMessages module" type="text/javascript" src="../../../_common/modules/integrationAPI.01/installationAPI.01/pemFioi/buttonsAndMessages.js" id="http://www.france-ioi.org/modules/integrationAPI.01/installationAPI.01/pemFioi/buttonsAndMessages.js"></script>
|
|
<script class="remove" type="text/javascript" src="../../../_common/modules/integrationAPI.01/official/miniPlatform.js" id="http://www.france-ioi.org/modules/integrationAPI.01/official/miniPlatform.js"></script>
|
|
<script class="task" type="text/javascript">
|
|
stdAnsTypes.genTaskFreeInput("integer", "#answers_2010-pomme-pin", 100, 1);
|
|
</script>
|
|
<script class="remove" type="text/javascript">var json = {
|
|
"id": "http://castor-informatique.fr/tasks/2010/2010-pomme-pin/",
|
|
"language": "fr",
|
|
"version": "fr.01",
|
|
"authors": "France-ioi",
|
|
"translators": [],
|
|
"license": "CC BY-SA 3.0",
|
|
"taskPathPrefix": "",
|
|
"modulesPathPrefix": "",
|
|
"browserSupport": [],
|
|
"acceptedAnswers": ["28"]
|
|
};</script>
|
|
</head>
|
|
<body>
|
|
<div id="task">
|
|
<h1>Pomme de pin</h1>
|
|
<p>
|
|
Les castors ont un jeu qui exerce à la fois leur agilité et leur intelligence.
|
|
Cela se passe dans un système de grottes reliées par des tunnels. Le meneur de jeu dépose un certain
|
|
nombre de pommes de pin dans chaque grotte. Les tunnels entre les grottes sont à sens unique, indiqué par
|
|
des flèches. Les castors sont obligés de suivre le sens de la flèche. Le joueur ramasse toutes les pommes de
|
|
pin qu'il trouve sur son passage.
|
|
</p><p>
|
|
Vous voyez sur l'image le système de grottes. Les chiffres donnent le nombre de pommes de pin déposées dans
|
|
chaque grotte.
|
|
</p>
|
|
<center><img src="enonce.jpg" /></center>
|
|
<p><b>Combien de pommes de pin un castor peut-il ramasser au maximum en effectuant un passage ?</b></p>
|
|
<div class="reponses" id="answers_2010-pomme-pin">
|
|
</div>
|
|
|
|
|
|
<img style="display: none;" src="enonce.jpg" />
|
|
|
|
</div><!-- task -->
|
|
<div id="solution">
|
|
<!-- réponse : 3 -->
|
|
|
|
<div class="explications">
|
|
<h2>La solution</h2>
|
|
|
|
<p>
|
|
La réponse est 28.
|
|
</p><p>
|
|
Le meilleur chemin, donnant ce résultat, est 3-3-3-6-6-2-5.
|
|
</p>
|
|
<h2>C'est de l'informatique </h2>
|
|
<p>Ce jeu est en fait un problème d'optimisation. Parmi toutes les possibilités de chemins, il faut trouver celui qui est
|
|
optimal. C'est à dire celui qui permet à Castor de ramasser le plus grand nombre possible de pommes de pin. Pour
|
|
résoudre un problème d'optimisation, on peut essayer toutes les possibilités et prendre la meilleure, mais cela
|
|
prend beaucoup de temps. Ce petit réseau de grottes contient déjà 20 chemins différents. Plutôt que de reparcourir
|
|
de nombreuses fois chacune des grottes, il est plus intéressant de se souvenir pour chaque grotte, du plus grand
|
|
nombre de pommes de pin que l'on peut avoir récolté quand on y arrive. Pour une grotte donnée, cette valeur peut
|
|
se calculer directement à partir des valeurs des deux grottes qui permettent d'y accéder. Le principe de la résolution
|
|
d'un problème en enregistrant et réutilisant ainsi les solutions de sous-problèmes est très utilisé en algorithmique,
|
|
et porte le nom de "Programmation Dynamique".
|
|
</p>
|
|
</div>
|
|
</div> <!-- task-solution -->
|
|
</body>
|
|
</html>
|