sicp 5.1节习题尝试解答
习题 尝试 解答 5.1
2023-09-11 14:16:06 时间
5.1 图就不画在机器上了,麻烦
5.2 用寄存器语言描述5.1题中的阶乘机器,加上了读取和打印,这里的解答全部在实际的寄存机器中验证过,但是仍然按照该节的表示法表示。
(controller
fac-loop
(assign n (op read))
(assign product (const 1))
(assign counter (const 1))
iter-loop
(test (op ) (reg counter) (reg n))
(branch (label iter-done))
(assign product (op *) (reg product) (reg counter))
(assign counter (op +) (reg counter) (const 1))
(goto (label iter-loop))
iter-done
(perform (op print) (reg product))
(goto (label fac-loop)))
5.3 牛顿法求平方根,将这个过程转化为寄存器语言,第一个版本,假设good-enough?和improve都是基本过程,
;version1
(controller
sqrt-loop
(test (op good-enough?) (reg guess))
(branch (label sqrt-done))
(assign guess (op improve) (reg guess))
(goto (label good-enough))
sqrt-done) 第二个版本,展开good-enough?过程,
;version2
(controller
good-enough
(assign t (op square) (reg guess))
(assign t (op -) (reg t) (reg x))
(assign t (op abs) (reg t))
(test (op ) (reg t) (const 0.001))
(branch (label sqrt-done))
(assign guess (op improve) (reg guess))
(goto (label good-enough))
sqrt-done) 最后,展开improve过程,
;version3
(controller
sqrt-init
(assign guess (const 1.0))
(assign x (op read))
good-enough
;good-enough
(assign t (op square) (reg guess))
(assign t (op -) (reg t) (reg x))
(assign t (op abs) (reg t))
(test (op ) (reg t) (const 0.001))
(branch (label sqrt-done))
;improve
(assign t (op /) (reg x) (reg guess))
(assign t (op +) (reg guess) (reg t))
(assign guess (op /) (reg t) (const 2.0))
(goto (label good-enough))
sqrt-done) 在start之后,从寄存器guess中得到最后结果。
5.4
a)第一个是一个指数计算过程,用到了递归,因此需要引入continue寄存器来保存和恢复堆栈,实现与阶乘相似,如下
(controller
(assign continue (label expt-done))
expt-loop
(test (op =) (reg n) (const 0))
(branch (label expt-base-case))
;;保存continue
(save continue)
(assign n (op -) (reg n) (const 1))
(assign continue (label after-expt))
(goto (label expt-loop))
after-expt
;;恢复continue
(restore continue)
(assign val (op *) (reg b) (reg val))
(goto (reg continue))
expt-base-case
(assign val (const 1))
(goto (reg continue))
expt-done
(perform (op display) (reg val))) b) 迭代型的递归计算过程,尾递归调用,因此不需要continue寄存器来保存和恢复堆栈,这道习题就是希望能分辨非尾递归和尾递归带来的寄存机器语言的区别
(controller
(assign product (const 1))
(assign n (op read))
(assign b (op read))
(assign counter (reg n))
expt-iter-loop
(test (op =) (reg counter) (const 0))
(branch (label expt-done))
(assign counter (op -) (reg counter) (const 1))
(assign product (op *) (reg b) (reg product))
(goto (label expt-iter-loop))
expt-done
(perform (op display) (reg product)))
5.5 手工模拟就算了,5.2节就可以机器模拟了
5.6 是有一个多余的save和一个多余的restore操作,请看注释:
(
(assign continue (label fib-done))
fib-loop
(test (op ) (reg n) (const 2))
(branch (label immediate-answer))
;;compute fib(n-1)
(save continue)
(assign continue (label after-fib-1))
(save n)
(assign n (op -) (reg n) (const 1))
(goto (label fib-loop))
after-fib-1
;;compute fib(n-2)
(restore n)
;这里多余,(restore continue)
(assign n (op -) (reg n) (const 2))
;这里多余,(save continue)
(assign continue (label after-fib-2))
(save val) ;;save fib(n-1)
(goto (label fib-loop))
after-fib-2
(assign n (reg val))
(restore val)
(restore continue)
(assign val (op +) (reg val) (reg n))
(goto (reg continue))
immediate-answer
(assign val (reg n))
(goto (reg continue))
fib-done) 文章转自庄周梦蝶 ,原文发布时间2009-06-11
谭浩强-习题6.3 求Sn=a+aa+aaa+…+aa…aaa(有n个a)之值,其中a是一个数字。 例如:2+22+222+2222+22222(n=5),n由键盘输入。
谭浩强-习题5.8 企业发放的奖金根据利润提成。利润低于或等于100000元的,奖金可提10%; 利润高于100000元,低于200000元(100000 I 200000)时,低于100000元的部分按10%提成,高于100000元的部分,可提成 7.5%; 200000 I 400000时,低于200000元部分仍按上述办法提成,(下同),高于200000元的部分按5%提成; 400000 I 600000元时,高于400000元的部分按3%提成;600000 I 1000000时,高于600000元的部分按1.5%提成; I 1000000时,超过1000000元的部分按1%提成。从键盘输入当月利润I,求应
谭浩强-习题5.7 给出一个不多于5位的整数,要求 1、求出它是几位数 2、分别输出每一位数字 3、按逆序输出各位数字,例如原数为321,应输出123
谭浩强-习题4.8 设圆半径r,圆柱高h 求圆周长C1、圆面积Sa、圆球表面积Sb、圆球体积Va、圆柱体积Vb。 用scanf输入数据,输出计算结果,输出时要求文字说明,取小数点后两位数字。请编程序。 PI=3.14
谭浩强-习题6.9 一球从M米高度自由下落,每次落地后返回原高度的一半,再落下。 它在第N次落地时反弹多高?共经过多少米? 保留两位小数
谭浩强-习题5.6 给出一百分制成绩,要求输出成绩等级‘A’、‘B’、‘C’、‘D’、‘E’。 90分以上为A 80-89分为B 70-79分为C 60-69分为D 60分以下为E
谭浩强-习题6.10 猴子吃桃问题。猴子第一天摘下若干个桃子,当即吃了一半,还不过瘾,又多吃了一个。 第二天早上又将剩下的桃子吃掉一半,又多吃一个。以后每天早上都吃了前一天剩下的一半零一个。 到第N天早上想再吃时,见只剩下一个桃子了。求第一天共摘多少桃子。
5.2 用寄存器语言描述5.1题中的阶乘机器,加上了读取和打印,这里的解答全部在实际的寄存机器中验证过,但是仍然按照该节的表示法表示。
(controller
fac-loop
(assign n (op read))
(assign product (const 1))
(assign counter (const 1))
iter-loop
(test (op ) (reg counter) (reg n))
(branch (label iter-done))
(assign product (op *) (reg product) (reg counter))
(assign counter (op +) (reg counter) (const 1))
(goto (label iter-loop))
iter-done
(perform (op print) (reg product))
(goto (label fac-loop)))
5.3 牛顿法求平方根,将这个过程转化为寄存器语言,第一个版本,假设good-enough?和improve都是基本过程,
;version1
(controller
sqrt-loop
(test (op good-enough?) (reg guess))
(branch (label sqrt-done))
(assign guess (op improve) (reg guess))
(goto (label good-enough))
sqrt-done) 第二个版本,展开good-enough?过程,
;version2
(controller
good-enough
(assign t (op square) (reg guess))
(assign t (op -) (reg t) (reg x))
(assign t (op abs) (reg t))
(test (op ) (reg t) (const 0.001))
(branch (label sqrt-done))
(assign guess (op improve) (reg guess))
(goto (label good-enough))
sqrt-done) 最后,展开improve过程,
;version3
(controller
sqrt-init
(assign guess (const 1.0))
(assign x (op read))
good-enough
;good-enough
(assign t (op square) (reg guess))
(assign t (op -) (reg t) (reg x))
(assign t (op abs) (reg t))
(test (op ) (reg t) (const 0.001))
(branch (label sqrt-done))
;improve
(assign t (op /) (reg x) (reg guess))
(assign t (op +) (reg guess) (reg t))
(assign guess (op /) (reg t) (const 2.0))
(goto (label good-enough))
sqrt-done) 在start之后,从寄存器guess中得到最后结果。
5.4
a)第一个是一个指数计算过程,用到了递归,因此需要引入continue寄存器来保存和恢复堆栈,实现与阶乘相似,如下
(controller
(assign continue (label expt-done))
expt-loop
(test (op =) (reg n) (const 0))
(branch (label expt-base-case))
;;保存continue
(save continue)
(assign n (op -) (reg n) (const 1))
(assign continue (label after-expt))
(goto (label expt-loop))
after-expt
;;恢复continue
(restore continue)
(assign val (op *) (reg b) (reg val))
(goto (reg continue))
expt-base-case
(assign val (const 1))
(goto (reg continue))
expt-done
(perform (op display) (reg val))) b) 迭代型的递归计算过程,尾递归调用,因此不需要continue寄存器来保存和恢复堆栈,这道习题就是希望能分辨非尾递归和尾递归带来的寄存机器语言的区别
(controller
(assign product (const 1))
(assign n (op read))
(assign b (op read))
(assign counter (reg n))
expt-iter-loop
(test (op =) (reg counter) (const 0))
(branch (label expt-done))
(assign counter (op -) (reg counter) (const 1))
(assign product (op *) (reg b) (reg product))
(goto (label expt-iter-loop))
expt-done
(perform (op display) (reg product)))
5.5 手工模拟就算了,5.2节就可以机器模拟了
5.6 是有一个多余的save和一个多余的restore操作,请看注释:
(
(assign continue (label fib-done))
fib-loop
(test (op ) (reg n) (const 2))
(branch (label immediate-answer))
;;compute fib(n-1)
(save continue)
(assign continue (label after-fib-1))
(save n)
(assign n (op -) (reg n) (const 1))
(goto (label fib-loop))
after-fib-1
;;compute fib(n-2)
(restore n)
;这里多余,(restore continue)
(assign n (op -) (reg n) (const 2))
;这里多余,(save continue)
(assign continue (label after-fib-2))
(save val) ;;save fib(n-1)
(goto (label fib-loop))
after-fib-2
(assign n (reg val))
(restore val)
(restore continue)
(assign val (op +) (reg val) (reg n))
(goto (reg continue))
immediate-answer
(assign val (reg n))
(goto (reg continue))
fib-done) 文章转自庄周梦蝶 ,原文发布时间2009-06-11
谭浩强-习题6.3 求Sn=a+aa+aaa+…+aa…aaa(有n个a)之值,其中a是一个数字。 例如:2+22+222+2222+22222(n=5),n由键盘输入。
谭浩强-习题5.8 企业发放的奖金根据利润提成。利润低于或等于100000元的,奖金可提10%; 利润高于100000元,低于200000元(100000 I 200000)时,低于100000元的部分按10%提成,高于100000元的部分,可提成 7.5%; 200000 I 400000时,低于200000元部分仍按上述办法提成,(下同),高于200000元的部分按5%提成; 400000 I 600000元时,高于400000元的部分按3%提成;600000 I 1000000时,高于600000元的部分按1.5%提成; I 1000000时,超过1000000元的部分按1%提成。从键盘输入当月利润I,求应
谭浩强-习题5.7 给出一个不多于5位的整数,要求 1、求出它是几位数 2、分别输出每一位数字 3、按逆序输出各位数字,例如原数为321,应输出123
谭浩强-习题4.8 设圆半径r,圆柱高h 求圆周长C1、圆面积Sa、圆球表面积Sb、圆球体积Va、圆柱体积Vb。 用scanf输入数据,输出计算结果,输出时要求文字说明,取小数点后两位数字。请编程序。 PI=3.14
谭浩强-习题6.9 一球从M米高度自由下落,每次落地后返回原高度的一半,再落下。 它在第N次落地时反弹多高?共经过多少米? 保留两位小数
谭浩强-习题5.6 给出一百分制成绩,要求输出成绩等级‘A’、‘B’、‘C’、‘D’、‘E’。 90分以上为A 80-89分为B 70-79分为C 60-69分为D 60分以下为E
谭浩强-习题6.10 猴子吃桃问题。猴子第一天摘下若干个桃子,当即吃了一半,还不过瘾,又多吃了一个。 第二天早上又将剩下的桃子吃掉一半,又多吃一个。以后每天早上都吃了前一天剩下的一半零一个。 到第N天早上想再吃时,见只剩下一个桃子了。求第一天共摘多少桃子。
相关文章
- ACM入门之【树状数组习题】
- sort函数的应用习题(二)
- sicp习题2.2节尝试解答
- sicp 3.1.1小节习题尝试解答
- sicp 4.4.1小节习题
- 《“笨办法”学Ruby》(第3版)—习题1第一个程序
- 《“笨办法”学Ruby》(第3版)—习题2 注释和#号
- 《“笨办法”学Python(第3版)》——习题3 数字和数学计算
- 算法设计与分析第三章课后习题(部分)
- 《高性能科学与工程计算》——1.7 习题
- 数据库原理及应用第7章课后习题答案
- 习题 3: 数字和数学计算
- 0528习题 11-15
- c程序设计语言_习题1-19_编写函数reverse(s)将字符串s中字符顺序颠倒过来。
- c程序设计语言_习题7-6_对比两个输入文本文件_输出它们不同的第一行_并且要记录行号
- 习题4.1 将学生的学习成绩按不同的分数段分为优、良、中、及格和不及格五个等级,从键盘上输入一个0~100之间的成绩,输出相应的等级。要求用switch语句实现。