二分递归的是什么原理,教教
10205102406 edited 3 年,10 月前
1、(20 points)《计算机导论》练习题2.3.1, 2.3.3, 2.3.4, 2.3.5, 2.3.6, 2.3.7. 2.3.9, 2.3.11。假设浮点数存放用书本描述的简单方式。
练习2.3.1
290
143
154500
练习2.3.3
11110000
练习2.3.4
10000100
练习2.3.5
124
练习2.3.6
-8
练习2.3.7
3次移位,3次加法
练习2.3.9
00101010
练习2.3.11
-19
2、(20 points)《计算机导论》练习题2.4.2,2.4.3,2.4.4,2.4.6
练习2.4.2
非
01
10
或
000
101
011
111
与
000
010
100
111
练习2.4.3
8个
2^n个
练习2.4.4
1
1
0
练习2.4.6
非1001
1001或1111
3、(20 points)《计算机导论》练习题2.5.1, 2.5.2,2.5.3, ,2.5.4,2.5.5, ,2.5.6,2.5.7,2.5.8
练习题2.5.1
8192b
练习题2.5.2
5*2^20KB
练习题2.5.3
536870912000B
练习题2.5.4
10^12
10^15
练习题2.5.5
0x6c99
0x8001
0x5e08
练习题2.5.6
0x6c99
0x884c
0x52c9
练习题2.5.7
o
?
练习题2.5.8
a
4、(10 points)请问你如何检查一个三进制数是2的倍数。例如,121,101,2200都是2的倍数,请证明你的方法。注意,要证明,不是凭感觉。
各位数字之和为偶数,因为每位数对应的十进制都是一个奇数,与2取模为1,故可以表示为2k+每位数之和
5、(20 points)This programming assignment can be done by you alone or a group of two students. 写下合作同学的名字。
(A)习题2.10。试验x=128, y=8; x=129, y=8; x=1, y=12; x=2047, y=12 这些-x 的补码二进制值。
(B)类似习题 2.7,八位元CPU。但是输入x, y 是介于-128 到127间的任意整数。转为二进制后,做加法,如果有溢出,需要返回错误,否则返回十进制的结果。此题的重点是负数补码,二进制加法,和判断溢出。判断溢出必须用书上的方法,在二进制的结果上直接判断。
请同学试验各种情况,例如,64+65, 100+10, 100+(-128),10+(-100), (-30)+(-100), (-127)+127
A
for x,y in [[128,8],[129,8],[1,12],[2047,12]]:
print(x,y,end=":")
if x >= 1<<y:
print(False)
else:
if x == 0:
print("0"*y)
else:
print("0"*(2+y-len(bin(2**y+~x+1)))+format(2**y+~x+1,'b'))
B
def d2b(a,n):
flag = False
if a<0:
a = -a
flag = True
res = []
e = 1<<(n-1)
for i in range(n):
if a >= e:
a-=e
res.append(not flag)
else:
res.append(flag)
e>>=1
return add(res,[False for i in range(n-1)]+[flag])
def b2d(a):
flag = 1
if a[0] == True:
for i in range(len(a)):
a[i] = not a[i]
a = add(a,[False for i in range(len(a)-1)]+[True])
flag = -1
res = 0
for i in range(len(a)):
res = res*2+(1 if a[i] else 0)
return res*flag
def FA(a,b,c):
carry = (a and b)or(b and c)or(a and c)
sum = (a and b and c)or(a and (not b) and (not c))or((not a) and b and (not c))or((not a) and (not b) and c)
return carry,sum
def add(x,y):
carry = False
res = []
for i in range(len(x)-1,-1,-1):
carry,sum = FA(x[i],y[i],carry)
res = [sum]+res
return res
for x,y in [[64,65],[100,10],[100,-128],[10,-100],[-30,-100],[-127,127]]:
print(x,y,end=":")
x = d2b(x,8)
y = d2b(y,8)
res = add(x,y)
if x[0] == y[0] and x[0] != res[0]:
print("ERROR")
else:
print(b2d(res))
6、(15 points)这题可以两人合作,写下合作同学的名字及学号。请同学们把你的代码拷贝到word报告中,并将程序的运行结果截图粘贴到代码下方。
输入两个任意长度的字符串代表两个浮点数,假设没有符号,都是正数,输出字符串代表此两浮点数的和。例如,输入“12.123”,“1.2”输出为“13.323”;又例如,输入为“12.1234567890123456789”,“1.987654321”,输出为其和“14.1111111100123456789”。请你尽量利用Python整数可以任意多位的特性来完成此程序。你可以将一个浮点数分成两部分整数:小数点前和小数后,再分别处理。
(挑战题额外10分)处理任意负数,和任意乘法。建议没时间就跳过,有时间则练习,试试看,请告知我们你的程序能处理什么样的情况,例如加法,减法,什么样的乘法?
#!/usr/bin/env python
# _*_ coding:utf-8 _*_
def add(x, y):
x1,x2 = x.split(".")
y1,y2 = y.split(".")
s = str(int(y.replace(".","")+"0"*((len(x2) - len(y2)) if len(x2) - len(y2) > 0 else 0))+int(x.replace(".","")+"0"*((len(y2) - len(x2)) if len(y2) - len(x2) > 0 else 0)))
a = s[:len(s)-max(len(x2),len(y2))]
if a == "-":
return "-0."+s[len(s)-max(len(x2),len(y2)):]
elif a == "":
return "0."+s[len(s)-max(len(x2),len(y2)):]
else:
return s[:len(s)-max(len(x2),len(y2))]+"."+s[len(s)-max(len(x2),len(y2)):]
def dec(x, y):
return add(x, ("-"+y if y[0] != "-" else y[1:]))
def mul(x,y):
x1,x2 = x.split(".")
y1,y2 = y.split(".")
s = str(int(y.replace(".",""))*int(x.replace(".","")))
a = s[:len(s)-(len(x2)+len(y2))]
if a == "-":
return "-0."+s[len(s)-(len(x2)+len(y2)):]
elif a == "":
return "0."+s[len(s)-(len(x2)+len(y2)):]
else:
return s[:len(s)-(len(x2)+len(y2))]+"."+s[len(s)-(len(x2)+len(y2)):]
for x,y in [["12.123","1.2"],["12.1234567890123456789","1.987654321"]]:
print(x,y,end=":")
print(add(x,y))
能处理位数不那么大的加法减法乘法
7、(15 points) Python编程,递归练习。这题要自己写,可以与同学讨论,但是不是合作,请同学们把你的代码拷贝到word报告中,并将程序的运行结果截图粘贴到代码下方。输入字符串X代表一个无符号二进制数,输出它的十进制值。例如,X=”101”,输出5。注意,你必须要用二分法递归方式!!试试X=”101”*10, X=”1100”*30
dic = {"0":0,"1":1}
def cal(x):
if x in dic:
return dic[x]
length = int(len(x)/2)
x1 = x[:length]
x2 = x[length:]
res = (cal(x1)<<(len(x)-length))+cal(x2)
dic[x] = res
return res
print(cal("101"))
print(cal("101"*10))
print(cal("1100"*30))
8.、(20 points)This programming assignment can be done by you alone or a group of two students. 写下合作同学的名字。
输入2个十进制的整数,你的程序将它们转为二进制后,编写二进制乘法函数,函数返回二进制值,再转为十进制输出。我们现在有正负和位数限制。假设CPU是N位(你的程序要适用给定任意N介于8到20),用补位法表示正负值,例如N=12,则可表示范围是-2048 到 2047 之间的任意值。输入2个十进制的整数,检查介于可表示范围内,就马上转为二进制表示,编写二进制乘法函数mult(),限制在N位,函数返回是否溢出,如果没有溢出返回正确的结果二进制值,再转为十进制输出。例如给定N=12时:
例如x=-12, y=100, 最后输出是 -1200。
例如 x=-30, y=-10, 最后输出是 300
例如,x=4, y=-512, 最后输出是 -2048
例如,x=4, y=512, 最后输出是 “溢出错误”
例如 x=40, y=-80, 最后输出是 “溢出错误”
函数Mult(a, b , N): 输入a, b 是补位后二进制(可以是字符串),N 代表最大限制位数。例如, N=12。 建议如果a, b都是负数,将它们转为正数,再做正数相乘 ;假如a正 b负,则a,b可以交换。让b作为正数,然后一位位看b的位是否0、1,需要时加上移位后的a,如同多个负数相加,只需留下N位部分,仍然能保持它正确的补位值。在函数内检查是否有溢出,绝对不能转为十进制来检查,这不是CPU内使用的方式,在CPU内的运算都是二进制,所以必须在二进制中检查。
请同学们把你的代码拷贝到word报告中,并将程序的运行结果截图粘贴到代码
N=12
def d2b(a):
flag = False
if a<0:
a = -a
flag = True
res = []
e = 1<<(N-1)
for i in range(N):
if a >= e:
a-=e
res.append(not flag)
else:
res.append(flag)
e>>=1
return add(res,[False for i in range(N-1)]+[flag])
def b2d(a):
if a == [True]+[False for i in range(N-1)]:
return -1*2**(N-1)
flag = 1
if a[0] == True:
for i in range(len(a)):
a[i] = not a[i]
a = add(a,[False for i in range(len(a)-1)]+[True])
flag = -1
res = 0
for i in range(len(a)):
res = res*2+(1 if a[i] else 0)
return res*flag
def FA(a,b,c):
carry = (a and b)or(b and c)or(a and c)
sum = (a and b and c)or(a and (not b) and (not c))or((not a) and b and (not c))or((not a) and (not b) and c)
return carry,sum
def add(x,y):
carry = False
res = []
for i in range(len(x)-1,-1,-1):
carry,sum = FA(x[i],y[i],carry)
res = [sum]+res
if x[0] == y[0] and x[0] != res[0]:
return False
return res
def mult(x,y,N):
res = x[:] if y[-1] else [False for i in range(N)]
for i in range(N-2,-1,-1):
passed = left_move(x)
if y[i]:
if not passed:
return False
res = add(res,x)
if res == False:
return False
return res
def left_move(x):
if x[0] != x[1]:
return False
for i in range(N-1):
x[i] = x[i+1]
x[N - 1] = False
return True
for x,y in [[-12,100],[-30,-10],[4,-512],[4,512],[40,-80]]:
print(x,y,end=":")
if -2**(N-1)<=x<=2**(N-1)-1 and -2**(N-1)<=y<=2**(N-1)-1:
if x<0 and y<0:
x = d2b(-x)
y = d2b(-y)
elif y<0:
t=x
x = d2b(y)
y = d2b(t)
else:
x = d2b(x)
y = d2b(y)
res = mult(x,y,N)
if res == False:
print("溢出错误")
else:
print(b2d(res))
制作者:姜博远
仅供参考
我也不知道他这个二分递归什么意思,我就把字符串分成了两半,用字典保存已经处理过的字符串,然后每一半先检测有没有处理过,没处理的再二分处理,然后前半左移后半的位数加上后半就好了。
观察了一下,我觉得这题搞二分递归挺脱裤子放屁的,不管怎么写,最后时间复杂度还是O(n)
+1,我也不晓得二分必要何在,不过把处理过的存起来就能空间换时间拉到O(lgn),最优情况下。