第十二章：算法与程序设计

文章目录：

一：基本概念

1.算法与程序

1.1 算法 

1.2 程序

2.编译预处理

3.面向对象技术

4.程序设计方法

5.SOP标志作业流程

6.工具

6.1 自然语言

6.2 流程图

6.3 N/S图

6.4 伪代码

6.5 计算机语言

二：程序设计 基础

1.常数

2.变量

3.运算符

4.表达式

5.函数

6.循环

6.1 顺序结构

6.2 选择结构

6.3 循环结构

6.3.1 当型和直到型 

6.3.2 循环四要素

6.3.3 循环的分析

三：程序设计 算法

1.数值

1.1 迭代

1.2 数论

1.2.1 取数

1.2.2 进制转换

1.2.3 素数

2.非数值

2.1 枚举

2.2 数组

2.2.1 基础

2.2.2 CEUD

2.2.3 进阶

2.3 字符串

3.优化

3.1 算法的性能

3.2 算法的优化

可参考：VB(Visual Basic)程序设计教案、C编程语言、C++程序设计教案、Python程序设计教案、Java编程语言、数据结构

一：基本概念

1.算法与程序

1.1 算法 

算法的基本概念
    概念
        算法就是解决问题的⽅法和步骤，解决问题的过程就是算法实现的过程
        在数学中，算法（Algorithm）通常是指按照⼀定规则解决某⼀类问题的明确和有限的步骤
        算法是解决⼀类问题的⽅法，可以理解为由基本运算及规定的运算符顺序所构成的完整和有限的解题步骤
    分类
        根据处理的数据是数值数据还是⾮数值数据，可以分为数值计算算法和⾮数值计算算法两⼤类
        数值计算算法⽤于科学计算，其特点是少量的输⼊、输出，复杂的运算，例如求⾼次⽅程的近似根、求函数的定积分、求圆周率等
        ⾮数值计算算法⽤于数据管理，其特点是⼤量的输⼊、输出，简单的算术运算和⼤量的逻辑运算，例如对数据的排序、查找等算法
    说明
        算法决定程序，是程序设计的核⼼
        算法通常⽤于解决⼀类问题而不是专⻔针对某⼀个具体的问题
        ⼀种问题通常有很多种不同的解决办法（算法），采⽤不同的算法效率不同


算法的两⼤要素
    操作：包括算术运算、关系运算、逻辑运算等运算符，以及⽤于实现数据传送的操作，包括输⼊、输出、赋值等
    结构：即控制结构，包括顺序结构、选择结构和循环结构三种基本结构


算法的五⼤特性：著名计算机科学家Donald E.Knuth把算法的性质归纳为5点
    有穷性 ⼜叫有限性，即算法在执⾏有穷个计算步骤后必须终⽌
    确定性 ⼜叫⽆⼆义性，即每⼀个计算步骤必须是精确地定义，要执⾏的每⼀个动作都是清晰的、⽆歧义的
    可⾏性 ⼜叫能⾏性，即算法中的运算都是基本运算，原则上可以由⼈们⽤纸和笔在有限的、合理的时间内精确地完成
    输⼊ ⼀个算法有0个或多个输⼊，作为算法开始执⾏前的初始值，或初始状态
    输出 ⼀个算法有1个或多个输出，即算法必须有输出

1.2 程序

程序的基本概念
    ①程序是计算机为完成某⼀任务所必须执⾏的⼀系列指令的集合
     包含⼤量重复性的、事务性的操作的任务适合编程解决，创造性的任务不适合编程解决
     计算机系统能完成各种⼯作的核⼼是程序，而程序的核⼼是算法，编写程序的过程称为程序设计，设计算法是程序设计的关键
    ②⼀个程序包含两⽅⾯的内容：对数据的描述和对操作的描述
     著名计算机科学家沃思（Nikiklaus Wirth）提出的经典公式：程序 = 数据结构 + 算法
     数据结构指定待处理数据的数据类型和数组的组织形式，算法描述对数据进⾏操作的⽅法和步骤
    ③⼀个完整的程序除了以上两个必备要素之外，还应当采⽤⼀定的程序设计⽅法进⾏设计，并⽤某种计算机语⾔来表⽰
     因此，也可表述为：程序 = 数据结构 + 算法 + 程序设计⽅法 + 语⾔⼯具和环境


