一道筆試：階乘比較

ypxing

原帖由 MMMIX 于 2007-5-31 18:39 發(fā)表

沒錯，樓主的問題可以簡化為如下：

給定正整數(shù) n1, n2, 問當(dāng)什么情況下 n1 >= n2!...! ? (假設(shè)有 n 個 !，n 為正整數(shù)）

這個問題怎么解決呢？

這個問題這樣解決,
求滿足n3!<n1<n4!的最大的n3和最小的n4
n3和n4是比較好求的,
然后再進行比較

[ 本帖最后由 ypxing 于 2007-5-31 18:52 編輯 ]

parkerchou

那么大的數(shù)如何階乘�。�！
曾經(jīng)有看過一個高手寫了一 個能在普通pc上算1000階乘的代碼，經(jīng)研究后發(fā)現(xiàn)也是有局限性的。
階乘的結(jié)果最多是32767位。
代碼如下：
#include   <stdio.h>   
#define   max   32767   
main()   
{         
        int   n;   
        int   sum=0;   
        int   a[max+1];                              
        int   i,j,k,x;
        while   (1)   
          {   
                  printf(   "輸入要求階乘的數(shù):   "   );   
                  scanf   (   "%d",   &n   );   
                    k=max;   
                  a[k]=1;   
                  for(i=2;i<=n;i++)                     
                  {   
                          x=0;                                         
                          for(j=max;j>=k;j--)   
                          {   
                          x=a[j]*i+x;                  
                          a[j]=x%10;                                                     
                          x=x/10;                           
                         }   
                 while(x>0)                             
                 {   
                          k--;   
                          a[k]=x%10;   
                          x=x/10;   
                 }
        }
//輸出   
                for(i=k;i<=max;i++)   
                {   
                        printf(   "%d",   a[i]   );   
                }   
                printf(   "\n"   );   
        }   
        return   0;   
}


小弟對他的算法佩服得5體投地！！

MMMIX

原帖由 ypxing 于 2007-5-31 18:44 發(fā)表


這個問題這樣解決,
求滿足n3!<n1<n4!的最大的n3和最小的n4
n3和n4是比較好求的,
然后再進行比較

感覺距離解決遙之又遙。

ypxing

原帖由 MMMIX 于 2007-5-31 19:28 發(fā)表

感覺距離解決遙之又遙。

如果n1是個任意大的數(shù),大過計算機對整數(shù)的表示能力,就比較難解決
但如果n1小于等于計算機對整數(shù)的表示能力,問題很簡單

MMMIX

原帖由 ypxing 于 2007-5-31 19:34 發(fā)表


如果n1是個任意大的數(shù),大過計算機對整數(shù)的表示能力,就比較難解決
但如果n1小于等于計算機對整數(shù)的表示能力,問題很簡單

這樣啊，那你直接給個完整的實現(xiàn)得了，就假設(shè) n1 是 int 型的。

red999

如果只是比較大小的話，個人感覺沒必要將階乘全部算出來，
這里說下個人的想法：
這里我把一個!叫做“1階”；
首先我們可以將較低的階數(shù)“約掉”，
例如，3!!!!!!!!!和4!!!!!!!,通過判斷可以知道分別是9階和7階，那么我們可以“約掉”7階
也就是說只要比較3!!和4就可以了。
其次，約掉之后也沒必要算出，畢竟如果兩個數(shù)的階數(shù)相差太大，那么還是不能忍受的，那我
們可以這樣,將需要階乘的那個數(shù)從0階開始，每計算一階就和不需階乘的數(shù)做比較，那么還是
這樣的結(jié)果我覺得可以完全可以接受。

drowsyboy

呵呵，我只是發(fā)上來，大家討論下~，這幾天過六一節(jié)去了

drowsyboy

#include <stdio.h>
#include <stdlib.h>
/**************************************************************************
* function : get_element
*
* Discription:
*        the function is used to extract elemnts from formatted string
*       
* Input parameters:
*        char *pstr:         the input string
*        int *value:         record the value
*       int *length:         record the length of (!)
*       
* Output parameters:
*        void
*
* Author: Created by huzza.hu May.30th.2007
**************************************************************************/
static void get_element( char *pstr, int *value, int *length)
{
        int string_len = strlen( pstr );
        int i = 0;
       
        *value = 0;
        *length = 0;
       
        while ( i < string_len ){
                if ( pstr[i] != '!'){
                        *value = (*value)*10 + pstr[i] - '0';
                }
                else{
                        break;
                }
               
                i++;       
        }

        while ( i < string_len ){
                (*length) ++;

                i++;
        }               
}

/**************************************************************************
* function : calfac
*
* Discription:
*       the function is used to calculate the factorial of base
*
* Input parameters:
*      int base: the base value
*
* Output parameters:
*      int : the factorial of base
*
* Author: Created by huzza.hu May.30th.2007
**************************************************************************/
static int calfac( int *base, int compval )
{
        int i = *base;
        int calvalue=1;
       
        for( ; i > 1 ; i-- ){
                calvalue = calvalue * i;
                if ( calvalue > compval ){
                        return 1;
                }       
        }
       
        *base = calvalue;

        return 0;
}

/**************************************************************************
* function : compare
*
* Discription:
*       the function is used to compare the elements
*
* Input parameters:
*        char *pa: the first input parameters
*        char *pb: the second input paramters

* Output parameters:
*       int: if (*pa > *pb) return 1
*             esle        retrun 0
*
* Author: Created by huzza.hu May.30th.2007
**************************************************************************/
int compare(char *pa, char *pb)   //no static here, so can be called by other program
{
        int iCompa, iCompb;
        int numa, numb;
        int min = 0;
        int result = 0;
       
        get_element( pa , &iCompa, &numa);
        get_element( pb , &iCompb, &numb);
       
        printf("%d,the length of (!) is:%d\n", iCompa, numa);
        printf("%d,the length of (!) is:%d\n", iCompb, numb);
       
        min = (( numa > numb ) ? numb:numa);
        numa = numa - min;
        numb = numb - min;

        result = ( iCompa > iCompb );
       
        if ( 0 == numa ){
                while( numb > 0 ){
                        result = calfac( &iCompb, iCompa );
                        if ( 1 == result ){
                                result = 0;
                                break;
                        }
                        else{
                                result = 1;
                        }
                        numb--;
                }
        }
        else{
                while( numa > 0 ){
                        result = calfac( &iCompa, iCompb );
                        if ( 1 == result){
                                break;
                        }
                        else{
                                result = 0;
                        }
                        numa--;
                }
        }       
       
        return result;  
}

/**************************************************************************
* function : main
*
* Discription:
*       the function is used to get the input of customer and output the result
*
* Input parameters:
*        void
*
* Output parameters:
*       int: error code
*             0 no error; >0 error
*
* Author: Created by huzza.hu May.30th.2007
**************************************************************************/
int main(void)
{
        char acCompa[128];
        char acCompb[128];
        int flag = 0;

        printf("please input two compares:\n");
        scanf("%s", acCompa);
        scanf("%s", acCompb);

        printf("number1:%s\n", acCompa);
        printf("number2:%s\n", acCompb);

        flag = compare(acCompa, acCompb);
       
        printf("%s is bigger than %s.\n", (flag == 1) ? acCompa:acCompb,(flag == 1) ? acCompb:acCompa);
       
        return 0;
}