Главная > Программирование > Старый тест для начинающих программистов. Разбор.

Старый тест для начинающих программистов. Разбор.

Итак, два дня назад я рассказал об одной задачке, некогда предлагавшейся для проверки мышления студентов — будущих программистов. Это было здесь.

Давайте посмотрим, что же в этой задачке такого хитромудрого, как её обычно решают, и как её надо решать.

Для начала посмотрим на лобовое решение, которое чаще всего и предлагают в качестве ответа. Вот оно:

long fact(long k) {
    long r=1;
    for(long i=1;i<=k;i++) r*=i;
    return r;
}

long C1(long m,long n) {
    return fact(n)/(fact(m)*fact(n-m));
}

Примерно так. Здесь нечего комментировать. Число сочетаний считается прямо по формуле, как отношение трёх факториалов, причём вычисление факториала вынесено в отдельную функцию.

На самом деле это вообще не решение. 🙂 Почему — станет понятно через несколько абзацев.

Реже предлагают следующий вариант:

long C2(long m,long n) {
    long mf=1, nf=1, nmf=1;
    for(long i=1;i<=n;i++) {
        nf*=i;
        if(i==m) mf=nf;
        if(i==n-m) nmf=nf;
    }
    return nf/(mf*nmf);
}

С точки зрения конечного результата он столь же никудышен, как и предыдущий. 🙂 Но идеологически авторов такого варианта уже есть за что похвалить — здесь замечено, что из трёх факториалов n!, m! и (n-m)! два последних сами по себе не нужны. Оба они меньше первого и de-facto всё равно считаются в процессе нахождения n! как промежуточные этапы. То есть наличествует анализ проводимых вычислений и определённая оптимизация программы.

А чем же плохи оба этих варианта? Очень просто: попробуйте для проверки посчитать любым из них… ну, например, следующее:

Сейчас угадаю — программа либо вылетит, либо даст неправильный ответ. 🙂

А чего ж вы хотели, считая факториалы?! 🙂 Факториал — это, знаете ли, такая штука, которая возрастает не очень быстро, а потрясающе быстро. В 2 байта (16 бит) не влезет уже 9!. В 4 байта (32 бита) не влезет уже 13!. В 8 байт (64 бита) не влезет уже 21!. В 16 байт (128 бит) не влезет уже 35!. Ну, вы поняли. При этом результаты, как видно из приведённого примера, вовсе не обязательно являются астрономическими числами.

Посмотрим на формулу внимательнее. Вот она ещё раз:

Давайте обозначим k=min(m,n-m) и K=max(m,n-m). В этих терминах можно записать, что

Теперь замечаем, что множители, образующие К!, полностью сокращаются. Итого в числителе и знаменателе остаётся по k сомножителей:

А зачем я написал сомножители в числителе по убыванию, а не по возрастанию? А вот зачем.

Смотрите. Всегда n будет нацело делиться на 1. Всегда n·(n-1) будет нацело делиться на 1·2, ведь из двух идущих подряд натуральных чисел одно обязательно делится на 2. Всегда n·(n-1)·(n-2) будет нацело делиться на 1·2·3, и так далее.

Вот так-то, парными умножениями-делениями, и надо накапливать результат. Соответствующий код очень прост:

long C3(long m,long n) {
    long k,r=1;
    k=(m<n-m)?m:n-m;
    for(long i=0;i<k;i++) r=(r*(n-i))/(i+1);
    return r;
}

Эта функция будет работать, если только ответ вообще влазит в разрядную сетку. Заметьте — никаких рекурсий, массивов, треугольников Паскаля, динамического программирования и прочих хитростей. 😉

Тут есть только одна тонкость. Обратите внимание на накопление результата r=(r*(n-i))/(i+1). Почему нельзя писать без скобок просто r=r*(n-i)/(i+1)? Да потому что умножение и деление имеют одинаковый приоритет — где гарантии, что компилятор не сгенерирует код, в котором сначала производится деление?! А вот оно делиться нацело вовсе не обязано!!! По той же причине нельзя писать в исконно С-шном стиле r*=(n-i)/(i+1) — здесь деление гарантированно выполняется первым, и результат будет заведомо неправильным.

Такая вот старая задачка. Надеюсь, вам понравилось. 🙂

Реклама
  1. Ruslan
    20.03.2009 в 20:07

    Напомнило алгоритм CRC — там подобная штука объясняется (тоже на примере потери точности) при поиске остатка от деления. Красиво сделано.

  2. Dmitry
    20.03.2009 в 20:26

    офигеть)вчера по дороге домой думал над решением и таки оказывается, ответ который придумал — правильный.

  3. Ruslan
    20.03.2009 в 20:31

    Димка, если ты такое устно решаешь, то я готов к тебе пойти работать. Райт, так сказать, нау.

  4. Dmitry
    20.03.2009 в 20:36

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

  5. Dmitry
    20.03.2009 в 21:16

    еще мелкий когда был ходил на занятия по математике в МГУ (там для школьников занятия были)там подобное рассказывали. и как раз про деление было.

  6. Ruslan
    20.03.2009 в 21:18

    Называлось это МММ — Малый МехМат. Я тоже туда ходил. А кто вёл — не вспомнишь?

  7. Dmitry
    25.03.2009 в 15:12

    точно-точно. не вспомню. давно было… может если потом найду свои записи (они у меня где то далеко спрятаны) вспомню:)

  1. No trackbacks yet.

Добавить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s

%d такие блоггеры, как: