Chinaunix首页 | 论坛 | 博客
  • 博客访问: 556883
  • 博文数量: 99
  • 博客积分: 5015
  • 博客等级: 大校
  • 技术积分: 1209
  • 用 户 组: 普通用户
  • 注册时间: 2009-05-28 23:08
文章存档

2011年(7)

2010年(6)

2009年(86)

我的朋友

分类: C/C++

2009-11-02 11:15:22

本文来源于csdn2001年的一个帖子,题目是有谁可以用四行代码求出1000000的阶乘!!!,见
,我在该帖中给出了代码。但严格的将,这个代码的行数并未控制在4行以内。这次给出一个只用4行代码计算10000以内的阶乘的完整程序,并给出代码优化(压缩)过程)
   下面看看这个程序的最初形式
//第一版,正常的格式 
#define N 10    //计算N的阶乘,最多只能算到9999 
long a[8916]={1,0},n,i,c,len;
int main() 
{
    n=N;
    for ( len=1;n>1; n--)
    {
        for (c=0,i=0; i        {
            long p= a[i]*n+c;
            a[i]= p % 10000;
            c=p / 10000;
        }
        a[i]= c;
        if (c>0)
            len++;
    }
    printf("%d",a[len-1]);
    for( len--;len>=0;len--)
        printf("%04d",a[len]);
    return 0;
}
代码的首次改进,压缩代码行数
// 第二版: 将打印语句缩写到1行,同时化简计算部分的内循环
#define N 100   //计算N的阶乘,最多只能算到9999
long a[8916]={1,0},n,i,c,len;
int main() 
{
    n=N;
    for ( len=1;n>1; n--)
    {
        for (c=0,i=0; i        {
            a[i]= ( c+= a[i]*n ) % 10000; c/=10000;
        }
        a[i]= c;
        if (c>0)
        len++;
    }
    for( len--,printf("%d",a[len--]);len>=0; len--) printf("%04d",a[len]);
        
    return 0;
}
进一步改进

// 版本3:将外循环的最后2条语句改为一个 "?" 语句 将
#define N 10    //计算N的阶乘,最多只能算到9999
long a[8916]={1,0},n,i,c,len;
int main() 
{
    n=N;
    for ( len=1;n>1; n--)
    {
        for (c=0,i=0; i        {
            a[i]= ( c+= a[i]*n ) % 10000; c/=10000;
        }
        
        ((a[i]=c)>0)?len++:0;
    }   
    for( len--,printf("%d",a[len--]);len>=0; len--) printf("%04d",a[len]);
        
    return 0;
}
再次改进
// 版本4
// 将内循环中的两条语句变成一条语句,用逗号分隔,去掉{}
// 将外循环最后一行 和 外循环 for语句第三部分 "n--"合并,
// 进行格式重排,将main函数和变量定义语句放入一行
// 将将 len从1开始改为从0开始
#include
#define N 10 //计算N的阶乘,修改N的定义可计算10000以内任意数的阶乘    
long a[N]={1,0},n,i,c,len; void main() {
for ( n=N,len=0;n>1;((a[i]=c)>0) ? (len++,n--) : n--)
    for (c=0,i=0; i<=len;i++ )  a[i]= ( c+= a[i]*n ) % 10000, c/=10000;
for( printf("%d",a[len--]);len>=0; len--) printf("%04d",a[len]); }
版本5,进一步优化,不算include, #define 及回车换行符,只有170个byte. 主要改进有:
1. 删除多余的空格
2. "a[8916]={1,0}" 改为 "a[N]={1}",节省5个字符
3. 变量赋值 n=N 放到变量声明语句,减少1个字符
4. len 改为单变量m, 减少了10个以上的字符
5. 全局变量自动初始化为0,len=0,这句去掉
6. "((a[i]=c)>0)?(m++,n--):n--" 改为 "(a[i]=c)>0?m++:0,n--",节省了6个字符
7. 最后一个for 语句中,由"printf("%d",a[m--]);m>=0;m--" 调整为 "printf("%d",a[m]);--m>=0;", 节省了4个字符
8. 虽然说long 改为int 可节约一个字符,但这样的话,在16为编译器的运行结果将出错,失去了通用性
//版本5
#include  
#define N 10 //计算N的阶乘,修改N的定义可计算10000以内任意数的阶乘     
long a[N]={1},n=N,i,c,m;void main(){
for(;n>1;(a[i]=c)>0?m++:0,n--)
for(c=0,i=0;i<=m;i++)a[i]=(c+=a[i]*n)%10000,c/=10000;
for(printf("%d",a[m]);--m>=0;)printf("%04d",a[m]);}
版本6,再次改进,又减少11个字符,扣除#include 和 #define语句,共159个字节
#include
#define N 10 //计算N的阶乘,修改N的定义可计算10000以内任意数的阶乘 
int a[N]={1},n=N,i,c,m;void main(){
for(;n;(a[i]=c)>0?m++:0,n--)
for(c=i=0;i<=m;i++)a[i]=(c+=a[i]*n)%10000,c/=10000;
for(c=m+1;c;)printf(c>m?"%d":"%04d",a[--c]);}
版本7:采用10进制,在主流编译器可以实现1-200000的阶乘,扣除#include 和 #define语句,共153个字节,但是速度较慢。
 
#include
#define N 10 //计算N的阶乘,修改N的定义可计算200000以内任意数的阶乘
int a[N*5]={1},n=N,i,c,m;void main(){
for(;n;n--){
for(c=i=0;i<=m;i++)a[i]=(c+=a[i]*n)%10,c/=10;
while(c)a[++m]=c%10,c/=10;}
for(;m>=0;)printf("%d",a[m--]);}

本文来自CSDN博客,转载请标明出处:http://blog.csdn.net/liangbch/archive/2008/11/05/3230428.aspx
 
雨中飞燕也写了个,参考:
//计算1000!
#include
#define N 1000    //要计算的N
long s[N]={1,1},n=N,t=2,a=1,b=0;
int main()//雨中飞燕之作
{
    for(;a <= *s || (++t <= n ? (b = 0 , a =1) : 0) ; (*s == a++ && b) ? (*s) ++ : 0)
        s[a] = (b += s[a] *t) %10000 , b /= 10000 ;


    for(printf("%d",s[*s]);--*s>0;)printf("%04d",s[*s]);
    return 0;
}
阅读(4337) | 评论(12) | 转发(0) |
给主人留下些什么吧!~~

kennethb2009-11-20 00:52:21

我喜欢!楼主加油!

chinaunix网友2009-11-12 23:16:17

ls你确认你的精度足够了?

brauceunix2009-11-11 10:45:44

void jc(long num) { double sum; if(num == 1) sum = 1; else jc = jc(num-1)*num; }

brauceunix2009-11-11 10:43:26

dfdf

naihe20102009-11-07 21:30:40

确实是够垃圾的!