SICP2

习题1.11

 

递归

(define (f n)
  (if (< n 3)
      n
      (+ (f (- n 1))
         (* 2 (f (- n 2)))
         (* 3 (f (- n 3))))))

(f 3)

 

迭代：

 

#lang racket
(define (f a b c n)
  (if (= n 2) 
      a
      (f (+ a
          (* 2 b)
          (* 3 c))
         a
         b
          (- n 1))))

(define (g n)
  (f 2 1 0 n))

(g 4)

如何分析迭代？

1、迭代有二个状态：中间值的保存、迭代次数保存

2、确定初始化状态

比如：这题g(2)=a, g(1)=b, g(0)=c    

3、确定一步迭代过称

g(3)=a+2b+3c

4、确定中间值的保存替换规则

a<-a+2b+3c 代

b<-a

c<-b

5、确定迭代时候，迭代次数值

n=3   迭代一次 值返回a

可以证明 n=x  迭代 x-2 值返回a

6、所以当n-2=0时候，迭代结束，返回a值，就是g(n)的值

 

习题1.12

 

#lang racket
(define (f x y)
  (cond ((or (> y x) (< x 0)) 0)
        ((= 1 x) 1)
        ((= 1 y) 1)
        ((= x y) 1)
        (else (+ (f (- x 1) (- y 1))
                (f (- x 1) y)))))

(f 5 6)

 

习题1.16

 

 

(define (double x)
  (* x x))


(define (halve x)
  (if (even? x)
      (/ x 2)
      x))

(define (fast_expt a b n)
  (if (= n 0) 
      a
       (if (even? n)
           (fast_expt a  (double b)  (halve n))
           (fast_expt (* a b) b   (- n 1)))))

(fast_expt 1 2 0)
(fast_expt 1 2 1)
(fast_expt 1 2 2)
(fast_expt 1 2 10)
(fast_expt 1 2 100)  
(fast_expt 1 2 1000)  
(fast_expt 1 2 10000)  


运行结果是：

Welcome to DrRacket, version 5.2.1 [3m].
Language: Beginning Student; memory limit: 128 MB.
1
2
4
1024
1267650600228229401496703205376
10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376
19950631168807583848837421626835850838234968318861924548520089498529438830221946631919961684036194597899331129423209124271556491349413781117593785932096323957855730046793794526765246551266059895520550086918193311542508608460618104685509074866089624888090489894838009253941633257850621568309473902556912388065225096643874441046759871626985453222868538161694315775629640762836880760732228535091641476183956381458969463899410840960536267821064621427333394036525565649530603142680234969400335934316651459297773279665775606172582031407994198179607378245683762280037302885487251900834464581454650557929601414833921615734588139257095379769119277800826957735674444123062018757836325502728323789270710373802866393031428133241401624195671690574061419654342324638801248856147305207431992259611796250130992860241708340807605932320161268492288496255841312844061536738951487114256315111089745514203313820202931640957596464756010405845841566072044962867016515061920631004186422275908670900574606417856951911456055068251250406007519842261898059237118054444788072906395242548339221982707404473162376760846613033778706039803413197133493654622700563169937455508241780972810983291314403571877524768509857276937926433221599399876886660808368837838027643282775172273657572744784112294389733810861607423253291974813120197604178281965697475898164531258434135959862784130128185406283476649088690521047580882615823961985770122407044330583075869039319604603404973156583208672105913300903752823415539745394397715257455290510212310947321610753474825740775273986348298498340756937955646638621874569499279016572103701364433135817214311791398222983845847334440270964182851005072927748364550578634501100852987812389473928699540834346158807043959118985815145779177143619698728131459483783202081474982171858011389071228250905826817436220577475921417653715687725614904582904992461028630081535583308130101987675856234343538955409175623400844887526162643568648833519463720377293240094456246923254350400678027273837755376406726898636241037491410966718557050759098100246789880178271925953381282421954028302759408448955014676668389697996886241636313376393903373455801407636741877711055384225739499110186468219696581651485130494222369947714763069155468217682876200362777257723781365331611196811280792669481887201298643660768551639860534602297871557517947385246369446923087894265948217008051120322365496288169035739121368338393591756418733850510970271613915439590991598154654417336311656936031122249937969999226781732358023111862644575299135758175008199839236284615249881088960232244362173771618086357015468484058622329792853875623486556440536962622018963571028812361567512543338303270029097668650568557157505516727518899194129711337690149916181315171544007728650573189557450920330185304847113818315407324053319038462084036421763703911550639789000742853672196280903477974533320468368795868580237952218629120080742819551317948157624448298518461509704888027274721574688131594750409732115080498190455803416826949787141316063210686391511681774304792596709376
> 

 

java代码：

 

package lisp;

public class W116 {
	
	public static int doubleNum(int x) {
		return 2 * x;
	}
	
	public static boolean isEven(int x) {
		if(x % 2 == 0) {
			return true;
		}
		else return false;
	}
	
	public static  int halve(int x) {
		if(isEven(x)) {
			return x / 2;
		}
		else return x;
	}

	public static int fastExpt(int a, int b, int n) {
		
		if(n == 0) return a;
		else {
			if(isEven(n)) {
				return fastExpt(a, b*b, n/2);
			}
			else {
				return fastExpt(a*b, b , n-1);
			}
		}
	}
	
	public static void main(String arg[]) {
		
		int b = 2;
		int n = 4;
		
		System.out.println(fastExpt(1, b,1));
	}
}

 

 

习题1.17

 

(define (double x)
  (+ x x))


(define (halve x)
  (if (even? x)
      (/ x 2)
      x))

(define (fast_expt a b)
  (if (= 0 b) 
      0
       (if (even? b)
           (fast_expt (double a) (halve b))
           (+ a (fast_expt a  (- b 1))))))

(fast_expt 5 10)
(fast_expt 5 11)  
(fast_expt 3 11)  
(fast_expt 5 23)  

 

 

package lisp;

public class W117 {
	
	public static int doubleNum(int x) {
		return 2 * x;
	}
	
	public static boolean isEven(int x) {
		if(x % 2 == 0) {
			return true;
		}
		else return false;
	}
	
	public static  int halve(int x) {
		if(isEven(x)) {
			return x / 2;
		}
		else return x;
	}

	public static int fastExpt(int a, int b) {
		
		if(b == 0) return 0;
		else {
			if(isEven(b)) {
				return fastExpt(doubleNum(a), halve(b));
			}
			else {
				return fastExpt(a, b-1) + a;
			}
		}
	}
	
	public static void main(String arg[]) {
		
		int a = 5;
		int b = 93;
		
		System.out.println(fastExpt(a, b));
	}
}

 

1.29  习题（写的有点乱）

 

 

#lang racket
(define (sum term a  next k h b n)
  (if (> a b)
      0
      (+ (* (term a) (pre k h n))
         (sum term (next a h) next (+ k 1) h b n))))

(define (pre k h n)
  (cond ((or (= k 0) (= k n)) (/ h 3))
        ((= (remainder k 2) 0) (* 2 (/ h 3)))
        (else (* 4 (/ h 3)))))

(define (f a)
  (* a a a))

(define (next a h)
  (+ a h))



(define (sum_init n)
  (sum f 0 next 0 (/ 1.0 n) 1 n))

(sum_init 100)
(sum_init 1000)
(sum_init 100000)

答案是：
0.2466666666666672
0.2496666666666673
0.24999999999913322

上述答案明显不对，试问，代码哪里出问题了了？