数据结构与算法分析原书第三版(Java语言描述)课后习题答案（更新中）
Chapter-1：引论
1.1 编写一个程序解决选择问题. 令k=N/2. 画出表格显示程序对于N种不同的值的运行时间
import java.util.Arrays;
import java.util.Random;
/**
* 1 确定 N 个数中第 K 个最大值
* 2 根据《数据结构与算法分析-Java语言描述》将前K个数读入一个数组，使用冒泡排序递减
* 3 将剩下的元素逐个读入
* 4 如果新元素小于第 K 个元素，忽略；否则将新元素插入正确的位置
*/
public class Select {
public static final Random RANDOM = new Random(47);
// 设N = 6
public static void main(String[] args) {
for (int i = 0; i < 6; i++) {
printResult(createArray(RANDOM.nextInt(100000)));
}
}
// 冒泡排序
public static void sort(int[] values) {
for (int i = 1; i < values.length; i++) {
for (int j = 0; j values[j + 1]) {
int temp = values[j];
values[j] = values[j + 1];
values[j + 1] = temp;
}
}
}
}
// 分批处理
public static int select(int[] values) {
if (values == null || values.length == 0) {
throw new NullPointerException("values can't be null");
}
int k = values.length / 2;
int[] temp = Arrays.copyOf(values, k);
sort(temp);
for (int i = k; i < values.length; i++) {
if (values[i] 0; j--) {
if (values[i] > temp[j]) {
temp[j + 1] = values[i];
break;
} else {
temp[j] = temp[j - 1];
}
}
}
}
return temp[k - 1];
}
// 创建随机数组
public static int[] createArray(int length) {
int[] values = new int[length];
for (int i = 0; i < length; i++) {
values[i] = RANDOM.nextInt(length * 2);
}
return values;
}
public static void printResult(int[] values) {
System.out.println("长度:" + values.length);
long start = System.currentTimeMillis();
System.out.println("result:" + select(values));
System.out.println("用时:" + (System.currentTimeMillis() - start) + "ms");
System.out.println("--------------------------------------");
}
}
运行结果：
长度:69258
result:69656
用时:2880ms
--------------------------------------
长度:62440
result:62383
用时:2220ms
--------------------------------------
长度:69968
result:70050
用时:2174ms
--------------------------------------
长度:84314
result:84052
用时:3168ms
--------------------------------------
长度:16447
result:16526
用时:104ms
--------------------------------------
长度:55856
result:55804
用时:1350ms
--------------------------------------
Process finished with exit code 0
1.2编写一个程序求解字谜游戏问题
class Riddle {
public static final String[] WORDS = {"this", "two", "fat", "that"};
public static final char[][] CONST = {{'t', 'h', 'i', 's'}, {'w', 'a', 't', 's'}, {'o', 'a', 'h', 'g'}, {'f', 'g', 'd', 't'}};
public static void main(String[] args) {
findWords(CONST, WORDS);
}
public static void findWords(char[][] arr, String[] words) {
// 记录首字母，不重复
StringBuilder initials = new StringBuilder();
for (String word : words) {
String initial = word.substring(0, 1);
if (!initials.toString().contains(initial)) {
initials.append(initial);
}
}
// 遍历每个元素是否是首字母
for (int x = 0; x < arr.length; x++) {
for (int y = 0; y < arr[x].length; y++) {
if (initials.toString().contains(String.valueOf(arr[x][y]))) {
for (int p = 1; p <= 8; p++) {
String tem = "";
int xEnd = x, yEnd = y;
while (xyAva(arr, xEnd, yEnd)) {
tem += arr[xEnd][yEnd];
printWord(tem, x, y, xEnd, yEnd);
if (p == 1) {
xEnd--;
}
if (p == 2) {
xEnd++;
}
if (p == 3) {
yEnd++;
}
if (p == 4) {
yEnd--;
}
if (p == 5) {
xEnd--;
yEnd++;
}
if (p == 6) {
xEnd++;
yEnd--;
}
if (p == 7) {
xEnd++;
yEnd++;
}
if (p == 8) {
xEnd--;
yEnd--;
}
}
}
}
}
}
}
public static boolean xyAva(char[][] arr, int x, int y) {
if (0 <= x && x < arr.length) {
return 0 <= y && y (" + (xEnd + 1) + "," + (yEnd + 1) + ")");
}
}
}
}
运行结果：
单词：two 向量:(1,1)->(3,1)
单词：this 向量:(1,1)->(1,4)
单词：fat 向量:(4,1)->(2,3)
单词：that 向量:(4,4)->(1,1)
Process finished with exit code 0
1.3 只使用处理I/O的printDigit方法，编写一种方法以输出任意double型量（可以是负的）
/**
* @author ycw
*/
public class Digit {
public static void printDigit(double num, int integerLength, int decimalLength) {
//递归方法的的基准
if (integerLength == decimalLength) {
return;
}
//往基准靠拢
integerLength++;
int n = (int) (num * Math.pow(10, integerLength));
System.out.print(n % 10);
// 判断输出小数
if (integerLength == 0) {
System.out.print(".");
}
printDigit(num, integerLength, decimalLength);
}
public static void main(String[] args) {
double num = -12.63;
System.out.print("输出Double:" + "-");
num = Math.abs(num);
int integer = (int) num;
int integerLength = Integer.toString(integer).length();
int decimalLength = Double.toString(num).length() - integerLength - 1;
printDigit(num, -integerLength, decimalLength);
}
}
运行结果：
输出Double:-12.63
Process finished with exit code 0
1.5 编写一种递归方法，它返回数N的二进制表中1的个数. 利用这样的事实：如果N是奇数，那么其1的个数等于N/2的二进制表中1的个数加1
import java.util.Scanner;
public class Recursion {
/**
* 功能：编写一个递归方法，它返回数N的二进制表示中1的个数
* 算法：如果N是奇数，那么其1的个数等于N/2的二进制表示中1的个数加1
*/
public static int recursion(int n){
if (n == 0) {
return 0;
} else if (n == 1) {
return 1;
} else {
if (n % 2 == 0) {
return recursion(n / 2);
} else {
return recursion(n / 2) + 1;
}
}
}
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n = input.nextInt();
int sum = recursion(n);
System.out.println("二进制表中1的个数：" + sum);
}
}
运行结果：
5
二进制表中1的个数：2
1.6 编写带有下列声明的例程 :
public void permute(String str);
public void permute(Char [] str, int low, int high);
/**
* 第一个例程是个驱动程序，它调用第二个例程并显示String str中字符的所有排列。
* 例如，str是"abc"， 那么输出的串则是abc，acb，bac，bca，cab，cba
* 考察全排列、递归和非递归
*/
class Permute {
public static void permute(String str) {
permute(str.toCharArray(), 0, str.length());
}
/**
* 递归
*/
public static void permute(char[] str, int low, int height) {
if (low == height - 1) {
StringBuilder s = new StringBuilder();
for (int i = 0; i < height; i++) {
s.append(str[i]);
}
System.out.println(s);
}
for (int i = low; i < height; i++) {
if (isSwap(str, low, i)) {
swap(str, low, i);
permute(str, low + 1, height);
swap(str, low, i);
}
}
}
/**
* 交换
*/
public static void swap(char[] str, int a, int b) {
if (str[a] == str[b]) {
return;
}
char c = str[a];
str[a] = str[b];
str[b] = c;
}
/**
* a到b是否重复
*/
public static boolean isSwap(char[] str, int a, int b) {
for (int i = a; i < b; i++) {
if (str[i] == str[b]) {
return false;
}
}
return true;
}
public static void main(String[] args) {
String str = "abc";
permute(str);
}
}
运行结果：
abc
acb
bac
bca
cba
cab
Process finished with exit code 0
作者：.WYc
