Третье домашнее задание мы взяли немного попроще, чтоб побольше народу его решило. Задача такая: есть лестница из 1000 ступеней, приставленная к стене дома. На каждой ступени есть стрелка, показывающая вверх или вниз (определяется случайном образом), и на одну из ступенек рандомайзером забросило садовника. Садовник может подниматься или опускаться только в ту сторону, куда показывает стрелка, и проходя по ступеньке, садовник меняет направление стрелки на противоположное. Надо сказать, спустится он когда-нибудь или нет. Сперва я подумал, что это нерешаемая алгоритмически Проблема Останова (в общем случае нельзя определить, остановится когда-нибудь произвольный алгоритм или нет), но моделирование ситуации в голове во время мытья под душем показало обратное.
Садовник движется в одну сторону до тех пор, пока наступает на ступеньки со стрелками, которые показывают в эту сторону, при этом он разворачивает их в противоположную. Встретив стрелку, показывающую ему навстречу, он разворачивает её и идёт по стрелочкам обратно до тех пор, пока снова не встретит стрелочку, показывающую ему навстречу. То есть он будет болтаться вверх и вниз по лестнице, с каждым разом поднимаясь всё выши и опускаясь всё ниже. Стало быть, опустится он когда-нибудь или нет, определяется количеством стрелочек, которые расположены выше него и разворачивают его вниз и стрелочек, которые разворачивают его вверх и расположены ниже его.
Алгоритм:
<?php $_LADDER = array(); for($i = 0; $i < 1000; $i++) { $_LADDER[$i] = mt_rand(0, 400) > 200 ? 1 : 0; // 1 - флажок наверх, 0 - флажок вниз } $M = round(mt_rand(0, 1000)); // ступенька, на которой стоит садовник if($M == 0) { echo "Садовник уже спустился\n"; } // вариант первый, более изящный $flags_up_under_M = 0; // флажков "наверх" ниже садовника $flags_down_higher_M = 0; // флажков "вниз" выше садовника for($i = 0; $i < 1000; $i++) { $flags_down_higher_M += ($i > $M && !$_LADDER[$i]); $flags_up_under_M += ($i < $M && $_LADDER[$i]); } if($flags_up_under_M + $_LADDER[$M] > $flags_down_higher_M) { echo "1) Садовник не спустится\n"; } else { echo "1) Садовник спустится\n"; } // вариант второй, "в лоб" class TuringMachine { protected $position; public function __construct($position) { $this->position = $position; } public function run() { while($this->position > 0 && $this->position < 999) { $this->step(); } if($this->position) { echo "2) Садовник не спустился\n"; } else { echo "2) Садовник спустился\n"; } } protected function step() { global $_LADDER; if($_LADDER[$this->position]) { $_LADDER[$this->position] = 0; $this->position++; } else { $_LADDER[$this->position] = 1; $this->position--; } } } $sadovnik = new TuringMachine($M); $sadovnik->run(); ?>
Комментариев нет:
Отправить комментарий
Ублюдочный Гугл поломал форму комментариев. Извините.
Примечание. Отправлять комментарии могут только участники этого блога.