| 网站首页 | 业界新闻 | 小组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
共有 8882 人关注过本帖, 1 人收藏
标题:挑战C版所有人,1000!
只看楼主 加入收藏
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
回复 59楼 lin5161678
刚刚试过用位运算取位,但发现了实现的过程中数据输出会出现问题,或者这个不适合用位运算实现,刚刚就是想到说了一下,看来还是要对数据取余输出的~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2018-06-02 20:12
lin5161678
Rank: 12Rank: 12Rank: 12
等 级:贵宾
威 望:35
帖 子:1103
专家分:3530
注 册:2011-12-3
收藏
得分:0 
回复 52楼 xzlxzlxzl
哦 看懂了 的确算法是一样的

https://zh.
2018-06-02 20:20
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
我也弄了个简单的出来不过得出的结果却是16进制的,如果要转换成10进制那么要把那个大数看作一个整体转换才行,没有验证结果,(或者结果是错误的),当然效率也不怎么样了,就是简单弄个看看而已~

还有一个小优化的方案,就是在内循环开始之前跳过前导0直接从非0位开始判断,n!统计0的个数这个好弄吧~
要想更高效的或者只能直接用FFT之类的算法减少乘法运算量了,算是这样了~

PS:此代码有bug,把 a[count++]=0;改成a[count++]=GET_HIGH(a[j-1]);即可~具体可以看看80楼的代码
嗯,80楼的应该可以了~


程序代码:
#include<stdio.h>

#define GET_LOW( s )    \
    ((s)&0x0000ffff)
        
#define GET_HIGH( s )    \
    (((s)&0xffff0000)>>16)

unsigned fun( unsigned[],unsigned );

void print( const unsigned[],unsigned );

int main( void )
{
   unsigned a[3000];

   print(a,fun(a,1001));
        
    return 0;
}

unsigned fun( unsigned a[],unsigned len )
{
    unsigned i;
    unsigned j;
    unsigned count=3;
        
    a[1]=1;
    a[0]=0;
    a[2]=0;

 
    for (i=1;i!=len;++i)
    {
        for (j=1;j!=count;++j) 
            a[j]=GET_LOW(a[j])*i+GET_HIGH(a[j-1]);
        
        if (GET_HIGH(a[count-1]))
        {
            a[count++]=0;
        }
    }
    
    return count;
           
}

void print( const unsigned a[],unsigned len)
{
    while (--len)
        printf("%04x",GET_LOW(a[len]));
        
    puts("");
}


[此贴子已经被作者于2018-6-7 21:57编辑过]


