小夫的笔记

但行好事 莫问前程

0%

程序设计的基本元素

Posted on Edited on In

程序设计的基本元素

  1. 基本表达式

    用于表示语言所关心的最简单的个体

  2. 组合的方法

    通过它们可以从比较简单的东西出发构造出复合的元素

  3. 抽象的方法

    通过它们可以为复合对象命名，并将它们当作单去操作

表达式

（* 1 2 3 4）

像上面这样的表达式称为组合式，其构成方式就是用一对括号括起一些表达式，形成一个表 用于表示一个过程应用。在表最左边的元素被称为运算符，其他元素都称为运算对象。

命名和环境

（define size 2）

组合式的求值

（ * （+ 2 （* 4 6） （+ 3 5 7））

复合过程

  • 数和算数计算是基本的数据和过程
  • 组合式的嵌套提供了一种组织起多个操作的方法
  • 定义是一种受限的抽象手段，它为名字关联相相应的值

（define （ ） ）

过程应用的代换模型

1
2
3
4
5
6
7
8
9
(define (f a)
  (define (square n)
    (* n n)
    )
  (define (sum-of-squares a)
    (+ (square (+ 1 a)) (square(+ 2 a)))
    )
  (sum-of-squares a)
  )

要得到结果先要把式子替换成sum-of-squares的定义，进一步的要替换成square的定义。这样的计算过程被称为代换模型。

应用序和正则序

这种“完全展开而后归约”的求值模式被称为正则序求值，对于上面的f 函数来说就是 变成

1
(+ (* (+ 5 1) (+ 5 1)) (* (* 5 2) (* 5 2)))

然后进行规约

与之相对应的是现在解释器里实际使用的“先求值参数而后应用”的方式，它称为应用序求值。

条件表达式和谓词

（cond

​ ( )

​ ( )

）

(if () () () )

谓词中允许中使用的词

  • (and … ）
  • (or … )
  • (not )

实例：采用牛顿法求平方根

$ \frac { {x} / {y^2} + 2y} {3}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
(define (square x)
  (x * x)
  )
(define (cue x)
  (x * x *x)
  )
(define good_guess(this_guess last_guess)
  (< (abs (- this_guess last_guess)) 0.0001)
  )
(define get_this_time_guess(last_guess x)
  (/ (+ (/ x square(last_guess)) (* 2 last_guess)) 3)
  )
(define cue_root_inter(last_guess x) 
  (if (good_guess (get_this_time_guess last_guess x) last_guess)
                (get_this_time_guess last_guess x)
                (cue_root_inter (get_this_time_guess last_guess x) x)
      )
  )
)
(define (cue_root x)
  	cue_root_inter(1.0 x)
  )

过程作为黑箱抽象

与其说cue_root 是一个过程，还不如说它一个过程的的抽象

局部名

过程的形式参数在过程体系里扮演着一种非常特殊的角色，在这里，形式参数的具体名字是什么，其实完全没有关系。这样的名字被称为约束变量。 如果一个变量不是被约束的，我们称它为自由的。

在good_guess中this_guess和last_guess是约束的，< abs 是自由的。

内部定义和块结构

目前的程序是几个相互分离的过程组成，如果统一到同一个方法块中。 这种嵌套的定义称为块结构

过程与它们所产生的计算

我们现在已经考虑了程序设计中的一些要素

使用许多基本的算数操作

对这种操作进行组合

定义各种复合过程

线性的递归和迭代

1.

1
2
3
4
5
(define (factorial n)
  if (= n 1)
  (1)
  (* n factorial(- n 1)))

2.

1
2
3
4
5
6
7
8
(define (factorial n)
  (define (factorial-iter product current_count max_count) 
    (if(= current max_count)
       (* product current)
       (factorial-iter (* product current) (+ current 1) max_count)
       )
    )
  )

在第1个中。代换模型解释出一个推迟进行的操作所形成的链条。收缩阶段表现为这些运算的实际进行。称为*递归计算过程*，它的长度随着n值而线性增长，这样的计算过程为一个线性递归过程

在第2个中，没有任何增长或者收缩。在我们需要保存轨迹里，所有的东西就是变量product、current_count和max_count的值。我们称这种过程为一个迭代计算过程。迭代计算过程就是那种其状态可以用固定数据的状态变量描述的计算过程

从另一个角度来看这两个过程之间的对比。在迭代的情况里，在计算过程中的任何一点，那几个程序变量都提供了有关计算状态的完整表述。如果我们令上述计算在某两个步骤之间停下来，想要重新唤醒这一计算，只需要为解释器提供有关这三个变量的值。

对于递归计算而言，这里还存在着另外的一些隐含信息，它们由解释器维持着。

注意

这不表示第二种方式不是递归。 只是解释器采用优化 把它优化成类似于while等的方式。我们称之为尾递归。

树形递归

斐波那契数列

  1. 递归方式调用
1
2
3
4
5
6
(define (fib n) 
  (cond ((= n 1) (1))
        ((= n 2) (1))
        ((> n 2) (+ fib((- n 1)) fib((- n 2))))
      )
)
  1. 迭代的方式调用
