《计算机算法通俗教程》课件全套 王丰 第1-12章 算法基础 -图论算法

本章导读在本章中，我们将一起探索算法的基本概念、特征、设计方法以及如何评价一个算法的优劣。同时，我们会简要介绍实现算法的编程语言和开发环境。希望通过本章的学习，大家能对算法有一个清晰的认识，并为后续的深入学习打下坚实的基础。第1章算法基础1.1算法概述1.2算法设计与描述1.3算法评价1.4编程语言与编程环境目录什么是算法？算法是解决特定问题的一系列明确、有限的步骤，是计算机解决问题的核心方案。核心属性：1.强调“步骤”而非最终的“答案”，是达成目标的过程。2.具有针对性：一个问题可以有多种不同的算法来解决。1.1.1算法的概念1.1.2算法的特征输入性：0个或多个输入，部分输入可嵌入算法。输出性：至少1个输出，无输出的算法无意义。确定性：步骤定义明确，相同输入必得相同输出。有穷性：有限步骤结束，每步有限时间完成。可行性：操作可通过基本运算有限次实现。1.1.3学好算法很重要●解决实际问题的能力电商推荐、社交排序、导航路径规划等。●培养计算思维抽象问题、逻辑严谨、权衡取舍。●应对大规模数据高效算法是处理海量数据的关键。算法应用的三大核心维度1.2.1算法设计1.理解问题：明确问题要求和输入输出。2.预测输入：考虑合法和非法输入，确保算法健壮性。3.确定数据结构：选择合适的数据组织方式。4.设计并描述算法：核心步骤，选择合适的描述方法。1.2.2算法描述（自然语言）优点：简单易懂，适合描述简单算法，便于非专业人员理解算法逻辑。缺点：不够严谨，容易产生歧义；冗长且难以描述复杂逻辑，无法直接转化为计算机程序。案例：描述“求两个正整数的最大公约数”：1.输入两个正整数m和n；2.计算r=m%n（m除以n的余数）；3.若r等于0，则n即为最大公约数，算法结束；4.否则，令m=n，n=r，返回步骤2继续执行。1.2.2算法描述（流程图）一、流程图的特点优点：简洁明了，逻辑结构清晰，分支循环一目了然，能直观展示算法执行步骤。缺点：绘制复杂，修改不便，当算法逻辑过于复杂时，图形会变得庞大且难以维护。二、应用案例右图展示了经典的“求最大公约数”算法的流程图实现。求最大公约数算法流程图核心优势：介于自然语言和编程语言之间，书写灵活、描述能力强，是算法描述的最常用方式。主要局限：没有统一的官方标准，不同的书籍或资料可能采用不同的书写格式和语法约定。应用案例：展示“求最大公约数”的伪代码逻辑，清晰描述算法步骤。//示例逻辑1.输入两个数a,b2.Whileb≠03.r=a%b4.a=b,b=r5.输出a算法评价核心逻辑设计出的算法需要通过分析评价判断其实用价值，核心评价指标主要包含以下两个方面：1.时间复杂度：用于衡量算法运行过程中时间资源的消耗情况，反映算法执行的快慢效率。2.空间复杂度：用于衡量算法运行过程中内存空间资源的消耗情况，反映算法对内存的占用程度。1.3.1算法评价指标1.3.2时间复杂度【概念】衡量算法运行时间随输入规模增长的变化趋势，分析操作次数的增长级别。【表示方法】大O表示法（O），表示最坏情况的时间性能。【计算方法】忽略低阶项和常数系数，如T(n)=3n²+2n+1的时间复杂度为O(n²)。【效率对比】O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(2ⁿ)。不同时间复杂度的效率对比算法性能评估的重要指标1.3.3空间复杂度概念定义衡量算法运行过程中临时占用存储空间的大小随输入规模增长的趋势。通常关注算法本身额外占用的空间。表示方法与时间复杂度一致，使用大O表示法来描述空间增长的量级。典型案例：递归算法递归算法的空间复杂度主要取决于递归调用栈的深度。例如，阶乘递归的空间复杂度为O(n)。1.4编程语言与编程环境编程语言选择：C++本书选用C++作为教学语言，原因在于其语法简洁、执行效率高且在算法竞赛中普及度极高。需要强调的是，算法逻辑本身独立于具体的编程语言，任何语言均可实现算法思想，C++是实现高效算法的优选工具。推荐环境：Dev-C++推荐初学者使用Dev-C++，它免费、轻量且安装简单，无需复杂配置。主要操作包括：新建源文件、编写代码、编译运行程序以及查看报错信息进行调试，是入门算法编程的理想工具。课堂小结1.算法概念与特征：明确算法的定义，掌握算法的五大基本特征（输入、输出、有穷性、确定性、可行性）。2.算法设计与描述：学习算法设计的基本步骤，熟练运用自然语言、流程图和伪代码三种方式描述算法逻辑。3.算法评价：理解算法效率的衡量标准，重点掌握时间复杂度和空间复杂度的分析方法。4.编程语言与环境：熟悉C++语言基础，掌握Dev-C++开发环境的配置与使用，为后续编程实现打下基础。简单算法在本章中，我们将学习一些经典且实用的基础算法，包括数字的分离与合成、素数判断、最大公约数求解以及如何巧妙地运用数组下标。这些算法是编程的基石，掌握它们对于理解更复杂的算法逻辑至关重要。希望大家能认真练习，深入理解算法背后的数学思想与逻辑。第2章简单算法2.1数字分离与合成2.2素数判断2.3最大公约数2.4巧用数组下标目录1.整除运算（/）对整数进行除法，结果无小数部分。例如：5/2=2。2.模除运算（%）求余数。例如：5%2=1。3.核心逻辑通过整除和模除组合，分离数字的每一位。2.1.1数字分离inti=123,a,b,c;a=i%10; //提取个位c=i/100; //提取百位b=i%100/10;//提取十位数字合成：将各位数字合并成一个整数，核心算法是((0*10+1)*10+2)*10+3。计数问题：统计数字x在1到n中出现的次数，核心是循环分离每一位并计数。核心代码如下//计数问题核心代码片段for(inti=1;i<=n;i++){ intb=i; while(b!=0)