程序设计的流程
    步骤
        分析问题
            在开始解决问题之初，⾸先要弄清楚所求解问题相关领域的基本知识
            分析题意，搞清楚问题的含义，要解决的问题的⽬标，问题的已知条件、已知数据以及应该得到什么样的结果
        数学建模 建⽴计算机可实现的计算模型，也就是把实际问题转化为数学问题，直到得到求解问题的公式
        算法设计 算法是求解问题的⽅法和步骤，算法设计即设计从给定的输⼊到期望的输出的处理步骤
        编写程序 选择某种程序设计语⾔，按照设计的算法和选择的语⾔的语法规则编写程序
        测试运⾏
            设计测试数据（测试⽤例），尽可能多地找出程序中的错误
            测试以程序通过编译，没有语法上的错误为前提
    说明
        ①算机求解问题的过程可以⼤致分成两步：抽象和⾃动化
         在计算机科学中，抽象是简化复杂的现实问题的最佳途径，包含形式化和数学建模两个要素
         形式化是指采⽤严格的数学语⾔描述清楚问题的条件、⽬标以及达到⽬标的过程的数学⽅法
         数学建模是以数学的⽅法来求解问题和描述系统⾏为的⼀种形式化⽅法
         计算机通过程序实现⾃动化，程序的核⼼是算法，⾃动化分两步：设计算法和编写程序
        ②问题的复杂程度决定了程序的复杂程度
         分析问题时，⼀般需要和提出问题的⼈进⾏讨论，搞清楚程序的功能，这个过程称为需求分析
        ③如果时间紧迫，可以选择开发效率⾼或⾃⼰熟悉的语⾔，例如Visual Basic语⾔
         如果要求在多种平台上使⽤，可以选择移植性好的语⾔，例如Java语⾔
         如果对程序响应要求⾼，可与选择运⾏效率⾼的语⾔，例如C语⾔
        ④证明程序的正确性是极为困难的，⽐较实⽤的⽅法就是测试
         测试的⽬的是找出错误，调试的⽬的是解决错误

2.编译预处理

概念：编译预处理即在编译之前对源程序进⾏的处理，源程序 → [预处理] → [编译] → ⽬标代码


包括
    ⽂件包含 在⼀个源⽂件中插⼊另⼀个源⽂件的全部内容，例如“#include <stdio.h>”
    常量替换 ⼜叫宏定义，即将程序中所有宏名替换成宏定义（#define）中的内容
    条件编译 在编译前，按照条件筛选出源程序中的部分代码，再进⾏编译

3.面向对象技术

对象
    概念
        对象是类的实例化
        对象是现实世界中可以独⽴存在、可以区分的实体，也可以是⼀些概念上的实体
        对象可以⽤对象名、属性和⽅法来描述
    描述
        对象名：每个对象区别于其它对象的名字，具有唯⼀性
        属性：⽤⼀组状态（属性值）来描述的对象的静态特征，即对象拥有的数据
        ⽅法：对属性的各种操作，每⼀个操作决定对象的⼀种功能或⾏为


消息
    消息是对象之间相互请求和相互协作的⼿段，是激活某个对象执⾏其中某个功能的“源”
    对象之间的相互作⽤通过消息传递来实现，即对象之间的联系是通过消息传递的


事件
    事件就是⼀些能够激活对象功能的动作，不同的事件往往引发对象不同的动作
    ⽤⼾按键、移动⿏标、单击⿏标、打开⽂件、关闭⽂件等都是发⽣在计算机上的事件
    事件驱动
        在传统的⾯向过程的应⽤程序中，程序执⾏的先后次序由设计⼈员编写的代码决定，⽤⼾⽆法改变程序的执⾏流程
        在⾯向对象的程序设计中，程序是由若⼲个规模较小的事件过程组成，特定事件的发⽣将引发对象执⾏相应的事件过程
        程序的执⾏由事件的发⽣驱动，编写好的⼀段程序并不总是能够被执⾏，只有当对应的某⼀事件发⽣才执⾏这段程序


特征
    封装
        将对象的属性和⽅法封装成⼀个整体，使对数据的操作只可通过该对象本⾝的⽅法来进⾏
        封装是⼀种信息隐蔽技术，A对象不能直接操作B对象的数据，只能通过B对象提供的⽅法来实现
    继承
        使⽤已存在的类作为基础建⽴新类的技术，新的类可以增加新的属性或新的⽅法，也可以直接使⽤⽗类的属性和⽅法
        继承是⼀种代码复⽤技术
    多态
        同⼀消息被不同对象接收时，可以解释为不同的含义
        即相同的操作可作⽤于多种类型的对象，并能获得不同的结果

4.程序设计方法

概念
    ⽬前最常⽤的是结构化程序设计⽅法和⾯向对象的程序设计⽅法
    程序设计的⽅法在很⼤程度上影响到程序设计的成败和程序的质量
    程序的可靠性（鲁棒性）、易读性、⾼效性和可维护性是衡量程序质量的重要特性


