龙空技术网

文心一言 VS chatgpt (3)-- 算法导论2.1

福大大架构师每日一题 163

前言:

眼前大家对“线性查找的伪代码”可能比较注意,咱们都想要学习一些“线性查找的伪代码”的相关内容。那么小编也在网摘上收集了一些有关“线性查找的伪代码””的相关文章,希望各位老铁们能喜欢,朋友们一起来学习一下吧!

# 一、以图 2-2 为模型,说明INSERTION-SORT 在数组 A=(31,41,59,26,41,58)上的执行过程。

文心一言:

以图 2-2 为模型,说明INSERTION-SORT 在数组 A=(31,41,59,26,41,58) 上的执行过程。

首先,将数组 A 中的每个元素 a[i] 插入到数组 A[i-1] 的后面,即 a[i] = a[i-1]+1。

接着,将数组 A 中的每个元素 a[i] 插入到数组 A[i-1] 的前面,即 a[i] = a[i-1]-1。

最后,将数组 A 中的每个元素 a[i] 插入到数组 A[i-1] 的左边,即 a[i] = a[i-1]+1。

因此,INSERTION-SORT 在数组 A=(31,41,59,26,41,58) 上的执行过程如下:

a[0] = 31

a[1] = 26

a[2] = 41

a[3] = 41

a[4] = 26

a[5] = 59

a[6] = 58

在这个过程中,数组 A 中的每个元素 a[i] 都被插入到了正确的位置。

chatgpt:

以下是在数组 A=(31,41,59,26,41,58)上执行 INSERTION-SORT 的过程:

1. 第一次迭代:

- i = 2, key = 41

- 将 41 与 31 比较,大于 31,则不进行交换,数组为 (31, 41, 59, 26, 41, 58)

2. 第二次迭代:

- i = 3, key = 59

- 将 59 与 41 比较,大于 41,则不进行交换,数组为 (31, 41, 59, 26, 41, 58)

3. 第三次迭代:

- i = 4, key = 26

- 将 26 与 59 比较,小于 59,则将 59 向右移动一位,数组为 (31, 41, 26, 59, 41, 58)

- 将 26 与 41 比较,小于 41,则将 41 向右移动一位,数组为 (31, 26, 41, 59, 41, 58)

- 将 26 与 31 比较,小于 31,则将 31 向右移动一位,数组为 (26, 31, 41, 59, 41, 58)

- 将 26 插入到正确的位置,数组为 (26, 31, 41, 59, 41, 58)

4. 第四次迭代:

- i = 5, key = 41

- 将 41 与 59 比较,小于 59,则将 59 向右移动一位,数组为 (26, 31, 41, 41, 59, 58)

- 将 41 插入到正确的位置,数组为 (26, 31, 41, 41, 59, 58)

5. 第五次迭代:

- i = 6, key = 58

- 将 58 与 59 比较,小于 59,则将 59 向右移动一位,数组为 (26, 31, 41, 41, 58, 59)

- 将 58 插入到正确的位置,数组为 (26, 31, 41, 41, 58, 59)

最终得到排序后的数组 A=(26, 31, 41, 41, 58, 59)。

# 二、重写过程 INSERTION-SORT,使之按非升序(而不是非降序)排序。

文心一言:

在 INSERTION-SORT 算法中,如果要按非升序排序,可以使用以下步骤:

将数据分成两个部分:要插入的数据和已排序的数据。

对要插入的数据进行排序。可以使用任何一种排序算法,例如冒泡排序、快速排序、归并排序等。

将要插入的数据插入到已排序的数据中。可以使用任何一种插入算法,例如直接插入、归并插入等。

重复步骤 2 和步骤 3,直到所有数据都被插入到已排序的数据中。

下面是一个示例实现:

```python

def insertion_sort(arr):

# 将数据分成两个部分:要插入的数据和已排序的数据

n = len(arr)

for i in range(1, n):

# 对要插入的数据进行排序

arr[i] = arr[i-1]

# 将要插入的数据插入到已排序的数据中

j = i - 1

while j >= 0 and arr[j] > arr[i]:

arr[j+1] = arr[j]

j -= 1

arr[j+1] = arr[i]

return arr

```

在这个实现中,我们首先将数据分成两个部分:要插入的数据和已排序的数据。然后,我们对要插入的数据进行排序,并将其插入到已排序的数据中。最后,我们重复这个过程,直到所有数据都被插入到已排序的数据中。

chatgpt:

以下是重写后的 INSERTION-SORT 过程,使其按非升序排序:

```

INSERTION-SORT(A)

1 for j = 2 to A.length

2 key = A[j]

3 i = j - 1

4 while i > 0 and A[i] < key

5 A[i+1] = A[i]

6 i = i - 1

7 A[i+1] = key

```

相较于原来的 INSERTION-SORT,该算法对第 4 行的判断条件进行了修改。在原来的算法中,判断条件为 `A[i] > key`,即当前元素大于待插入元素时,继续进行循环操作。而在这里,我们将其改为 `A[i] < key`,即当前元素小于待插入元素时,继续进行循环操作。这样就能够实现按非升序排序了。

# 三、考虑以下查找问题:

输入:n个数的一个序列A=(al,a2,……,an)和一个值v。

输出:下标i使得v=A[i]门或者当v不在A 中出现时,v为特殊值 NIL。

写出线性查找的伪代码,它扫描整个序列来查找 v。使用一个循环不变式来证明你的算法是正确的。确保你的循环不变式满足三条必要的性质。

文心一言:

chatgpt:

以下是线性查找的伪代码:

```

LINEAR-SEARCH(A, v)

1 for i = 1 to A.length

2 if A[i] == v

3 return i

4 return NIL

```

循环不变式:在每次循环之前,将会检查前 i-1 个元素是否与 v 相等,如果存在,则已经返回该元素的下标,否则返回 NIL。

循环不变式需要满足三个必要性质:

1. 初始化:在第一次循环之前,i=1。此时前 i-1 个元素为空序列,因此循环不变式成立。

2. 保持:假设前 i-1 个元素都不等于 v,在第 i 次迭代中,会检查 A[i] 是否等于 v。如果 A[i] 等于 v,则算法会返回 i;否则进入下一个迭代,此时前 i 个元素仍然都不等于 v,因此循环不变式仍然成立。

3. 终止:当循环终止时,有两种情况:(a) 找到了等于 v 的元素,返回其下标 i;(b) 遍历完整个数组后没有找到等于 v 的元素,此时返回 NIL。在两种情况下,循环不变式成立。

因此,根据循环不变式,可以证明该算法的正确性。

# 四、考虑把两个n 位二进制整数加起来的问题,这两个整数分别存储在两个n元数组A和B中。这两个整数的和应按二进制形式存储在一个(n+1)元数组 C中。请给出该问题的形式化描述,并写出伪代码。

文心一言:

题目描述:

给定两个n位二进制整数A和B,它们的和应按二进制形式存储在一个(n+1)元数组C中。请你编写一个算法,将A和B的和转换为二进制形式存储在C中。

算法步骤:

1.创建一个新的(n+1)元数组C,长度为n+1。

2.将A和B的值按位相加,并将结果存储在C的第一个位置。

3.将C的第一个位置后面的所有位置设置为0,以便存储下一个元素。

4.重复步骤2和步骤3,直到C的所有位置都被填充为0。

5.返回C的值。

伪代码:

```scss

function binarySum(A, B, C)

n = length(A)

for i from 0 to n-1

C[i] = A[i] + B[i]

end for

C[n] = 0

for i from n+1 to length(A)

C[i] = C[i-1] + A[i]

end for

return C

end function

```

该算法的时间复杂度为O(n+1),其中n是A和B的长度。

chatgpt:

问题形式化描述:

输入:两个n元数组A和B,表示两个二进制整数;

输出:一个(n+1)元数组C,表示两个二进制整数的和。

伪代码如下:

```

BINARY-ADDITION(A, B)

1 let C[1...n+1] be a new array

2 carry = 0

3 for i = n downto 1

4 sum = A[i] + B[i] + carry

5 if sum == 2

6 C[i+1] = 0

7 carry = 1

8 else if sum == 3

9 C[i+1] = 1

10 carry = 1

11 else

12 C[i+1] = sum

13 carry = 0

14 if carry == 1

15 C[1] = 1

16 else

17 C = C[2...n+1]

18 return C

```

该算法从右向左逐位相加,使用变量 `carry` 记录上一位的进位。若当前位为 0 或 1,则直接将其加到对应的位置 `C[i+1]` 上,并将进位 `carry` 设为 0。若当前位为 2 或 3,则需要分别设置 `C[i+1]` 的值,并将进位 `carry` 设置为 1。在处理完所有位后,需要检查最高位是否有进位,若有则在 `C[1]` 上设置为 1,否则去掉最高位并返回。

# 五、给我画一个虎背熊腰的妹子

文心一言:

标签: #线性查找的伪代码