跳至主要內容

Part0 Representing numbers as strings

AI悦创原创2023年9月20日Python辅导gatech.eduPython 作业代写乔治亚理工Python辅导gatech.eduPython 作业代写乔治亚理工大约 27 分钟...约 8055 字

Part 0: Representing numbers as strings

第0部分:将数字表示为字符串

The following exercises are designed to reinforce your understanding of how we can view the encoding of a number as string of digits in a given base.

以下练习旨在加强您对如何在给定的进制中查看数字编码为数字字符串的理解。

If you are interested in exploring this topic in more depth, see the "Floating-Point Arithmetic" section of the Python documentation.

如果您对深入探讨此主题感兴趣,请参阅Python文档中的"浮点数运算"部分

Integers as strings

Consider the string of digits:

    '16180339887'

If you are told this string is for a decimal number, meaning the base of its digits is ten (10), then its value is given by

[ ⁣[16180339887] ⁣]10=(1×1010)+(6×109)+(1×108)++(8×101)+(7×100)=16, ⁣180, ⁣339, ⁣887. [\![ \mathtt{16180339887} ]\!]_{10} = (1 \times 10^{10}) + (6 \times 10^9) + (1 \times 10^8) + \cdots + (8 \times 10^1) + (7 \times 10^0) = 16,\!180,\!339,\!887.

Similarly, consider the following string of digits:

    '100111010'

If you are told this string is for a binary number, meaning its base is two (2), then its value is

[ ⁣[100111010] ⁣]2=(1×28)+(1×25)++(1×21). [\![ \mathtt{100111010} ]\!]_2 = (1 \times 2^8) + (1 \times 2^5) + \cdots + (1 \times 2^1).

(What is this value?)

And in general, the value of a string of d+1d+1 digits in base bb is,

[ ⁣[sdsd1s1s0] ⁣]b=i=0dsi×bi. [\![ s_d s_{d-1} \cdots s_1 s_0 ]\!]_b = \sum_{i=0}^{d} s_i \times b^i.

Bases greater than ten (10). Observe that when the base at most ten, the digits are the usual decimal digits, 0, 1, 2, ..., 9. What happens when the base is greater than ten? For this notebook, suppose we are interested in bases that are at most 36; then, we will adopt the convention of using lowercase Roman letters, a, b, c, ..., z for "digits" whose values correspond to 10, 11, 12, ..., 35.

zh

字符串表示的整数

考虑以下数字字符串:

    '16180339887'

如果你被告知这个字符串表示一个十进制数,也就是说它的基数是十(10),那么其值为

[ ⁣[16180339887] ⁣]10=(1×1010)+(6×109)+(1×108)++(8×101)+(7×100)=16, ⁣180, ⁣339, ⁣887. [\![ \mathtt{16180339887} ]\!]_{10} = (1 \times 10^{10}) + (6 \times 10^9) + (1 \times 10^8) + \cdots + (8 \times 10^1) + (7 \times 10^0) = 16,\!180,\!339,\!887.

同样,考虑以下数字字符串:

    '100111010'

如果你被告知这个字符串表示一个二进制数,也就是说它的基数是二(2),那么其值为

[ ⁣[100111010] ⁣]2=(1×28)+(1×25)++(1×21). [\![ \mathtt{100111010} ]\!]_2 = (1 \times 2^8) + (1 \times 2^5) + \cdots + (1 \times 2^1).

(这个值是多少?)

总的来说,一个基数为bbd+1d+1位数字符串的值是:

[ ⁣[sdsd1s1s0] ⁣]b=i=0dsi×bi. [\![ s_d s_{d-1} \cdots s_1 s_0 ]\!]_b = \sum_{i=0}^{d} s_i \times b^i.

大于十(10)的基数。 注意当基数最大为十时,其数字是常见的十进制数字,012、...、9。当基数大于十时会怎样呢?在这个笔记本中,假设我们只关心最大为36的基数;那么,我们将采用使用小写罗马字母,abc、...、z 来代表其值分别为10、11、12、...、35的"数字"。

Exercise 0 (3 points)

Write a function, eval_strint(s, base). It takes a string of digits s in the base given by base. It returns its value as an integer.

That is, this function implements the mathematical object, [ ⁣[s] ⁣]b[\![ s ]\!]_b, which would convert a string ss to its numerical value, assuming its digits are given in base bb. For example:

    eval_strint('100111010', base=2) == 314

Hint: Python makes this exercise very easy. Search Python's online documentation for information about the int() constructor to see how you can apply it to solve this problem. (You have encountered this constructor already, in Notebook/Assignment 2.)

zh

翻译如下:

练习 0 (3 分)

编写一个函数,eval_strint(s, base)。它接受一个以 base 为基数的数字字符串 s。函数应返回其作为整数的值。

也就是说,此函数实现了数学对象 [ ⁣[s] ⁣]b[\![ s ]\!]_b,该对象将字符串 ss 转换为其数值,假设其数字是以基数 bb 给出的。例如:

    eval_strint('100111010', base=2) == 314

提示:Python 使这个练习变得非常简单。查阅 Python 的在线文档,了解有关 int() 构造函数的信息,看看如何应用它来解决此问题。(你已经在 Notebook/Assignment 2 中遇到过这个构造函数。)

The demo included in the solution cell below should display the following output:

eval_strint('6040', 8) -> 3104
eval_strint('deadbeef', 16) -> 3735928559
eval_strint('4321', 5) -> 586

Note: This demo calls your function 3 times.

### Exercise 0 solution
def eval_strint(s, base=2):
    assert type(s) is str
    assert 2 <= base <= 36
    ###
    ### YOUR CODE HERE
    ###
    
### demo function call
print(f"eval_strint('6040', 8) -> {eval_strint('6040', 8)}")
print(f"eval_strint('deadbeef', 16) -> {eval_strint('deadbeef', 16)}")
print(f"eval_strint('4321', 5) -> {eval_strint('4321', 5)}")
eval_strint('6040', 8) -> None
eval_strint('deadbeef', 16) -> None
eval_strint('4321', 5) -> None

The cell below will test your solution for Exercise 0. The testing variables will be available for debugging under the following names in a dictionary format.

详情

翻译成中文为:

下面的单元格将测试你为练习0提供的解决方案。测试变量将以字典格式可用于调试,以下是名称:

  • input_vars - 你的解决方案的输入变量。
  • original_input_vars - 在运行解决方案之前的输入变量的副本。这些 应该input_vars 相同 - 否则意味着你的解决方案修改了输入。
  • returned_output_vars - 你的解决方案返回的输出。
  • true_output_vars - 预期的输出。这 应该 基于问题要求与 returned_output_vars "匹配" - 否则,你的解决方案没有返回正确的输出。

Solution 0

1

根据题目描述,可以使用 Python 的 int() 构造函数来实现。这是一个简单的实现:

def eval_strint(s, base):
    return int(s, base)

# 测试示例
print(eval_strint('100111010', base=2))  # 输出 314

如上面的代码所示,int() 函数可以接受两个参数:要转换的字符串和该字符串的基数。它会返回对应基数的整数值。

Fractional values

Recall that we can extend the basic string representation to include a fractional part by interpreting digits to the right of the "fractional point" (i.e., "the dot") as having negative indices. For instance,

[ ⁣[3.14] ⁣]10=(3×100)+(1×101)+(4×102). [\![ \mathtt{3.14} ]\!]_{10} = (3 \times 10^0) + (1 \times 10^{-1}) + (4 \times 10^{-2}).

Or, in general,

[ ⁣[sdsd1s1s0.s1s2sr] ⁣]b=i=rdsi×bi. [\![ s_d s_{d-1} \cdots s_1 s_0 \, \underset{\Large\uparrow}{\Huge\mathtt{.}} \, s_{-1} s_{-2} \cdots s_{-r} ]\!]_b = \sum_{i=-r}^{d} s_i \times b^i.

Exercise 1 (4 points)

Suppose a string of digits s in base base contains up to one fractional point. Complete the function, eval_strfrac(s, base), so that it returns its corresponding floating-point value.

