算法导论——第二章习题

矫情吗；* 2022-04-02 15:40 328阅读 0赞

2.1-3、

**问题描述：**

输入：一个规模为n的序列A=<a1, a2, ... , an>、一个值v

输出：当v = A\[i\]时，输出下标 i ；当v没有在A中出现，输出特殊值NIL

**算法描述和验证：**

i = NIL
    for  j = 0 to A.length  do
        if  A[j] = v  then 
            i = j
            return i
        end if 
    end for
    return 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<n; i++) {
    			A[i] = sc.nextInt();
    		}
    		System.out.print("Please enter the number you want to search：");
    		int v = sc.nextInt();
    		
    		System.out.println("i="+search(A, v));
    	}
    	
    	public static int search(int A[], int v) {
    		int i = -10000;
    		for (int j=0; j<A.length; j++) {
    			if (A[j] == v) {
    				i = j;
    				return i;
    			}
    		}
    		return i;
    	}
    }

**运行结果：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzMwOTczNDMx_size_16_color_FFFFFF_t_70][]

2.1-4、

**问题描述：**

输入：两个n位二进制数a、b（分别用大小为n的数组A、B存放）

输出：一个大小为 n + 1 的数组C（存放 a + b 的二进制运算结果）

**算法描述：**

carry = 0
    for 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 if
    end for
    C[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的位置存放的是二进制数的最高位。

**运行结果：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzMwOTczNDMx_size_16_color_FFFFFF_t_70 1][]

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<n; i++) {
    			arr[i] = sc.nextInt();
    		}
    		
    		selectSort(arr);
    		
    		System.out.print("\n排序后的数组为：");
    		for (int i=0; i<n; i++) {
    			System.out.print(arr[i] + "\t");
    		}
    	}
    	
    	//选择排序
    	public static void selectSort(int[] arr) {
    		for (int i=0; i<arr.length-1; i++) {
    			int min = i;
    			// 找到排除i前面部分  的剩余部分arr[i ... n]中的min值，让它与arr[i]交换
    			for (int j=i+1; j<arr.length; j++) {
    				if (arr[j] < arr[min]) {
    					min = j;
    				}
    			}
    			//如果min还是arr[i]，就不用交换了
    			if (min != i) {
    				int temp = arr[min];
    				arr[min] = arr[i];
    				arr[i] = temp;
    			}
    			
    		}
    	}
    }

**运行结果：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzMwOTczNDMx_size_16_color_FFFFFF_t_70 2][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzMwOTczNDMx_size_16_color_FFFFFF_t_70]: /images/20220402/bc488195c55f4cdeb24ea9b91719512a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzMwOTczNDMx_size_16_color_FFFFFF_t_70 1]: /images/20220402/1a15c0b2637e4b409e28355762f7270f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzMwOTczNDMx_size_16_color_FFFFFF_t_70 2]: /images/20220402/112451264a004d8482d1d7830fbef42a.png