归纳证明斐波那契数等式与算法实现

"USTC 算法基础课 第一次习题课" 在这次USTC算法基础课的第一次习题课中，我们关注的重点是通过归纳法来证明斐波那契数列的特定性质，以及几种排序算法的实现和分析。 首先，关于斐波那契数列，题目要求用归纳法证明第i个斐波那契数满足某个等式。斐波那契数列定义为F(0) = 0，F(1) = 1，后续的每个数都是前两个数之和，即F(i) = F(i-1) + F(i-2)。要使用归纳法证明，通常需要分为两步：基础步骤（验证基本情况）和归纳步骤（假设对于k小于i的情况成立，证明对于i也成立）。具体等式未给出，但通常涉及斐波那契数的一些性质，如模运算、平方关系或者递推关系。 接下来，我们来看INSERT-SORT算法的修改。原始INSERT-SORT算法是一种简单的排序方法，它按照非降序对数组进行排序。题目要求修改算法使其能按非升序排序。这是通过在比较条件中将"A[i]>key"更改为"A[i]<key"实现的，这样当A[i]小于key时，元素会被交换位置，从而达到降序排列的效果。 然后，是二进制整数的相加问题。这个问题涉及到两个n位二进制数A和B的相加，结果存储在具有(n+1)个元素的数组C中。伪代码BINARY-ADD描述了这个过程，通过逐位相加，考虑进位（flag）来完成。如果某位相加结果超过1，则会产生进位，并更新到下一位置。 最后，我们讨论了选择排序（SELECT-SORT）算法。该算法通过每次遍历找到剩余未排序部分的最小元素并将其移到正确的位置来工作。循环不变式是：在每一轮循环结束后，数组的前i个元素都是已排序的最小元素。选择排序的时间复杂度在最好和最坏情况下都是O(n^2)，因为无论输入顺序如何，都需要对所有n(n-1)/2对元素进行比较。 本次习题课涵盖了归纳证明、排序算法（INSERT-SORT和SELECT-SORT）的实现及其时间复杂度分析，以及二进制数的加法操作。这些都是计算机科学和算法学习中的基本概念，对于理解和解决问题至关重要。