Your function should always return a value of type float, even if the input happens to correspond to an exact integer.

Examples:

    eval_strfrac('3.14', base=10) ~= 3.14
    eval_strfrac('100.101', base=2) == 4.625
    eval_strfrac('2c', base=16) ~= 44.0   # Note: Must be a float even with an integer input!

Comment. Because of potential floating-point roundoff errors, as explained in the videos, conversions based on the general polynomial formula given previously will not be exact. The testing code will include a built-in tolerance to account for such errors.

Hint. You should be able to construct a solution that reuses the function, eval_strint(), from Exercise 0.

zh

翻译如下:

分数值

回想一下,我们可以通过解释"小数点"(即"点")右边的数字为负指数来扩展基本的字符串表示以包括一个小数部分。例如,

[ ⁣[3.14] ⁣]10=(3×100)+(1×101)+(4×102). [\![ \mathtt{3.14} ]\!]_{10} = (3 \times 10^0) + (1 \times 10^{-1}) + (4 \times 10^{-2}).

或者,更一般地说,

[ ⁣[sdsd1s1s0.s1s2sr] ⁣]b=i=rdsi×bi. [\![ s_d s_{d-1} \cdots s_1 s_0 \, \underset{\Large\uparrow}{\Huge\mathtt{.}} \, s_{-1} s_{-2} \cdots s_{-r} ]\!]_b = \sum_{i=-r}^{d} s_i \times b^i.

练习 1 (4 分)

假设一个数字字符串 s 在基数 base 中包含至多一个小数点。完成函数 eval_strfrac(s, base),使其返回相应的浮点数值。

你的函数应该始终返回一个 float 类型的值,即使输入恰好对应于一个确切的整数。

示例:

    eval_strfrac('3.14', base=10) ~= 3.14
    eval_strfrac('100.101', base=2) == 4.625
    eval_strfrac('2c', base=16) ~= 44.0   # 注意:即使输入是整数,也必须是浮点数!

评论:由于可能的浮点舍入误差,正如视频中解释的那样,基于之前给出的一般多项式公式的转换将不会是精确的。测试代码将包括一个内置的容忍度来考虑这样的错误。

提示:你应该能够构建一个解决方案,该解决方案重用了练习 0 中的函数 eval_strint()

The demo included in the solution cell below should display the following output:

eval_strfrac('3.14', base=10) -> 3.14
eval_strfrac('100.101', base=2) -> 4.625
eval_strfrac('2c', base=16) -> 44.0

Note: This demo calls your function 3 times.

### Exercise 1 solution
def eval_strfrac(s, base=2):    
    ###
    ### YOUR CODE HERE
    ###
    
### demo function call
print(f"eval_strfrac('3.14', base=10) -> {eval_strfrac('3.14', base=10)}") 
print(f"eval_strfrac('100.101', base=2) -> {eval_strfrac('100.101', base=2)}")
print(f"eval_strfrac('2c', base=16) -> {eval_strfrac('2c', base=16)}")

The cell below will test your solution for Exercise 1. The testing variables will be available for debugging under the following names in a dictionary format.

Solution 1

1

要解决这个问题,我们可以先将字符串s分成整数部分和小数部分,然后分别使用 eval_strint 函数计算每部分的值,并将它们相加。

以下是如何实现的:

上面的代码首先检查输入字符串 s 是否包含小数点。如果有,它将字符串分为整数部分和小数部分。接下来,我们使用 eval_strint 函数分别计算整数部分和小数部分的值,并最终将它们相加以得到最终的浮点数值。

Floating-point encodings

Recall that a floating-point encoding or format is a normalized scientific notation consisting of a base, a sign, a fractional significand or mantissa, and a signed integer exponent. Conceptually, think of it as a tuple of the form, (±,[ ⁣[s] ⁣]b,x)(\pm, [\![s]\!]_b, x), where bb is the digit base (e.g., decimal, binary); ±\pm is the sign bit; ss is the significand encoded as a base bb string; and xx is the exponent. For simplicity, let's assume that only the significand ss is encoded in base bb and treat xx as an integer value. Mathematically, the value of this tuple is ±[ ⁣[s] ⁣]b×bx\pm \, [\![s]\!]_b \times b^x.