[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2018-06-02 21:27
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
以下是引用xzlxzlxzl在2018-6-2 20:12:11的发言:

回复 58楼 九转星河:我觉得你应该写一个才行,我52楼图片已经显示出求大阶乘的代码了,遮住的部分就两句,你不擅长填空么,以你的资质应该很轻松填对的。

回复 57楼 lin5161678:既是进位,当然是要加到下一位的,看了你的演示,思路完全一样。

刚才看了一位专门研究大数阶乘的大神的文章,大部分篇幅介绍如何快速得到非精确的大数阶乘,求1千万的非精确阶乘只需0.01秒,的确快,不过他随后附了一个求精确阶乘的,好慢啊,在我电脑上需要5828毫秒,比我的代码慢7倍~~~
文章链接:https://blog.

二分法求乘幂的确可以优化,和我想到的一样~
所以说,100000!用9s可以理解吧~
而且我不觉得他的代码比较慢,要看看10000!或者更大的数效率如何才行,而我自己弄了个出来,不过是16进制的,效率也算是这样了

~


[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2018-06-03 08:55
童生
Rank: 6Rank: 6
等 级:侠之大者
威 望:8
帖 子:205
专家分:455
注 册:2018-3-7
收藏
得分:0 
哈哈,这贴是我发的吗?酒后一贴都快成神贴了。
2018-06-03 10:10
自学的数学
Rank: 13Rank: 13Rank: 13Rank: 13
等 级:贵宾
威 望:46
帖 子:966
专家分:4139
注 册:2017-11-15
收藏
得分:0 
能出神贴,也不错了,俺现在正在整理一份资料,到时候也来一份哦。不过,还需要一些时间。
2018-06-03 11:29
xzlxzlxzl
Rank: 15Rank: 15Rank: 15Rank: 15Rank: 15
来 自:湖北
等 级:贵宾
威 望:125
帖 子:1091
专家分:5825
注 册:2014-5-3
收藏
得分:0 
怎么就结贴了?非常想学习题主@童生的算法,肯定他算法有先进之处,否则不会发挑战帖的!
最近拜读了很多做大数阶乘的帖子,发现算法都差不多,不是使用10000进制的,就是使用100000进制的。我比较贪心,使用1000000进制,这样的代码最多只能做到4200的阶乘,刚好满足题意。通过与所有类似代码对比,我的代码都比他们的快那么一点,由于算法相同,并没有质的变化,比如“https://bbs.bccn.net/viewthread.php?tid=32009&highlight=%2Bkai”里@Knocker大神的代码在我电脑上求10000!用时840毫秒,我的790毫秒(双方都运行10次的平均耗时),仅此而已。题主是在此基础上发挑战帖的,肯定算法有质的变化!
我此前也提到的用64位做,经过实验,无论是自始至终使用64位,还是大部分时间32位计算,有进位时使用64位取进位,都不行,运行100次1000!都超过了1000ms。后来我使用了现在这个算法,这个算用了共用体数据结构,运算过程中只需要做一次按位乘法,不再需要做除法和取余数运算,经测试运算100次1000!由515ms提高到375ms,提高了140毫秒,算是有质的飞跃了。但这个算法有一个缺点:它纯粹是16进制运算,运算结果是一个超大的16进制数,为了显示结果,我专门写了个内存超大16进制数10进制显示的函数,1000的阶乘的结果16进制只有2136位,显示起来速度还可以,但显示超过万位的16进制数耗时不少。
图片附件: 游客没有浏览图片的权限,请 登录注册

2018-06-05 06:36
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
回复 67楼 xzlxzlxzl
用共用体我看看你的代码,似乎要涉及到大端小端的处理,不知道会不会因为电脑的端口模式不同而会产生不同的结果~

PS:个人感觉还是a&0x0000ffff和(a&0xffff0000)>>16比较直接~

[此贴子已经被作者于2018-6-5 07:57编辑过]


[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2018-06-05 07:41
烟雨晨曦
Rank: 7Rank: 7Rank: 7
等 级:黑侠
威 望:7
帖 子:150
专家分:599
注 册:2017-3-5
收藏
得分:0 
我也来一个
程序代码:
#include <stdio.h>
#include <time.h>
#include <sys/time.h>
char current[100] = "";
long int lTime = 0;
struct tm NowTime;
struct timeval st,et;

#define DebugInfo(fmt,args...)\
        lTime = time(NULL); \
        localtime_r(&lTime, &NowTime);\
        sprintf(current, "[%02d/%02d %02d:%02d:%02d]", NowTime.tm_mon+1, NowTime.tm_mday, \
        NowTime.tm_hour, NowTime.tm_min, NowTime.tm_sec);\
        printf("\033[33m%s %s %d -- " fmt "\033[0m\n", current,  __func__, __LINE__, ##args);

#define BEGIN gettimeofday(&st, NULL);
#define END gettimeofday(&et, NULL);
#define RESP ((et.tv_sec-st.tv_sec)*1000000 + et.tv_usec - st.tv_usec)
#define SIZE 3000           


int main(int argc, char** argv)
{
        int n,i,j,k,l;
        sscanf(argv[1],"%d", &n);
        int a[SIZE]={1,0};

        BEGIN
        for(i = 2; i <= n; i++)
        {

                //进位
                for(k = 0,j = 0; j < SIZE; j++)
                {
                        l = a[j]*i + k;
                        a[j] = l%10;
                        k = l/10;
                }
        }

        for(i = SIZE - 1; i >= 0; i--)
            if(a[i])
                break;

        for(j=i;j>=0;j--)
            printf("%d",a[j]);

        printf("\n");

        END
        DebugInfo("%ldus", RESP);

        return 0;
}
图片附件: 游客没有浏览图片的权限,请 登录注册



[此贴子已经被作者于2018-6-5 14:54编辑过]

2018-06-05 11:55
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
物是人非

重剑无锋,大巧不工
2018-06-05 12:16
快速回复:挑战C版所有人,1000!
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.252215 second(s), 9 queries.
Copyright©2004-2021, BCCN.NET, All Rights Reserved