Algorithm 版 (精华区)
发信人: ssos (存在与虚无·戒酒戒网), 信区: Algorithm
标 题: [合集]下午acm比赛最难的一题(转寄)(转载)
发信站: 哈工大紫丁香 (2001年11月03日11:45:47 星期六), 站内信件
────────────────────────────────────────
sino (一层秋雨一层凉) 于 2001年10月31日11:04:50 星期三 说道:
【 以下文字转载自 sino 的信箱 】
────────────────────────────────────────
rogerz (第一滴雨) 于 发信站: BBS 水木清华站 (Sat Oct 27 20:51:37 2001)
The problem is given a positive integer N,calculate how many zero
digits the N! has.
注意要计算的不是末尾的0的个数，还包括中间的。
一看给的case，登时傻了。
12345678909876543210
这似乎更是一个数学问题。下午那么多队没有一队能做出来。
谁有好的解决方法吗？
────────────────────────────────────────
davidchang (离休干部) 于 2001年10月31日11:19:25 星期三 说道:
没做出来还是做的效果不好？
────────────────────────────────────────
rogerz (第一滴雨) 于
────────────────────────────────────────
thering (没完没了) 于 2001年10月31日11:26:22 星期三 说道:
我倒有一种方法：
可以将这个数（任意），作为字符串存储起来，再将它从个位起划分为4位一组，例如（
345 2363 4375），然后取N-1，也类似这样划分，4x4的计算是没问题的，计算后存到文本中，重
复上述操作，一的可以得到N!的文本形式，就得到结果了。
────────────────────────────────────────
rogerz (第一滴雨) 于
────────────────────────────────────────
Lerry (Lerry) 于 2001年10月31日15:39:24 星期三 说道:
这是一个集合运算
────────────────────────────────────────
rogerz (第一滴雨) 于
────────────────────────────────────────
ssos (存在与虚无·戒酒戒网) 于 2001年10月31日17:26:10 星期三 说道:
faint
超级高精计算~~~
────────────────────────────────────────
rogerz (第一滴雨) 于
────────────────────────────────────────
sino (一层秋雨一层凉) 于 2001年10月31日21:13:09 星期三 说道:
是没有人做出来
────────────────────────────────────────
rogerz (第一滴雨) 于
────────────────────────────────────────
sino (一层秋雨一层凉) 于 2001年10月31日21:20:28 星期三 说道:
我觉得，这个数不能直接计算出来。
所有19的数乘起来，已经就有18*9E18位，去掉末尾的0，也是1E19数量级的
实在无法存储如此多的数字。
────────────────────────────────────────
rogerz (第一滴雨) 于
────────────────────────────────────────
sino (一层秋雨一层凉) 于 2001年10月31日21:20:59 星期三 说道:
具体的呢？
────────────────────────────────────────
rogerz (第一滴雨) 于
────────────────────────────────────────
ssos (存在与虚无·戒酒戒网) 于 2001年10月31日21:23:53 星期三 说道:
如果时间允许,可以编一个压缩算法:)
────────────────────────────────────────
sino (一层秋雨一层凉) 于 2001年10月31日21:54:43 星期三 说道:
faint.....
────────────────────────────────────────
ssos (存在与虚无·戒酒戒网) 于 2001年10月31日21:59:03 星期三 说道:
n的上限是多少??
────────────────────────────────────────
deem (摩亚迪·沙丘男爵) 于 2001年11月01日10:48:38 星期四 说道:
哈哈，不管多少，直接搞肯定算不出来！
肯定有其他的方法
────────────────────────────────────────
sino (一层秋雨一层凉) 于 2001年11月01日12:05:49 星期四 说道:
n只有一个数：12345678909876543210
────────────────────────────────────────
cucme (说你说我) 于 2001年11月01日12:32:17 星期四 说道:
我现在开始做这个题，看看中午能不能做完.
────────────────────────────────────────
cucme (说你说我) 于 2001年11月01日13:49:07 星期四 说道:
做完了，测试以下吧，呵呵。
$ time ./main 12345678909876543210
there are 3086419727469135788 factor 5 in 12345678909876543210!
so, there are 3086419727469135788 0 in the end of 12345678909876543210!, :-)
0.00user 0.00system 0:00.00elapsed 0%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (89major+11minor)pagefaults 0swaps
直接就出来了，:-)
────────────────────────────────────────
ssos (存在与虚无·戒酒戒网) 于 2001年11月01日14:11:46 星期四 说道:
硬做的???
────────────────────────────────────────
cucme (说你说我) 于 2001年11月01日14:12:22 星期四 说道:
小学就做过有到题，问100!的最后0的个数，当时是这么做的（心算）：
100/5 = 20
20 /5 = 4
4 /5 = 0
----
24
显然查一个数最后0的个数就是查该数的因子10的个数，也就是查
因子2,5个数中最少的那个，显然因子2的个数比5的个数多得多，
那么，这个问题就变成查一个数中因子5的个数了，
而本题中n太大，让我心算是不可能的了（心算高手肯定可以做）
而让computer直接按以上方式计算也不可能，
so, 问题就转换成超大数的/+运算了:
1. / 幸好只需要处理n/5这样的除以“单字节”数的问题，这个
也不难，按照计算机的标准算法从高位往低位逐步计算就可以了
2. + 当然是从低位往高位逐步加，处理好进位链就可以了。
以下是我做的源码：
---------------------------main.c----------------------------------------
#include <stdio.h>
#include <string.h>
#include <malloc.h>
void add(char *x, char *y);
void div5(char *num);
void rev(char *num);
int main(int argc, char **argv)
{
char *number, *num;
char *five;
int len;
if( argc < 2 )
{
printf("Usage: %s num\n", argv[0]);
exit(1);
}
if( strspn(argv[1], "0123456789") < strlen(argv[1]) )
{
printf("the number you give is invalid.\n");
exit(1);
}
len = strlen(argv[1]);
number = malloc(len+1);
five = malloc(len+1);
strcpy(number, argv[1]);
memset(five, '0', len);
five[len] = '\0';
while(1)
{
div5(number);
if( strlen(number) == 0 )
break;
add(five, number);
}
rev(five);
printf("there are %s factor 5 in %s!\n", five, argv[1]);
printf("so, there are %s 0 in the end of %s!, :-)\n", five, argv[1]);
free( number );
free( five );
return 0;
}
void div5(char *num)
{
int reg, flag;
char *p, *q;
p = q = num;
flag = 1;
reg = 0;
for( ; *p != '\0'; p++ )
{
reg = reg*10 + *p - '0';
*q = reg/5 + '0';
if( flag )
{
if( *q != '0' )
{
flag=0;
q++;
}
}
else
q++;
reg = reg%5;
}
*q = '\0';
}
void add(char *x, char *y)
{
int reg;
int p, q;
p = 0;
q = strlen(y)-1;
for( reg = 0; q>=0; p++,q--)
{
reg += x[p] - '0' + y[q] - '0';
x[p] = reg%10 + '0';
reg /= 10;
}
for(; reg>0; p++)
{
reg += x[p] - '0';
x[p] = reg%10 + '0';
reg /=10;
}
}
void rev(char *num)
{
int p,q;
char ch;
p=0;
q=strlen(num)-1;
for( ; q>0; q-- )
if( num[q] != '0' )
break;
num[q+1] = '\0';
for(; p<=q; p++, q--)
{
ch = num[p];
num[p] = num[q];
num[q] = ch;
}
}
────────────────────────────────────────
ssos (存在与虚无·戒酒戒网) 于 2001年11月01日14:14:04 星期四 说道:
不是求最后的0的个数,而是求整个结果中0的个数(包括中间的0
────────────────────────────────────────
deem (摩亚迪·沙丘男爵) 于 2001年11月01日14:14:29 星期四 说道:
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
────────────────────────────────────────
rogerz (第一滴雨) 于 发信站: BBS 水木清华站 (Sat Oct 27 20:51:37 2001)
The problem is given a positive integer N,calculate how many zero
digits the N! has.
注意要计算的不是末尾的0的个数，还包括中间的。
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 老大！！
一看给的case，登时傻了。
12345678909876543210
────────────────────────────────────────
cucme (说你说我) 于 2001年11月01日14:20:09 星期四 说道:
掩面而去...... 呵呵，:-)
────────────────────────────────────────
rogerz (第一滴雨) 于
────────────────────────────────────────
deem (摩亚迪·沙丘男爵) 于 2001年11月01日14:28:41 星期四 说道:
呵呵，要是在锦赛的时候范了这样的错误，一遍又一遍地
提交结果，判决就是错误，那才郁闷呢！
────────────────────────────────────────
rogerz (第一滴雨) 于
────────────────────────────────────────
ssos (存在与虚无·戒酒戒网) 于 2001年11月01日14:28:57 星期四 说道:
为啥不用你们那里的高档机器试一下硬做的效果呢
────────────────────────────────────────
rogerz (第一滴雨) 于
────────────────────────────────────────
ssos (存在与虚无·戒酒戒网) 于 2001年11月01日14:29:19 星期四 说道:
没关系
不对的题不加时间
────────────────────────────────────────
sino (一层秋雨一层凉) 于 2001年11月01日15:03:05 星期四 说道:
分析的很好啊！
────────────────────────────────────────
sino (一层秋雨一层凉) 于 2001年11月01日15:03:37 星期四 说道:
呵呵，精神可嘉！
────────────────────────────────────────
rogerz (第一滴雨) 于
────────────────────────────────────────
sino (一层秋雨一层凉) 于 2001年11月01日15:04:13 星期四 说道:
是啊！
────────────────────────────────────────
Powered by KBS BBS 2.0 (http://dev.kcn.cn)
页面执行时间：214.167毫秒