单位圆的绘制在数字3中展示： 'x y'=: |: +. rotate ^: (i. 360) 1j0 plot x;y Figure 3: 单位圆的绘制
|
Howland [How 1998]经常使用递归的Fibonacci函数描述递归和迭代过程。在J语言中，递归Fibonacci 定义如下：
fibonacci =. monad define if. y. < 2 do. y. else. (fibonacci y. - 1) + fibonacci y. - 2 end. )
使用 fibonacci 计算从0开始计算10个 fibonacci 整数：
fibonacci "0 i.11 0 1 1 2 3 5 8 13 21 34 55
Howland [ How 1998 ]也阐述了接续（即优先次序）的概念；在表达式中，一元表达式表示计算子表达式的结果
Given a compound expression e and a sub-expression f of e, the continuation of f in e is the computation in e, written as a monad, which remains to be done after first evaluating f. When the continuation of f in e is applied to the result of evaluating f, the result is the same as evaluating the expression e. Let c be the continuation of f in e. The expression e may then be written as c f.
Continuations provide a ``factorization'' of expressions into two parts; f which is evaluated first and c which is later applied to the result of f. Continuations are helpful in the analysis of algorithms.
用定义分析递归的fibonacci函数，fibonacci 每次递归都包含一个fibonacci函数。因此，至少有一次递归过程不是单个过程，fibonacci 函数的执行是一个递归过程。
定义一个一元函数fib_work，统计fibonacci的执行次数并作出评估。fib_work 是一个J语言定义的序列函数。
ib_work =. monad define if. y. < 2 do. 1 else. 1 + (fib_work y. - 1) + fib_work y. - 2 end. )
应用fib_work计算从0到10整数递归的次数：
fib_work "0 i.11 1 1 3 5 9 15 25 41 67 109 177
考虑一个实验，评估工作站上执行fibonacci需要多长时间。先估计fib_work 100，尽管上面已经给出递归过程的定义，但有必要给出一个迭代过程的定义以便于评估。考虑下面的函数定义：
fib_work_iter =: monad def 'fib_iter 1 1 , y.'
fib_iter =: monad define
('a' ; 'b' ; 'count') =. y.
if. count = 0
do. b
else. fib_iter (1 + a + b) , a , count - 1
end.
)使用fib_work_iter可以得到与fib_work相同的统计递归次数结果：
fib_work_iter "0 i. 11 1 1 3 5 9 15 25 41 67 109 177
下面使用fib_work_iter 计算fib_work 100（精确的）。
fib_iter 100x 57887932245395525494200
最终，在工作站上执行一系列fibonacci 函数递归所使用的时间不超过20s。
使用3500 applications/sec作为估计：
0 3500 #: 57887932245395525494200x 16539409212970150141 700 0 100 365 24 60 60 #: 16539409212970150141x 5244612256 77 234 16 49 1
最大结果是 5244612256 个世纪。
解决这一问题的一种可选的实验性方法是对递归的fibonacci定义进行计时，并从成果时间的倍数中寻找模式.
[ experiment =: (4 10 $'fibonacci ') ,. ": 4 1 $ 20 21 22 23 fibonacci 20 fibonacci 21 fibonacci 22 fibonacci 23 t =: time "1 experiment t 2.75291 4.42869 7.15818 11.5908 (1 }. t) % _1 }. t 1.60873 1.61632 1.61924
请注意赔率大概是一样的，这意味着计算fibonacci的时间应该是指数级的。执行下面的计算，作为对事件的一个估计值:
[ ratio =: (+/ % #) (1 }. t) % _1 }. t 1.61476 0 100 365 24 60 60 rep x: ratio^100 205174677357 86 306 9 14 40
这一试验性质的方法产生了某种比 205174677357 更大的估计值. 同学们应该警惕任意试验性设计中的某些缺陷.
假设我们有下面这些测试成绩.
[ scores =: 85 79 63 91 85 69 77 64 78 93 72 66 48 76 81 79 85 79 63 91 85 69 77 64 78 93 72 66 48 76 81 79 /:~scores NB. sort the scores 48 63 64 66 69 72 76 77 78 79 79 81 85 85 91 93
在干叶图上可以看到一条轴上有观察的单元数字值（页），还有其它轴上的更多重要的数字值（干）. 这些可能是从如下这些分数中计算得来的:
stem =: 10&* @ <. @ %&10 leaf =: 10&| sl_diagram =: ~.@stem ;"0 stem </. leaf sl_diagram /:~scores +--+-----------+ |40|8 | +--+-----------+ |60|3 4 6 9 | +--+-----------+ |70|2 6 7 8 9 9| +--+-----------+ |80|1 5 5 | +--+-----------+ |90|1 3 | +--+-----------+
一个更加传统的频率表可以由 fr =: +/"1 @ (=/) 的定义得出. 左边的参数是一个频率的范围，而右边的参数是一个观察值的列表.
4 5 6 7 8 9 fr <. scores%10 1 0 4 6 3 2
这个频率表可以用一个使用了内置统计库的柱形图来展示(图 4).
图 4: 分数频率的柱形图
|
pd 'new' pd 'type bar' pd 'xlabel "40" "50" "60" "70" "80" "90"' pd 4 5 6 7 8 9 fr <. scores%10 pd 'show'