{ if(b%10==x)t++; b=b/10; }}2.1.2数字合成&2.1.3计数问题1.素数定义与判断方法定义：大于1的自然数，除了1和自身外，不能被其他自然数整除。方法：让n除以2到√n之间的每一个数，若均不能整除则为素数。intisPrime(intn){intk=sqrt(n),i;for(i=2;i<=k;i++)

if(n%i==0)break;//循环判断returni>k;//返回判断结果}2.2.1素数及其判断2.2.2批量求素数（埃氏筛选法）算法思想：先假设所有数都是素数，然后逐步排除合数。核心步骤：从2开始，将每个素数的所有倍数标记为合数。代码实现：//埃氏筛选法核心代码片段for(inti=2;i<=k;i++){ if(!a[i])continue; for(intj=2;j<=n/i;j++) a[i*j]=false;}图2-1埃氏筛选法执行过程示意图总结：该算法通过“空间换时间”的策略，高效地将合数筛选出来。2.3.1最大公约数概念最大公约数（GCD）是数论中的重要概念，指两个或多个整数共有约数中最大的一个。理解其定义并掌握欧几里得算法等高效求解方法。定义：几个整数公有的约数，称为这几个数的公约数。公约数核心概念：在所有公约数中数值最大的那一个，即为最大公约数。最大公约数实例演示：整数12和16的公约数有1、2、4，其中最大公约数是4。示例：12&162.3.2辗转相除法▍算法步骤：用二数相除得到余数，再用除数和余数重复此过程，直到余数为0，最后的除数就是最大公约数。▍核心代码（C++）：r=m%n;while(r!=0){

m=n;

n=r;

r=m%n;}cout<<n<<endl;图2-3辗转相除法流程示意图技巧核心：利用数组的下标来表示一项信息（例如学生的学号），而数组元素对应的值则用来存储另一项关联信息（例如该学生的成绩）。核心优势：这种方法充分利用了数组的随机访问特性，可以实现数据的快速查找和高效统计，避免了繁琐的遍历匹配过程。典型应用：经典算法如“筛选法求素数以及“桶排序等，均是此技巧的经典实践。2.4.1巧用数组下标桶排序核心原理与代码实现2.4.2桶排序(1)算法思想将数据分配到有限数量的“桶”里，最后按顺序合并所有桶内数据，完成整体排序。(2)核心代码(C++)//初始化桶并分配数据for(inti=1;i<=n;i++)

{cin>>x;a[x]++;}//遍历桶输出结果for(inti=0;i<10;i++)

for(intj=0;j<a[i];j++)

cout<<i<<"";课堂小结●数字处理：掌握了数字分离与合成的基本方法，能够处理复杂的数值运算。●素数问题：学会了素数判断和埃氏筛选法批量求素数，提升了算法效率。●最大公约数：掌握了高效的辗转相除法，解决了数论中的经典问题。●编程技巧：理解了巧用数组下标的思想，并学习了桶排序算法。3.1枚举法概述3.2枚举法实例-3.2.1百钱买百鸡-3.2.2火柴棒等式目录3.1枚举法概述枚举法，也叫穷举法，是一种非常基础但实用的算法思想。它的核心思想是在可能的解空间中逐一列举所有可能的候选解，并逐一验证是否符合问题的条件。虽然枚举法在某些情况下效率可能不高，但对于小规模数据或作为优化算法的基础，它是不可或缺的。本章我们将学习枚举法的基本概念，并通过经典案例掌握其应用与剪枝优化技巧。3.1算法基础核心思想：将所有可能的解逐一代入问题中进行验证，满足所有限定条件的解即为正确解。核心思想适用场景：解的范围已知且有限，无明显规律可循的问题。例如密码破解、组合问题等。适用场景特点：效率不高，但实用有效。依赖计算机强大的计算能力来弥补算法本身的低效。特点3.1枚举法概述题目描述鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一。百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？人工分析思路设鸡翁为x，鸡母为y，鸡雏为z，建立二元一次方程组进行求解。计算机枚举思路确定变量取值范围，逐一验证是否满足方程条件：鸡翁x范围：0~20鸡母y范围：0~33鸡雏z范围：0~3003.2.1百钱买百鸡（题目与分析）3.2.1百钱买百鸡（程序实现）优化思路：利用总数为100的条件，将三重循环优化为双重循环。确定鸡翁(x)和鸡母(y)数量后，鸡雏(z)数量可由z=100-x-y直接得出。关键点：判断条件中需包含z%3==0，确保鸡雏数量是3的倍数。for(x=0;x<=100/5;x++)//列举鸡翁的所有可能取值for(y=0;y<=100/3;y++) //列举鸡母的所有可能取值

{z=100-x-y;//根据x，y计算鸡雏的数量

if(5*x+3*y+z/3==100&&z%3==0)//找到一组正确答案

cout<<x<<""<<y<<""<<z<<endl;}3.2.2火柴棒等式（题目与分析）【题目描述】用n根火柴棒拼出形如A+B=C的等式，火柴棒必须全部用完。【分析思路】1.计算每个数字所需的火柴棒数量。2.枚举A和B的可能值，计算C=A+B。3.验证拼出A、B、C及符号所需的火柴棒总数是否等于n。【取值范围】A、B不超过1000。图3-1火柴棒数字拼法示意图核心函数：Num(x)计算拼出数字x所需的火柴棒数量，支持多位数拆分计算。intNum(intx){if(x<10)returna[x];intsum=0;while(x>0){sum+=a[x%10];x/=10;}returnsum;}主逻辑：枚举验证枚举A和B的所有可能值，计算C=A+B，验证火柴棒总数是否符合要求。for(inti=0;i<=1000;i++)for(intj=0;j<=1000;j++)if(Num(i)+Num(j)+Num(i+j)==n-4)ans++;3.2.2火柴棒等式（程序实现）枚举法优化思路1.缩小枚举范围：根据问题条件，合理估计变量的最大和最小值，避免无效的遍历。2.减少枚举变量：利用问题中的等式关系，用其他变量表示某些变量，从而减少循环层数。3.提前终止：在循环内部设置条件判断，一旦找到解或确定无解，立即终止循环。课堂小结枚举法思想：穷举所有可能解，逐一验证条件。这是最基础的算法设计思路，虽然简单但应用广泛。经典实例：掌握了“百钱买百鸡”和“火柴棒等式”的求解方法，理解了如何将实际问题转化为循环验证问题。优化策略：学会了缩小范围、减少变量、提前终止等优化技巧，以提高程序运行效率，避免不必要的计算。4.1递归概述4.2Fibonacci数列4.3其它典型题目-4.3.1Hanoi塔问题-4.3.2数的计算第4章递归4.1递归的概念与应用递归是一种非常重要的算法思想，它不仅是一种编程技巧，更是一种解决问题的思维方式。在本章中，我们将深入学习递归的基本概念，并通过几个经典的例子来掌握它的应用和优化方法。递归通过将复杂问题分解为更小的、相似的子问题来解决。理解递归的核心在于找出递归关系和递归终止条件，这是编写高效递归代码的关键。第4章递归4.1递归概述递归是一种强大的算法设计思想，通过将复杂问题分解为更小的子问题来求解。理解递归的关键在于掌握其“递推”与“回归”的过程。核心思想：将复杂问题分解为简单的子问题，直到子问题可直接求解，再回溯得到原问题的解。核心思想工作流程：包含“递推”（将问题分解为子问题）和“回归”（从子问题回溯求解）两个过程。工作流程典型应用：1.问题定义递归（如阶乘、斐波那契）2.数据结构递归（如树、文件夹）3.问题解法递归（如汉诺塔）典型应用1)定义F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2)(n≥2)。从第三项开始，每一项都是前两项之和。2)递归求解代码利用递归思想实现的C++代码如下：4.2.1Fibonacci数列概述intfib(inti)//返回第i项的值{if(i==0)return0;if(i==1) return1;returnfib(i-2)+fib(i-1);}4.2.2消除重复求解（备忘录）1.问题分析原始递归解法会导致大量的重复计算，随着n的增大，时间复杂度呈指数级增长，效率极其低下。2.解决方案：备忘录法引入“备忘录”（通常是数组或哈希表），将已经计算过的子问题结果存储起来。当再次需要该结果时，直接从备忘录中读取，避免重复递归计算。inta[100]={0,1};//备忘录数组intfib(inti){if(a[i]>0||i==0)