zh

浮点数编码

回想一下,浮点数编码或格式是一个标准的科学记数法,它由一个 基数、一个 符号、一个小数 有效数字尾数,以及一个有符号的整数 指数 组成。从概念上讲,把它看作是一个形式为 (±,[ ⁣[s] ⁣]b,x)(\pm, [\![s]\!]_b, x) 的元组,其中 bb 是数字基数(例如,十进制、二进制);±\pm 是符号位;ss 是以基数 bb 编码的尾数;而 xx 是指数。为了简单起见,我们假设只有尾数 ss 是以基数 bb 编码的,并将 xx 视为一个整数值。数学上,这个元组的值为 ±[ ⁣[s] ⁣]b×bx\pm \, [\![s]\!]_b \times b^x

IEEE double-precision. For instance, Python, R, and MATLAB, by default, store their floating-point values in a standard tuple representation known as IEEE double-precision format. It's a 64-bit binary encoding having the following components:

Thus, the smallest positive value in this format 210222.23×103082^{-1022} \approx 2.23 \times 10^{-308}, and the smallest positive value greater than 1 is 1+ϵ1 + \epsilon, where ϵ=2522.22×1016\epsilon=2^{-52} \approx 2.22 \times 10^{-16} is known as machine epsilon (in this case, for double-precision).

zh

IEEE 双精度。例如,Python、R 和 MATLAB 默认将其浮点值存储在一个称为 IEEE 双精度格式 的标准元组表示中。它是一个64位二进制编码,具有以下组件:

  • 最重要的位表示值的符号。
  • 尾数是一个53位的字符串,其前导数字_隐式地_为一。也就是说,如果 ss 的位字符串表示为 s0.s1s2sds_0 . s_1 s_2 \cdots s_d,那么 s0=1s_0=1 总是成立的,并且从不明确地存储。这也意味着 d=52d=52
  • 指数是一个11位的字符串,并被视为范围在 [1022,1023][-1022, 1023] 之间的有符号整数。

因此,这种格式的最小正值为 210222.23×103082^{-1022} \approx 2.23 \times 10^{-308},大于1的最小正值为 1+ϵ1 + \epsilon,其中 ϵ=2522.22×1016\epsilon=2^{-52} \approx 2.22 \times 10^{-16} 被称为 机器 epsilon(在这种情况下,是双精度)。

Special values. You might have noticed that the exponent is slightly asymmetric. Part of the reason is that the IEEE floating-point encoding can also represent several kinds of special values, such as infinities and an odd bird called "not-a-number" or NaN. This latter value, which you may have seen if you have used any standard statistical packages, can be used to encode certain kinds of floating-point exceptions that result when, for instance, you try to divide zero by zero.

If you are familiar with languages like C, C++, or Java, then IEEE double-precision format is the same as the double primitive type. The other common format is single-precision, which is float in those same languages.

zh

特殊值。 你可能已经注意到,指数有些不对称。部分原因是IEEE浮点数编码还可以表示几种特殊值,如无穷大以及一个被称为“非数字”的奇怪值,或者叫做 NaN。如果你曾使用过任何标准的统计软件包,你可能已经看到过这个值。当你试图用零除以零时,可能会出现这种浮点异常,此时可以用该值来编码这种异常。

如果你熟悉C、C++或Java这样的语言,那么IEEE双精度格式与这些语言中的 double 原始类型是相同的。另一种常见格式是单精度,它在这些语言中被称为 float

def print_fp_hex(v):
    assert type(v) is float
    print("v = {} ==> v.hex() == '{}'".format(v, v.hex()))
    
print_fp_hex(0.0)
print_fp_hex(1.0)
print_fp_hex(16.0625)
print_fp_hex(-0.1)

Inspecting a floating-point number in Python. Python provides support for looking at floating-point values directly! Given any floating-point variable, v (that is, type(v) is float), the method v.hex() returns a string representation of its encoding. It's easiest to see by example, so run the following code cell:

zh

