Вычисление lg (N!): У кого-нибудь есть лучший рекурсивный метод? - PullRequest
Новая
       27

Вычисление lg (N!): У кого-нибудь есть лучший рекурсивный метод?

2 голосов
/ 08 августа 2011

Я думаю, что заголовок поста отвечает на мой вопрос. Но, повторюсь, мне интересно, есть ли у кого-нибудь лучший подход к этой проблеме. 

/* Write a recursive program to compute lg( N! ) */

#include <iostream>

#include <cmath>

using namespace std;

long double log_base2( long double N ) {
    return log( N )/log( 2.0 );
}

long double lg_n_factorial( long N ) {
    if( 1 == N ) return log_base2( static_cast<long double>( N ) );
    else return lg_n_factorial( N -1 ) + log_base2( static_cast<long double>( N ) );
}

int main( int argc, char *argv[] ) {
    cout << ( lg_n_factorial( 10 ) ) << endl;
    return 0;
}

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

Ответы [ 3 ]

3 голосов
/ 08 августа 2011

Почему это с помощью рекурсии? Итеративное решение работает так же хорошо: 

long double lg_n_factorial( long N ) {
    long double result = 0;
    while (N > 1) {
        result += log_base2(static_cast<long double>(N));
        N--;
    } 
    return result;
}

Таким образом, максимальное значение, которое вы можете обработать, ограничено только значением LONG_MAX, а не количеством рекурсивных вызовов, которые умещаются в вашем стеке до его переполнения.

2 голосов
/ 08 августа 2011

Просто сделать это итеративно?Я не вижу причин, по которым эту проблему нужно решать рекурсивно.Если у вас есть требование (по тем или иным причинам) сделать это рекурсивно, ваш путь, кажется, работает нормально, хотя ваш базовый случай может просто возвращать 0 (log (1) в любой базе равен 0).

Кроме того, нет необходимости конвертировать в базу 2 на каждом шаге: вы можете сделать это один раз в конце.

0 голосов
/ 08 августа 2011

Я бы сказал, что вы правильно поняли основную идею.С точки зрения стилистики, код был бы более читабельным, если бы вы использовали один оператор return и использовали ?:, но для таких коротких программ разница незначительна и не стоит беспокоиться.И больше личного вкуса, я бы поставил рекурсию в самом конце, чтобы было очень ясно, что это хвостовая рекурсия.(И компилятор, обнаруживающий хвостовую рекурсию, должен иметь возможность переупорядочить арифметику и найти ее, но читатели-люди видят это яснее, если рекурсия - самая последняя вещь.)

...