returna[i];a[i]=fib(i-1)+fib(i-2);returna[i];}图4-2斐波那契数列递归求解的重复计算示意与优化代码问题描述：将n个圆盘从A柱移到C柱，每次只能移动一个，且不能将大盘放在小盘上移动规则：一次只能移一个圆盘。圆盘只能在三根柱子间移动。任何时刻，大盘不能放在小盘之上。图4-3-1Hanoi塔初始状态图4.3.1Hanoi塔问题递归思想：要移动n个盘子，可以分解为三个步骤：1.将n-1个盘子从A柱移到B柱（以C柱为辅助）。2.将第n个盘子从A柱移到C柱。3.将n-1个盘子从B柱移到C柱（以A柱为辅助）。核心：将移动n个盘子的问题，转化为移动n-1个盘子的子问题。算法分析核心代码：递归函数move实现移动逻辑。voidmove(intn,chara,charc,charb){if(n==0)return;move(n-1,a,b,c);//把n-1个盘子从a移到b，用c做辅助cout<<++k<<":"<<a<<"→"<<c<<endl;//移动第n个盘子move(n-1,b,c,a);//把n-1个盘子从b移到c，用a做辅助}参数说明：n：盘子数量，a：源柱子，c：目标柱子，b：辅助柱子4.3.1Hanoi塔问题（程序实现）4.3.2数的计算（题目与分析）题目规则：找出满足特定规则的数的个数。规则是在数的左边添加不超过其一半的自然数，且该过程可递归进行。题目描述递归分析：设f(n)为n能扩展出的数的个数，则递推公式为：f(n)=1+f(1)+...+f(n/2)其中，“1”代表数n本身。算法分析优化问题：在直接递归求解过程中，会存在大量重复计算子问题的情况，导致效率低下。解决：需引入“备忘录”技术进行剪枝优化。优化策略4.3.2数的计算（程序实现）inta[1001];//备忘录数组intdfs(intm){//递归函数定义if(a[m]>0)returna[m];//记忆化搜索a[m]=1;//包含自身for(inti=1;i<=m/2;i++)//枚举左加数a[m]+=dfs(i);//累加结果returna[m];//返回总数}//函数结束课堂小结核心知识回顾递归思想：将复杂问题逐步分解为规模更小的子问题，通过递归调用自身求解，最终合并子问题答案得到原问题解。经典实例：斐波那契数列、汉诺塔问题、数的计算等，这些问题均具有明显的重复子问题特征。优化技巧：递归算法常存在大量重复计算，可使用“备忘录”技术（如哈希表、数组缓存）存储已计算结果，以空间换时间，将时间复杂度从指数级降低至线性级。目录5.1排序问题概述5.2冒泡排序5.3选择排序5.4快速排序5.5其它排序算法简介5.1排序算法概述排序是计算机科学中最基础、最常用的算法之一，在我们的日常生活中也无处不在。它不仅是数据处理的基础，也是许多复杂算法的核心组成部分。在本章中，我们将深入学习几种经典的排序算法，包括冒泡排序、选择排序和快速排序。我们将逐一分析它们的基本原理、时间复杂度、空间复杂度以及各自的适用场景，帮助大家建立起对算法效率的直观认识。第5章排序定义：将数据按规则重排。常见算法：冒泡、选择、快速、插入、希尔、归并、堆排序等。比较排序：比大小定次序，下界O(nlogn)。非比较排序：利用数据特性，可达O(n)，需额外空间。稳定性定义：稳定：相等元素相对顺序不变。不稳定：不保证相对顺序。（3）算法稳定性5.1排序问题概述5.2.1冒泡排序原理核心思想：重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。执行过程：每一趟冒泡都会将当前未排序区的最大值“冒泡”到未排序区的末尾。算法特点：n个数据需要进行n-1趟冒泡，每趟比较次数递减。核心代码：通过两层循环实现，外层循环控制趟数，内层循环进行相邻元素的比较与交换。for(inti=0;i<n-1;i++){for(intj=0;j<n-1-i;j++)

{if(a[j]>a[j+1])swap(a[j],a[j+1]);}}算法说明：1.时间复杂度为O(n²)，属于稳定排序算法。2.优化策略：可通过设置标志位，若某一趟未发生交换则说明已有序，提前退出循环。5.2.2冒泡排序程序5.2.3车厢重组（冒泡排序应用）问题描述：通过旋转桥交换相邻车厢，求将车厢按编号排序的最少旋转次数。算法分析：问题本质就是统计冒泡排序过程中发生交换操作的次数。通过引入计数器并利用提前退出机制可优化效率。for(inti=0;i<n-1;i++){boolok=true;for(intj=0;j<n-1-i;j++){if(a[j]>a[j+1]){swap(a[j],a[j+1]);count++;ok=false;}}if(ok)break;//提前退出优化}5.3.1选择排序原理核心思想：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。（1）核心思想排序过程：1.从未排序区找到最小元素。2.将其与未排序区的第一个元素交换。3.缩小未排序区，重复上述步骤。（2）排序过程算法特点：交换次数比冒泡排序少，但无法提前退出，时间复杂度为O(n²)。（3）算法特点5.3.2选择排序程序核心思想：外层循环遍历每个位置，内层循环寻找最小值的下标，最后进行交换。算法特性：时间复杂度为O(n²)，是不稳定排序算法。for(inti=0;i<n-1;i++)

//进行n-1轮选择{intk=i; //最小元素的下标

for(intj=i+1;j<n;j++) //在当前无序区a[i]..a[n-1]中选最小的元素a[k]

if(a[j]<a[k])k=j;if(k!=i)swap(a[i],a[k]); //交换a[i]和a[k]，将当前最小值放到a[i]位置}5.4.1快速排序原理核心思想：采用分治思想。选择一个基准值，将数据分为两部分，左边小于基准值，右边大于基准值，然后递归处理两部分。执行过程：1.选择基准值；2.分区操作（小左大右）；3.递归排序左右子数组。算法特点：平均时间复杂度为O(nlogn)，最坏情况O(n²)，属于不稳定排序。图5-8快速排序分区与归位过程示意图核心代码（递归实现）：voidquick_sort(inta[],intleft,intright){if(left>=right)return;intL=left,R=right,key=a[L];while(L<R)

{while(L<R&&a[R]>=key)R--;while(L<R&&a[L]<=key)L++;if(L<R)swap(a[L],a[R]);}swap(a[left],a[L]);quick_sort(a,left,L-1);quick_sort(a,R+1,right);}5.4.2快速排序程序问题描述：找出数列排序后的第k小的数。算法分析：利用快速排序的分区思想，只需递归处理第k个数所在的子数组，无需完全排序。核心优化：在递归前判断第k个数是否在当前区间内，不在则直接返回，避免无效递归。5.4.3第k小整数（快速排序应用）if(left>k||right<k)return;//关键优化：提前终止5.5.1插入排序简介核心思想：将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据。核心思想生活类比：如同打牌时抓牌，每抓一张就插入到手中合适的位置，保持手牌有序。生活类比算法特点：简单直观，对基本有序的数据效率较高；时间复杂度O(n²)，属于稳定排序算法。算法特点排序算法对比算法平均时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序O(n²)O(n²)O(1)稳定选择排序O(n²)O(n²)O(1)不稳定快速排序O(nlogn)O(n²)O(logn)不稳定插入排序O(n²)O(n²)O(1)稳定冒泡排序：相邻比较交换，稳定，可提前退出。选择排序：选择最小元素交换，不稳定，交换次数少。快速排序：分治思想，效率高，平均O(nlogn)，不稳定。排序算法选择：根据数据规模、有序程度和稳定性要求综合考虑。算法设计的核心在于平衡时间复杂度与空间复杂度，选择最适合场景的策略。目录6.1查找概述6.2顺序查找6.3二分查找6.4STL中的查找函数6.1查找概述查找是计算机编程中最基本、最常用的操作之一，我们每天都在使用它，比如在通讯录里找联系人，在文件系统中找文件。在本章中，我们将学习几种经典的查找算法，包括顺序查找和二分查找，并了解如何利用C++标准库中的查找函数来提高编程效率。第6章查找定义：在大量信息中寻找特定元素的过程。基本定义常见算法：1.顺序查找2.二分查找3.插值查找4.哈希查找等常见算法分类：无序查找：数列无需有序（如顺序查找）。有序查找：数列必须有序（如二分查找）。算法分类6.1查找概述6.2.1顺序查找基础一、基本思想逐个比较数组元素与目标值，找到则返回索引，否则返回-1。二、性能分析•时间复杂度：O(n)•最好情况：1次比较•最坏情况：n次比较•平均情况：(n+1)/2次比较三、核心代码实现intSequenceSearch(inta[],intn,intkey){for(inti=0;i<n;i++)if(a[i]==key)returni;return-1;}监视哨技术核心思想在数组末尾添加一个等于目标值的“监视哨”，避免每次循环都检查数组是否越界，将两次判断合并为一次。操作步骤1.将目标值存入数组末尾。2.从数组头部开始查找，找到目标值即停止。3.判断位置，若是末尾则说明原数组无目标值。代码优化点在循环中只需判断元素是否相等，无需判断索引是否越界。从而减少了一半的比较次数，提高了查找效率。优化代码通过引入监视哨，我们将原本在循环中需要进行的“索引越界检查”和“目标值比较”这两个操作，简化为了单一的“目标值比较”。这种优化在数据量较大时能显著减少CPU的指令执行次数，从而提升算法效率。6.3.1二分查找概述一、基本思想利用分治思想，在有序数组中，通过不断将查找区间减半来快速定位目标值。二、适用条件待查找的数据序列必须是有序的（升序或降序）。三、查找步骤取中间位置元素与目标值比较；若相等则查找成功；若目标值更小，在左半区间继续查找；若更大，在右半区间继续查找；重复步骤，直到找到目标值或区间为空（查找失败）。图6-1二分查找过程示意图一、核心代码（C++实现）intBinSearch(inta[],intn,intkey){intleft=0,right=n-1;while(left<=right){intmid=(left+right)/2;if(a[mid]==key)

