• 【基础算法Ⅰ】算法入门篇

    目录

    进入算法世界

    1.输入输出

    1.1输入输出

    1.2快读

    2.位运算

    2.1运算符

    2.2位运算

    3.枚举

    3.1枚举的引入

    3.2枚举的简单理解

    3.3枚举简介

    3.4 枚举算法实例

    算法复杂度

    时间复杂度

    进入算法世界

      瑞士著名的科学家Niklaus Wirth教授曾提出：数据结构+算法=程序。数据结构是程序的骨架，算法是程序的灵魂

     算法是对特定问题求解步骤的一种描述。它不依赖于任何一种语言，既可以用自然语言、程序设计语言描述，也可以用流程图、框图来表示。

     算法的特性

       ■ 有穷性：算法是由若干条指令组成的有穷序列，总是在执行若干次后结束，不可能永不停止。

      ■ 确定性：每条语句都有确定的含义、无歧义。

        ■可行性：算法在当前环境条件下可以通过有限次运算来实现。

        ■ 输入/输出：有零个或多个输入以及一个或多个输出。

    如何衡量一个算法的好坏？

                     高效率、低存储

                      1. 准确性    2.易读性 3.健壮性 4.高效性 5.低存储性

    1.输入输出

    1.1输入输出

    输入输出方法

    ■  C/C++ ，格式化输入输出： scanf,printf 。速度快，格式容易控制。
    ■  C++输入输出流： cin ， cout 。速度慢，使用简单，自动识别类型。
    ■  快读： 用 getchar 达到快速读入，其实也简单。

    输入输出的选择

    ■  数据量大： 建议选择 scanf 或者快读，防止 TLE 。
    ■  数据量小 ：可以按照喜欢的来。

    1.2快读

    快读代码

    1. inline int read()
    2. {
    3.     int x=0,f=1;
    4.     char ch=getchar();
    5.     while(ch<'0'||ch>'9'){
    6.         if(ch=='-') f=-1;
    7.         ch=getchar();
    8.     }
    9.     while(ch>='0'&&ch<='9'){
    10.         x=(x<<1)+(x<<3)+(ch^48);
    11.         ch=getchar();
    12.     }
    13.     return x*f;
    14. }
    15.  
    16.  
    17.

    2.位运算

    2.1运算符

    运算符简介

    ■  运算符是什么： 运算符是一种告诉编译器执行特定的数学或逻辑操作的符号。
    ■   运算符有哪些： C 语言内置了丰富的运算符，并提供了以下类型的运算符：

      算术运算符，关系运算符，逻辑运算符，位运算符，赋值运算符，杂项运算符。

    重要运算符

    ■  算术运算符： + ， - ， * ， / ， % ， ++ ， -- 。
    ■  关系运算符 ： == ， != ， > ， < ， >= ， <= 。
    ■  逻辑运算符： && ， || ， ! 。
    ■  位运算符： & ， | ， ^ ， ~ ， << ， >> 。

    2.2位运算

    位运算简介

    ■  位运算有啥用： 位运算符作用于位，并逐位执行操作。
    ■  位运算具体讲解： 下表显示了 C /C++ 支持的位运算符 。

      假设变量 A 的值为 60，变量 B 的值为 13。

    运算符描述实例

    &

    按位与运算符，按二进制位进行"与"运算。运算规则：0&0=0;  

    0&1=0;   

    1&0=0;    

    1&1=1;

    (A & B) 将得到 12

    即为 0000 1100

    |

    按位异或运算符，按二进制位进行"异或"运算。运算规则：

    0^0=0;  

    0^1=1;  

    1^0=1; 

    1^1=0;

    (A ^ B) 将得到 49,即为 0011 0001

    ^

    按位异或运算符，按二进制位进行"异或"运算。运算规则：

    0^0=0;  

    0^1=1;  

    1^0=1; 

    1^1=0;

    (A ^ B) 将得到 49,即为 0011 0001

    ~

    ~

    		(~A ) 将得到 -61,即为 1100 0011，一个有符号二进制数的补码形式

    <<

    二进制左移运算符。将一个运算对象的各二进制位全部左移若干位（左边的二进制位丢弃，右边补0）。

    A << 2 将得到 240，即为 1111 0000

    >>

    二进制右移运算符。将一个数的各二进制位全部右移若干位，正数左补0，负数左补1，右边丢弃。

     A>> 2 将得到 15，即为 0000 1111

    3.枚举

     

    3.1枚举的引入

         

    如果让你去开一扇门，从别人那拿到了一串若干把钥匙，你该怎么办呢？

    3.2枚举的简单理解

    1、拿出第一把钥匙                                                               1、验证第一把钥匙能否开门

    2、拿出第二把钥匙                                                                2、验证第二把钥匙能否开门

    3、拿出第三把钥匙                                                                 3、验证第三把钥匙能否开门

    .

    N、拿出第N把钥匙                                                                    N、验证第N把钥匙能否开门            

     列举                                                                                                                                          验证

    3.3枚举简介

    什么是枚举

    ■   枚举是什么： 枚举是基于已有知识来猜测答案的一种问题求解策略。
    ■    枚举的思想： 枚举的思想是不断地猜测，从可能的集合中一一尝试，然后再判断题目的条件是否成立。
    枚举的要点
    ■  给出解空间： 建立简洁的数学模型。

      枚举的时候要想清楚：可能的情况是什么？要枚举哪些要素？

    ■  减少枚举的空间： 枚举的范围是什么？是所有的内容都需要枚举吗？

      在用枚举法解决问题的时候，一定要想清楚这两件事，否则会带来不必要的时间开销。

    ■  选择合适的枚举顺序： 根据题目判断。

      比如例题中要求的是最大的符合条件的素数，那自然是从大到小枚举比较合适。 

    3.4 枚举算法实例

    例一：百钱买白鸡

    1.问题描述：

          公鸡每只5元，母鸡每只3元，三只小鸡1元，用100元买100只鸡，问公鸡、母鸡、小鸡各多少只？

    2.算法分析：

          利用枚举法解决该问题，以三种鸡的个数为枚举对象,分别设为i，j和k，用三种鸡的总数（ i+j+k=100）和买鸡钱的总数（1/3*i+3*j+5*k=100）作为判定条件，枚举各种鸡的个数。直到找到正确的答案

    例一代码简易实现：

     例二：骰子的游戏

    1.问题描述：

          在Alice和Bob面前的是两个骰子，上面分别写了六个数字。

        Alice和Bob轮流丢掷骰子，Alice选择第一个骰子，而Bob选择第二个，如果谁投掷出的数更大，谁就可以获胜。

        现在给定这两个骰子上的6个数字，你需要回答是Alice获胜几率更大，还是Bob获胜几率更大。（请注意获胜几率相同的情况）。

    2.算法分析：

          先枚举Alice的骰子的数字，再枚举Bob的骰子的数字。比较大小，然后统计谁获胜的情况多，也就表明谁获胜的几率更大。

    例二代码简易实现：

    算法复杂度

    好，学了枚举算法。                 

    是不是所有问题都可以用枚举解决呢？

      NO！

    同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。

          算法分析的目的在于选择合适算法和改进算法。

    这就要引入算法复杂度的概念

    算法复杂度分为时间复杂度和空间复杂度。

    时间复杂度是指执行算法所需要的计算工作量，

    而空间复杂度是指执行这个算法所需要的内存空间。

    算法复杂度中，主要考虑时间复杂度，当然这不是说空间复杂度不重要。

    在讲时间复杂度之前，先再引入一个概念，基本操作数。

    基本操作数

    ■  同一个算法在不同的计算机上运行的速度会有一定的差别，并且实际运行速度难以在理论上进行计算，实际去测量又比较麻烦，所以我们通常考虑的不是算法运行的实际用时，而是算法运行所需要进行的基本操作的数量。
    ■  在普通的计算机上，加减乘除、访问变量（基本数据类型的变量，下同）、给变量赋值等都可以看作基本操作。
    ■  对基本操作的计数或是估测可以作为评判算法用时的指标。 

    时间复杂度

    时间复杂度

    ■  时间复杂度定义： 在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。
    ■  时间复杂度的作用： 衡量一个算法的快慢，一定要考虑数据规模的大小。所谓数据规模，一般指输入的数字个数、输入中给出的图的点数与边数等等。一般来说，数据规模越大，算法的用时就越长。而在算法竞赛中，我们衡量一个算法的效率时，最重要的不是看它在某个数据规模下的用时，而是看它的用时随数据规模而增长的趋势，即时间复杂度。
    ■  时间复杂度的表示： 一般情况下，算法竞赛只会用到大 O ，也就是最差复杂度。例如 O(n),O(n 2 ) 和 O(nlogn) 等等。

                                                           算法篇下篇继续！

  • 相关阅读:
    OpenCV 07(图像滤波器)
    【智慧工地源码】基于AI视觉技术赋能智慧工地
    C++多线程学习06 利用RAII
    Linux系统搭建DataEase并结合内网穿透实现任意设备公网查看本地数据
    《算法导论》学习（十四）----散列表（哈希表）（C语言）
    Java中transient关键字的详细总结
    浅析ARMv8体系结构：异常处理机制
    CRUD-SQL
    【CentOS 7】CentOS 7极致指南：高级部署PyCharm 2022.3.3专业版，实现定制化配置与无缝桌面集成
    IPFoxy：什么是数据中心代理IP？好用吗？
  • 原文地址：https://blog.csdn.net/weixin_72686492/article/details/128034376