计导第六次作业

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.22.4.32.4.42.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.22.5.3, ,2.5.42.5.5, ,2.5.62.5.72.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的倍数。例如,1211012200都是2的倍数,请证明你的方法。注意,要证明,不是凭感觉。

各位数字之和为偶数,因为每位数对应的十进制都是一个奇数,与2取模为1,故可以表示为2k+每位数之和

5、(20 pointsThis 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 pointsThis programming assignment can be done by you alone or a group of two students. 写下合作同学的名字。

输入2个十进制的整数,你的程序将它们转为二进制后,编写二进制乘法函数,函数返回二进制值,再转为十进制输出。我们现在有正负和位数限制。假设CPUN位(你的程序要适用给定任意N介于820),用补位法表示正负值,例如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的位是否01,需要时加上移位后的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))

制作者:姜博远
仅供参考

Past Versions

Comments

请PSG.LGD挑选冠军

二分递归的是什么原理,教教

10205102406

我也不知道他这个二分递归什么意思,我就把字符串分成了两半,用字典保存已经处理过的字符串,然后每一半先检测有没有处理过,没处理的再二分处理,然后前半左移后半的位数加上后半就好了。

请PSG.LGD挑选冠军

观察了一下,我觉得这题搞二分递归挺脱裤子放屁的,不管怎么写,最后时间复杂度还是O(n)

# coding: utf-8
# Convert a binary num to D by using binary meth.

def convert(x, left, right):
    if left > right:
        return 0
    if left == right:
        return int(x[left])*(2**left)
    mid = (left+right)//2
    return convert(x, left, mid)+convert(x, mid+1, right)


def main():
    e = input()
    times = int(input())
    e*=times
    x = list(e)
    x.reverse()
    print(convert(x, 0, len(x)-1))


if __name__ == "__main__":
    main()
10205102406

+1,我也不晓得二分必要何在,不过把处理过的存起来就能空间换时间拉到O(lgn),最优情况下。