结构化程序设计
    概念
        结构化程序设计的概念最早由荷兰科学家E.W.Dijkstra提出
        在软件设计和实现过程中，提倡采⽤“⾃顶向下、逐步细化”的模块化程序设计原则
        在代码编写时，强调采⽤单⼊口、单出口的3种基本控制结构，避免使⽤goto语句
    优点
        结构简单清晰，可读性好，模块化强，符合⼈们解决复杂问题的普遍规律
        在软件重⽤性、软件维护等⽅⾯有所进步，可以显著提⾼软件开发的效率
        在应⽤程序的开发种发挥了重要作⽤
    缺点
        难以适应⼤型软件的设计，程序和数据分开存储，在开发中容易出错，难以维护
        程序可重⽤性差，即使⾯对⽼问题，数据类型的变化或处理⽅法的改变都将导致重新设计


⾯向对象程序设计
    概念
        20世纪80年代时提出，以满⾜现代化软件开发的要求
        ⽤⾯向对象的⽅法解决问题，不再将问题分解为过程，而是将问题分解为对象
        ⽬前，“对象+消息”的⾯向对象的程序设计模式有取代“数据结构+算法”的⾯向过程的设计模式的趋向
    过程
        ⾯向对象分析(OOA)
            Object Oriented Analyzing，是⼀种软件开发过程分析的⽅法学
            把软件开发过程中的每⼀样东西都想象成类，OOA主要关⼼怎样导出系统需要的类
        ⾯向对象设计(OOD) 
            Object Oriented Designing，该阶段的焦点是OOA阶段确定的类如何实现功能的问题
        ⾯向对象实现(OOP)
            Object Oriented Programming，即采⽤某种⾯向对象语⾔具体实现OOD的设计
            常⽤的⾯向对象的程序设计语⾔有C++/C#、Java、Visual Basic、Python等
    说明
        ⾯向对象的程序设计并不是要抛弃结构化程序设计⽅法，而是站在更⾼、更抽象的层次上解决问题
        当所要解决的问题被分解为低级代码模块时，仍需要结构化编程的⽅法和技巧
        ⾯向对象程序设计分解⼤问题为小问题时采取的思路于结构化⽅法不同
    区别
        结构化的分解突出过程，强调代码的功能是如何得以完成
        ⾯向对象的分解突出真实世界和抽象的对象，涉及哪个对象的功能，便由哪个对象⾃⼰去处理
        不同对象之间通过消息或事件发⽣联系，对象依据接收到的消息或事件进⾏⼯作
    优点
        符合⼈们习惯的思维⽅法，便于分析复杂而多变化的问题
        易于软件的维护和功能的增减
        可重⽤性好，能⽤继承的⽅式尖端程序开发所⽤的时间
        与可视化技术相结合，改善了⼯作界⾯

5.SOP标志作业流程

画流程图 代码生成流程图 流程图自动运行 

Standard Operating Procedure，SOP，标准作业流程

程序设计有⼀个标准化的流程，按照⽼唐总结的流程，可以确保每⼀位考⽣都能写出程序，⾄少能搭建起程序的基本框架

6.工具

算法的表⽰⽅法有很多，常⽤的有⾃然语⾔、程序流程图、N/S图、伪代码和计算机程序设计语⾔等

6.1 自然语言

⽤⼈们使⽤的语⾔，即⾃然语⾔来描述算法通俗易懂，但存在如下缺陷
    ① 易产⽣歧义，即存在⼆义性，往往需要根据上下⽂才能确切判别含义，不太严格
    ② 语句⽐较繁琐、冗⻓，并且很难清楚地表达算法的逻辑流程，尤其对描述含有选择和循环结构的算法时，不太⽅便和直观

6.2 流程图

流程图是描述算法的常⽤⼯具，采⽤⼀些图框、线条以及⽂字说明来形象、直观地描述算法处理过程

6.3 N/S图

N/S图是⼀种简化的流程图，去掉了流程图中的流程线，全部算法写在⼀个矩形框内

N/S图表⽰算法直观、形象，且⽐流程图紧凑易画，实际应⽤中也经常采⽤

6.4 伪代码

由于绘制流程图较为费时，⾃然语⾔易产⽣歧义和难以清楚表达算法的逻辑流程等缺陷，可以选择使⽤伪代码描述算法


伪代码（Pseudo-Code）使⽤介于⾃然语⾔和计算机程序设计语⾔之间的⽂字和符号来描述算法，有如下简单约定


伪代码中的约定
    ① 每个算法⽤begin开始，以end结束，若仅表⽰部分实现代码可省略
    ② 每⼀条指令占⼀⾏，指令后不跟任何符号
    ③ “//”标志表⽰注释的开始，⼀直到⾏尾
    ④ 算法的输⼊输出以“input/print”后加参数表的形式表⽰
    ⑤ ⽤“←”表⽰赋值
    ⑥ ⽤缩进表⽰代码块结构，包括while和for循环、if分⽀判断等，块中多条语句⽤⼀对“{}”括起来
    ⑦ 数组形式为“数组名[下界...上界]”，数组元素为“数组名[序号]”
    ⑧ ⼀些函数调⽤或者处理简单任务可以⽤⼀句⾃然语⾔代替    

