Archive for February, 2010

2010/02/19
Tags: ,. 15,714 views
2010/02/10

前两天一直在做这一道题,题目其实很简单,求n的阶乘,即从1× 2× 3……× n。但是这个要求的数特别大,当n=100000时,结果恐怕有上万位,所以,一种解决方法是用数组存储各个数位,例如用数组 array[] 储123456789,那么array[0]=1,array[1]=2 …..array[8]=9。至于计算过程,我们可以想象一下自己做乘法,例如,算12× 34 ,先算12×4,再将结果移位并×3。好了,整个解题的基本原理就是这样了。 初次尝试 为了节约储存的空间,我第一次是用char型数组存储各位的,但在计算的过程中,不可避免的要遇到把字符转换为数字的过程,在每次一次算中,特别是数据非常大时,每一次计算要有成千上万次的字符转数字过程,所以最后的结果是时间超时,并不是我当初未雨绸缪的“内存超限”,当然,其中有一步没有优化,总之失败。 第二次尝试 这次,去网上搜了一些成功的案例以及在论坛提问,于是决定用int数组存储数字的各位,例如,结果是 123456789,那么 int[0]=1,int[1]=2…..int[8]=9。再用一个int型 pos记录结果有多少位,这样可以节约for()循环的时间,最后AC了。 按照 davelv 的思路优化 主要的思想是用一个int存很多个数据,而之前我是一个int只存一个数。 如果最后结果是 12345678909876543210000 D大是 r[0]=543210000 r[1]=678909876 r[2]=12345 我原来理解是 从r[0]~~r[23]各存一位,那么每次的取模(MOD)就应该是1 000 000 000了,而不是10。一个int 4字节,最大2^32-1 ,结果 =4 294 967 294,一共9位。 这样优化的确大大的提高了执行效率,减少了内存占用,上图,下面一行为优化后的。 可见,优化的力量是非常强大的! 好了,就写到这儿 贴出   我的代码 和   davelv的代码(你不介意吧 ^_^) 后记:就在我写这篇博文的时候,神奇的D牛还在优化代码,据说他的代码已经可以在200毫秒左右执行完了!膜拜之~等待明天他的解题报告!

Tags: . 14,692 views

D大叫我要勤更新,好吧,再贴一个HDU的ACM题,这道很简单,相当简单,小牛以上的都请路过 原题:http://acm.hdu.edu.cn/showproblem.php?pid=1012 其实就是用它给出的一个公式计算e的近似值,好了,贴代码,顺便透露一下,下一篇日志,我将写一下上次热烈讨论的HDU 1042 ,尽请期待~ 01 /* ******************* 02 *Author: Wang Runzhen  03 *Date:   2010.2.9 04 ******************** */ 05 #include<stdio.h> 06 int main(void) 07 { 08     int i,j,k=1; 09     double e=0.0; 10     printf(“n e\n– ———–\n“); 11  12     for(i=0;i<10;i++){ 13         for(j=1;j<=i;j++) 14         { 15             k*=j; 16    […]

Tags: . 4,945 views
2010/02/03

对于独立博客的前途,哥笑而不语,哥静观其变,哥想看看伟大的CNNIC、域名商、主机商到底想怎么折腾

Tags: . 12,901 views