returnmid;elseif(a[mid]<key)

left=mid+1;else

right=mid-1;}return-1;}6.3.2二分查找程序（循环法）二、性能分析二分查找每次比较都将查找区间缩小一半，时间复杂度为O(logn)，在数据量较大时，查找效率远优于顺序查找（O(n)）。6.3.2二分查找程序（递归法）算法思想：递归法将查找问题分解为更小的子问题，直到规模缩小到可直接解决。代码简洁，但性能略逊于循环法，且存在栈溢出风险。intBinSearch(inta[],intleft,intright,intkey){if(left>right)return-1;//递归终止条件intmid=left+(right-left)/2;if(a[mid]==key)

returnmid;elseif(a[mid]<key)returnBinSearch(a,mid+1,right,key);elsereturnBinSearch(a,left,mid-1,key);}6.3.3查找左右边界1.问题描述在有序数组中存在重复元素时，需要查找目标值第一次出现（左边界）或最后一次出现（右边界）的位置。2.算法思路基于二分查找框架，当找到目标值时不立即返回。查找左边界时，收缩右边界继续向左搜索；查找右边界时，收缩左边界继续向右搜索。直到区间无效，最终确定边界位置。3.核心代码逻辑(查找左边界)intleft_bound(int[]nums,inttarget){...if(nums[mid]==target)

right=mid-1;...}6.4.1STL查找概述概述：C++标准模板库（STL）提供了丰富的查找函数，无需手动实现。binary_search功能：判断指定元素是否存在于有序区间中。返回值：存在返回true，否则返回false。存在性判断lower_bound功能：查找第一个大于等于目标值的元素。返回值：指向该元素的迭代器。查找下界upper_bound功能：查找第一个大于目标值的元素。返回值：指向该元素的迭代器。查找上界【功能描述】在有序区间内查找目标值是否存在。该函数不返回具体位置，仅判断存在性。【函数语法】

