forked from Open-CT/openct-tasks
114 lines
6.2 KiB
HTML
114 lines
6.2 KiB
HTML
<!DOCTYPE html>
|
|
<html>
|
|
<head>
|
|
<meta charset="utf-8">
|
|
<title>2014-FR-05-laser</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 = '../../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',
|
|
'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-05-laser/",
|
|
"language": "en",
|
|
"version": "en.01",
|
|
"authors": "Mathias Hiron, Eljakim Schrijvers, France-ioi",
|
|
"license": "CC BY-SA 3.0",
|
|
"translators": [
|
|
],
|
|
"taskPathPrefix": "",
|
|
"modulesPathPrefix": "",
|
|
"browserSupport": [
|
|
],
|
|
"acceptedAnswers": [
|
|
],
|
|
"difficulty": {"2": "hard", "3": "medium", "4": "easy"},
|
|
"categories": {ALG : true, PUZ : true},
|
|
"answerType": "Interactive, click on a grid",
|
|
"fullFeedback": true,
|
|
"status": "test"
|
|
};
|
|
</script>
|
|
<script>
|
|
var stringsLanguage = 'en';
|
|
taskStrings = {
|
|
targetReached: function(nbUsed) {
|
|
return "You have reached the target in " + nbUsed + " mirrors.";
|
|
},
|
|
success: "Congratulations, This is the minimum possible.",
|
|
partialSuccess: "It is possible to do better.",
|
|
failure: "The laser does not reach the target."
|
|
};
|
|
</script>
|
|
<script type="text/javascript" src="task.js"></script>
|
|
<style>
|
|
</style>
|
|
|
|
</head>
|
|
<body>
|
|
<div id="task">
|
|
<h1>Laser</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>
|
|
The image shows a room in which mirrors are placed. The Beaver starts a laser beam from the corner. The laser is reflected in the mirrors according to the mirror angle.
|
|
</p>
|
|
<p>
|
|
The Beaver wants to add Only one mirrors so that the laser beam <b> reaches the gray corner through few mirrors as possible</b>. Click on the drawing to place this new mirror. Note that you can not choose the angle of the mirror.
|
|
</p>
|
|
</div>
|
|
</div>
|
|
<div id="zone_2">
|
|
<center>
|
|
<div id="anim"></div>
|
|
</center>
|
|
</div>
|
|
<img src="castor_tete.png" style="display:none">
|
|
<img src="icon.png" style="display:none" >
|
|
</div><!-- task -->
|
|
<div id="solution">
|
|
<!--
|
|
<h2>Solution</h2>
|
|
<p>
|
|
Pour trouver la position du miroir, il fallait trouver une stratégie.
|
|
</p>
|
|
<ul>
|
|
<li>Une stratégie naïve consiste à essayer toutes les cases dans l'ordre. Mais cela prend beaucoup de temps.</li>
|
|
<li>Une stratégie déjà plus astucieuse consiste à essayer toutes les cases par lesquelles passe le laser, dans l'ordre en partant de Castor. On finit par trouver la solution, mais cela prend encore pas mal de temps.</li>
|
|
<li>Une meilleure stratégie consiste à partir de la fin. On voit tout de suite que le laser ne peut pas atteindre le coin gris par le haut, à cause du miroir qui se trouve juste au dessus. On sait donc que le laser va arriver par la gauche, et on peut donc remonter le trajet par lequel il peut arriver, comme illustré ci-dessous.
|
|
</li>
|
|
</ul>
|
|
<center><img src="strategy.png" /></center>
|
|
<p>La position du miroir à placer se trouver forcément à une intersection entre ce trait et le tracé rouge du laser. Il n'y a donc que 3 positions à essayer, marquées par des gros points verts. La seconde intersection correspond à la bonne réponse.</p>
|
|
<center><img src="solution.png" /></center>
|
|
|
|
|
|
<h2>C'est de l'informatique !</h2>
|
|
<p>
|
|
Les trois stratégies décrites ci-dessus correspondent à des « algorithmes », c'est-à-dire à des suites précises d'opérations permettant de trouver la solution. Certains algorithmes amènent à la solution plus rapidement que d'autres. On parle alors d'algorithmes plus « efficaces ».
|
|
</p>
|
|
<p>
|
|
Le premier algorithme proposé ici examine toutes les solutions possibles, et il y en a beaucoup. Le second restreint l'ensemble des solutions possibles, en exploitant l'observation que le miroir doit forcément se trouver sur le parcours du laser. Le troisième restreint encore davantage l'ensemble des solutions possibles, en remarquant que le miroir se trouve forcément à l'intersection de deux trajectoires.
|
|
</p>
|
|
<p>
|
|
Effectuer des observations permettant de restreindre la taille des solutions possibles à examiner est une technique essentielle en « algorithmique », la science des algorithmes. De même, partir de la fin est une approche qui amène très souvent à des algorithmes plus efficaces.
|
|
</p>
|
|
<p>
|
|
Partir de la fin n'est pas toujours très intuitif, comme par exemple dans ce sujet, où l'on a naturellement tendance à suivre la progression du laser en partant du début. Cependant, c'est en se forçant à voir les problèmes autrement que l'on arrive souvent à concevoir des algorithmes plus efficaces.
|
|
</p>
|
|
-->
|
|
</div>
|
|
</body>
|
|
</html>
|