2012年4月12日星期四

有理数的葡萄判定

倒时差,失眠中。半夜三更,思维不清楚,如果错了,见谅。
之前@双料黑客 提出过一个问题,[如何判定一个数是无理数](http://www.guokr.com/question/130064/)

今有不知何数x,注意要产生一个可能是无理数的数字,肯定是要无限位的,所以是需要一个程序来生成这个x的,这是如何产生一个无理数的问题,不在此处讨论。请参考[解读求pi的怪异代码](http://wangcong.org/articles/puzzle.html)。

不失一般性,以十进制来表示x,不失一般性,只考虑小数部分,也就是0<x<1

伪代码如下:

x(0)=floor[x*2]
  x=x*2-x(0)
  y=x
x(1)=floor[x*2]
  x=x*2-x(0)
u=x(0)*2+x(1)

Do
n++
x=y
x(0)=floor[x*2]
  x=x*2-x(0)
  y=x
x(1)=floor[x*2]
  x=x*2-x(0)
v=x(0)*2+x(1)

// 将x转化成二进制小数,取前3位,第1位和第2位组成一个数u,第2位和第3位组成一个数v,(u,v)是平面上一个点。(u,v)可能有四个(0,0), (0,1), (1,0), (1,1),其数量分别记为a,b,c,d

if u=0 and v=0 then a++
if u=0 and v=1 then b++
if u=1 and v=0 then c++
if u=1 and v=1 then d++

SD=(a-n/4)^2+(b-n/4)^2+(c-n/4)^2+(d-n/4)^2
// 如果是无理数,那么(u,v)将会等可能的分布在这四个点上,也就是说当重复次数足够多的时候,a,b,c,d是非常接近的,那么其方差Sqrt(SD)是一个非常小的数,这个数是一个小于F(n)的数字,其中F(n)是一个与重复次数有关的函数,具体是什么,我今天也不知道,恐怕要留着下次失眠的时候来算了。

if SD>F(n) then return(x是有理数), break

u=v
Loop

-EOF-

这是根据前几天看过的一个“通过Pi求Pi”的文章来写的,名字不记得了,好像原文的方法是取Pi的小数部分,每4位算一个点,比如3.14159265358....,那么(0.1415, 0.9265)就是一个点,(0.3589,0.7932)是下一个点。如果是无理数,那么应该布满单位正方形,于是u^2+v^2<=1的点的数量,应该总数的Pi/4。

其实不一定是要来求圆,只要是这些点均匀的布满单位正方形之内就可以,那么随便找个图形画上,只要图形内的点数量的比例=图形面积即可。

而且我不喜欢用Pi,这种方法有两个问题,第一,用一个无理数去判定一个无理数,这数值计算烦死了。第二,即使是4位小数,也是平面上离散的有限个点,跟Pi总是有很大差距的。

所以,既然是平面上的离散点,那么干脆取出最小的值,也就是4个点来做就好了,如果只有4个数的话,还算什么单位圆,直接求方差就够了。然后,我不喜欢间断的求点,我觉得那样会漏掉东西,(0.1415, 0.9265),(0.3589,0.7932)我觉得不好,我更喜欢(0.1415,0.4159),(0.1592,0.5926)这样的点阵。

同样无聊的人们,谁愿意来求解一下最大能够满足F(n)判别作用的表达式呢?

Posted via email from goldengrape's posterous

没有评论:

发表评论