1
2
3
4
5
6
7
8
9
10
(define (fib n)
  			(fib-iter(n 3 1 1))
  )
(define (fib-iter N cur less1 less2)
  (cond ((= 1 N) 1)
         ((= 2 N) 1)
         ((= cur N) (less1))
         (else (fib-iter N (+ cur 1) (+ less1 less2) less1)
         )
  )

换零钱方式

这个会比较复杂一点。就是用递归的方法进行计算有多少种方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
(define (first-denomination kinds-of-conions)
  (cond ((= kinds-of-conins 1) 1)
        ((= kinds-of-conins 2) 5)
        ((= kinds-of-conins 3) 10)
        ((= kinds-of-conins 4) 25)
        ((= kinds-of-conins 5) 50)
  )
)
(define (count-change amount)
  (cc amount 5))

(define (cc amount kinds-of-conions)
  (cond ((= 0 amount) 1)
        ((or (< amount 0) (= kinds-of-conions 0)) 0)
        (else ( (+ (cc amount (- kinds-of-conions 1))
                 (cc (- amount 
                        (first-denomination kinds-of-conions))
                     )
                   )
                )
              )
        )  	
  )

下面是比较好理解的Java的方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public class Main {
    public static void main(String[] args) {
       int[] arrange = {0, 0, 0, 0, 0};
       cal(arrange, 50);
    }

    public static void cal(int[] arrange, int money) {
        if (money == 0) {
            System.out.println("50 cent " + arrange[0] + " 25 cent " + arrange[1] + " 10 cent " + arrange[2] + " 5 cent " + arrange[3] + " 1 cent" + arrange[4]);
            return;
        }
        if (money >= 50) {
            arrange[0] += 1;
            cal(arrange, money - 50);
            arrange[0] -= 1;
        }
        if (money >= 25) {
            arrange[1] += 1;
            cal (arrange, money - 25);
            arrange[1] -= 1;
        }
        if (money >= 10) {
            arrange[2] += 1;
            cal(arrange, money - 10);
            arrange[2] -= 1;
        }
        if (money >= 5) {
            arrange[3] += 1;
            cal(arrange, money -5);
            arrange[3] -= 1;
        }
        if (money >= 1) {
            arrange[4] += 1;
            cal(arrange, money - 1);
            arrange[4] -= 1;
        }
    }
}

练习 1.11

1
2
3
4
5
6
7
8
9
10
(define (fun-iter n cur a b c)
  (cond (((= n 1) 1)
         ((= n 2) 2)
         ((= n 3) 3)
         ((= n cur) a)
         (else (fun-iter n (+ cur 1) (+ (* a 3) (* b 2) c) a b)
        )
(define (func n)
  (fun-iter n 3 3 2 1)
  )

练习 1.12

1
2
3
4
5
6
(define (pascal row col)
  cond ( (> col row) (error "unvalid col value")
         ((or (= col 0) (= col row)) 1)
         (+ pascal((- row 1) col) pascal((- row 1) (+ col 1)))
        )
  )

这样的效率会很慢

由帕斯卡三角形（杨辉三角形）的公式可得 ${row \choose col}= \frac {row!} {col!(row−col)!}$

杨辉三角就是 $(x+1)^n$ 的系数的值

单就3项而言 $\frac {n(n-1)} {2!}$ => $ \frac {n(n-1)(n-2)(n-3)…} {(n-k)!k!}$ => 这个值等价于 $\frac {n!} {k! (n-k)!}$

在二项式的展开中 除了第一项和最后一项 每一项中都会有n，根据素数的定义，素数的因数只有1和它本身，所以后在二项式展开的2到n-1 项中的n都不会被整除，会被保留。

所以在n是素数的情况下从第2项到n-1项的值都是n的倍数

所以检查素数的方法

求$(x+1)^n$展开式从第2到n-1项

1
2
3
4
5
6
7
8
9
(define (factorial n)
    (fact-iter 1 1 n))
(define (fact-iter p b e)
  (if  (> b e) 
       p
       (fact-iter (* p b)(+ b 1) e))
)
(define (pascal row col)
  (/ (factorial row) (* (factorial col) (factorial (- row col)))

更相减损术

1
2
3
(define (gcb a b)
  (if (= 0 b) a ( gcb b (remainder a b) )
  )

实例 1.2.6 素数检测

1
2
3
4
5
6
7
8
9
10
(define (devides? a b) 
	(= (remainder a b) 0)
(define (smallest-divisor n)
	(find-divisor n 2))
	
(define (find-devisor n b)
	(conds ((> (square b) n)) n)
		((devides? n b) b)
		(else (find-deversior n (+ b 1)) 
	)

费马小定理

先说结论当n为素数的时候 $(a^n-a)mod(n) = 0$ 进一步的

$a^nmod(n) = a$

=>

$a^{n-1}mod(n)=1$

人们通常把这样的式子写作

$a^{n-1} \equiv 1 (mod \ n)$

证明

  1. 首先我们根据二项式定理能证明，当n为素数的时候 $((a + 1) ^ n - 1 - a^n )mod (n) = 0$
  2. 将费马小定理和二项式定理进行加和 $(a + 1) ^ n - 1 - a^n + a^n-a$
  3. 整理一下 得到 $((a+1)^n - (a+1))$
  4. 发现整理后的结果是 费马小定理的 n + 1 项。 已知二项式定理成立， 其结果能被n整除，若费马小定理的n项成立，即结果能被n整除，通过上式可知， 费马小定理的第 n+1 项必然成立
  5. 那么通过数学归纳法，我们去求当a为的0时候，那么 $(0^n-0)$ 的值。 0能被任何素数整除
  6. 所以费马小定理成立

注意 费马小定理是证明素数的充分不必要条件，比方说561 = 17 * 3 * 11. 但是 561 复合费马小定理的公式

换个表述方式我们定义$\phi(n)$ 为1～n中和n互质的数，我们可以得到 $a^{\phi(n)} = 1 (mod \ n)$，这个就是欧拉函数

欧拉函数

$a^{\phi(n)} = 1 (mod \ n)$

$\phi(n)$表示在1～n中和n互质的数

几个常用的定理

  1. 当n和m互质

$\phi(nm) = \phi(n) * \phi(m)$

  1. 当p为质数

    $\phi(p) = p - 1$

  2. 当n为奇数的时候

    $\phi(2 * n) = \phi(n)$

  3. 当 $n = p ^k$的时候

    $\phi(n) = p^k * (1-\frac {1} {p}) = p^k - p^{k-1}$

其他性质

题目

求$3^{83}$最后两位的值

​ 根据欧拉公式$a^{\phi(n)} = 1 (mod \ n)$

$\phi(100) = \phi(4)\phi(25)=(2^2-2)*(5^2-5)=40$

$3^{83} = 3^3 * 3^{80} = 3^3 * (3 ^{\phi(100)})^2\equiv 3^3 = 27$

凶残小姐姐的知乎介绍

用高阶函数抽象

过程作为参数

例子1

1
2
3
4
5
(define (sum-cubes a b)
  	(if ((a > b) 0)
        (+ (cube a) (sum-cubes (+ 1 a) b))
    )
  )

例子2

$$\sum_{n 0\to\infty }{\frac{1}{(1+4n)(3+4n)}} = {\frac {\pi} {8}}$$

1
2
3
4
5
(define (pi-sum a b)
  	(if ( (> a b) 0)
        (else (+(/ 1 (+ 1 (* 4 n)))))
    )
 )

我们可以填充下面模板中的各空位，产生出上面的各个过程：

1
2
3
4
5
6
7
(define (<name> a b)
  (if (
       ((> a b) 0)
       (+ (<term> a)
          (<name> (<next> a) b)
      )
  )

转换一下

1
2
3
4
5
6
7
8
9
(define (sum term a next b)
  (if ((> a b) 0)
      (else (+ (term a) 
               (sum term (next a) next b)))

)
(define (inc n) (+ n 1))
(define (sum-cube a b)
  (sum cube a inc b))

相当于把过程作为参数传入

然而，即使在数值计算过程中，如果将过程限制为只能以数作为参数，那么会严重的限制我们抽象的能力。经常有一些同样的程序设计模式能用于若干不同的过程，为了把这种模式描述为响应的概念吗，我们就需要构造出这样的过程，让他们以过程为参数。这类能操作过程的过程称为高阶过程。

用lambda构造过程

如果不需要显示定义pi-term和pi-next，而是有一种方法直接刻画过程。我们可以通过引入一种lamdba特殊形式完成这种描述。

定义名称很麻烦我们利用lambda, 按照如下方式写出所需的东西

(lambda (x) (+ x 4))

(lambda表达式可用作组合式的运算符。 lambda表达式可做运算符

1
((lambda (x y z) (+ x y (square z))) 1 2 3)

逻辑的过程是

我们通过过程名称调用过程 -> 将过程作为参数传入 -> 将lambda （匿名函数） 作为参数传入

用let创建局部变量

$f(x,y) = x(1+xy)^2+y(1-y) + (1+xy)(1-y)$

1
2
3
4
5
6
7
8
9
(define (f x y)
  (define (f-helper a b) 
    (+ (* x square a) (* y b) (* a b))
  )
  (f-helper 
   	(+ 1 (* x y))
   	(- 1 y)
   )
)

如果使用lambda的话

1
2
3
4
5
6
7
8
9
(define (f x y)
  ((lambda (a b) 
    (+ (* x square a) 
       (* y b) 
       (* a b)))
   (+ 1 (* x y))
   (- 1 y)
  )
)

如果使用let的话

1
2
3
4
5
6
7
8
9
10
(define (f x y)
  (let (
        (a (+ 1 (* x y)))
        (b (- 1 y)))
    (+ (x (square x))
       (* y b)
       (* a b)
       )
    )
  )

let 表达式只是作为基础lambda表达式的语法外衣罢了