新浪博客

LOGO语言编程题  999的阶乘的精确值★★★★

2009-11-26 19:12阅读:
说说世界上最大的数字和最长的数字
你相信有长达2.7万亿位的数字吗?
LOGO语言编程题 <wbr> <wbr>999的阶乘的精确值★★★★
人人都知道的googolplex来源于此,但是实际上比整个宇宙中所有粒子数还要大的数

最大的数,从数学意义上来说,世界上根本没有。如果一定要说很大很大很大……已知的世界上有名称、有具体数值的是是“古戈布来
克斯”(googolplex),也有把它拼写成“古戈尔”(googol)的。搜索引擎“谷歌”的名称google,就是从上面的词汇转变而来。当年“谷歌”的命名颇有些“狂傲”的气势(近年来'谷歌'公司在不遵守他国法律、侵犯作家著作权、“谷歌实景地球”暴露个人隐私等方面,受到许多国家的严厉批评),如果“谷歌”真的打算收集、分类这么多网络信息的话,很显然,他们距离这个目标还远着呢。
1938年美国数学家爱德华·卡斯纳打算给自己的学生展示一个数字,这个数字应该是无法想象的大,于是,他想到了在1的后面加上100个0(也就是10的100次方,相当于100个10连乘的结果)。数字有了,叫它什么呢?卡斯纳的侄子米尔顿有自己的意见,他认为这么大一个数字,一定得起个有个性点的名字,于是,命名为“古戈尔”。
1googol=10,​000,000,000,​000,000,000,​000,000,000,​000,000,000,000,000,000,000,000,000,​000,000,000,​000,000,000,​000,000,000,​000,000,000,​000,000,000
这是一个101位的数字。1个古戈尔到底有多大呢?具体些说吧,现在世界上运算最快的计算机每秒钟能够运算1千万亿次以上。就是从137亿年以前宇宙诞生的开始,运算到现在,总的运算次数也远没有达到1古戈尔。还有,所有的物质都是由分子构成的,分子是由原子构成的,原子是由“基本粒子”构成的。现在人类能够观察到的整个宇宙中的所有的“基本粒子”的总数大约是10的80次方个(这个数字是1后面加上80个零),可是这连1个古戈尔的1千以分之一也都达不到。
但是在用LOGO计算“阶乘”的过程中,我们马上就会遇到比1古戈尔大得多的数。
求1×2×3×…×8=?这个问题也就是求8!(读成“8的阶乘”)。连乘问题需要一个“累乘器”:S。累乘器:S的初值必须是1,而不能是0。如果:S开始的值是0,那么无论有多少数往里乘,最终的结果还是0。在LOGO语言中计算到9!都可以显示准确的数值,但是从10!开始显示的是“科学计数法”数值。下面是用JS5程序求解计算8!和计算12!的结果。
TO JS5 :N
MAKE 'S 1 ;累乘器开始的值是1
FOR 'I 1 :N[MAKE 'S :S * :I]
(PR :N [!=] :S)
END
JS5 8
8 ! = 40320
? JS5 12
12 ! = 4.79E+08
(注:4.79E+08等于4.79×100000000。就是4.79乘以10的8次方)
这种“科学计数法”虽然显示的结果十分简练,但是无法看到所有数位具体的数值总有些“不过瘾”。下面的JC“阶乘”程序能够求出不大于999的阶乘的具体数值。例如1×2×3×……×998×999就是一个2565位数!这个数比1个“古戈尔”要大多了。

