с интервью

[juan_gandhi]

Интервьюировал тут интересного француза, из-под Гренобля - Еколь Политекник, потом Бёркли. Мой первый вопрос - хрен ли тут у нас на посёлке делать после прекрасных предгорий? А тут типа у нас жизнь (а там типа нету). Молодёжь!

Короче, задал ему недавно тут пролетавшую задачу - сумму максимальных нечётных делителей для чисел от 1 до N. Сначала написал джавный код, который, будь у нас tail recursion (у него второй язык CAML), был бы ничо бы.

Я его попросил пооптимизировать. Нарисовал алгоритм, пропорциональный N. Я предложил поискать алгоритм, пропорциональный логарифму N. И тут он нарисовал чудесную вещь.

Он нарисовал график, где по горизонтальной оси N, а по вертикальной - значения, которые он складывает (ну понятное дело, логарифмы складывает). По горизонтали N столбиков. Или, по вертикали, log2(N) полосок. После чего решил взять, да интегрировать не по x, а по y. Так что сумм у нас будет всего log2(N), а значения, что суммируются - ну не биг дил посчитать.

Ребята, я такой фокус первый раз вижу! Наглядно донельзя: на графике.

Остаток интервью допрашивал его про метод Годунова - так, чтоб языком почесать.

Ну дай бог он к нам согласится.

Comments

Так, что ли?

[spamsink.livejournal.com]

unsigned f(unsigned x) {
    return x <= 1 ? x : ((x+1)/2)*((x+1)/2) + f(x/2);
}

Re: Так, что ли?

[ivan-gandhi.livejournal.com]

Оно. :)