SONY Go For It: 2) の解答

問題

http://www.sony.co.jp/SonyInfo/Jobs/newgrads/sus/q02.html

i) の解答

factorial_int.cpp

 // FILE: factorial_int.cpp
 // AUTHOR: rhysd (http://d.hatena.ne.jp/rhysd/)
 // License: MIT license  {{{
 //     Permission is hereby granted, free of charge, to any person obtaining
 //     a copy of this software and associated documentation files (the
 //     "Software"), to deal in the Software without restriction, including
 //     without limitation the rights to use, copy, modify, merge, publish,
 //     distribute, sublicense, and/or sell copies of the Software, and to
 //     permit persons to whom the Software is furnished to do so, subject to
 //     the following conditions:
 //
 //     The above copyright notice and this permission notice shall be included
 //     in all copies or substantial portions of the Software.
 //
 //     THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
 //     OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 //     MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 //     IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
 //     CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
 //     TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
 //     SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 // }}}

#include <cstddef>
#include <iostream>

using std::size_t;

constexpr size_t factorial_int( size_t n )
{
    return n==0 ? 1 : n * factorial_int( n-1 );
}

static_assert( factorial_int(0)==1,        "0  faild" );
static_assert( factorial_int(1)==1,        "1  faild" );
static_assert( factorial_int(2)==2,        "2  faild" );
static_assert( factorial_int(3)==6,        "3  faild" );
static_assert( factorial_int(4)==24,       "4  faild" );
static_assert( factorial_int(5)==120,      "5  faild" );
static_assert( factorial_int(6)==720,      "6  faild" );
static_assert( factorial_int(7)==5040,     "7  faild" );
static_assert( factorial_int(8)==40320,    "8  faild" );
static_assert( factorial_int(9)==362880,   "9  faild" );
static_assert( factorial_int(10)==3628800, "10 faild" );


int main()
{
    size_t n;
    std::cout << "value=";
    std::cin >> n;
    std::cout << factorial_int(n) << std::endl;
    return 0;
}

典型的な再帰を用いた実装．
constexprな関数を使ってコンパイル時に動作テストをしています．
constexprな関数はTMPと違って実行時にも使用できます．

ii), iii) の解答

factorial_real.cpp

 // FILE: factorial_real.cpp
 // AUTHOR: rhysd (http://d.hatena.ne.jp/rhysd/)
 // License: MIT license  {{{
 //     Permission is hereby granted, free of charge, to any person obtaining
 //     a copy of this software and associated documentation files (the
 //     "Software"), to deal in the Software without restriction, including
 //     without limitation the rights to use, copy, modify, merge, publish,
 //     distribute, sublicense, and/or sell copies of the Software, and to
 //     permit persons to whom the Software is furnished to do so, subject to
 //     the following conditions:
 //
 //     The above copyright notice and this permission notice shall be included
 //     in all copies or substantial portions of the Software.
 //
 //     THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
 //     OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 //     MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 //     IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
 //     CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
 //     TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
 //     SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 // }}}

#include <cmath>
#include <iostream>

namespace detail{
    static const double pi = 3.1415926535;
    static const double e = 2.71828183;

    inline double inv( double const n )
    {
        return 1.0 / n;
    }

    inline double gamma( double const z )
    {
        return std::sqrt( 2 * pi / z ) * std::pow((z + inv( 12 * z - inv( 10 * z ) )) / e, z);
    }

}

double factorial_real( double z )
{
    using std::size_t;
    double div_value = 1.0;
    ++z;

    while(  z < 10.0 ){
        ++z;
        div_value *= z - 1.0;
    }

    return detail::gamma(z) / div_value;
}

int main()
{
    double d;

    std::cout << "value=";
    std::cin  >> d;
    std::cout << factorial_real( d ) << std::endl;

    std::cout << "value=";
    std::cin  >> d;
    std::cout << factorial_real( d ) << std::endl;

    return 0;
}

ガンマ関数を利用することで階乗を正の実数に容易に拡張できます．
基本的な数学関数以外使ってはいけないということだったので，簡単に実装できるスターリングの公式を利用しました．
このままだと負数に対応できず，またスターリングの公式は10^0 〜 10^1手前までの近似が正しくできない（log n! ≒ n log n - n に由来）ので，zが10未満のときは

Gamma(z) = (z-1)! = Gamma(z+1) / z

の性質を使って Gamma(10)まで持って行ってから計算すると良い近似を得られます．

ライセンス

コード内にも明記してありますが，ライセンスはMIT Licenseです．