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

Source

目录

进入算法世界

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快读

快读代码

inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}



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.算法分析:

      利用枚举法解决该问题,以三种鸡的个数为枚举对象,分别设为ijk,用三种鸡的总数 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) 等等。

                                                       算法篇下篇继续!