binary_search(first,last,value)【返回值】布尔值（bool）：找到返回true，未找到返回false。【示例代码】

vector<int>v={1,3,5,7,9};boolfound=binary_search(v.begin(),v.end(),5);//found=true6.4.2binary_search函数lower_bound函数：返回容器中第一个大于等于目标值的元素位置。upper_bound函数：返回容器中第一个大于目标值的元素位置。返回值类型：迭代器（对于普通数组则是指针），指向找到的边界位置。核心用途：在有序序列中高效查找元素的插入点或边界，时间复杂度为O(logn)。6.4.3lower_bound与upper_bound函数图6-4lower_bound与upper_bound返回值示意图课堂小结●顺序查找：简单直观，适用于无序数据，时间复杂度O(n)，可通过监视哨优化。●二分查找：效率高，时间复杂度O(logn)，要求数据有序，有循环和递归两种实现方式。●STL查找函数：高效便捷，包括binary_search、lower_bound和upper_bound，是实际开发的首选。●算法选择：根据数据是否有序、数据规模和开发效率综合考虑。目录7.1贪心算法概述7.2典型例题7.1贪心算法贪心算法是一种非常重要且常用的算法思想，它通过在每一步都做出局部最优的选择，来期望最终得到全局最优解。在许多经典问题中，如最短路径、最小生成树等，它是高效且正确的。在本章中，我们将深入探讨贪心算法的基本概念、核心性质（贪心选择性质与最优子结构性质），并通过最优装载、活动选择等典型例题来掌握其实际应用。7.1贪心算法定义：所求问题的整体最优解可以通过一系列局部最优的选择（即贪心选择）来达到。含义：每一步的贪心选择都必须是最终最优解的一部分，即每一步都做出当前看似最好的选择。证明方法：通常使用交换论证法，即证明将贪心选择替换为其他选择，无法得到更优的解。举例：在矩阵中每行选一个数求和最大，贪心选择每行的最大值，该选择一定是全局最优解的一部分。7.1.2贪心选择性质7.1.3最优子结构定义：问题的最优解包含其子问题的最优解。这是贪心算法、动态规划算法等算法的核心特征之一。定义含义：全局最优解可以通过组合局部最优解得到，允许我们自底向上地构建解决方案。含义证明方法：通常使用反证法，即假设全局最优解不包含子问题的最优解，从而推出矛盾，以此证明性质成立。重要性证明方法1.着眼当前，简单高效：每一步都只做局部最优选择，不考虑未来，因此算法简单，效率较高。2.不回溯：一旦做出选择，就不会再回头修改，这与动态规划等算法有本质区别。7.1.4贪心算法的特点问题描述（详细描述见课本）已知每个集装箱的重量及轮船的载重上限，要求将尽可能多的集装箱装上船。贪心策略每次都挑选剩余集装箱中重量最轻的进行装载。选择过程①对所有集装箱按重量从小到大排序。②每次选择最轻的集装箱装船，然后判断是否超重。③重复上一步，直到超重停止。7.2.1最优装载问题描述（详细描述见课本）已知每个活动的开始时间与结束时间，要求安排尽可能多的活动，使得它们在时间上互不冲突。贪心策略每次选择结束时间最早的活动，为后续活动留出更多时间。选择过程按结束时间排序后，依次选择不与已选活动冲突的、结束时间最早的活动。活动选择贪心策略过程示意图7.2.2活动选择核心思路：定义活动结构体存储起止时间，按结束时间升序排序，遍历选择不冲突的活动。核心代码实现（C++）：structblock{intbegin;intend;}a[1000];boolcompare(blocka,blockb){returna.end<b.end;}intmain(){intn,ans=0;cin>>n;for(inti=0;i<n;i++)cin>>a[i].begin>>a[i].end;sort(a,a+n,compare);//按结束时间排序for(inti=0,x=-1;i<n;i++)

{if(a[i].begin>=x){ans++;x=a[i].end;}}cout<<ans<<endl;return0;}活动选择问题程序实现核心概念：贪心算法总结核心思想：每一步都做局部最优选择，期望通过这种方式得到全局最优解。它不回退，仅依据当前信息做决定。适用条件：问题必须具备“贪心选择性质”（局部最优能导出全局最优）和“最优子结构性质”（问题的最优解包含子问题的最优解）。解题步骤：1.分析问题，确定合适的贪心策略（如按某种规则排序）。2.证明策略的正确性，验证其满足贪心选择性质和最优子结构。3.根据策略编写代码实现，通常涉及排序和迭代选择。习题讲解（选择题）1.贪心算法的核心特征是（B）A.通过穷举所有可能解寻找最优解B.每一步选择当前局部最优解C.必须使用动态规划辅助决策D.总是能得到全局最优解2.最优装载问题的主要贪心策略是（B）A.价值最高者优先B.重量最轻者优先C.体积最小者优先D.随机选择习题讲解（判断题）1.贪心算法在每一步选择时不需要考虑后续子问题的结果（√）2.最优子结构性质是贪心算法和动态规划算法共有的特征（√）3.贪心算法适用于所有具有最优子结构的问题（×）8分治8.1分治算法概述8.2二分答案8.3典型分治例题8.1分治算法概述分治算法是一种非常重要的算法设计思想。它的核心策略是将一个复杂的大问题分解为若干个规模较小、相互独立且与原问题形式相同的子问题，递归地解决这些子问题，然后将各子问题的解合并，从而得到原问题的解。这种策略在处理大规模数据或复杂计算时非常有效，能够显著降低时间复杂度。本章我们将深入探讨分治算法的基本原理、适用条件，并通过经典案例掌握其应用。定义：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。核心思想：分：分解问题，将大问题分解为多个规模较小的子问题。治：合并结果，将子问题的解合并得到原问题的解。实现方式：通常采用递归的方式实现。递归能很好地匹配分治的“分解”与“回溯”过程。适用问题特征：问题规模缩小到一定程度就容易解决。问题可以分解为若干个规模较小的相同问题。子问题的解可以合并为原问题的解。子问题相互独立（无公共子问题）。经典应用：二分搜索、归并排序、快速排序大整数乘法、棋盘覆盖最接近点对问题、循环比赛日程表二分答案是分治算法的经典应用，通过不断猜测中间值并验证，在已知答案范围且具有单调性的场景中快速求解。定义以二分搜索的方式查找答案，是分治算法的一种简单应用。基本定义适用场景1.无法直接求解，但知道答案区间。2.答案在区间内具有单调性。适用场景核心思想通过不断猜测答案并验证其正确性，快速缩小搜索范围，最终找到符合条件的解。核心思想8.2.1二分答案概述问题描述：从n条绳子中切割出m条长度相同的绳段，求绳段的最大长度。解题思路：1.确定答案范围：[最长绳长/m,总绳长/m]。2.二分搜索：猜测一个长度mid，检查能否切割出m段。3.根据检查结果调整搜索范围，直到找到最大值。1boolCheck(intlen){...}//检查能否切割出m段2voidSearch(intL,intR){...}//二分搜索最大长度8.2.2切割绳子已知条件：贷款总额、每月还款额、还款总月数。求解目标：计算贷款的月利率。问题描述1.确定范围：利率范围[0,300]。2.二分搜索：猜测利率mid，检查m个月能否还清。3.注意事项：实数二分，循环条件while(l<r-0.05)。解题思路doublel=0,r=300;while(l<r-0.05){doublemid=(l+r)/2;if(check(mid))