在Python中检查浮点数。 Python提供了直接查看浮点值的支持!给定任何浮点变量 v(即 type(v) is float),方法 v.hex() 返回其编码的字符串表示。通过示例最容易看出,所以运行以下代码单元:

Observe that the format has these properties:

Thus, to convert this string back into the floating-point value, you could do the following:

For example, here is how you can get 16.025 back from its hex() representation, '0x1.0100000000000p+4':

zh

观察这种格式具有以下特性:

  • 如果 v 是负数,字符串的第一个字符是 '-'
  • 接下来的两个字符始终是 '0x'
  • 之后,直到但不包括字符 'p' 的下一个字符都是十六进制(基数为16)的小数字符串。换句话说,这个子字符串对应于以base-16编码的尾数。
  • 字符 'p' 分隔了尾数和指数。接下来是一个带符号的整数作为指数(前缀为 '+''-')。它隐含的基数是2——不是基数16,尽管尾数是。

因此,要将这个字符串转换回浮点值,你可以执行以下操作:

  • 记录符号为一个值,v_sign,它可以是+1或-1。
  • 假设基数为16的数字,将尾数转换为一个小数值,v_signif
  • 提取指数作为一个带符号的整数值,v_exp
  • 计算最终值为 v_sign * v_signif * (2.0**v_exp)

例如,以下是如何从其 hex() 表示,'0x1.0100000000000p+4',恢复16.025的方法:

# Recall: v = 16.0625 ==> v.hex() == '0x1.0100000000000p+4'
print((+1.0) * eval_strfrac('1.0100000000000', base=16) * (2**4))

Exercise 2 - (4 Points):

Write a function, fp_bin(v), that determines the IEEE-754 tuple representation of any double-precision floating-point value, v. That is, given the variable v such that type(v) is float, it should return a tuple with three components, (s_sign, s_signif, v_exp) such that

For example:

    v = -1280.03125
    assert v.hex() == '-0x1.4002000000000p+10'
    assert fp_bin(v) == ('-', '1.0100000000000010000000000000000000000000000000000000', 10)

There are many ways to approach this problem. One we came up exploits the observation that [ ⁣[0] ⁣]16==[ ⁣[0000] ⁣]2[\![\mathtt{0}]\!]_{16} == [\![\mathtt{0000}]\!]_2 and [ ⁣[f] ⁣]16=[ ⁣[1111] ⁣][\![\mathtt{f}]\!]_{16} = [\![\mathtt{1111}]\!] and applies an idea in this Stackoverflow post: https://stackoverflow.com/questions/1425493/convert-hex-to-binary

zh
# Demo of `float.hex()`
v = -1280.03125
print(v.hex())
### Exercise 2 solution
def fp_bin(v):
    assert type(v) is float
###
### YOUR CODE HERE
###

fp_bin(v)

The cell below will test your solution for Exercise 2. The testing variables will be available for debugging under the following names in a dictionary format.

Solution 2

Exercise 3 - (2 Points):

Suppose you are given a floating-point value in a base given by base and in the form of the tuple, (sign, significand, exponent), where

Complete the function,

def eval_fp(sign, significand, exponent, base):
    ...

so that it converts the tuple into a numerical value (of type float) and returns it.

For example, eval_fp('+', '1.25000', -1, base=10) should return a value that is close to 0.125.

zh

翻译为中文:

练习3 - (2 分):

假设你得到了一个基数为 base 的浮点值,这个值以元组的形式给出,形式为 (sign, significand, exponent),其中:

  • sign 是一个字符,如果这个值是正数则为 '+',否则为 '-';
  • significand 是一个在基数-base 下的字符串表示;
  • exponent 是表示指数值的整数。

完成以下函数:

def eval_fp(sign, significand, exponent, base):
    ...

使其将元组转换为数值(类型为 float)并返回。

例如,eval_fp('+', '1.25000', -1, base=10) 应该返回接近 0.125 的值。

### Define demo inputs

demo_inputs_ex3 = [{'sign': '-', 'significand': '2.G0EBPT', 'exponent': -1, 'base': 32},
                   {'sign': '+', 'significand': '1.20100202211020211211', 'exponent': 4, 'base': 3},
                   {'sign': '+', 'significand': '1.10101110101100100101001111000101', 'exponent': -5, 'base': 2}]

