当前位置: 首页 > 模式/算法 > 算法导论(三版):第二章第一节课后题

算法导论(三版):第二章第一节课后题

第二章:算法基础
第一节:插入排序

2.1-1

Using Figure 2.2 as a model, illustrate the operation of INSERTION-SORT on the array A =(31, 41, 59, 26, 41,58).

答:
插入排序过程

制作文档已经上传到了云盘:CLRS_exercises_2.1-1.xlsx

2.1-2

Rewrite the INSERTION-SORT procedure to sort into nonincreasing instead of nondecreasing order.
答:
应该是只将 第五行的 A[i] > key 改为 A[i] < key即可。

INSERTION-SORT-NONINCREASING(A)
for j = 2 to A.length
    key = A[j]
    i = j - 1
    while i > 0 and A[i] < key
        A[i+1] = A[i]
        i = i - 1
    A[i+1] = key

2.1-3

这里写图片描述

答:
思路非常简单,遍历一遍即可。
伪代码:

linear_search(A,v)
    for j = 1 to A.length
        if A[j] == v
            return j
    return NIL

循环不变式的证明,这个我觉得很奇怪,但我还是硬着头皮一个。

每一轮循环维持的循环不变式:
每次循环开始之前(是指赋值 j,但是没有在测试j与A.length大小之前),下标小于j-1的元素绝对不与v相等。

  • 初始化: 当第一次给j赋值时,j=1。j-1=0,没有元素,肯定不与v相等。
  • 保持: 当一轮循环结束时,如果没有执行到返回语句:return j,说明当前比对的元素A[j]不等于v。当下一轮循环开始时,j-1就是上一轮循环比过的元素,所以肯定不等于v。循环不定式成立。
  • 终止: 终止有两种情况。如果执行到return j,说明已经找到了一个与v相等的元素,那么返回对应的下标,循环终止。此时循环不定式没有提供太多的帮助。但是如果执行到是j大于A.length的终止情况:那么循环不定式将提供非常有用的性质。因为当 j = A.length + 1,循环要终止。根据循环不定式,j - 1 = A.length,也就是说小于A.length 的元素肯定不与v相等。此时代码的下一句是return NIL,是正确的。

    坦白说,这个循环不定式非常的讲究形式,我对其使用方式也不是十分熟悉。上面证明我也重写了很多次。书中有一句话让我很是介意,是关于终止的:Termination: When the loop terminates, the invariant gives us a useful property that helps show that the algorithm is correct. 这句话的意思是指循环不定式成为了一条有用的性质。我最终将我的循环不定式改了一条性质,非常有成就感。

2.1-4

Consider the problem of adding two n-bit binary integers, stored in two n-element arrays A and B. The sum of the two integers should be stored in binary form in an (n + 1)-element array C. State the problem formally and write pseudocode for adding the two integers.

答:
1、形式化描述:
输入:A、B两个长度为n的序列,分别以二进制的方式表示两个整数。(也就是序列的每个元素只能是0或1)
输出:长度为n+1的序列,为A、B两数组之和。也是用二进制表示的整数。

关于这个形式化定义,中文书第3页(第一章的首页)出现过,我是按照3页出现的形式来写的,不一定十分标准。

2、解决这个问题的思路也非常简单,A、B元素每位相乘的时候逢2进1即可。python代码如下:

#!/usr/bin/env python
# -*- coding: utf8 -*-
"""
brief:算法导论的练习题2.1-4
author:zhangyang27@baidu.com
"""
import doctest


def binary_adding(a,b):
    """
    二进制的相加
    Example
    -------
    >>> binary_adding('10','00')
    '010'
    >>> binary_adding('10','10')
    '100'
    >>> binary_adding('11','11')
    '110'
    >>> binary_adding('01','01')
    '010'
    """
    a=list(a)
    b=list(b)
    c = []

    for i in xrange(len(a)+1):
        c.append('0')

    for i in xrange(len(a)-1,-1,-1):
        c[i+1] = str(int(a[i]) + int(b[i]) + int(c[i+1]))
        if int(c[i+1]) == 2:
            c[i] = '1'
            c[i+1] = '0'
        if int(c[i+1]) == 3:
            c[i] = '1'
            c[i+1] = '1'
    return "".join(c)

def main():
    doctest.testmod()


if __name__ == '__main__' :
    main()

文章来源于网络

转载时请以 超链接的形式 注明:转自疯狂泰克