6.5 计算机语言

计算机⽆法识别⾃然语⾔、流程图、伪代码，这些⽅法仅为了帮助⼈们描述、理解算法

只有⽤计算机语⾔编写的程序才能被计算机执⾏（当然还要被编译成⽬标程序）

⽤计算机语⾔描述算法必须严格遵循所选择的编程语⾔的语法规则

二：程序设计 基础

1.常数

概念：程序运⾏的过程中，其值保持不变的数据


数值型：可以进⾏算术运算的数字，例如3.14、1、-3、...


字符型：⼜称为字符串，由英⽂字符、中⽂字符和数字字符组成
    ① 字符串⼀般使⽤⼀对双引号括起来，单个字符可以使⽤⼀对单引号
    ② 字符的个数 ⼜称为字符串的⻓度，即字符串中包含的字符的个数
      字符的位置 从左⾄右，依次编号为1、2、3、...


逻辑型
    ⼆元逻辑，即只有true（逻辑真）和false（逻辑假）两个值
    关系成⽴返回逻辑真，关系不成⽴返回逻辑假

2.变量

概念：程序运⾏的过程中，其值可以改变的数据


说明
    ① 在程序中，变量 = 可存放数据的容器
    ② 变量只能保存⼀个数据，后存⼊的数据会替换现有的数据
      变量当前保存的数据的类型决定变量的数据类型
    ③ 变量必须初始化，即变量必须先写后读


操作
    写：把⼀个数保存到变量中，赋值语句中赋值符号左边的变量和输⼊语句中的变量是在执⾏写操作
    读：读出变量当前的值，程序中出现的变量不是在执⾏写操作就⼀定是在执⾏读操作

3.运算符

概念
    运算符是完成数据处理的最基本单位
    不同类型的数据，使⽤不同类型的运算符进⾏处理
    除了not是单⽬运算符之外，其它所有的运算符都是双⽬运算符


分类
    数值运算符
        +(加)、-(减)、*(乘)、/(除)、^(乘⽅)、%(取余)
        数值运算符⽤于处理数字型的数据，处理的结果也是数值型
    字符运算符
        +(连接)，相当于Excel或Access中“&”运算符的功能
        字符运算符⽤于处理字符型的数据（⾄少其中⼀个是字符型），处理的结果也是字符型
    关系运算符
        <(小于)、<=(小于等于)、=(等于)、!=(不等于)、>=(⼤于等于)、>(⼤于)
        关系运算符两端的数据类型必须相同，处理的结果是逻辑型，逻辑真表⽰关系成⽴，逻辑假表⽰关系不成⽴
    逻辑运算符
        not(⾮)、and(与)、or(或)
        逻辑运算符⽤于处理逻辑型的数据，处理的结果也是逻辑型

4.表达式

概念：表达式是由数据、运算符和函数组成的⼀个整体，它是程序中完成数据转换的表达⽅式


分析：分析表达式的关键是理解运算符的优先级和结合性
    优先级：数值运算符 > 字符运算符 > 关系运算符 > 逻辑运算符
        数值运算符中，乘⽅(^)的优先级最⾼，其次是乘(*)、除(/)、求余(%)，最后是加(+)和减(-)
        所有的关系运算符的优先级都相同
        逻辑运算符中，逻辑⾮(not)的优先级最⾼，其次是逻辑与(and)，最后是逻辑或(or)
    结合性：当运算符的优先级相同时，决定运算的先后次序的就是结合性
        右结合 单⽬运算符(not)是右结合，即从右⾄左依次运算，例如not not true = not (not true) = not false = true
        左结合 所有的双⽬运算符都是左结合，即从左⾄右依次运算，例如4/2*3 = (4/2)*3 = 6


常见
    奇偶性     x%2=0 如果返回true，表⽰x是偶数，否则表⽰x是奇数
    整除       x%y=0 如果返回true，表⽰x能被y整除，否则表⽰x不能被y整除
    整数判定    x=floor(x) 如果返回true，表⽰x是整数，否则表⽰x不是整数
    区间
        x>a and x<b   如果返回true，表⽰x∈(a,b)区间，否则表⽰x不在(a,b)区间内
        x>=a and x<b  如果返回true，表⽰x∈[a,b)区间，否则表⽰x不在[a,b)区间内
        x>a and x<=b  如果返回true，表⽰x∈(a,b]区间，否则表⽰x不在(a,b]区间内
        x>=a and x<=b 如果返回true，表⽰x∈[a,b]区间，否则表⽰x不在[a,b]区间内
    否定
        原则：需要表⽰“否定”逻辑时，最好先表达“肯定”的逻辑，然后使⽤not运算符否定整体
        例如
            x能被a和b同时整除 x%a=0 and x%b=0
            x不能被a和b同时整除 not (x%a=0 and x%b=0)