TO JC1000 :N ;计算不大于999的阶乘的精确值
IF :N>=1000 THEN PR '请输入不大于999的数! STOP
MAKE 'PRECISION 6 ;计算显示位数设定为六位
MAKE 'A ARRAY 860 ;定义数组空间0-859组
ASET :A 1 1 ;乘法数组第1空间赋值为1
FOR 'I 2 859[ASET :A :I 0] ;其他数组空间赋值为0
FOR 'I 1 :N [JC :I] ;调用阶乘过程
MAKE 'K 0 ;数组空间是0的标记
MAKE 'Z 0 ;总共有多少组数字的标记
MAKE 'WS 0 ;累加总共有多少位的计数器
TYPE :N TYPE[!=] ;从高位到低位显示计算结果
FOR 'M 1 859[XXS 860-:M]
PR[ ] TYPE[这是一个]TYPE :WS TYPE[位数]PR[]
END
TO JC :I ;计算阶乘的过程
FOR 'J 1 858[CF :I :J] ;对所有数组空间逐一计算乘法
FOR 'J 1 858[CLJW :J] ;处理乘法过程中的进位
END
TO CF :I :J ;计算乘法的过程
MAKE 'ZJ AGET :A :J
MAKE 'ZJ :ZJ * :I ;I是阶乘中需要累乘的数
ASET :A :J :ZJ
END
TO CLJW :J ;处理进位的过程
MAKE 'X AGET :A :J
IF :X<1000 THEN GO 'XXX ;处理没有进位的数组
MAKE 'JINWEI INT (:X / 1000) ;截取小于1000的尾数
MAKE 'WEISHU :X - :JINWEI * 1000 ;截取进位的数字
ASET :A :J :WEISHU ;存储尾数
MAKE 'Y AGET :A :J+1
MAKE 'Y :Y + :JINWEI
ASET :A :J+1 :Y ;向上进位
LABEL 'XXX
END
TO XXS :P ;显示计算结果的过程
MAKE 'NN AGET :A :P
IF (AND :NN=0 :K=0) THEN[GO 'END_]ELSE[MAKE 'K 1 MAKE 'Z :Z+1] ;避开无效数组
IF :Z=1 THEN MAKE 'WS :WS+(COUNT :NN) GO 'UP ;计算头一个有效数组的位数
IF :Z>1 THEN MAKE 'WS :WS+3 ;累计数值的总位数
IF :NN < 10 THEN TYPE [0] ;填充空位0
IF :NN < 100 THEN TYPE [0]
LABEL 'UP
TYPE :NN
LABEL 'END_ ;越过开头的空数组
END

(注意:以下颜色为蓝色的说明段落,如果看不明白,可以越过不看。)

这里需要介绍一下编程的一些思路。
首先,我们需要估计999!计算出来是多少位数。在求许多数连乘的积时,我们可以先求出每个单独的数:I“取以10为底的对数”,就是计算LOGO10 :I,然后把它们累加起来。这件工作可以由下面的程序来计算。

TO JC :N ;求解任意数的阶乘是多少位数
MAKE 'S 0 ;先赋值位数为0
FOR 'I 1 :N[MAKE 'S :S+LOG10 :I]
TYPE[:S=]PR :S
END

例如输入JC 999:
JC 999
S =2564.605225
所以我们能够准确地确定这是一个256+1=2564位数。显然,999!是一个远比1古戈尔大得多的数。

在LOGO语言中,数值的精确值只能有6~7位。所以做乘法的话,被乘数和乘数都应该限定在3位数以内,那么乘出来的结果就不会大于6位数(也就是保证能够以精确值的形式显示出来)。现在我们已知999!是一个2564位数。如果把它3位分一截的话,共有854截。现在我们定义一个:A数组,去掉0空间,还有859个数组空间,足够容纳最多为854组的数据了。因为是进行“连乘”计算,所以一开始把存储最终数据的:A数组的第1空间赋值为1,其他空间赋值为0。
在计算“阶乘”的过程中,把数据1~999(是否算到999要根据输入的参数决定)逐一乘以:A数组的1~858号空间里的数值。乘完后,对1~858号空间里的数据进行检查,凡是大于999的部分就“进位”累加到上一个数组空间中,接着乘入下一个数……直到乘完为之。所以在进行乘法时,和用手工计算是一样的,从低位开始计算,再计算高位。
但是在输出计算结果时,就要从高位第859个空间开始“抄写”,一直抄到最低位。但是非常可能许多“高位空间”里全部都没有数据(那是因为乘出来的数据根本就没有那么多位),程序就自动“避开无效数组”,就是不理睬最前面全部是空的数组。当遇到某个数组中有数值时,就从这一组数组空间开始逐个向低位显示、并不断累计实际有多少个数位。有时这些需要显示的有效数组中“装”的数据全部都是零、或3个数位中的高位是零,这时就要“填充空位0”。

