第2章 简单算法

简单算法在本章中，我们将学习一些经典且实用的基础算法，包括数字的分离与合成、素数判断、最大公约数求解以及如何巧妙地运用数组下标。这些算法是编程的基石，掌握它们对于理解更复杂的算法逻辑至关重要。希望大家能认真练习，深入理解算法背后的数学思想与逻辑。第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<<"";课堂小结●数字处理：掌握了数字分离与合成的基本方法，能够处理复杂的数值运算。