5.函数

概念
    函数是⼀个独⽴的功能模块，与运算符⼀样，⽤于完成数据处理
    伪代码中并未限定可以使⽤的函数的功能和类型，⼀般情况下，这⾥介绍的函数可以直接使⽤


说明
    函数调⽤的⼀般格式为：函数名(参数1, 参数2, ..., 参数n)
    函数的功能，就是把输⼊数据（参数）转换成对应的输出数据（返回值）


常⽤
    数值函数
        下取整函数 floor(x) 返回x的整数部分，例如floor(3.999)的结果为3
        绝对值函数 abs(x) 返回x的绝对值，例如abs(-1)的结果为1
        平⽅根函数 sqrt(x) 返回x的平⽅根，例如sqrt(4)的结果为2
        最⼤值函数 max(x,y) 返回x和y中⼤的那个
        最小值函数 min(x,y) 返回x和y中小的那个
    字符函数
        字符串⻓度 length_of(x) 返回字符串x的⻓度，即字符串x中包含的字符的个数，数值型
        ASCII码
            to_ascii(x) 返回单个字符x对应的ASCII码值，数值型
            to_character(x) 返回数值x对应的ASCII码字符，x的值在0~255之间，字符型

6.循环

结构化程序设计的概念最早由荷兰科学家E.W.Dijkstra提出

任何程序都可由三种基本结构，即顺序、选择和循环结构组成，程序具有模块化特征，每个程序模块具有唯⼀的⼊口和出口

6.1 顺序结构

概念：顺序结构是最简单、最常⽤的⼀种结构，计算机按照语句出现的先后次序依次执⾏


赋值语句 x ← 表达式：先计算赋值号(←)右边表达式的值，然后将其保存到赋值号左边的变量中
    ⾃增 x ← x + 1 先读出x的值，加1后，写回到x
    交换
        ① t ← x
        ② x ← y
        ③ y ← t


输⼊语句 input x, y, ...
    运⾏时，⽤⼾输⼊⼀组数据，依次保存到变量x、y、... 中
    输⼊与赋值都可以完成对变量的写操作，使⽤输⼊语句可以由⽤⼾在程序运⾏时决定变量的值


输出语句 print x, y, ...
    运⾏时，依次将变量x、y、... 中保存的值输出到屏幕上
    ⼀个完整的程序必须包含输出语句，⾄少有⼀个输出

6.2 选择结构

概念：根据判定的结果（条件成⽴或不成⽴），选择其中⼀条分⽀执⾏，因此⼜称为分⽀结构


包括：单分⽀、双分⽀、多分⽀

6.3 循环结构

6.3.1 当型和直到型 

 

概念：计算机与⼈处理问题最⼤的特点，是计算机可以永不疲劳地重复算法所设计的操作，这通过循环结构来实现


包括：当型、直到型

6.3.2 循环四要素

6.3.3 循环的分析

说明：分析程序的关键就是分析循环，读懂了循环也就读懂了程序


⽅法
    ① 始于变量终于变量，即分析循环时，重点在搞清楚变量的值的每⼀步的变化过程
    ② 从特殊到⼀般，通过观察变量值的变化，总结出变量值的⼀般性的变化规律
    ③ ⼀定要分析“最后⼀次满⾜循环条件”时，循环的执⾏过程
    ④ 对于⼆重循环，固定外层循环变量的值，可以化⼆重循环为单循环

三：程序设计 算法

1.数值

1.1 迭代

概念：迭代法⼜称递推法，是利⽤问题本⾝所具有的某种递推关系求解问题的⼀种⽅法
    ① 从初值出发，归纳出新值与旧值间直到最后值为⽌存在的关系
    ② 从而把⼀个复杂的计算过程转化为简单过程的多次重复，每次重复都从旧值的基础上递推出新值，并由新值替代旧值


计数
    说明：记录在循环的过程中，某个条件满⾜的次数
    ⽅法
        ① 在循环开始前，把某个变量的初始值赋值为0，例如“c←0”
        ② 在循环体中，满⾜条件时，让c的值⾃增1，例如“c←c+1”


求和
    说明：⼜称累加和，即n项求和
    分类
        ① n已知，求s 例如，s=1+2+3+...+n，当n=100时，求s
        ② n未知，求s 例如，s=1+1/2+1/3+...+1/n，直到最后⼀项小于0.003为⽌，求s
        ③ s已知，求n 例如，s=1+2+3+...+n，当s等于300时，求n
    ⽅法
        ① 初始化：循环开始前，把某个变量的初始值赋值为0，例如“s←0”
        ② 找通项：所谓通项就是能代表累加和中每⼀项的表达式
            s=1+2+3+...+n，通项为i，i∈[1,n]
            s=1+1/2+1/3+...+1/n，通项为1/i，i∈[1,n]
            s=x+x^2/2+x^3/3+...+x^n/n，通项为x^i/i，i∈[1,n]
        ③ 迭代 在循环体中，执⾏“s←s+通项”
        ④ 常数项：单独处理常数项，⼀般可以把常数项作为s的初始值，即“s←常数项”
            s=1+1+2+3+...+n，通项为i，i∈[1,n]，第⼀个1为常数项
            此时，在循环开始前，可以把s的初始值赋值为1，即“s←1”