{

ans=mid;

l

=mid;

}else

r

=mid;}核心代码逻辑8.2.3银行贷款问题问题描述：找出序列中连续且非空的一段，使其和最大。分治策略：1.分解：将数组分成左右两半。2.求解：递归求解左右两半的最大子段和。3.合并：求解跨越中点的最大子段和，最终结果为三者中的最大值。跨越中点的处理：以中点为基准，分别向左右两侧搜索最大子段，再合并。8.3.1最大子段和最大子段和核心代码：递归实现分治策略intsubsegment(intleft,intright){if(left==right)returna[left];intmid=(left+right)/2;intleftmax=subsegment(left,mid);intrightmax=subsegment(mid+1,right);//计算跨越中点的最大子段和intsum1=MinInt,sum2=MinInt;for(inti=mid,sum=0;i>=left;i--){...}//向左搜索最大子段和for(inti=mid+1,sum=0;i<=right;i++){...}//向右搜索最大子段和returnmax(max(leftmax,rightmax),sum1+sum2);}问题描述：给定一个数组，它的第i个元素是一支给定股票第i天的价格。设计一个算法来计算你所能获取的最大利润。你最多只允许完成一笔交易（即买入和卖出一支股票）。分治策略：1.分解：将价格序列分成左右两半。2.求解：递归求解左右两半的最大利润。3.合并：求解左半部分买入、右半部分卖出的最大利润，最终结果为三者中的最大值。算法关联：本题是最大子段和问题的变种。若将价格序列转化为每日的利润序列（后一天减前一天），则原问题等价于寻找该利润序列的最大子段和。算法关联8.3.2股票买卖问题问题描述为n=2^k个运动员设计满足特定要求的循环赛日程表。分治策略分解：将n个运动员分成两半。求解：递归为两半运动员设计日程表。合并：根据规律填充整个日程表(A=D,B=C,B=A+n/2)。规律总结日程表可以由左上角的子表通过复制和加法生成。n=4时的日程表规律8.3.3循环赛日程表voidsolve(intn){if(n==1)return;inthalf=n/2;solve(half);//填写左上角for(inti=0;i<half;i++){for(intj=0;j<half;j++)

{arr[i+half][j]=arr[i][j]+half;//填写左下方arr[i][j+half]=arr[i+half][j];//填写右上方arr[i+half][j+half]=arr[i][j];//填写右下方}}}1.分治算法定义：分而治之，将大问题分解为子问题，合并子问题的解。2.适用条件：问题可分解、子问题可合并、子问题独立。3.二分答案：特殊的分治应用，适用于答案有范围且单调的问题。4.典型应用：最大子段和、股票买卖、循环赛日程表。一、选择题1.下列选项中，不属于分治算法特征的是（C）2.分治算法的基本思想是什么（A）二、判断题1.分治算法将一个大问题转化为若干个子问题，然后在子问题的基础上再进行划分，直到能够快速解决一个子问题时停止划分（√）2.分治算法适用于所有类型的问题（×）习题搜索算法概论搜索算法是计算机解题中的“万能解题法”，尤其适用于那些没有有效算法的问题。在本章中，我们将学习搜索的基本概念、深度优先搜索（DFS）、广度优先搜索（BFS）以及重要的回溯法，并通过经典的排列、子集和、迷宫等问题来掌握它们的应用。第9章搜索目录9.1搜索基础9.2回溯法9.3深搜与广搜9.1.1搜索概述定义：一种“万能解题法”，主要用于解决那些没有已知有效算法的问题。定义核心思想：在解空间中进行有组织地枚举，并通过“剪枝”策略避免无意义的搜索，从而显著提高效率。核心思想与暴力枚举的关系：搜索本质上是一种更高效、更有条理的枚举方式，相比暴力枚举减少了大量无效尝试。与暴力枚举的关系9.1.2全排列与解空间树全排列问题：枚举所有可能的排列组合，是理解搜索算法的经典案例。解空间树：解空间的一种树形组织形式，直观展示了解的逐步生成过程与状态空间。剪枝：在搜索过程中，通过约束条件提前判断并放弃不可能得到解的路径，从而大幅减少无效搜索，提高效率。三位数字全排列的解空间树示意图深度优先搜索（DFS）：沿着一条路径尽可能深地搜索，直到尽头再回溯。通常用递归或栈实现。广度优先搜索（BFS）：从根节点开始，“齐头并进”地搜索所有分支。通常用队列实现。回溯法：深搜的一种常见形式，强调“探索与撤销”，通过状态管理来穷举所有可能解。9.1.3深搜、广搜与回溯向前探索，发现错误就退回一步重新选择，反复进行直到找到解。基本思想包含“搜索”和“回溯”两大步骤，核心是“修改→递归→恢复”的三段式结构。算法框架排列组合、图与棋盘问题、人机对弈、决策问题等场景。典型应用9.2.1回溯法概述算法框架：voidSearch(intk)//第k步操作{if(到达目的地){输出解;return;}for(i=1;i<=本步可选方案总数;i++)if(第i种选法能够满足条件) //剪枝{

保存结果 //保存第k步的选择Search(k+1);

//进入第k+1步

回溯 //退回第k步的初始状态

}}问题描述：从n个整数中取出r个进行排列，列出所有可能。解题思路：通过交换元素来选择当前位置的数字（破坏现场），递归处理下一个位置，递归返回后再交换回来（恢复现场）。9.2.2排列问题voidsearch(intk)//参数k表示进行第k步选择{if(k>r)

{输出排列方案；return;}//已经选够了r位数

for(inti=k;i<=n;i++)//选择第k个字符{

swap(a[i],a[k]); //交换元素

search(k+1); //进入下一步

swap(a[i],a[k]); //恢复现场

}}问题描述：找出集合中所有和为给定值W的子集。解题思路：对每个元素，有选与不选两种选择。通过剪枝（左子树剪枝和右子树剪枝）来避免无效搜索。剪枝策略：若已选元素和超过W，则剪去左子树；若剩余元素和不足以达到W，则剪去右子树。子集和问题的解空间树9.2.3子集和问题程序核心代码：回溯法实现子集和问题（含剪枝）voiddfs(inti,intsum1,intsum2){if(i==n){...}//输出满足条件的解并结束if(sum1+w[i]<=W)//左子树剪枝：选择当前元素不超限{

x[i]=1;dfs(i+1,sum1+w[i],sum2-w[i]);}if(sum1+sum2>W)//右子树剪枝：不选当前元素仍有希望{x[i]=0;dfs(i+1,sum1,sum2-w[i]);}}子集和问题程序实现代码说明：1.左子树剪枝：判断加入当前元素后总和是否超过目标值W，若未超过则递归。2.右子树剪枝：判断即使不选当前元素，剩余元素的和加上已选和是否仍大于W，若是则递归。栈（stack）特性：先进后出，常用于实现深度优先搜索（循环方式）。常用操作：push(),pop(),top(),empty()队列（queue）特性：先进先出，常用于实现广度优先搜索。常用操作：push(),pop(),front(),back(),empty()9.3.1STL中的栈与队列9.3.2迷宫类问题问题描述在迷宫中找到从入口到出口的路径。问题分类1.寻找出口：找到任意一条可行路径，DFS和BFS均可。2.寻找最短路径：找到从入口到出口的最短路径，必须使用BFS。迷宫结构示意图问题：给定一个迷宫，求从左上角走到右下角最少需要走多少步？解题思路：使用队列来管理待探索的节点，从起点开始，依次探索其周围的节点，直到找到终点。搜索过程：像水波纹一样，从起点开始，一层一层地向外扩散，确保最先到达终点的路径是最短的。9.3.3广度优先搜索（迷宫最短路径）广度优先搜索迷宫路径过程迷宫最短路径广搜程序实现intbfs(intx,inty){queue<Node>q;q.push({x,y,1});a[x][y]='#';//标记为已访问while(!q.empty())

{Nodenode=q.front();q.pop();

//取队列首元素if(node.x==r&&node.y==c)returnnode.step;

//到达终点for(inti=0;i<4;++i)

//遍历四个方向

{inttx=node.x+f[i][0],ty=node.y+f[i][1];if(tx<1||tx>r||ty<1||ty>c||a[tx][ty]=='#')continue;a[tx][ty]='#';

//将新增的路径点设置为墙，以免重复进入q.push({tx,ty,node.step+1});

//将新增的路径点加入队列}}return-1;

//没有任何路径能到达出口时}迷宫最短路径BFS核心代码问题：给定一个迷宫，寻找从入口到出口的一条路径。解题思路：使用深度优先搜索即可，深搜可以使用递归模式来实现，也可以使用”栈+循环”模式来实现，本处选择使用”栈+循环”模式。9.3.4深度优先搜索搜索过程：while（栈非空）{

if(栈顶元素是出口){

输出路径;

结束;}else{

针对栈顶元素，在其四周寻找一个从未走过并且是“路”的单元格 if(能找到上述单元格)

将其入栈; else

将栈顶元素出栈}深度优先搜索迷宫路径过程（“栈+循环”模式）●搜索基础：解空间树、深搜（DFS）、广搜（BFS）。●回溯法：基本思想、算法框架、排列与子集和问题。●典型应用：使用BFS解决迷宫最短路径问题。●效率关键：剪枝是提高搜索效率的关键。小结第10章动态规划动态规划是一种非常重要的算法设计思想，它通过将复杂问题分解为多个子问题，并利用子问题的解来构建原问题的最优解。在本章中，我们将学习动态规划的基本概念、核心思想，并通过数字金字塔、股票买卖和01背包等经典问题来掌握其应用。10.1动态规划概述10.2典型例题10.301背包问题动态规划（DynamicProgramming，DP）是运筹学的重要分支，核心在于将复杂问题分解为子问题求解，与分治算法既有相似性又有本质区别。10.1动态规划概述引例：数字金字塔问题描述寻找一条从金字塔顶部到底部的路径，使路径上数字的和最大。贪心法的局限性贪心选择可能无法得到最优解，因为它无法证明当前选择是全局最优的。贪心法路径和为50，而最优路径和为62。数字金字塔与贪心法路径对比示意图核心思路：从顶向下分解问题，从底向上合并结果。分解过程：将原问题分解为求从下一行两个位置出发的最大路径和。合并过程：从最底层开始，逐步向上计算每个位置到底部的最大路径和，最终得到顶部的解。数字金字塔的求解过程数字金字塔的分解与合并过程示意图多阶段决策问题：决策过程可分为若干相互联系的阶段，每个阶段需要做出决策。状态：描述某个阶段子问题的变量集合，如dp[i][j]表示从第i行第j列出发的最大路径和。状态转移方程：描述状态之间关系的数学表达式，是动态规划的核心。例如：dp[i][j]=a[i][j]+max(dp[i+1][j],dp[i+1][j+1])。10.1.2重要概念最优子结构：原问题的最优解包含子问题的最优解。这意味着我们可以通过求解子问题的最优解来构建原问题的最优解。无后效性：某阶段的状态一旦确定，后续决策不受之前状态和决策的影响。即未来与过去无关，只取决于当前状态。公共子问题：递归求解时会产生重复的子问题。动态规划通过记录子问题的解（记忆化）来避免重复计算，从而显著提升效率。10.1.3三大特征递归模式：从顶向下分解问题，将复杂的数字金字塔问题拆解为多个子问题，同时使用备忘录（Memoization）记录子问题的解，避免重复计算，提升算法效率。递推模式：从底向上合并结果，利用循环结构从金字塔的底层开始，逐步向上计算每个位置的最优状态值，最终推导出顶层的全局最优解。核心代码：分别实现递归（含备忘录）和递推两种模式的代码逻辑，对比两种实现方式的时间复杂度与空间复杂度差异。10.2.1数字金字塔程序实现10.2.2股票买卖问题问题描述已知n天中每一天股票的价格，在最多允许一次买卖的情况下，计算股票的最大利润。问题描述解题思路遍历每一天的价格，记录到当前为止的最低价格，并计算当前卖出的利润，更新最大利润。解题思路状态定义minPrice：记录最低价格maxProfit：记录最大利润状态定义一、问题描述在背包容量有限的情况下，选择物品装入背包，使总价值最大。这是一个经典的组合优化问题。二、问题分类1.01背包：每件物品只能选一次（要么选，要么不选）。2.完全背包：每件物品可以选无限次。3.多重背包：每件物品有有限的数量限制。10.301背包问题背包问题示意图问题描述：给定物品的重量和价值，以及背包容量，选择物品使总价值最大。解题思路：从最后一个物品开始考虑，对于每个物品，有选和不选两种选择。递归求解这两种选择的最优解，取较大者。分解过程：将问题分解为“选当前物品”和“不选当前物品”两个子问题。背包问题递归解法状态转移方程

：f[i][v]=max(f[i-1][v],f[i-1][v-w[i]]+c[i])状态定义：f[i][v]表示前i件物品放入容量为v的背包的最大价值。背包问题递推解法使用递推法的解题过程，相当于在逐行填写如下表格。填写规则：要从第一行开始，从上向下逐行填写。使用f[i][v]代表第i行第v列上单元格的值，其计算公式为：f[i][v]=max(f[i-1][v],f[i-1][v-w[i]]+c[i])背包问题递推解法优化在递推法时，计算下一行数据只用到上一行数据，因此可只记录一行数据填写规则：从上向下逐行填写。每一行从右向左逐列填写！计算公式：f[v]=max(f[v],f[v-w[i]]+c[i])核心知识回顾：课堂小结1.动态规划概述：掌握基本概念、核心思想及重叠子问题、最优子结构、无后效性三大特征。2.典型例题：深入理解数字金字塔路径和股票买卖的动态规划解法思路。3.01背包问题：熟悉问题描述，对比递归解法与动态规划的差异，熟练推导状态转移方程以优化空间与时间复杂度。高精度运算概述在编程中，我们经常会遇到超出普通数据类型范围的大整数运算，这时候就需要用到高精度运算。本章将介绍高精度运算的基本概念、数据存储方式，并详细讲解高精度加减乘除的实现方法。第11章高精度运算11.1高精度运算概述11.2高精度加法11.3高精度减法11.4高精度乘法11.5高精度除法目录11.1.1什么是高精度运算（1）核心概念：定义处理超出普通数据类型（如int、longlong）表示范围的大整数运算，也称为大整数运算。（2）应用场景：必要性当数值超过普通数据类型的存储极限时，语言内置类型无法准确表示，必须手动实现存储和运算逻辑。（3）存储极限：longlong范围-9223372036854775808～9223372036854775807（3）数值界限11.1.2高精度数据的存储输入方式：通常采用字符串方式输入，以避免数值溢出问题。存储方式：将字符串逐位转换为数字存入数组，并逆序存储（低位在前，高位在后），便于运算时的个位对齐。高精度数据的存储示意图1.高精度与高精度运算：两个数都是高精度数，运算过程需要完全模拟手工计算。2.高精度与低精度运算：一个数是高精度数，另一个数是普通数据类型（如int）。3.区别与优势：高精度与低精度运算可以利用编程语言的内置运算功能，实现逻辑相对简单。11.1.3二类高精度运算11.2.1高精度加高精度原理：完全模拟手工加法，从个位开始逐位相加，并处理低位向高位的进位。步骤：遍历两个数组，对应位相加，计算进位，处理最高位的进位。高精度加法原理示意图1.字符串转数组：将输入的大数字符串逆序存储到整型数组中，以便从低位到高位进行运算。2.逐位相加：遍历两个数组，对应位相加，加上低位的进位值。3.处理进位：计算当前位的和，保留个位作为当前结果，十位作为新的进位传递到高位。4.结果输出：逆序输出结果数组，得到最终的高精度加法结果。高精度加高精度程序实现要点11.2.2高精度加低精度原理：将低精度数加到高精度数的个位上，而后不断向前进位即可。示例：以“987+556”为例，我们将“987”视为高精度数，首先将它的各位数字分离并存储至数组，结果为：a[0]=7，a[1]=8，a[2]=9。计算步骤：将a[0]加上556，得到563，扣除进位值56，得a[0]=3。将a[1]加上进位值56，得到64，再扣除向上的进位值6，得a[1]=4。将a[2]加上进位值6，得a[2]=15。比较两个数的大小，确保被减数大于等于减数。若不满足，需交换并记录负号。（1）比较大小从个位开始逐位相减，若当前位不够减，则向高位借位，借1当10。（2）借位处理计算完成后，去除结果中多余的前导零，以得到正确的数值表示。（3）处理前导零11.3.1高精度减高精度1.比较大小：首先比较两个数的长度和每一位数字，确定被减数是否大于等于减数，若否，则交换并记录结果符号。2.逐位相减：从最低位（个位）开始，对应位数字相减。若本位被减数小于减数，则向高位借位（借1当10），再进行减法运算。3.借位处理：处理借位对高位的影响，确保每一位计算的准确性。4.结果输出：删除结果数组中多余的前导零，然后从高位到低位输出最终结果。高精度减高精度程序实现要点11.3.2高精度减低精度要点将高精度数的个位减去低精度数，然后不断从低位向高位借位，直到每一位数字都>=0。一、算法原理模拟手工乘法过程，用乘数的每一位去乘被乘数的每一位，并将结果累加到正确的位置，最后统一处理进位。二、核心要点结果的位数最多为两个乘数位数之和。a[i]*b[j]的结果应累加到c[i+j]的位置。11.4.1高精度乘高精度高精度乘法过程示意图高精度乘高精度程序实现核心逻辑：使用双重循环模拟手工乘法。外层循环遍历乘数的每一位，内层循环遍历被乘数的每一位。每次相乘的结果累加到结果数组的对应位置，最后统一处理进位并输出。

for(inti=0;i<len1;i++)//乘法遵循交换律，不区分被乘数与乘数 { intx=0; //用于存放进位 for(intj=0;j<len2;j++) { c[i+j]+=a[i]*b[j]+x;//原有内容+当前乘积+进位 x=c[i+j]/10; c[i+j]%=10; } c[i+len2]=x; //结果中最高位向前的进位 }高精度乘高精度核心代码逻辑11.4.2高精度乘低精度【原理】详见课本，以一个具体数字为：987*56=（900+80+7）*56=900*56+80*56+7*56=55272图示如下：高精度乘以低精度运算过程示意图11.5.1高精度除以低精度【原理】模拟手工除法的计算过程，从被除数的高位开始，逐位进行除法运算，同时记录每一步的商和余数。【要点】被除数需按原顺序存储（高位在前），因为除法运算的逻辑是从高位向低位依次进行的。高精度除以低精度运算过程示意图课堂小结●高精度运算概述：定义、数据存储方式（字符串输入，数组逆序存储）。●高精度加法：模拟手工加法