(算法设计与分析)第一章算法概述-习题
文章目录
- 一:算法分析题
- 二:算法实现题
- (1)统计数字问题
- (2)字典序问题
- (3)最多约数问题
- (4)金币阵列问题
- (5)最大间隙问题
一:算法分析题
答
- 3 n 2 + 1 0 n = O ( n 2 ) 3n^{2}+10^{n}=O(n^{2}) 3n2+10n=O(n2)
- n 2 10 + 2 n = O ( 2 n ) \frac{n^{2}}{10}+2^{n}=O(2^{n}) 10n2+2n=O(2n)
- 21 + 1 n = O ( 1 ) 21+\frac{1}{n}=O(1) 21+n1=O(1)
- L o g n 3 = 3 l o g n = O ( l o g n ) Logn^{3}=3logn=O(logn) Logn3=3logn=O(logn)
- 10 l o g 3 n = 10 n l o g 3 = O ( n ) 10log3^{n}=10nlog3=O(n) 10log3n=10nlog3=O(n)
答 :两个算法时间复杂度相同,都是常数阶,区别在于常数因子不同
答 :一般来说, O ( 1 ) O(1) O(1)< O ( l o g 2 n ) O(log_{2}n) O(log2n)< O ( n ) O(n) O(n)< O ( n l o g 2 n ) O(nlog_{2}n) O(nlog2n)< O ( n 3 ) O(n^{3}) O(n3)< O ( 2 n ) O(2^{n}) O(2n)< O ( n ! ) O(n!) O(n!)< O ( n n ) O(n^{n}) O(nn)(常对幂指)
且有:
- 2 = O ( 1 ) 2=O(1) 2=O(1)
- 4 n 2 = O ( 2 ) 4n^{2}=O(^{2}) 4n2=O(2)
- 20 n = O ( n ) 20n=O(n) 20n=O(n)
故: 2 2 2< l o g n logn logn< n 2 3 n^{\frac{2}{3}} n32< 20 n 20n 20n< 4 n 2 4n^{2} 4n2< 3 n 3^{n} 3n< n ! n! n!
答:
(1):
- 由题意知,第一台机器在 t t t秒内可以完成 3 × 2 n 3×2^{n} 3×2n次基本运算
- 新机器速度比第一台机器速度快64倍,所以它在 t t t秒内可以完成 64 × 3 × 2 n = 3 × 2 n + 6 64×3×2^{n}=3×2^{n+6} 64×3×2n=3×2n+6次基本运算
- 由 T = 3 × 2 n T=3×2^{n} T=3×2n知 n = l o g 2 ( T 3 ) n=log_{2}(\frac{T}{3}) n=log2(3T)
- 假设新机器需要处理问题规模为 n n e w n_{new} nnew的问题,则 n n e w = l o g 2 ( 3 × 2 n + 6 3 ) = n + 6 n_{new}=log_{2(\frac{3×2^{n+6}}{3})}=n+6 nnew=log2(33×2n+6)=n+6
- 所以新机器上用同一算法 t t t秒内可以处理输入规模为 n + 6 n+6 n+6的问题
(2)
- 与(1)同理,所以此时新机器上用同一算法 t t t秒内可以处理输入规模为 8 n 8n 8n的问题
(3)
- 由于此时时间复杂度为 O ( 1 ) O(1) O(1),所以在新机器上用 t t t时间可以解决任意规模的问题
答: 此题与1-4同理
- O ( n ) O(n) O(n):能处理输入规模为 100 n 100n 100n的问题
- O ( n 2 ) O(n^{2}) O(n2):能处理输入规模为 100 n 2 100n^{2} 100n2的问题
- O ( n 3 ) O(n^{3}) O(n3):能处理输入规模为 100 n 3 100n^{3} 100n3的问题
- O ( n ! ) O(n!) O(n!):能处理输入规模为 n + l o g 100 n+log100 n+log100, ≈ n + 6.64 \approx n+6.64 ≈n+6.64的问题
二:算法实现题
(1)统计数字问题
答: 利用%
每次取出最后一位,同时让此位映射至数组索引处加和即可
import java.util.Arrays;
import java.util.Scanner;
public class PageNumber {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(sc.hasNextInt()){
int n = sc.nextInt();
int[] array = new int[10];
for(int i = 1; i < n+1; i++){
int temp = i;
while(temp != 0){
array[temp % 10] += 1;
temp /= 10;
}
}
System.out.println(Arrays.toString(array));
}
sc.close();
}
}
(2)字典序问题
答:以字符串str={e, m, v
}为例
- 该字符串长度是3,所以在其前面有长度分为1和2的字符串编号
- 然后是分别以a,b,c,d开头的长度为3的字符串编号
- 然后是分别以f,g,h,i,j,k,l,开头的长度为2的字符串编号
- 然后是分别以m,n,o,p,q,r,s,t,u开头的长度为1的字符串编号
- 以上字符串编号求和,再加1,即为该字符串待求编号
import java.util.Scanner;
public class LexicographicOrder {
/**
* 返回字符c对应的Ascii编码,范围设置到(1-26)
* @param c
* @return
*/
public static int toAscii(char c){
return c - 'a' + 1;
}
/**
* 返回以str_i为开头,长为len的字符串的编码个数
* @param str_i
* @param len
* @return
*/
public static int fun2(int str_i, int len){
int code = 0;
if(len == 1){return 1;}
for(int i = str_i+1; i < 27; i++){
code += fun2(i, len-1); // 采用递归求法
}
return code;
}
/**
* 返回长度为len的字符串对应的编码个数
* @param len
* @return
*/
public static int fun1(int len){
int code = 0;
for(int i = 1; i < 27; i++){
code += fun2(i, len);
}
return code;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(sc.hasNextLine()){
int code = 0;
String input = sc.nextLine();
//第一步:首先调用fun1计算长度小于输入字符串长度的编码个数
for(int i = 1; i < input.length(); i++){
code += fun1(toAscii(input.charAt(i-1)));
}
//第二步:从首位开始,计算以j为开头长度为i的字符串编码个数
int start = 0; //控制开始位置
for(int i = input.length(); i > 0; i--){
for(int j = start + 1; j < toAscii(input.charAt(input.length()-i)); j++){
code += fun2(j, i);
}
start = toAscii(input.charAt(input.length()-i));
}
int ret = code+1; //最终返回时要+1
System.out.println(input + "对应的编码为:" + ret);
}
sc.close();
}
}
(3)最多约数问题
答:直接暴力解决
import java.util.Scanner;
public class MaximumDivisor {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int max_divisor_num = 1; //最大约数个数
int max_divisor = 0; //最大约数
while(scanner.hasNextInt()){
int a = scanner.nextInt();
int b = scanner.nextInt();
for(int i = a; i <= b; i++){
int divisor = 2;
for(int j = 2; j < i; j++){
if(i % j == 0){
divisor++;
if(divisor > max_divisor_num){
max_divisor_num = divisor;
max_divisor = i;
}
}
}
}
System.out.println("最大约数为:" + max_divisor + ";div(" + max_divisor + ")=" + max_divisor_num);
}
}
}
(4)金币阵列问题
答:在变换金币阵列时,要先固定行变换或列变换,之后就不能再进行行变换或列变换。我们以列变换优先,每一列都可作为第一列,然后再进行第一列与目标列进行比较,如果不相同,则进行行翻转,此后,第一列将固定下来;然后再进行比较后续列是否有与目标列相同的列,如果有则交换,并更新最小次数;如果没有则进行下一次循环,直到结束
import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Scanner;
public class Gold {
public static int mindata = 9999;
public static int count = 0;
public static int[][] temp = new int[4][3];
public static void fipRow(int row_i){
for(int i = 0; i < temp[0].length; i++){
temp[row_i][i] ^= 1;
}
}
public static void swapTempFirstCol(int col_i, int col_j){
for(int i = 0; i < temp.length;i++){
int tmp = temp[i][col_i];
temp[i][col_i] = temp[i][col_j];
temp[i][col_j] = tmp;
}
if(col_i != col_j){
count++;
}
}
public static Boolean isSame(int[][] gold2, int col_i, int col_j){
boolean flag = true;
for(int k = 0; k < temp.length; k++){
if(temp[k][col_j] != gold2[k][col_i]){
flag = false;
break;
}
}
return flag;
}
public static void main(String[] args) {
//测试数据
// int[][] gold1 = {{1, 0, 1}, {0, 0, 0}, {1, 1, 0}, {1, 0, 1}};
// int[][] gold2 = {{1, 0, 1}, {1, 1, 1}, {0, 1, 1}, {1, 0, 1}};
Scanner scanner = new Scanner(System.in);
int rows = scanner.nextInt();
int cols = scanner.nextInt();
int[][] gold1 = new int[rows][cols];
int[][] gold2 = new int[rows][cols];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
gold1[i][j] = scanner.nextInt();
}
}
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
gold2[i][j] = scanner.nextInt();
}
}
//先设法固定列
for (int k = 0; k < cols; k++) {
//复制gold1数组给temp数组保存下来便于修改
for (int i = 0; i < gold1.length; i++) {
temp[i] = Arrays.copyOf(gold1[i], gold1[i].length);
}
//把第k列放置到第1列尝试
swapTempFirstCol(0, k);
//判断哪一行出现了不同,然后反转
for (int i = 0; i < rows; i++) {
if (temp[i][0] != gold2[i][0]) {
fipRow(i);
}
}
//判断后面列是否有相同
boolean found = false;
for (int i = 1; i < cols; i++) {
found = false;
for (int j = i; j < cols; j++) {
//如果有相同的则交换
if (isSame(gold2, j, i)) {
found = true;
swapTempFirstCol(j, i);
break;
}
}
}
if (found) {
mindata = count;
}
}
if (mindata < 9999) {
System.out.println(count);
} else {
System.out.println(-1);
}
scanner.close();
}
}
(5)最大间隙问题
答: 传统做法并不能满足题目中线性时间复杂度要求,这里用到鸽舍原理
- 把 n + 1 n+1 n+1个元素分为 n n n类,不管怎么分,一定有一类中有2个或2个以上的元素
- 把多于 m × n m×n m×n个物体放到 n n n个抽屉里,那么一定有一个抽屉里有 m + 1 m+1 m+1个或者 m + 1 m+1 m+1个以上的物体
算法步骤
-
找出数组中的最小值和最大值
-
创建n-1个抽屉并初始化,每个抽屉的小值放数组最大值,大值放数组的最小值
-
根据数组中n个元素的相对大小,将他们放在这n-1个抽屉中,可能有的抽屉中为空值,可能有的抽屉中含有多个元素,并记录每一个抽屉的小值和大值
-
用后一个抽屉的小值减去上一个抽屉的大值,得到抽屉之间的间隙,最后取出最大的那个间隙(前提:易知最大间隙一定大于等于n个元素的平均距离,所以抽屉内的元素间隙一定不是最大间隙,最大间隙只能在抽屉间)
import java.util.Scanner;
public class MaxGap {
//定义抽屉
public static class Drawer{
public double low;
public double high;
public int count;
public Drawer(double low, double high, int count) {
this.low = low;
this.high = high;
this.count = count;
}
}
//返回最小值
private static double min(double[] array){
double min_val = array[0];
for(int i = 1; i < array.length; i++){
if(array[i] < min_val){
min_val = array[i];
}
}
return min_val;
}
//返回最大值
private static double max(double[] array){
double max_val = array[0];
for(int i = 1; i < array.length; i++){
if(array[i] > max_val){
max_val = array[i];
}
}
return max_val;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int amount = scanner.nextInt();
double[] array = new double[amount];
for(int i = 0; i < amount; i++){
array[i] = scanner.nextDouble();
}
double max_val = max(array); //这组数最大值
double min_val = min(array); //这组数最小值
Drawer[] drawer = new Drawer[amount-1]; //创建amount-1个抽屉
//初始化抽屉,为了后面遍历,给抽屉最小值赋值为数组最大值,给抽屉最大值赋值为数组最小值
for(int i = 0; i < amount-1; i++){
drawer[i] = new Drawer(max_val, min_val, 0);
}
for(int i = 0; i < amount; i++){
//计算平均距离得到抽屉号
int drawer_id = (int)((amount - 1) * (array[i] - min_val) / (max_val - min_val));
//如果数组最大值那么就放在最后一个抽屉
if(drawer_id == amount - 1){drawer_id = amount - 2;}
drawer[drawer_id].count++;
if(array[i] < drawer[drawer_id].low){drawer[drawer_id].low = array[i];}
if(array[i] > drawer[drawer_id].high){drawer[drawer_id].high = array[i];}
}
//遍历,用下一个抽屉的小值减去上一个抽屉的最大值得到间隙,保存最大间隙
double max_gap = 0;
double left = drawer[0].high;
for(int i = 1; i < amount - 1; i++){
if(drawer[i].count != 0){
double current_gap = drawer[i].low - left;
if(current_gap > max_gap){max_gap = current_gap;}
left = drawer[i].high;
}
}
System.out.println(max_gap);
}
}