McCoushev Сообщение 18/06/2012 17:10 Копия темы
Задачи на интервью В крупных фирмах на западе принято устраивать тестирование кандидатов в той или иной форме. О вакансии в американской компании я узнал год назад совершенно  случайно. Послал письмо, абсолютно не надеясь на ответ – но в ответ пришло письмо с заданиями. Одно из них очень понравилось – было упомянуто наличие некоего алгоритма, реализация которого обещала бонусные очки. Я алгоритм не знал, но придумал свой вариант, достаточно эффективный. Надеюсь, что сообществу будет интересно найти решение этой задачи – с моей точки зрения, очень хороший способ выявить людей, умеющих находить нестандартные решения. Задачу даю в переводе с английского.

Реализовать функцию countDivisibles($limit, $divisors), вычисляющую количество неотрицательных целых чисел, включая $limit, которые делятся без остатка хотя бы на одно число из массива $divisors. При вызове гарантируется, что массив отсортирован и имеет в своем составе уникальные элементы, поэтому в реализации проверку массива производить не надо. 
Существует очень эффективный алгоритм для подсчета этого количества для любых значений $lim при условии, что длина массива будет относительно короткой. Найдите этот алгоритм для бонусных очков. 

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

С уважением, Александр

 

sergey65536 Сообщение 18/06/2012 18:32 Копия темы
Наверное найденные числа должны быть менее $limit?

sergey65536 Сообщение 18/06/2012 18:44 Копия темы
// дано
const $limit; // лимит
array $divisors; // массив с делителями
array $results; // массив для результатов


// переворачиваем массив с делителями
// потому что они будут множителями
// и не имеет смысла гонять вхолостую ветки
// внешнего цикла, так как результатов по маленьким
// будет больше, чем по большим
$divisors = array_reverse($divisors);
// перебираем перевернутый массив делителей
foreach ($divisors as $divisor)
{
    // множитель устанавливаем в единицу
    // результаты типа 1 выбрасываем?
    $factor = 0;
    do 
    {
        $factor++;
        // вычисляем значение
        $value = $factor * $divisor;
        // если значение уже не попадает в лимит – переходим 
        // на следующую итерацию внешнего цикла
        if ($value > $limit)
        {
            break;
        }
        // если попало, то надо его записать
        $result[$divisor][] = $value
    }
    // выглядит бессмысленно, но работает
    while ($value < $limit);
}
// отдаем результаты
return $results;

sergey65536 Сообщение 18/06/2012 18:45 Копия темы
Кратко function find_values($limit,$divisors)
{
    $divisors = array_reverse($divisors);
    foreach ($divisors as $divisor)
    {
        $factor = 0;
        do 
        {
        $factor++;
            $value = $factor * $divisor;
            if ($value > $limit)
            {
                break;
            }
            $result[$divisor][] = $value
        }
        while ($value < $limit);
    }
    return $results;
}

McCoushev Сообщение 18/06/2012 19:03 Копия темы
Надо не числа найти, а придумать метод как найти количество чисел, который делятся без остатка на любое число и массива.
Подходите просто – пусть $limit = скажем 20, а массив – 3, 7,11 . тогда результат – 3,6,9,12,15,18  —  7,14  —   11   --> 9
9 – это искомое количество чисел. Можно его использовать для проверки

McCoushev Сообщение 18/06/2012 19:19 Копия темы
И хорошо, и нет. Во первых –   $result[$divisor][] = $value  – без точки с запятой.
Во вторых, $result, а потом  return $results; .   Функция вернет 0.
Ну а в третьих – результат – массив. А нужно число. Count нужен :)

Перечитал решение еще раз и вьехал, что неправильно. Алгоритм не учитывает повторяющиеся числа
если для того же массива $limit = 40, то Ваш алгоритм даст 21 ( 13 + 5 + 3 ), а правильное число – 19, потому как 21 и 33 посчитаются дважды. Мимо.

abbat Сообщение 18/06/2012 22:35 Копия темы

VGrato Сообщение 19/06/2012 01:16 Копия темы
function countDivisibles( $limit, $divisors ) {
    $ok = 0;
    for( $x = 1; $x <= $limit; $x++ ) {
        foreach( $divisors as $val ) {
            if( $x % $val == 0 ) { $ok++; break; }
        }
    }
    return $ok;
}

echo countDivisibles( 20, array( 3,7,11 ) );

чет не понял, а смысл то в чем? решение в одну строчку должно быть?

MaxSerov Сообщение 19/06/2012 02:35 Копия темы
Читаю топик и думаю: ну всё, ребята обкурились)) Или нет?

McCoushev Сообщение 19/06/2012 04:55 Копия темы
Смысл в том,  чтобы не делать перебор по всем числам, не решать задачи в лоб. При маленьком количестве это не принципиально, а если число очень велико и массив под тысячу чисел? Ответ то будет, но не оптимальный. У Вас решение перебором.

McCoushev Сообщение 24/06/2012 11:12 Копия темы
Жаль, конечно, что в итоге только один человек попробовал найти решение, ну да ладно. Опишу тот вариант, который нашел я. В институте на первом курсе нас славно гоняли по теории чисел, и там среди прочих была формула ( теорема ) Мейсселя, котрая позволяла выяснить число простых чисел, не делящихся на требуемое. Не буду утомлять математическими выкладками, они есть в в монографии Бухштаба "Теория чисел", а приведу лишь конечный алгоритм, который был получен в результате переработки этой формулы. Искомое число вычисляется как сумма ряда, где члены вычисляются по следующим правилам : Пусть $limit — это "a", массив чисел – "b" , "c" ,"d"  Тогда итог равен ( [ a / b ] + [ a / c ] + [ a / d ] ) – ( [ a / (b*c) ] + [ a / (b*d) ] + [ a / (c*d) ] )  + ( [ a / ( b*c*d) ]) 
Если текущий элемент ряда  будет равен 0 ( здесь "[ ]" – цельночисленное деление ), то дальнейшие члены ряда вычислять не имеет смысла. Метод очень сильно сокращает время вычисления при очень большом $limit или "а".