?

Log in

No account? Create an account

Чт, 9 авг, 2012, 00:45
Какая боль, какая боль

У Йона Бентли прочитал однажды про поиск методом половинного деления: Большинство программистов полагают, что про приведенному выше описанию можно легко написать код. Они ошибаются. Не верите — отложите на время книгу и напишите сами. Попробуйте. Отложил, написал, работает. Ну ладно.

Сейчас вот ширим ряды, собеседую разработчиков. Дай, думаю, подкину задачку, посмотрим. И что же? Пока 2:0 в пользу Бентли. Ладно бы кандидаты написали не вполне корректно, я бы простил. Но они просто ничего не написали! Вот задумайтесь: профессиональные разработчики с многолетним стажем не смогли внятно записать на бумаге школьный алгоритм на своем любимом языке программирования. Не укладывается это в моей бедной голове.

Индусы, говорите? Ха.

Ср, 8 авг, 2012 21:03 (UTC)
pigdeon

К таким постам надо добавлять строчку: "А вот в мои годы... кхе-кхе..." :Е

Чт, 9 авг, 2012 19:18 (UTC)
egorius

Это когда на пенсию выйду. А пока я в строю, у них большие проблемы :)

Ср, 8 авг, 2012 22:09 (UTC)
autoench


$start = 0;
$end = 1000;

do {
	$guess = myGuess($start, $end);
	echo "My guess is {$guess}. Is your number (g)reater, (s)maller or (e)qual? ";
	$line = trim(fgets(STDIN)); 
	if ($line == "g") {
		// bigger
		$start = $guess+1;
	} elseif ($line == "s") {
		// smaller
		$end = $guess-1;
	} elseif ($line == "e") {
		// equal
		die("And the answer is: ".$guess."\n");
	} else {
		echo "Please enter 'e' for x == {$guess}, 's' if x < {$guess} or 'g' for x > {$guess}\n";
	}
} while (true);

function myGuess($start, $end) {
	return round(($start+$end)/2);
}



Типа такого что-то?

Чт, 9 авг, 2012 19:23 (UTC)
egorius

В задаче надо было определить индекс заданного элемента массива, при условии, что элементы упорядочены по возрастанию. Но суть та же, да.
Правда ведь, не очень сложно?

Пт, 10 авг, 2012 11:56 (UTC)
autoench

Задача-то школьная. Может, стрессовая ситуация на собеседовании?

Чт, 9 авг, 2012 05:34 (UTC)
slone

Я чего-т не понимаю? Енто ж попросту дихотомия какая-то, коллега... нну, скажем...
while ((b-a) > precision)
{
c = (a+b)/2;
if(f(b)*f(c)<0)
a=c;
else
b=c;
}
precision это в принципе некая желаемая точность.. ну, понятно, что начальные точки отрезка надо определить и саму функцию задать - просто кнопки давить лень...
но я опять о своём - я не понял задания или как хотя бы ЭТО можно было не написать?...

Чт, 9 авг, 2012 19:30 (UTC)
egorius

Ну примерно. Нахождение корня функции тоже из той же серии, а моя задача была на поиск индекса элемента в массиве, упорядоченного по возрастанию. Я вот тоже недоумеваю, коллега.

Сб, 24 ноя, 2012 09:38 (UTC)
nikname

Достаточно открыть и тупо спереть реализацию binary_search. Но вообще многие молодые люди, приходящие на работу в качестве программистов, ничего не читали. Бинарный поиск - классика, описан у Вирта, описан у Кнута, не удивлюсь, если и у Страустрапа.
Можно сказать, что написание классических алгоритмов - велосипедизм и стоит использовать готовые решения - наверняка он есть и для контейнеров в C#, но беда в том, что они не понимают, как это работает и не могут оценить сложность (трудность). Видимо это какой-то фундаментальный пробел в образовании + отсутствие интереса.

Сб, 24 ноя, 2012 21:17 (UTC)
egorius

Мне в этом плане очень нравится вот эта статья Спольски: «Назад, к основам».

Вс, 25 ноя, 2012 06:22 (UTC)
nikname

Да. Отличная статья. Спасибо, что напомнили про Спольски - давно я его не читал.