一道笔试：阶乘比较

ypxing

原帖由 MMMIX 于 2007-5-31 18:39 发表

没错，楼主的问题可以简化为如下：

给定正整数 n1, n2, 问当什么情况下 n1 >= n2!...! ? (假设有 n 个 !，n 为正整数）

这个问题怎么解决呢？

这个问题这样解决,
求满足n3!<n1<n4!的最大的n3和最小的n4
n3和n4是比较好求的,
然后再进行比较

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

parkerchou

那么大的数如何阶乘啊？！
曾经有看过一个高手写了一 个能在普通pc上算1000阶乘的代码，经研究后发现也是有局限性的。
阶乘的结果最多是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(   "输入要求阶乘的数:   "   );   
                  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 发表


这个问题这样解决,
求满足n3!<n1<n4!的最大的n3和最小的n4
n3和n4是比较好求的,
然后再进行比较

感觉距离解决遥之又遥。

ypxing

原帖由 MMMIX 于 2007-5-31 19:28 发表

感觉距离解决遥之又遥。

如果n1是个任意大的数,大过计算机对整数的表示能力,就比较难解决
但如果n1小于等于计算机对整数的表示能力,问题很简单

MMMIX

原帖由 ypxing 于 2007-5-31 19:34 发表


如果n1是个任意大的数,大过计算机对整数的表示能力,就比较难解决
但如果n1小于等于计算机对整数的表示能力,问题很简单

这样啊，那你直接给个完整的实现得了，就假设 n1 是 int 型的。

red999

如果只是比较大小的话，个人感觉没必要将阶乘全部算出来，
这里说下个人的想法：
这里我把一个!叫做“1阶”；
首先我们可以将较低的阶数“约掉”，
例如，3!!!!!!!!!和4!!!!!!!,通过判断可以知道分别是9阶和7阶，那么我们可以“约掉”7阶
也就是说只要比较3!!和4就可以了。
其次，约掉之后也没必要算出，毕竟如果两个数的阶数相差太大，那么还是不能忍受的，那我
们可以这样,将需要阶乘的那个数从0阶开始，每计算一阶就和不需阶乘的数做比较，那么还是
这样的结果我觉得可以完全可以接受。

drowsyboy

呵呵，我只是发上来，大家讨论下~，这几天过六一节去了

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;
}