forked from Open-CT/openct-tasks
132 lines
8.2 KiB
HTML
132 lines
8.2 KiB
HTML
<!doctype html>
|
|
<html>
|
|
<head>
|
|
<meta charset="utf-8">
|
|
<title>2014-FR-04</title>
|
|
<script>
|
|
window.stringsLanguage = 'fr';
|
|
</script>
|
|
<script class="remove" type="text/javascript" src="../../../_common/modules/pemFioi/importModules-1.1_M.js" id="import-modules"></script>
|
|
<script class="remove" type="text/javascript">
|
|
var modulesPath = '../../../_common/modules';
|
|
importModules([
|
|
'jquery-1.7.1', 'jquery-ui.touch-punch', 'raphael-2.2.1', 'JSON-js',
|
|
'beav-1.0', 'beaver-task-2.0', 'simulation-2.0', 'raphaelFactory-1.0',
|
|
'delayFactory-1.0', 'simulationFactory-1.0', 'raphaelButton-1.0',
|
|
'jschannel', 'platform-pr', 'buttonsAndMessages', 'installationAPI.01', 'randomGenerator-1.0',
|
|
'miniPlatform', 'taskStyles-0.1','graph-1.0', 'visual-graph-1.0', 'drag_lib-2.0']);
|
|
</script>
|
|
<script class="remove" type="text/javascript">
|
|
|
|
var json = {
|
|
"id": "http://castor-informatique.fr/tasks/2014/2014-FR-04-gattaca/",
|
|
"language": "en",
|
|
"version": "en.01",
|
|
"authors": "Mathias Hiron, France-ioi",
|
|
"license": "CC BY-SA 3.0",
|
|
"translators": [
|
|
],
|
|
"taskPathPrefix": "",
|
|
"modulesPathPrefix": "",
|
|
"browserSupport": [
|
|
],
|
|
"difficulty": {"3": "hard", "4": "hard"},
|
|
"categories": {ALG : true},
|
|
"answerType": "Interactive, click on a grid",
|
|
"fullFeedback": true,
|
|
"status": "test"
|
|
};
|
|
</script>
|
|
<script>
|
|
var taskStrings = {
|
|
numberOfLetters: "Nombre de lettres inscrites :",
|
|
clickOnCells: "Cliquez sur les cases pour que Castor y inscrive des lettres.",
|
|
failure: "Vous n'avez pas trouvé le mot",
|
|
success: function(nbSteps) {
|
|
return "Bravo, vous avez trouvé le mot en demandant " + nbSteps + " lettres seulement !";
|
|
},
|
|
partialSuccess: function(nbSteps) {
|
|
return "Vous avez trouvé le mot en demandant " + nbSteps + " lettres.<br /><br />" +
|
|
"Recommencez pour essayer de faire mieux.";
|
|
}
|
|
};
|
|
</script>
|
|
<script type="text/javascript" src="task.js"></script>
|
|
<style>
|
|
.twolines { display:none; }
|
|
</style>
|
|
</head>
|
|
<body>
|
|
<div id="task">
|
|
<h1>Le défi</h1>
|
|
<div id="tabsContainer"></div> <!-- will contain the versions tabs -->
|
|
<div id="taskContent"> <!-- will contain the content of the task -->
|
|
<div id="zone_1">
|
|
<div class="consigne">
|
|
<p>
|
|
<img src="castor_small.png" style="float:right;margin-left:1em;height:120px" >
|
|
Castor vous défie au jeu suivant. Quand vous cliquez sur une case, il y inscrit une lettre parmi <b>C</b>, <b>A</b>, <b>S</b> ou <b>T</b>.
|
|
</p>
|
|
<p>
|
|
Votre but est d'obtenir le mot « <span id="target_pattern" style="font-weight:bold"></span> » en cliquant sur un <b>minimum</b> de cases.
|
|
</p>
|
|
<p>
|
|
Castor est obligé de faire apparaître ce mot quelque part, mais attention, il a une stratégie efficace pour vous empêcher de réussir à le trouver facilement !
|
|
<span class="hard">La séquence peut se trouver soit sur la première ligne, soit sur la seconde.</span>
|
|
</p>
|
|
</div>
|
|
</div>
|
|
<div id="zone_2">
|
|
<center>
|
|
<div id="anim"></div>
|
|
<b><div id="status" style="margin-bottom:0.8em"></div></b>
|
|
</center>
|
|
</div>
|
|
<img src="icon.png" style="display:none">
|
|
</div><!-- task -->
|
|
<div id="solution">
|
|
<h2>Solution</h2>
|
|
<p>
|
|
Une approche méthodique consiste à chercher le mot « CATS » en progressant parmi les cases de gauche à droite, et en réduisant petit à petit la zone où le mot peut se trouver.
|
|
Si l'on commence en cliquant sur la première case, et que cette lettre n'est pas un <b>C</b>, on peut uniquement déduire que le mot ne commence pas là. </p>
|
|
<center><img src="gattaca_sol2.png" /></center>
|
|
<p>
|
|
Cependant, on n'apprend rien de plus. Du coup, si l'on continue comme cela à cliquer sur la première case vide à chaque fois, on devra potentiellement cliquer sur toutes les cases une par une.
|
|
</p>
|
|
<p>
|
|
Une meilleure stratégie consiste à cliquer dès le départ sur la 4ème case. Supposons pour commencer que l'on obtienne un <b>C</b>. Dans ce cas, on peut tout de suite déduire que Castor ne pourra pas utiliser les trois premières cases pour faire apparaître le mot « CATS ». On n'aura alors jamais besoin de cliquer sur ces cases.
|
|
</p>
|
|
<center><img src="gattaca_sol3.png" /></center>
|
|
<p>
|
|
Dans une telle situation, on se dit que Castor pourrait écrire « CATS » en utilisant le <b>C</b> qui est visible. Plutôt que de cliquer sur la case située juste après le <b>C</b>, on va cliquer sur la case correspondant au <b>S</b>, car c'est celle qui se trouve le plus à droite possible.
|
|
</p>
|
|
<p>
|
|
Supposons que l'on découvre la lettre <b>A</b>. On en déduit que Castor ne pourra plus utiliser la case située juste après le <b>C</b> pour afficher son mot. Par contre, il pourrait utiliser la case suivante en y mettant un <b>C</b>, de sorte à écrire « CATS » en utilisant le <b>A</b> qui est déjà visible. Pour tester cette hypothèse, plutôt que de cliquer sur la case qui pourrait correspondre au <b>C</b>, on va de nouveau cliquer sur la case qui pourrait correspondre au <b>S</b>, car c'est une case située plus à droite, et qui nous apportera donc davantage d'information.
|
|
</p>
|
|
<center><img src="gattaca_sol1.png" /></center>
|
|
<p>
|
|
Si Castor fait apparaître un <b>S</b> à la position marquée ci-dessus, il faudra alors cliquer sur la case précédente pour voir si Castor y place un <b>T</b>, et si c'est le cas cliquer sur la case située avant le <b>A</b> pour voir si Castor y place un <b>C</b>. En revanche, si Castor fait apparaître autre chose qu'un <b>S</b> à la position marquée ci-dessus, alors on pourra en déduire qu'il ne pourra plus se servir de la case située avant le <b>A</b>, et on pourra donc éliminer cette case.
|
|
</p>
|
|
<p>
|
|
En résumé, la stratégie consiste à cliquer à chaque fois sur la case la plus à droite possible parmi celles qui pourraient servir à éliminer la case blanche située la plus à gauche. (Une case est blanche si elle ne contient ni uen lettre ni une croix rouge).
|
|
</p>
|
|
<p>
|
|
<p>
|
|
Voici ci-dessous un autre exemple illustrant une application de cette stratégie jusqu'au bout.
|
|
</p>
|
|
<center><img src="gattaca_sol4.png" /></center>
|
|
<p>
|
|
Notez cependant que, si Castor était vraiment vicieux, il pourrait vous forcer à cliquer sur toutes les cases avant de faire apparaître le mot. Comment s'y prendrait-il ?
|
|
</p>
|
|
<h2>C'est de l'informatique !</h2>
|
|
<p>
|
|
L'objectif de cet exercice est de trouver et d'appliquer un algorithme efficace pour rechercher une « occurrence » (une « apparition ») d'un mot dans un texte.
|
|
L'algorithme décrit dans la solution, développé par Boyer et Moore en 1977, est utilisé encore dans de nombreux programmes actuels.
|
|
</p>
|
|
<p>
|
|
Le problème consistant à trouver un mot dans un texte a des applications bien au-delà des logiciels de traitement de textes. Par exemple, une séquence d'ADN peut être vue comme une très long texte (avec des milliards de lettres), écrit avec seulement 4 lettres différentes (A, C, G, et T). Un gène particulier correspond à un très long mot. Déterminer si un fragment d'ADN contient ou non un gène donné revient à déterminer si un mot apparaît dans un texte.
|
|
</p>
|
|
</div>
|
|
</body>
|
|
</html>
|