计导第六次作业 - Blog - ECNU Online Judge

Compare

10205102406 edited 4 年前

This is a past version of blog 计导第六次作业

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

非

或

000

101

011

111

与

000

010

100

111

练习2.4.3

8个

2^n个

练习2.4.4

练习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

练习题2.5.8

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

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'))

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 = [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))

制作者：姜博远

计导第六次作业 (Past)

服务

开源

关于我们