一、过程与它们产生的运算
1.阶乘
在factorial函数中填入代码，实现n的的阶乘。 所谓n的阶乘就是，1 X 2 X 3 .... X ( n -1 ) X n
举例来说
1的阶乘是 1
2的阶乘是 1 X 2 = 2
3的阶乘是 1 X 2 X 3 = 6
解：
function factorial(n){
if (n == 1) return 1;
return n*factorial(n-1);
}
2.斐波那契数列
在fib函数中填入代码，返回菲波那契数列的第n个数的值。 菲波那契数列是指每一位都是前两位相加之和的一个数列，一个有限的菲波那契数列如下所示
0 1 1 2 3 5 8 13 ...
举例来说
fib(0)的返回值是 0
fib(1)的返回值是 1
fib(2)的返回值是 1( 因为1 = 0 + 1 )
fib(3)的返回值是 2( 因为2 = 1 + 1 )
fib(4)的返回值是 3( 因为3 = 2 + 1 )
解：
function fib(n){
if (n == 0) return 0;
if (n == 1) return 1;
return fib(n-1) + fib(n-2);
}
3.找零钱问题
假定有1美分,5美分,10美分,25美分,50美分的零钱无限多，试把任意钱换成零钱，写一个函数计算有多少种换法。
请将代码写在count_change函数里，返回有多少种换算方法。该函数有一个参数，传入的是一个数字，单位是美分，比如，1美元，传入的是100美分。
解：
function count_change(amount,n){
var m = n || 5;
if(amount === 0) return 1;
if(amount < 0 || n === 0) return 0;
return count_change(amount, m - 1) + count_change(amount - value_of_currency(m), m);
}
function value_of_currency(n){
if (n === 1) return 1;
if (n === 2) return 5;
if (n === 3) return 10;
if (n === 4) return 25;
if (n === 5) return 50;
}
4.分支与递归
写一个f函数,满足下面的需求:
如果 n < 3，那么f(n) = n
如果 n >= 3, 那么 f(n) = f(n-1)+2f(n-2)+3f(n-3)
function f(n){
if (n < 3) return n;
return f(n-1)+2*f(n-2)+3*f(n-3);
}
5.帕斯卡三角
实现pascal_triangle函数，以打印帕斯卡三角。
所谓帕斯卡三角就是三角形的边界上都是1，内部的每个数是位于它上面的两个数之和。形如
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
每个数是上一层相邻两个数的和。为了表现容易。我们生成下面这样的三角形：
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
pascal_triangle的参数是帕斯卡三角的行数，上图中参数为5。 该函数返回一个字符串，数字之间用空格隔开，打印该字符串可得到帕斯卡三角。
解：
function pascal_triangle(n){
var result = '1';
if(n === 1) return result + '\n';
for(var i = 1; i <= n-1; i++){
result = result + ' ' + factorial(n - 1)/ (factorial(i) * factorial(n - 1 - i));
}
return pascal_triangle(n - 1) + result + '\n';
}
function factorial(n){
if(n === 1 || n === 0 ) return 1;
return factorial(n - 1) * n;
}
6.最大公约数
实现gcd函数，用欧几里得法求两个参数的最大公约数 这一算法基于下面的观察，如果r是a和b的余数，那么a和b的公约数正好也是b和r的公约数，因此我们可以借助等式
gcd(a,b) = gcd(b,r)
把一个gcd的计算问题连续的归约到越来越小的整数对的gcd的计算问题。例如
gdc(206,40) = gcd(40,6)
= gcd(6,4) = gcd(4,2) = gcd(2,0) = 2
可以证明，从任意两个正整数开始，反复执行这种归约，最终会产生一对数，其中的第二个是0，此时最大公约数就是另一个数。
这个算法被称为欧几里得算法
解：
function gcd(num1, num2){
if(num2 === 0) return num1;
return gcd(num2,num1%num2);
}
二、函数是一等公民
1.高级函数求和
题目
举例：
举例
function sum(term, a, next, b){
if (a > b) return 0;
return term(a) + sum(term,next(a),next,b);
}
2.高阶函数累积
题目：
题目
解：
function product(term, a, next, b){
if (a > b) return 1;
return term(a)*product(term,next(a),next,b);
}
3.抽象无止境
题目
题目
解：
function accumulate(combiner, null_value, term, a, next, b)
{
if (a > b) return null_value;
return combiner(term(a), accumulate(combiner,null_value,term,next(a),next,b));
}
4.再抽象一点
题目：
题目
解：
function filtered_accumulate(filter, combiner, null_value, term, a, next, b)
{
if (filter_current_and_next_a(filter, next, a) > b) {
return null_value;
}
return combiner(term(filter_current_and_next_a(filter, next, a)),
filtered_accumulate(filter,combiner,null_value,term,next(filter_current_and_next_a(filter ,next , a)),next,b));
}
function filter_current_and_next_a(filter ,next , a)
{
if (filter(a)) {
return a;
}
return filter_current_and_next_a(filter, next, next(a));
}
5.连分式
题目：
题目
解：
function tag_cf(x, k){
return x*tag_b(x,k-1)/tag_a(x, k-1) ;
}
function tag_a(x,k)
{
if (k == 0 || k == -1) return 1;
return (2*k+1)*tag_a(x,k-1) - x*x*tag_a(x,k-2);
}
function tag_b(x,k)
{
if (k == 0) return 1;
if (k == -1) return 0;
return (2*k+1)*tag_b(x,k-1) - x*x*tag_b(x,k-2);
}
6.牛顿法解函数
题目：
题目
解：
function solve(fun, x, dx){
if (dx > Math.abs(fun(x))) return x;
return solve(fun, x - fun(x)/diff(fun,x,dx), dx);
}
function diff (fun,x,dx)
{
return (fun(x+dx)-fun(x))/dx;
}
7.一等公民函数
题目：
题目
解：
function compose(f, g){
return function(x) {
return f(g(x));
};
}
8.迭代改进
题目：
题目
解：
function solve_iter(check, buzz)
{
return function(fun,x,dx)
{
if (!check(fun,x,dx)) return solve_iter(check, buzz)(fun, buzz(fun,x,dx),dx);
else return x;
};
}
网友评论