Chinaunix

标题: 一道笔试：阶乘比较 [打印本页]

作者: drowsyboy 时间: 2007-05-31 18:13
标题: 一道笔试：阶乘比较
记得以前在CU上看到过，有关大数阶乘计算的文章，这道题目应该没有那么难，给各位大人小练一下。

题目是这样的：

写一个程序，接受两个输入比如 12！！！！！和 3！！！！，这里输入，一定是由一个大于0的整数和！符号组成，！表示阶乘（3！！表示3阶乘后再求阶乘，依次类推）

程序要实现的就是要比较两个输入数的大小。

呵呵，不知道说清楚没有：）

作者: MMMIX 时间: 2007-05-31 18:18

原帖由 drowsyboy 于 2007-5-31 18:13 发表
记得以前在CU上看到过，有关大数阶乘计算的文章，这道题目应该没有那么难，给各位大人小练一下。

题目是这样的：

写一个程序，接受两个输入比如 12！！！！！和 3！！！！，这里输入，一定是由一个大于0的 ...

啥公司出这种考数学的题目？

作者: ypxing 时间: 2007-05-31 18:23

原帖由 drowsyboy 于 2007-5-31 18:13 发表
记得以前在CU上看到过，有关大数阶乘计算的文章，这道题目应该没有那么难，给各位大人小练一下。

题目是这样的：

写一个程序，接受两个输入比如 12！！！！！和 3！！！！，这里输入，一定是由一个大于0的 ...

说清楚了,感觉是挺简单的

作者: MMMIX 时间: 2007-05-31 18:25

原帖由 ypxing 于 2007-5-31 18:23 发表

说清楚了,感觉是挺简单的

说说详细算法吧。

作者: doni 时间: 2007-05-31 18:32
12！！！！！和 3！！！！
应该就是比12!和3吧

作者: ypxing 时间: 2007-05-31 18:33

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

说说详细算法吧。

说说我的想法吧,
这么大的数,我会选择用字符串表示
比如"4!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!"

有两个这样的数的话,
比如3!!!!和5!!!
我会先比较它们!的个数
然后,我会比较3! 和5 (就是去掉相同个!后)

这样,后面的就比较容易比较了

作者: namei 时间: 2007-05-31 18:39

原帖由 ypxing 于 5/31/2007 18:33 发表

说说我的想法吧,
这么大的数,我会选择用字符串表示
比如"4!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!"

有两个这样的数的话,
比如3!!!!和5!!!
我会先比较它们!的个数
然后,我会比较3! 和5 ( ...

汗

要不咱先估计一下4!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!有多少十进制位

作者: MMMIX 时间: 2007-05-31 18:39

原帖由 ypxing 于 2007-5-31 18:33 发表

说说我的想法吧,
这么大的数,我会选择用字符串表示
比如"4!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!"

有两个这样的数的话,
比如3!!!!和5!!!
我会先比较它们!的个数
然后,我会比较3! 和5 ( ...

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

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

这个问题怎么解决呢？

作者: MMMIX 时间: 2007-05-31 18:41

原帖由 doni 于 2007-5-31 18:32 发表
12！！！！！和 3！！！！
应该就是比12!和3吧

嗯，正整数上的 ! 运算是严格单增的。

作者: ypxing 时间: 2007-05-31 18:42

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

汗
要不咱先估计一下4!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!有多少十进制位

所以,字符串伺候之

作者: ypxing 时间: 2007-05-31 18:44

原帖由 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 时间: 2007-05-31 19:10
那么大的数如何阶乘啊？！
曾经有看过一个高手写了一个能在普通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 时间: 2007-05-31 19:28

原帖由 ypxing 于 2007-5-31 18:44 发表

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

感觉距离解决遥之又遥。

作者: ypxing 时间: 2007-05-31 19:34

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

感觉距离解决遥之又遥。

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

作者: MMMIX 时间: 2007-05-31 19:36

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

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

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

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

作者: drowsyboy 时间: 2007-06-05 16:45
呵呵，我只是发上来，大家讨论下~，这几天过六一节去了

作者: drowsyboy 时间: 2007-06-05 16:48
标题: 贴下我的当时答题的代码
#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;
}

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)