计算机算法设计与分析(王晓东著)第一章算法实现题解

计算机算法设计与分析(王晓东著)第一章算法实现题解

思想：借助辅助数组num去统计0-9出现的次数即可。

case1:直接在控制台输入输出。

import java.util.Arrays;import java.util.Scanner;public class CountNumber {public static void countNumber(int n, int [] num){Arrays.fill(num, 0) ;for(int i=1; i<=n; i++){String s = String.valueOf(i) ;for(int j=0; j<s.length(); j++){num[s.charAt(j) - '0'] ++ ;}}for(int i=0; i<num.length; i++){System.out.println(num[i]) ;}}public static void main(String[] args) {Scanner input = new Scanner(System.in) ;int n = input.nextInt() ;int [] num = new int [10] ;countNumber(n, num) ;}}

case2: 通过读取input.txt文件的测试数据，测试结果输出到output.txt文件。

在D盘的study文件夹下创建input.txt文件和output.txt文件，并在input.txt文件中输入测试数据，运行程序，结果将在output.txt文件输出。

import java.io.*;import java.util.Arrays;public class CountNumber {public static String line ;public static int [] countNumber(int n, int [] num){Arrays.fill(num, 0) ;for(int i=1; i<=n; i++){String s = String.valueOf(i) ;for(int j=0; j<s.length(); j++){num[s.charAt(j) - '0'] ++ ;}}return num ;}public static void main(String[] args) {int[] num = new int[10];try (FileInputStream input = new FileInputStream("D:\\study\\input.txt");DataInputStream dataInputStream = new DataInputStream(new BufferedInputStream(input))){line = dataInputStream.readLine() ;} catch (FileNotFoundException ex) {ex.printStackTrace();} catch (IOException ex) {ex.printStackTrace();}System.out.println("文件读取成功！！！");try ( FileOutputStream output = new FileOutputStream("D:\\study\\output.txt");DataOutputStream dataOutputStream = new DataOutputStream(new BufferedOutputStream(output))){int [] res = countNumber(Integer.parseInt(line), num) ;for(int i=0; i<res.length; i++) {dataOutputStream.writeBytes(res[i] + "\n");}} catch (IOException e) {e.printStackTrace();}System.out.println("文件写入成功！！！");}}