累乘：⼜称累乘积，即n项求积，例如求k的阶乘：k!=1*2*3*...*k
    与“求和”的⽅法相似，两点区别
        ① 初始化时，把某个变量的初始值赋值为1，例如“k←1”
        ② 在循环体中，执⾏“k←k*通项”


数列
    概念：⼀组有规律变化的数据
    常⻅
        等差数列 形如“1、2、3、...”
        等⽐数列 形如“1、2、4、8、...”
        斐波拉契数列 f(1)=1, f(2)=1, f(n)=f(n-1)+f(n-2)(当n>=3时)
    ⽅法：找出迭代（递推）公式，有必要时可借助数组，以简化迭代关系


其它：包括复息利率、辗转相除、猴⼦摘桃、⾼次⽅程求根等问题

1.2 数论

1.2.1 取数

概念：取出⼀个正整数的每⼀位


公式：floor(n/m)%10
    m=1时，取n的个位数
    m=10时，取n的⼗位数
    m=100时，取n的百位数

1.2.2 进制转换

概念：通常是2、8、10、16进制的整数的相互转换


⽅法
    10→R 除R逆序取余
    R→10 按权展开，乘权求和

1.2.3 素数

概念：素数⼜叫质数，即只能被1和⾃⾝整除的正整数


注意
    1不是素数，2是最小的素数，也是唯⼀的偶素数
    按定义，当n>=3时，不能被2~n-1中的任何⼀个数整除的数就是素数
    事实上，数论学家研究发现，只要n不能被2~sqrt(n)之间的数整除，n就是⼀个素数

2.非数值

2.1 枚举

概念
    枚举法⼜称为穷举法或试凑法，它是⼀种⽐较耗时的算法，需要利⽤计算机快速运算的特点
    实际上，橘⼦分堆、物不知数、韩信点兵、百钱百鸡、素数判定、数组和字符串的遍历等，都是枚举法的应⽤


⽅法
    ① 采⽤搜索的⽅法，根据题⽬的条件确定解的⼤致搜索范围（解空间）
    ② 把解空间内所有可能的情况逐⼀验证，直到所有情况验证完
    ③ 若某个情况符合题⽬的条件，则为本题的⼀个答案；若全部情况验证完后均不符合题⽬的条件，则问题⽆解


说明
    ① 枚举法能有效解决问题的关键在于确定搜索的范围和确定解应该满⾜的条件
    ② 枚举法解决问题效率不⾼，因此，为提⾼效率，根据解决问题的情况，应该尽量减少内循环层数或每层循环的次数
    ③ 对某类特定问题，在规模较小的情况下，枚举法往往是⼀个简单有效的⽅法

2.2 数组

2.2.1 基础

初始化
    概念：数组是⼀组有序的变量，在使⽤前，需要为数组中的每⼀个变量赋初始值，这个操作称为“初始化”
    包括
        数组已知，则可以直接使⽤数组，⽆需进⾏初始化
        数组未知，则在遍历过程中，对数组中的每个变量执⾏输⼊或赋值
        字符串可以理解为⼀个字符数组，题⽬中已知的字符串可以直接当作⼀个字符数组使⽤
    说明
        ①组成数组的变量称为数组中的数据元素
         组成数组的变量的个数称为数组的⻓度或⼤小，记为N
        ②数组中变量的位置称为“下标”
         数组中的每个变量都可以使⽤“数组名[下标]”的⽅式进⾏引⽤
         下标
            如果从0开始，则数组中每个变量的位置可标记为：0、1、2、...、N-1
            如果从1开始，则数组中每个变量的位置可标记为：1、2、3、...、N
        ③可以把字符串理解为⼀个字符数组，下标通常从1开始


遍历
    假设数组a的⻓度为N，所谓“遍历”，即在⼀个循环中，依次访问a[1]~a[N]
    遍历的⽅向可以从左⾄右，也就是从a[1]→a[N](或a[0]→a[N-1])，也可以从右⾄左，即从a[N]→a[1](或a[N-1]→a[0])
    所谓“访问”，即执⾏对变量的“读”或“写”

2.2.2 CEUD

增
    在数组中的指定位置插⼊⼀个变量，插⼊变量后，数组的⻓度加1
    插⼊位置右边的所有变量需要依次向右移动1位


删
    在数组中的指定位置删除⼀个变量，删除变量后，数组的⻓度减1
    删除位置右边的所有变量需要依次向左移动1位


改
    将数组中指定位置的变量的值修改为⽬标值，不影响数组的⻓度
    如果要把数组中的某个值或某些值修改为⽬标值，可以先使⽤“查”，找到对应的值后，再修改
    在遍历数组的过程中，实现数组元素的两两交换，也属于“改”的范畴


查：找到并返回数组中的某个值或某些值在数组中的位置
    顺序查找
        概念：适⽤于“⽆序”数组，查找效率较低，n个数的平均查找次数为(n+1)/2
        ⽅法：从左⾄右或从右⾄左依次遍历数组，将其中的每⼀个值取出与⽬标值⽐较

    ⼆分查找
        概念
            ⼜叫“折半查找”，要求数组有序，即适⽤于“有序”数组
            ⼆分查找是对数据量很⼤时采⽤的⼀种⾼效查找算法，n个数的平均花费为log2(n)
        ⽅法
            ① 已知待查找数组的下界low、上界high，数组升序有序
            ② 当high>=low时，计算中间项mid=(low+high)/2下取整
              若high<low，则说明查找不成功，结束查找
            ③ ⽐较待查找的关键字key与中间项a[mid]，有以下三种情况
                Ⅰ key>a[mid]，则low←mid+1，即右半部分作为继续查找的区域，返回②
                Ⅱ key<a[mid]，则high←mid-1，即前半部分作为继续查找的区域，返回②
                Ⅲ key=a[mid]，则查找成功，结束查找

2.2.3 进阶

统计：统计数组中满⾜条件的对象的个数、和、平均值等


最值
    概念
        找到数组中的最⼤值或最小值（或最⼤值、最小值的位置）
        在数组中，“位置”⽐“值”更重要，知道位置可以直接得到对应的值
    ⽅法：依次⽐较法
        循环开始前，m ← 1
        遍历数组，i∈[2,N]
            如果a[m]<a[i]，m←i m表⽰当前已经⽐较过的i个数中最⼤值的位置
            如果a[m]>a[i]，m←i m表⽰当前已经⽐较过的i个数中最小值的位置
        完成遍历后，m即为数组中最⼤值（最小值）的位置，a[m]是最⼤值（最小值）


排序
    概念
        把⽆序的数据整理成有序数据称为排序，从小到⼤的顺序叫升序，从⼤到小的顺序叫降序
        排序算法有很多，考试中可能涉及到的是选择排序和冒泡排序

    选择排序
        概念：每次在⽆序数中找到最小数（或最⼤数）的位置，然后存放在⽆序数的第⼀个（或最后⼀个）位置
            升序
                每次在⽆序数中找到最小数的位置，然后与⽆序数中第⼀个位置的数交换
                每次在⽆序数中找到最⼤数的位置，然后与⽆序数中最后⼀个位置的数交换
            降序
                每次在⽆序数中找到最小数的位置，然后与⽆序数中最后⼀个位置的数交换
                每次在⽆序数中找到最⼤数的位置，然后与⽆序数中第⼀个位置的数交换
        步骤
            从n个数中找出最小数的下标，⼀轮⽐较结束，最小数与第⼀个数交换位置，通过这⼀轮排序，第1个数已排好
            在余下的n-1个数中再按①中的⽅法选出最小数的下标，最小数与第2个数交换位置
            以此类推，重复步骤②，最后构成递增序列

    冒泡排序
        概念：冒泡排序在每⼀轮排序时将相邻两个数组元素进⾏⽐较，次序不对时⽴即交换位置，⼀轮⽐较结束时小数上浮，⼤数沉底
            升序
                从前往后依次两两⽐较，⼤的后移(如果a[j]>a[j+1]，交换a[j]和a[j+1])
                从后往前依次两两⽐较，小的前移(如果a[j]<a[j-1]，交换a[j]和a[j-1])
            降序
                从前往后依次两两⽐较，小的后移(如果a[j]<a[j+1]，交换a[j]和a[j+1])
                从后往前依次两两⽐较，⼤的前移(如果a[j]>a[j-1]，交换a[j]和a[j-1])
            说明
                冒泡排序和选择排序每⼀轮⽐较都仅仅只确定⼀个数在数组中的位置，对n个数，需要进⾏n-1轮⽐较
                选择排序每⼀轮只交换⼀次，冒泡排序在每⼀轮可能交换多次，因此花费的时间略多⼀点
                如果在某⼀轮⽐较中，没有发⽣⼀次交换，就说明数组已经有序了

2.3 字符串

基础
    化整为零：字符串 = 字符数组，对字符串的处理即是对字符数组的处理
    化零为整：遍历字符数组，通过字符串的连接运算，可以根据题⽬的要求，得到⼀个新的字符串，它通常就是问题的解


操作：字符串的所有处理，都可以在化零为整的过程中完成
    CRUD：将字符串理解为字符数组后，字符串的CRUD（增、删、改、查）操作就类似于数组的CRUD操作
    截取：⼜称为取⼦串，即取出字符串中的⼀部分


图形：⼜称为“字符图形”，⼀般是输出多⾏有规律的字符，组成⼀个特定的图形，这样的图形称为字符图形
    注意
        ① 可以将字符图形中的⼀⾏看作为⼀个字符串，字符串的末尾带有⼀个换⾏符，由多个这样的字符串组成⼀个完整的字符图形
        ② ⼀般而⾔，每⼀⾏输出的符号的种类和符号的个数是有规律的，因此，求解图形问题的关键在以下3点
            Ⅰ 总⾏数，即字符图形的总⾏数，记为“n”
            Ⅱ ⾏号，代表字符图形中的某⼀⾏，记为“i”，i∈[1,n]
            Ⅲ 每⼀⾏中，每种符号的个数与总⾏数“n”和⾏号“i”之间的数学关系

3.优化

3.1 算法的性能

概念
    可以⽤算法的复杂性来衡量⼀个算法的效率，也可⽤它来衡量计算机求解问题的难易程度，包含算法的时间复杂性和空间复杂性
    算法的时间复杂性越⾼，算法的执⾏时间越⻓，反之越短；算法的空间复杂性越⾼，算法所需的存储空间越多，反之越少
    在算法的复杂性分析中，对时间复杂性的分析考虑得更多


时间复杂度
    概念
        通常采⽤“渐进时间复杂度”描述数据量的规模n与算法的执⾏时间t之间的函数关系
        时间复杂度为指数阶O(2^n)的问题，当n值稍⼤时就⽆法计算了，但仍然属于可计算性范畴
        时间复杂度为O(2^n)或O(n!)这类算法，⽤提⾼计算机的运⾏速度来扩⼤其求解规模，可能性是微乎其微的
        ⼀般来说，通过对算法中循环次数的统计，即可直观地估计出算法的时间复杂性
    常⻅：O(1) < O(logn) < O(nlogn) < O(n^2) < O(n^3) < ... < O(n^k) < O(2^n) < O(n!) < O(n^n)
        O(1) 常数阶：问题的规模n和执⾏之间没有关系，例如利⽤求和公式求等差数列之和
        O(logn) 对数阶：⼆分查找、辗转相除法求最⼤公约数（欧⼏⾥得法）
        O(n) 线性阶：考试中的多数算法的渐进时间复杂度就是O(n)级的，例如顺序查找
        O(nlogn) 线性对数阶：快速排序、归并排序等
        O(n^2) 平⽅阶：冒泡排序、选择排序等
        O(2^n) 指数阶：例如汉诺塔（hanoi）、旅⾏商（TSP）等


空间复杂度
    概念：通常采⽤“渐进空间复杂度”来描述数据量的规模m与算法的执⾏空间需求之间的函数关系
    常⻅：O(1) < O(n) < O(n^2)
        O(1) 常⻅于不需要使⽤数组的算法
        O(n) 常⻅于使⽤⼀维数组的算法
        O(n^2) 常⻅于使⽤⼆维数组的算法


注意
    ①在很多问题中，时间和空间是⼀个对⽴⾯
     当时间是⼀个重要因素时，有可能通过增加算法的空间复杂度以减少算法的时间复杂度，即⽤空间换时间
     当空间是⼀个重要因素时，有时也可以⽤算法的运⾏时间取换取空间
    ②时间复杂度和空间复杂度之间仅仅具有相对性而不具备必然性
     也就是说，通过牺牲空间不必然能换取时间，通过牺牲时间也不必然能够换取空间

3.2 算法的优化

原则：主要针对算法的时间性能进⾏优化，优化的原则是尽可能减少基本操作的执⾏次数


⽅法
    ① 减少循环次数，或减少循环中基本操作的执⾏次数
        Ⅰ 常数运算放在循环外执⾏，即把不需要反复执⾏的操作放在循环外
        Ⅱ 减少循环的执⾏次数，例如，把验证n是否是素数的范围从2~n-1缩小到2~sqrt(n)，以及在素数的判定或冒泡排序中，使⽤标志位提前结束循环等
        Ⅲ 需要多次执⾏数组的查找操作时，先对数组排序，就可以使⽤时间复杂度为O(logn)的⼆分查找代替时间复杂度为O(n)的顺序查找
    ② 平衡分⼦结构的层数，即对于多分⽀结构，尽可能构造⼀棵平衡树
    ③ 记忆化（memoization），把复杂计算的结果存储起来，以⽅便多次重复使⽤，是⼀种⽤空间换时间的优化思路