本文共 2980 字，大约阅读时间需要 9 分钟。
2.1-3、
问题描述：
输入：一个规模为n的序列A=<a1, a2, ... , an>、一个值v
输出：当v = A[i]时，输出下标 i ；当v没有在A中出现，输出特殊值NIL
算法描述和验证：
i = NILfor j = 0 to A.length do if A[j] = v then i = j return i end if end forreturn i
我们采用循环不变式验证该算法的正确性：
初始化：在第一次迭代开始时，j = 1，说明在A[0 ... 0]中没有与v相等的元素
保持：在第 j 次迭代开始时，j作为一个控制量能递增到这里，说明在A[0 ... j-1]中没有找到与v相等的元素
终止：算法有两个终止条件，一个是 j=A.length=n，此时说明在A[0...A.length-1]中都没有找到和v相等的元素；
另一个是j<n 且 v==A[j]，此时说明找得到与v相等的元素。
整个过程中的一个循环不变量是A[0...j-1]，在每一次迭代中，它都表示前i个元素中没有找到v。为了进行下一次迭代，需要满足A[j] != v。
如果在中途就中断了，那说明已经找到 v 了，返回等于 v 的元素的下标；如果我们耗尽所有可能取到的 j 值，则说明没有找到 v 值，返回NIL。
所以说，上面的算法是正确的。
代码实现：
import java.util.Scanner;public class Test2_1_3 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.print("Please enter the size of Array："); int n = sc.nextInt(); int[] A = new int[n]; System.out.println("Please enter every elements of Array："); for (int i=0; i 运行结果：
2.1-4、
问题描述：
输入：两个n位二进制数a、b（分别用大小为n的数组A、B存放）
输出：一个大小为 n + 1 的数组C（存放 a + b 的二进制运算结果）
算法描述：
carry = 0for i=1 to n do C[i] = (A[i] + B[i] + carry)(mod 2) if A[i] + B[i] + carry >= 2 then carry = 1 else carry = 0 end ifend forC[n + 1] = carry
这里的carry表示进位。如果两个数组对应的位A[i]、B[i]和低一位的进位（carry）相加之后≥2，说明需要向高一位进位(carry = 1)，否则不用进位（carry=0）。然后把剩余的部分通过取模运算留下来，放在C[i]。
代码实现：
import java.util.Scanner;public class Test2_1_4 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.print("请输入两个数组的大小n："); int n = sc.nextInt(); int[] A = new int[n]; int[] B = new int[n]; int[] C = new int[n+1]; System.out.print("请输入两个二进制数a、b（大小不能≥2^n）："); int a = sc.nextInt(); int b = sc.nextInt(); //分别把输入的a、b值的二进制位存进对应的A、B数组。（我这里A[0]表示最高位） int i = n-1; while (a > 0) { A[i] = a % 2; a = a / 2; i --; } int j = n-1; while (b != 0) { B[j] = b % 2; b = b / 2; j --; } plus(A, B, C); System.out.print("\n计算后，数组C的内容为："); for (int k=0; k<=n; k++) { System.out.print(C[k] + "\t"); } } public static void plus(int[] A, int[] B, int[] C) { int carry = 0; for (int i=A.length-1; i>=0; i--) { C[i+1] = (A[i]+B[i]+carry) % 2; if ((A[i]+B[i]+carry) >= 2) { carry = 1; } else { carry = 0; } } C[0] = carry; }} 注意，我这里的A、B、C数组的下标为0的位置存放的是二进制数的最高位。
运行结果：
2.2-2、
问题描述：
输入：一个规模为n的数组
输出：该数组按升序排序后的状态（要求采用选择排序）
算法描述和分析：
for i=1 to n-1 do min=i for j=i+1 to n do //在数组剩余未排序的部分A[i ... n]中找最小值，将它与A[i]进行交换 if A[j] < A[min] then min = j end if end for Swap A[min] and A[i]end for
该算法的循环不变式为：
初始：第二次迭代开始之前，A[1 ... 1]已经有序
维持：每一次迭代A[1 ... i-1]始终保持升序的有序状态
终止：当i跑完所有能取的i之后（1 ... n-1），第1 ... n-1小的数已经分别放在A[1 ... n-1]对应的位置上，所以剩下的一个数据A[n]是最大值，所以整个数组排序完毕。故，该算法是正确的。
代码实现：
// 习题2.2-2 选择排序import java.util.Scanner;public class Test2_2_2 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.print("请输入数组的大小n："); int n = sc.nextInt(); int[] arr = new int[n]; System.out.print("请输入数组的所有元素（n个）："); for (int i=0; i 运行结果：
转载地址：http://qbnii.baihongyu.com/