学步园

这题我看了好几次,因为没学过错排,一直不敢做,今天看了下错排,可以用错排的公式做,但一神牛告诉我,可以DP,DP公式

f( n ) = (  f( n - 1 ) + f( n -2 )  ) * ( n - 1 );

#include<stdio.h>
double num[25],N[25];
void chart( )
{
     num[1] = 0;
     num[2] = 1;
     N[1] = 1;
     N[2] = 2;
     for( int i = 3; i < 25; ++i )//num[i]是错排
          num[i] += ( num[i-1] + num[i-2] ) * ( i - 1 ),N[i] = i * N[i-1];//DP
 }
int main( )
{
    chart( );
    int t,n;
    scanf( "%d",&t );
    while( t-- )
    {
           scanf( "%d",&n );
           printf( "%.2lf%%\n",( num[n] * 1.0 / N[n] ) * 100 );
           }
    return 0;
}

下面的是用错排公式f( n ) = n!( 1 / 2! - 1 / 3! + 1/4! ......+( -1 ) ^ n * 1 / n! )

#include<stdio.h>
double num[25];
void chart( )//求n的阶乘
{
     num[1] = 1;
     for( int i = 2; i < 25; ++i )
          num[i] = i * num[i-1];//printf( "%.lf\n",num[i] );
 }
double cal( int n )
{
       double sum = 0;
       for( int i = 2; i <= n; ++i )
       {
            int t = 1;
            if( i % 2 )
                t = -1;
            sum += num[n] / num[i] * t;//公式
        }
        return sum;
}
int main( )
{
    chart(  );
    int t,n;
    scanf( "%d",&t );
    while( t-- )
    {
           scanf( "%d",&n );
           double sum = cal( n );
           printf( "%.2lf%%\n",sum / num[n] * 100 );
           }
    return 0;
}