计算999!的结果如下(请自己在计算机中运行,为节约篇幅,仅仅显示前面若干位的数值):
JC1000 999
999!=40238726007377354370243392300398571937486421071463254……
这是一个2565位数
如果要计算大于999的阶乘,上面的程序已经不能使用了,还需要改进算法。LOGO语言具备这样的能力,但是程序会麻烦一些。

最后,林老师还要告诉你:比“古戈尔”位数更多的数是“圆周率π”。“圆周率π”虽然称不上是“最大的数”,但是它是人类已经知道的精确数值位数最多的数:
1948年费格森与雷思奇合作,用人工算出808位小数的π 值;
20世纪50年代,人们借助计算机算得了10万位小数的 π;
70年代又突破这个记录,算到了150万位;
到90年代初,用新的计算方法,算到的π 值已到4.8亿位;
2002年,日本的金田康正和日立制作所的技术员用最先进的电脑,花了601时56分将圆周率算到了小数点后12411亿位,创下了当今世界的最高记录。
虽然任何最为精密的科学计算用到圆周率π时,精确到小数30位就完全足够了(11位的精度计算地球的圆周,就能精确到毫米;46位的精度,就能计算出人类已知宇宙的周长),但是今后人类一定还会继续去突破“圆周率计算到多少多少亿位”的记录。
这个世界上最长的数圆周率的世界纪录在本文写就后又被刷新。根据最新得到的信息:
2008年8月日本筑波大学的大佐隆司用一台94.2terafiops(每秒万亿次浮点运算)的超级计算机(这个计算速度差不多比后面法国人用的手提电脑快2000倍),花29天的时间把圆周率计算到小数下2.577万亿位。
而最新的最高记录是法国人法布里斯•贝拉尔采用了自己编制的先进程序,利用家用的手提电脑(该计算机的价格不到2000欧元。这意味着在我们的家里只要有了这样的程序也能进行计算)计算了131天,把圆周率计算到小数下2.7万亿位,比前一个记录多出1230亿位小数。这个圆周率的数值在硬盘中占用了1000 GB的空间,在网络上下载它需要10天,快速朗读它需要4.9万年!

LOGO语言编程题 <wbr> <wbr>999的阶乘的精确值★★★★
法布里斯•贝拉尔

你说说,数学是不是很奇妙?LOGO语言是不是也很神奇?


这里是新颖有趣的LOGO、DEV-C++语言之家
欢迎评论 欢迎转载

查找林老师博客最便捷的方法:
百度、谷歌、搜狗、搜搜、雅虎、有道搜索引擎中输入
林老师 LOGO 就能找到林老师博客文章了

查阅林老师最新发表文章的链接:
http://blog.sina.com.cn/lzs2099

快速检索数百篇博客提高阅读效率的链接:
《LOGO语言简明教程》及初学者题库
《LOGO语言画图编程题》目录
LOGO及DEV-C++计算编程题》目录
《LOGO竞赛试题及解题分析指导》目录
《LOGO语言编程新理念及编程技巧》目录
《奥数及趣味数学问题》目录
《LOGO语言竞赛教程·习题集内容剖析》目录
《林老师话说天南地北》目录

初学者题库及编程技巧分析
查看林老师拍摄及推荐的照片的链接

林正山老师邮箱: linzhengshan@21cn.com
因网络拥挤“纸条”常不能及时打开查阅。有信息尽量使用“评论”或邮件。

需要LOGO系统文件常用表格工具文件及DEV-C++系统文件的可以发邮件给林老师

声明:
林正山老师发表的文章及照片,媒体、网站或出版物未经本人许可谢绝进行任何形式的删节、改编、重组及转载。

允许个人博客按原文(含图片及附注)进行完整转载,转载时敬请注明本博作者姓名、文章原始出处,并以链接形式标明来源。

我的更多文章

下载客户端阅读体验更佳

APP专享