Домашняя работа 2 и 3

Второе домашнее задание разработчикам получилось очень сложным. Задача стояла такая: есть 25 гробов, каждый из которых характеризуется двумя случайно заданными числами - массой гроба (от 1 до 10 кг) и его жёсткостью (сколько килограмм он выдержит на себе, от 10 до 100 кг). И надо найти максимально высокую башню, которую можно построить из данного набора гробов. Совершенно случайно я задал такие параметры (25 гробов, 1-10 кг масса и 10-100 жёсткость), что перебором решить эту задачу не представлялось возможным. Я с помощью всяческих ухищрений ухитрился значительно сократить количество возможных итераций, но всё равно перебор шёл оооочень долго. на 11 гробах - долю секунды, 12 - секунды, 13 гробах - десятки секунд, 14 гробах - минуты, а вот на 15... мне надоело ждать, пока оно переберёт хотя бы половину комбинаций, и я прервал расчёт. А вот наш начальник отдела конроля качества (и единственный его сотрудник) Роман Сергеевич молодец, он единственный придумал или нашёл где-то быстрый алгоритм, заключающийся в поиске максимально жёсткой башни заданной высоты (метод подъёма на холм, что ли, называется - поиск максимума на каждом шаге и инкрементация). Так как никто не смог доказать наличие локального ложного максимума, куда может завести этот метод, проверка его перебором с небольшим количеством гробов и методом Монте-Карло подтвердили правильность результатов, то результат засчитали.

Третье домашнее задание мы взяли немного попроще, чтоб побольше народу его решило. Задача такая: есть лестница из 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();

?>