当前位置: 首页 > news >正文

(算法设计与分析)第一章算法概述-习题

文章目录

  • 一:算法分析题
  • 二:算法实现题
    • (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);
    }
}

在这里插入图片描述

相关文章:

  • C生万物 | 第一篇 —— 初识C语言【适合入门,建议收藏】
  • 多线程同步-条件变量
  • FPGA项目开发之同步信号和亚稳态
  • 【机器学习】Linear Regression Experiment 线性回归实验 + Python代码实现
  • 【数据结构 C语言版】第四篇 栈、堆栈、Stack(超级详细版)
  • Django(3):数据模型定义
  • Linux系统编程·进程概念引入
  • 对抗生成网络GAN系列——CycleGAN简介及图片春冬变换案例
  • 第二课 ceph基础学习-OSD扩容换盘和集群运维
  • 帮助命令---学习Linux命令的第一步
  • C++ - 文件读写(fstream)
  • JavaScript:二维码生成与解析
  • SpringBoot 2 配置文件 2.4 多环境配置
  • JavaWeb编年史(远古时期)
  • 【Spring】面向切面编程详解(AOP)
  • 收藏网友的 源程序下载网
  • android图片蒙层
  • ES6之路之模块详解
  • Fundebug计费标准解释:事件数是如何定义的?
  • MySQL主从复制读写分离及奇怪的问题
  • PyCharm搭建GO开发环境(GO语言学习第1课)
  • Spring Cloud Feign的两种使用姿势
  • vue从创建到完整的饿了么(11)组件的使用(svg图标及watch的简单使用)
  • Vue组件定义
  • 翻译 | 老司机带你秒懂内存管理 - 第一部(共三部)
  • 服务器之间,相同帐号,实现免密钥登录
  • 高度不固定时垂直居中
  • 工程优化暨babel升级小记
  • 老板让我十分钟上手nx-admin
  • 马上搞懂 GeoJSON
  • 面试题:给你个id,去拿到name,多叉树遍历
  • 让你的分享飞起来——极光推出社会化分享组件
  • 容器服务kubernetes弹性伸缩高级用法
  • 使用Maven插件构建SpringBoot项目,生成Docker镜像push到DockerHub上
  • 一道面试题引发的“血案”
  • 阿里云ACE认证学习知识点梳理
  • 阿里云IoT边缘计算助力企业零改造实现远程运维 ...
  • ​ubuntu下安装kvm虚拟机
  • ​卜东波研究员:高观点下的少儿计算思维
  • #define、const、typedef的差别
  • #我与Java虚拟机的故事#连载11: JVM学习之路
  • (8)Linux使用C语言读取proc/stat等cpu使用数据
  • (libusb) usb口自动刷新
  • (力扣)1314.矩阵区域和
  • (力扣记录)1448. 统计二叉树中好节点的数目
  • (三维重建学习)已有位姿放入colmap和3D Gaussian Splatting训练
  • (转)http协议
  • (转载)CentOS查看系统信息|CentOS查看命令
  • (转载)OpenStack Hacker养成指南
  • .net 设置默认首页
  • .net6Api后台+uniapp导出Excel
  • .Net的C#语言取月份数值对应的MonthName值
  • .NET开发人员必知的八个网站
  • .NET下ASPX编程的几个小问题
  • .net下简单快捷的数值高低位切换