大学计算机计算思维与信息素养第4章.pptx

;第4章 程序与递归;程序构造思维概述 ;首先，设计并实现系统可以执行的基本动作(可实现的)，例如： “与”动作、 “或”动作、 “非”动作、 “异或”动作;指令：控制基本动作执行的命令;指令：控制基本动作执行的命令;基本动作 对基本动作的 抽象与控制 “与”动作 AND “或”动作 OR “非”动作 NOT;分层式构造;第4章 程序与递归;(100 + 205) ;(+ 100 205) ;;;(define pi 3.14159) ;;(square 10) (square (+ 2 8)) (square (square 3)) (square (square (+ 2 5))) ;(define (NewProc a) (SumOfSquare (+ a 1) (* a 2))) ;;代入、求值、计算;(cond ( p1 e1) ( p2 e2) ... ( pn en) ) ;对于计算式 ，其正确的运算组合式(前缀表示法)为_____。 (A) (/ (+ 10 / 20 + 8 4) (+ * 3 6 * 8 2 ))； (B) ((10 + (20 / (8 + 4))) / ((3 * 6) + (8 * 2)))； (C) (/ (+ 10 (/ 20 (+ 8 4))) (+ (* 3 6) (* 8 2)))； (D) (/ (/ 20 (+ 10 (+ 8 4))) (* (+ 3 6) (+ 8 2)))。;问题1：用前缀表示法书写下述表达式 ;第4章 程序与递归; (* (* (* 1 1) 2) 3);25;26;27;递归的典型视觉形式---自相似性事物的无限重复性构造;29;递归是表达相似性对象及动作的无限性重复性构造的方法。 递归基础：定义、构造和计算的起点，直接给出。即h(0)。 递归步骤：由前n项或第n项定义第n+1项；由低阶h(k)且kn，来构造高阶h(n+1)； 即: h(n+1) = g ( h(n), n )，或者 h(n+1) = g( h(k), n, k )形式，g是需要明确给出的，以说明h(n+1)怎样由h(k), k和n构造出来。;31;32;(define (fib n) ( cond ((= n 0) 0) ((= n 1) 1) (( n 1) (+ (fib (- n 1)) (fib (- n 2)))) ));34;体验两种不同的递归函数;;37;梵天塔(汉诺塔)问题：有三根柱子，梵天将64个直径大小不一的金盘子按照从大到小的顺序依次套放在第一根柱子上形成一座金塔，要求每次只能移动一个盘子，盘子只能在三根柱子上来回移动不能放在他处，在移动过程中三根柱子上的盘子必须始终保持大盘在下小盘在上。;;;;递归法求n!的算法或程序;n1;long int Fact(int n) { int counter； long product=1; for counter=1 to n step 1 { product = product * counter； } /*迭代*/ return product; } ;程序思维小结