新书推介：《语义网技术体系》
作者：瞿裕忠，胡伟，程龚
   XML论坛     >>W3CHINA.ORG讨论区<<     计算机科学论坛     SOAChina论坛     Blog     开放翻译计划     新浪微博  
 
  • 首页
  • 登录
  • 注册
  • 软件下载
  • 资料下载
  • 核心成员
  • 帮助
    		•   Add to Google

    >> We choose to study algorithmic problems,  not because they are easy,  but because they are hard.
    [返回] W3CHINA.ORG讨论区 - 语义网·描述逻辑·本体·RDF·OWL → 计算机理论与工程 → 『 算法理论与分析 』 → 求N!的最后一位非0位 ◇查看新帖 ◇ 用户列表 ◇

      发表一个新主题  发表一个新投票  回复主题  (订阅本版) 您是本帖的第 7130 个阅读者浏览上一篇主题  刷新本主题   树形显示贴子　浏览下一篇主题
     * 贴子主题： 求N!的最后一位非0位 举报  打印  推荐  IE收藏夹 
       本主题类别:     
     hitlyq 帅哥哟，离线，有人找我吗？
      
      
      等级：大一新生
      文章：2
      积分：58
      门派：XML.ORG.CN
      注册：2007/12/12

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给hitlyq发送一个短消息 把hitlyq加入好友 查看hitlyq的个人资料 搜索hitlyq在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看hitlyq的博客楼主
    发贴心情 求N!的最后一位非0位

    今有一个数N,数值较大,为0~10^1000,求其阶乘的最后一非0位,输出其值
    sample :
    input :0
    1
    5
    10
    output:1(0!=1)
    1(1!=1)
    2(5!=120)
    8(10!=3628800)

    数值很大,应该没人直接求其阶乘再判断吧.大家给个好方法,期待中................


       收藏   分享  
    顶(0)
      




    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2007/12/14 23:04:00
     
     njurain 帅哥哟，离线，有人找我吗？
      
      
      等级：大一新生
      文章：1
      积分：58
      门派：XML.ORG.CN
      注册：2007/12/20

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给njurain发送一个短消息 把njurain加入好友 查看njurain的个人资料 搜索njurain在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看njurain的博客第2楼
    发贴心情 
    你可以这么做：
    写成：
      1   2  3   4   5   6   7   8   9   10
    11 12 13 14 15 16 17 18  19 20
    。。。。。
    X1 X2.....

    多少行很容易知道；[N/10]
    然后XX0的没有影响
    在看看有多少个5因子，就看5那列就可以了
    然后先用8那列 并这些5（每个8=2^3）
    用2那列填补可能的不足的5；
    下面乘乘就是了。丢掉高位注意。

    当然，你可以用数论的知识更快的做；
    手算就可以了。

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2007/12/20 20:07:00
     
     homeren0215 帅哥哟，离线，有人找我吗？
      
      
      等级：大一(猛啃高等数学)
      文章：37
      积分：186
      门派：XML.ORG.CN
      注册：2007/12/13

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给homeren0215发送一个短消息 把homeren0215加入好友 查看homeren0215的个人资料 搜索homeren0215在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看homeren0215的博客第3楼
    发贴心情 
    令r= N mod (『N/100『 * 100)
    如果 r=0, 那么最后一位非零位是8
    如果 r in (1-9) 则计算s = 8 × r!,
    如果 r in (1-19),则计算s = 4 * (r-10)!,
    如果 r in (1-29), 则计算s = 2 *(r-20)!*2,
    如果 r in (1-39)，则计算s = 6*(r-30)!*2*3,
    如果 r in (1-49), 计算s = 8*(r-40)!*2*3*4,
    如果r in (1-59), 计算 s = 4*(r-50)!*2*3*4*5,
    ....
    如果r in（１－９９），则计算ｓ＝４×（ｒ－９０）！×９！
    最终，Ｎ！的最后一个非零位是ｓ的最后一位非零位
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2008/1/13 21:31:00
     
     caruru331 帅哥哟，离线，有人找我吗？
      
      
      等级：大一新生
      文章：0
      积分：56
      门派：XML.ORG.CN
      注册：2007/1/8

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给caruru331发送一个短消息 把caruru331加入好友 查看caruru331的个人资料 搜索caruru331在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看caruru331的博客第4楼
    发贴心情 
    楼上的方法复杂度是指数级的
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2008/1/17 1:42:00
     
     fishyuze 帅哥哟，离线，有人找我吗？
      
      
      等级：大二期末(Java考了96分!)
      文章：57
      积分：309
      门派：XML.ORG.CN
      注册：2007/4/8

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给fishyuze发送一个短消息 把fishyuze加入好友 查看fishyuze的个人资料 搜索fishyuze在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看fishyuze的博客第5楼
    发贴心情 
    用数论做 分解质因数
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2008/2/2 11:28:00
     
     qianjigui 帅哥哟，离线，有人找我吗？天蝎座1987-11-14
      
      
      等级：大一(高数修炼中)
      文章：9
      积分：113
      门派：GOOGLEBBS.NET
      注册：2007/7/25

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给qianjigui发送一个短消息 把qianjigui加入好友 查看qianjigui的个人资料 搜索qianjigui在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看qianjigui的博客第6楼
    发贴心情 
    以下是引用fishyuze在2008-2-2 11:28:00的发言：
    用数论做 分解质因数


    这个题目好熟悉啊，好象是tju上面的。谢谢提示。

    ----------------------------------------------
    Code my future

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2008/2/16 23:42:00
     
     fishyuze 帅哥哟，离线，有人找我吗？
      
      
      等级：大二期末(Java考了96分!)
      文章：57
      积分：309
      门派：XML.ORG.CN
      注册：2007/4/8

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给fishyuze发送一个短消息 把fishyuze加入好友 查看fishyuze的个人资料 搜索fishyuze在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看fishyuze的博客第7楼
    发贴心情 
    以下是引用qianjigui在2008-2-16 23:42:00的发言：
    [quote]以下是引用fishyuze在2008-2-2 11:28:00的发言：
    用数论做 分解质因数
    [/quote]
    这个题目好熟悉啊，好象是tju上面的。谢谢提示。


    嗯 poj也有 类似的~~
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2008/2/17 10:28:00
     
     xbtianlang 帅哥哟，离线，有人找我吗？
      
      
      等级：大一新生
      文章：1
      积分：55
      门派：XML.ORG.CN
      注册：2008/1/10

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给xbtianlang发送一个短消息 把xbtianlang加入好友 查看xbtianlang的个人资料 搜索xbtianlang在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看xbtianlang的博客第8楼
    发贴心情 
    好久没写程序，只说一下大致算法：
    result=1;
    for(i=2;i<=n;i++)  //0,1结果为1
    { result*=i;
      while(result%10==0) result /=10;  //去末尾0
      while(result%2==1)
      { result *= 6; //末尾非0数为奇数则乘6
        while(result%10==0) result /=10;  //去末尾0
      }
      result %=10; //保留非0个位数。
    }


    [此贴子已经被作者于2008-4-16 16:32:26编辑过]
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2008/4/16 13:12:00
     
     GoogleAdSense
      
      
      等级：大一新生
      文章：1
      积分：50
      门派：无门无派
      院校：未填写
      注册：2007-01-01
    给Google AdSense发送一个短消息 把Google AdSense加入好友 查看Google AdSense的个人资料 搜索Google AdSense在『 算法理论与分析 』的所有贴子 访问Google AdSense的主页 引用回复这个贴子 回复这个贴子 查看Google AdSense的博客广告
    2024/4/28 10:33:17

    本主题贴数8，分页： [1]

    管理选项： 修改tag | 锁定 | 解锁 | 提升 | 删除 | 移动 | 固顶 | 总固顶 | 奖励 | 惩罚 | 发布公告
    W3C Contributing Supporter! W 3 C h i n a ( since 2003 ) 旗 下 站 点
    苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
    		 277.344ms