The demo included in the solution cell below should display the following output:

eval_fp('-', '2.G0EBPT', -1, 32) -> -0.0781387033930514
eval_fp('+', '1.20100202211020211211', 4, 3) -> 138.25708894296503
eval_fp('+', '1.10101110101100100101001111000101', -5, 2) -> 0.05257526742207119

Note the demo calls your fp_bin solution on 3 sets of inputs.

zh

下面的解决方案单元中包含的演示应显示以下输出:

eval_fp('-', '2.G0EBPT', -1, 32) -> -0.0781387033930514
eval_fp('+', '1.20100202211020211211', 4, 3) -> 138.25708894296503
eval_fp('+', '1.10101110101100100101001111000101', -5, 2) -> 0.05257526742207119

注意 演示调用了您的 fp_bin 解决方案,输入了3组数据。

### Exercise 3 solution
def eval_fp(sign, significand, exponent, base=2):
    assert sign in ['+', '-'], "Sign bit must be '+' or '-', not '{}'.".format(sign)
    assert type(exponent) is int

    ###
    ### YOUR CODE HERE
    ###
   
for params in demo_inputs_ex3:
    print(f"eval_fp('{params['sign']}', '{params['significand']}', {params['exponent']}, {params['base']}) -> {eval_fp(**params)}")

The cell below will test your solution for Exercise 3. The testing variables will be available for debugging under the following names in a dictionary format.

Solution 3

code

Exercise 4 - (2 Points):

Suppose you are given two binary floating-point values, u and v, in the tuple form given above. That is,

    u == (u_sign, u_signif, u_exp)
    v == (v_sign, v_signif, v_exp)

where the base for both u and v is two (2). Complete the function add_fp_bin(u, v, signif_bits), so that it returns the sum of these two values with the resulting significand truncated to signif_bits digits.

For example:

u = ('+', '1.010010', 0)
v = ('-', '1.000000', -2)
assert add_fp_bin(u, v, 7) == ('+', '1.000010', 0)  # Caller asks for a significand with 7 digits

and:

u = ('+', '1.00000', 0)
v = ('-', '1.00000', -6)
assert add_fp_bin(u, v, 6) == ('+', '1.11111', -1)  # Caller asks for a significand with 6 digits

(Check these examples by hand to make sure you understand the intended output.)

Note 0: Assume that signif_bits includes the leading 1. For instance, suppose signif_bits == 4. Then the significand will have the form, 1.xxx.

Note 1: You may assume that u_signif and v_signif use signif_bits bits (including the leading 1). Furthermore, you may assume each uses far fewer bits than the underlying native floating-point type (float) does, so that you can use native floating-point to compute intermediate values.

Hint: An earlier exercise defines a function, fp_bin(v), which you can use to convert a Python native floating-point value (i.e., type(v) is float) into a binary tuple representation.

The cell below will test your solution for Exercise 4. The testing variables will be available for debugging under the following names in a dictionary format.

Solution 4

code
公众号:AI悦创【二维码】

AI悦创·编程一对一

AI悦创·推出辅导班啦,包括「Python 语言辅导班、C++ 辅导班、java 辅导班、算法/数据结构辅导班、少儿编程、pygame 游戏开发、Web、Linux」,全部都是一对一教学:一对一辅导 + 一对一答疑 + 布置作业 + 项目实践等。当然,还有线下线上摄影课程、Photoshop、Premiere 一对一教学、QQ、微信在线,随时响应!微信:Jiabcdefh

C++ 信息奥赛题解,长期更新!长期招收一对一中小学信息奥赛集训,莆田、厦门地区有机会线下上门,其他地区线上。微信:Jiabcdefh

方法一:QQ

方法二:微信:Jiabcdefh

你认为这篇文章怎么样?
  • 0
  • 0
  • 0
  • 0
  • 0
  • 0
评论
  • 按正序
  • 按倒序
  • 按热度
通知
关于编程私教&加密文章