Драсьте всем!
Вошел тут малость в ступор....
Есть такая общеизвестная задачка — решение факториала. Вроде как любят ее задавать на собеседованиях.
Решение можно привести в виде цикла, можно в виде рекурсии.
Причем, имхо, последний вариант — тот еще изврат. Хотя, по видимому, ожидают именно такое решение.
Какой смысл забивать стек рекурсивными вызовами, если задача решается элементарным однострочным циклом?
Скажите мне плз, в чем кайф?

Здравствуйте, kaselli, Вы писали:

K>Скажите мне плз, в чем кайф?

Посмотреть, понимаешь ли ты рекурсию.
Далеко не все, на самом деле, могут мыслить рекурсивно.
Можно еще попросить написать какой-нибудь алгорим на рекурсивных структурах данных,
типа списки или деревья.

Задачки на собеседовании не всегда имеют прямое отношение к реальным вещам.

Здравствуйте, kaselli, Вы писали:

K>Хотя, по видимому, ожидают именно такое решение.

Я бы был осторожен с такими предположениями. Стив МакКоннелл, например, пишет что он уволил бы сотрудника, который бы стал вычислять факториал с помощью рекурсии.

PS. Правильный способ — это, конечно, table lookup

Здравствуйте, nikov, Вы писали:

N>Здравствуйте, kaselli, Вы писали:

K>>Хотя, по видимому, ожидают именно такое решение.

N>Я бы был осторожен с такими предположениями. Стив МакКоннелл, например, пишет что он уволил бы сотрудника, который бы стал вычислять факториал с помощью рекурсии.

N>PS. Правильный способ — это, конечно, table lookup

Да, table lookup — один из лучших вариантов. Все равно около 21! начинаем выходить за пределы ulong.

Здравствуйте, kaselli, Вы писали:

K>Драсьте всем!
K>Вошел тут малость в ступор....
K>Есть такая общеизвестная задачка — решение факториала. Вроде как любят ее задавать на собеседованиях.
K>Решение можно привести в виде цикла, можно в виде рекурсии.
K>Причем, имхо, последний вариант — тот еще изврат. Хотя, по видимому, ожидают именно такое решение.
K>Какой смысл забивать стек рекурсивными вызовами, если задача решается элементарным однострочным циклом?
K>Скажите мне плз, в чем кайф?

Ну я эту загадку пару раз формулировал на собеседовании так:
Дано: enum { N = x }; x — целочисленный литерал. Требуется объявить массив целых чисел размера N! Язык решения — C++.

Здравствуйте, kaselli, Вы писали:

K>Какой смысл забивать стек рекурсивными вызовами, если задача решается элементарным однострочным циклом?
K>Скажите мне плз, в чем кайф?

Кайф получается в языках с tail recursion

Здравствуйте, nikov, Вы писали:

N>PS. Правильный способ — это, конечно, table lookup

А можно поподробнее? )
Не совсем понимаю, чем хэшированная таблица может помочь вычислению факториала и предотвратить выход за пределы числа

Здравствуйте, kaselli, Вы писали:

K>Причем, имхо, последний вариант — тот еще изврат. Хотя, по видимому, ожидают именно такое решение.
K>Какой смысл забивать стек рекурсивными вызовами, если задача решается элементарным однострочным циклом?
K>Скажите мне плз, в чем кайф?

Возможно, что ожидалась рекурсия с запоминанием вычисленных значений (динамическое программирование).
Это решение включает преимущества как итеративного подхода (не надо ничего хардкодить), так и табличного подхода (эффективность).

Здравствуйте, Sergey, Вы писали:

S>Ну я эту загадку пару раз формулировал на собеседовании так:
S>Дано: enum { N = x }; x — целочисленный литерал. Требуется объявить массив целых чисел размера N! Язык решения — C++.

А в чем подвох, кроме того, что число может получиться нефигенно большим и система не даст? )

Здравствуйте, kaselli, Вы писали:

K>Здравствуйте, Sergey, Вы писали:

S>>Ну я эту загадку пару раз формулировал на собеседовании так:
S>>Дано: enum { N = x }; x — целочисленный литерал. Требуется объявить массив целых чисел размера N! Язык решения — C++.

K>А в чем подвох, кроме того, что число может получиться нефигенно большим и система не даст? )

видимо в вычислении факториала на этапе компиляции с пом. шаблончегов

Здравствуйте, kaselli, Вы писали:

S>>Дано: enum { N = x }; x — целочисленный литерал. Требуется объявить массив целых чисел размера N! Язык решения — C++.
K>А в чем подвох, кроме того, что число может получиться нефигенно большим и система не даст? )
А ты попробуй...