import java.util.Scanner;public class Lexicographic1 {//第i位字符开头，长度为k的升序序列个数public static int f(int i, int k){int sum = 0 ;if(k == 1){return 1 ;}else{sum += f(i, k-1) ;}return sum ;}//字符串长度为k的所有长度的总个数public static int g(int k){int sum = 0 ;for(int i=1; i<=26; i++){sum += f(i,k) ;}return sum ;}public static int getResult(String s){int len = s.length() ;int sum = 0 ;for(int i=1; i<len; i++){//长度小于len位的各个位的升序序列的总和sum += g(i) ;}char [] c = s.toCharArray() ;int head = c[0] - 'a' + 1 ;for(int i=1; i<head; i++){//长度等于len位的以head之前的字母打头的序列总和sum += f(i, len) ;}//计算以head打头的剩下字符，长度等于len位的到字符串s之前的序列总和for (int i = 1,temp = head; i < len; i++) {int str2 = c[i]-'a'+1;int len2 = len-i;for (int j = temp+1; j < str2; j++) {sum+=f(j,len2);}temp=str2;}return sum + 1 ;}public static void main(String[] args) {Scanner input = new Scanner(System.in) ;int n = input.nextInt() ;String [] num = new String [n] ;for(int i=0; i<num.length; i++){num[i] = input.next() ;}for(int j=0; j<n; j++) {System.out.println(getResult(num[j]));}}}

case1:直接在控制台输入输出。

import java.util.Scanner;public class Approximate {public static int count(int n){int sum = 0 ;for(int i=1; i<=n; i++){if(n % i == 0){sum ++ ;}}return sum ;}public static int findNumber(int a, int b){int max = 0 ;for(int i=a; i<=b; i++){max = Math.max(max, count(i)) ;}return max ;}public static void main(String[] args) {Scanner input = new Scanner(System.in) ;int a = input.nextInt() ;int b = input.nextInt() ;System.out.println(findNumber(a, b));}}

case 2:通过读取input.txt文件的测试数据，测试结果输出到output.txt文件。

在D盘的study文件夹下创建input.txt文件和output.txt文件，并在input.txt文件中输入测试数据，运行程序，结果将在output.txt文件输出。

import java.io.*;public class Approximate2 {public static String line = "" ;public static String [] num ;public static int count(int n){int sum = 0 ;for(int i=1; i<=n; i++){if(n % i == 0){sum ++ ;}}return sum ;}public static int findNumber(int a, int b){int max = 0 ;for(int i=a; i<=b; i++){max = Math.max(max, count(i)) ;}return max ;}public static void main(String[] args) {try (FileInputStream input = new FileInputStream("D:\\study\\input.txt");DataInputStream dataInputStream = new DataInputStream(new BufferedInputStream(input))){line = dataInputStream.readLine() ;num = line.split("[ ]") ;} catch (FileNotFoundException ex) {ex.printStackTrace();} catch (IOException ex) {ex.printStackTrace();}System.out.println("文件读取成功！！！");try ( FileOutputStream output = new FileOutputStream("D:\\study\\output.txt");DataOutputStream dataOutputStream = new DataOutputStream(new BufferedOutputStream(output))){int res = findNumber(Integer.parseInt(num[0]), Integer.parseInt(num[1])) ;dataOutputStream.writeBytes(res + "\n");} catch (IOException e) {e.printStackTrace();}System.out.println("文件写入成功！！！");}}

case1：控制台输入输出。

import java.util.Scanner;public class Main {public static int count = 0 ;public static boolean flag ;public static void swap(int [][] arr1, int c1, int c2){//交换矩阵的两列for(int i=0; i<arr1.length; i++){int temp = arr1[i][c1] ;arr1[i][c1] = arr1[i][c2] ;arr1[i][c2] = temp ;}if(c1 != c2){count ++ ;}}public static boolean sameColumn(int [][] arr1, int [][] arr2, int c1, int c2){//判断两个矩阵两列元素是否完全相同for(int i=0; i<arr1.length; i++){if(arr1[i][c1] != arr2[i][c2]){return false ;}}return true ;}public static void reverseRow(int [][] arr1, int row){//将矩阵的某行翻转for(int i=0; i<arr1[0].length; i++){arr1[row][i] = arr1[row][i] ^ 1 ;}count ++ ;}public static void copy(int [][] arr1, int [][] arr2, int m ,int n){//复制矩阵for(int i=0; i<m; i++){for(int j=0; j<n; j++){arr1[i][j] = arr2[i][j] ;}}}public static int find(int [][] arr1, int [][] arr2, int m, int n){int [][] temp = new int [m][n] ;int min = m + n + 1 ;copy(temp, arr1, m, n) ;for(int i=0; i<n; i++){//每一列作为第一列swap(arr1, i, 0) ;for(int j=0; j<m; j++){if(arr1[j][0] != arr2[j][0]){reverseRow(arr1, j);}}for(int j=0; j<n; j++){flag = false ;for(int k=j; k<n; k++){if(sameColumn(arr1, arr2, j, k)){swap(arr1, j, k) ;flag = true ;break ; //跳出内层循环}if(!flag){//没有符合条件的break ;}}}if(flag && count < min){min = count ;}count = 0 ;copy(arr1, temp, m, n);}if(min < m + n + 1){return min ;}else{return -1 ;}}public static void main(String[] args) {Scanner input = new Scanner(System.in);int n1 = input.nextInt();int [] res = new int [n1] ;int l = 0 ;while (n1 > 0) {int m = input.nextInt() ;int n = input.nextInt() ;int [][] arr1 = new int [m][n] ;int [][] arr2 = new int [m][n] ;for(int i=0; i<m; i++){for(int j=0; j<n; j++){arr1[i][j] = input.nextInt() ;}}for(int i=0; i<m; i++){for(int j=0; j<n; j++){arr2[i][j] = input.nextInt() ;}}res[l] = find(arr1, arr2, m, n) ;l ++ ;n1 -- ;}for(int i=0; i<res.length; i++){System.out.println(res[i] );}}}

case 2:通过读取input.txt文件的测试数据，测试结果输出到output.txt文件。

在D盘的study文件夹下创建input.txt文件和output.txt文件，并在input.txt文件中输入测试数据，运行程序，结果将在output.txt文件输出。

此部分略，把键盘读取换成IO流读取和输出即可。

case1：直接在控制台输入输出。

思想：先按升序排序，然后依次求间隔，比较找出最大的。

当然，这样，时间复杂度就不是线性了。

要想时间复杂度为线性，要用到鸽笼原理。

import java.util.Arrays;import java.util.Scanner;public class MaximalClearance {public static float max(float [] num){Arrays.sort(num); ;float res = Float.MIN_VALUE ;for(int i=0; i<num.length-1; i++){float interval = num[i+1] - num[i] ;if(interval >= res){res = interval ;}}return res ;}public static void main(String[] args) {Scanner input = new Scanner(System.in) ;int n = input.nextInt() ;float [] num = new float [n] ;for(int i=0; i<n; i++){num[i] = input.nextFloat() ;}System.out.printf("%.1f",max(num));}}

case 2:通过读取input.txt文件的测试数据，测试结果输出到output.txt文件。

在D盘的study文件夹下创建input.txt文件和output.txt文件，并在input.txt文件中输入测试数据，运行程序，结果将在output.txt文件输出。

import java.io.*;import java.util.Arrays;public class MaximalClearance1 {public static String line ;public static int n ;public static float [] num ;public static float max(float [] num){Arrays.sort(num); ;float res = Float.MIN_VALUE ;for(int i=0; i<num.length-1; i++){float interval = num[i+1] - num[i] ;if(interval >= res){res = interval ;}}res = Float.parseFloat(String.format("%.1f", res)) ;return res ;}public static void main(String[] args) {try (FileInputStream input = new FileInputStream("D:\\study\\input.txt");DataInputStream dataInputStream = new DataInputStream(new BufferedInputStream(input))){line = dataInputStream.readLine() ;n = Integer.parseInt(line) ;while(line != null){line = dataInputStream.readLine() ;String [] s = line.split("[ ]") ;num = new float [s.length] ;for(int i=0; i<s.length; i++){num[i] = Float.parseFloat(s[i]) ;}line = dataInputStream.readLine() ;}} catch (FileNotFoundException ex) {ex.printStackTrace();} catch (IOException ex) {ex.printStackTrace();}System.out.println("文件读取成功！！！");try ( FileOutputStream output = new FileOutputStream("D:\\study\\output.txt");DataOutputStream dataOutputStream = new DataOutputStream(new BufferedOutputStream(output))){float res = max(num) ;dataOutputStream.writeBytes(res + "\n");} catch (IOException e) {e.printStackTrace();}System.out.println("文件写入成功！！！");}}