Здравствуйте, Андрей Коростелев, Вы писали:

АК>Кайф получается в языках с tail recursion
Те во всех языках где компилятор умеет оптимизировать.

Здравствуйте, kaselli, Вы писали:

K>А можно поподробнее? )
K>Не совсем понимаю, чем хэшированная таблица может помочь вычислению факториала и предотвратить выход за пределы числа

Все просто. Например вот так:

int fact( int x )
{
  static const int table[] = {1, 1, 2, 6, 24, 120, 720,
                              5040, 40320, 362880, 3628800,
                              39916800, 479001600 };
  static const int tableSize = sizeof(table)/sizeof(int);

  if ( x>=0 && x<tableSize )
  {
      return table[x];
  }
  throw std::out_of_range( "fact:invalid argument" );
}

P.S. Надеюсь факториалы верно вписал

Здравствуйте, WolfHound, Вы писали:

WH>А ты попробуй...

попробовал...

enum 
{
    N = 4
};

long fac (long l)
{
    assert (l >= 0);
    long ret = 1;

    if (l > 0)
    {
        for (long i = 1; i <= l; i++)
        {
            ret *= i;
        }
    }

    return ret;
}

int main (int argc, _TCHAR* argv[])
{
    int * arr = new int [fac (N)];
    delete [] arr;

    return 0;
}

и?

Здравствуйте, kaselli, Вы писали:

K>Здравствуйте, WolfHound, Вы писали:

WH>>А ты попробуй...

K>попробовал...

K>

K>enum 
K>{
K>    N = 4
K>};

K>long fac (long l)
K>{
K>    assert (l >= 0);
K>    long ret = 1;

K>    if (l > 0)
K>    {
K>        for (long i = 1; i <= l; i++)
K>        {
K>            ret *= i;
K>        }
K>    }

K>    return ret;
K>}

K>int main (int argc, _TCHAR* argv[])
K>{
K>    int * arr = new int [fac (N)];
K>    delete [] arr;

K>    return 0;
K>}


K>

K>и?

И в котором месте тут объявлен массив? Я вижу только указатель на int. А надо int arr[x];, где x такое, что sizeof(arr)/sizeof(arr[0]) = N!.

Здравствуйте, Sergey, Вы писали:

S>И в котором месте тут объявлен массив? Я вижу только указатель на int. А надо int arr[x];, где x такое, что sizeof(arr)/sizeof(arr[0]) = N!.

О, вот в этом и есть подвох )
Ну, первое, что приходит в голову — умный макрос. Вспоминая, что вы говорили о С++ — макрос не подходит. Но далее идет мысль о умном шаблоне.
Пару минут побился с шаблонами, ничего не вышло (( Сложно сейчас совсем мыслить....


Кстати, а такой ответ прошел бы:

// здесь все то же...
...
int arr [fac (N)];

?
gcc с некоторыми опциями (не помню, какими) запросто это соберет, создав массив в куче

Здравствуйте, kaselli, Вы писали:

K>Пару минут побился с шаблонами, ничего не вышло (( Сложно сейчас совсем мыслить....

да это же задача для второкурсников

K>Кстати, а такой ответ прошел бы:

K>

K>// здесь все то же...
K>...
K>int arr [fac (N)];
K>

K>?

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

K>gcc с некоторыми опциями (не помню, какими) запросто это соберет, создав массив в куче

массив — он на стеке, в куче — это уже кусок памяти (в крайнем случае — динамический массив).

Здравствуйте, nikov, Вы писали:

N>Я бы был осторожен с такими предположениями. Стив МакКоннелл, например, пишет что он уволил бы сотрудника, который бы стал вычислять факториал с помощью рекурсии.

Если Стив действительно такое написал — то помоему он идиот. Или просто позвиздеть любит (т.е. не уволил бы даже еслибы бы кто-то из его работников стал вычислять ф-л рекурсией).

Здравствуйте, Кэр, Вы писали:

Кэр>Да, table lookup — один из лучших вариантов. Все равно около 21! начинаем выходить за пределы ulong.

А смысл тогда из-за этих 21-ой итерации делать оптимизацию? Неужели будет переполнения стека? Насколько я помню код функции факториала, там от силы несколько байт стека.

Здравствуйте, Sergey, Вы писали:
S>Дано: enum { N = x }; x — целочисленный литерал. Требуется объявить массив целых чисел размера N! Язык решения — C++.

template<int N>
struct factorial
{
    static const int value = N*factorial<N-1>::value;
};

template<>
struct factorial<0>
{
    static const int value = 1;
};

int main()
{
    int array[factorial<6>::value];
}