五大算法基本思想举例

1. 希尔排序的详解

希尔排序基本思想：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。

举例说明：

对于这样一个无序的数组5932611817410，想把它变成顺序递增的数组1234567891011。先隔3个元素取一次：把5284取了出来，往后搓一位，把96110取出来，再往后搓一位，又把3117取出来。分别对这三个小组排序成为递增的序列，再插回去，如图：

于是得到了第一趟排序的结果：2134675911810.现在再以2为间隔重复以上步骤（这次得到的是两个小组）得到了2134576811910。最后再以1为间隔再搞一次（实际上这一步就是从左到右两两比较，调整位置），就得到了想要的结果。

这就是希尔排序，其要义就是先进行宏观调整，再进行微观调整。

2. 两个数最大公因数怎么找

找两个数的最大公因数可以通过欧几里得算法（辗转相除法）实现。

本文将从算法流程、应用举例等角度进行介绍，并提供拓展知识，帮助读者全面了解最大公因数的概念和计算方法。

一、欧几里得算法流程

1.辗转相除法

欧几里得算法，也称为辗转相除法，是一种计算两个整数的最大公约数的算法。其基本思想是：假设两个整数为a和b，如果a>b，则a和b的最大公因数等于b和a%b（a除以b取余）的最大公因数。

如果b>a，则a和b的最大公因数等于a和b%a（b除以a取余）的最大公因数。不断重复这个过程，直到其中一个数为0时停止，此时另一个非零数即为这两个数的最大公因数。

三、拓展知识

1.最大公约数的性质

最大公因数有以下几个基本性质：

（1）互质性：两个数a、b的最大公约数为1时，称a和b互质。

（2）倍数性：设p是正整数，a、b为整数，则(a*p,b*p)的最大公约数等于p*(a,b)。

（3）整除性：若a整除b，则(a,b)=a。

2.欧几里得算法适用范围

欧几里得算法适用于计算整数之间的最大公约数。

3. 用穷举法求解问题的基本过程

1．If语句和For语句

If语句在穷举算法中一般用块结构居多，形式为：If条件Then

Else语句可以没有

End If

For语句结构形式为：

For循环变量＝初值To终值Step步长

循环体语句

Next循环变量

3．穷举算法的应用

(1)使用穷举算法时，可能解的范围是非常明确的，可能解的个数也是有限的，否则无法用此算法。

(2)穷举算法应用举例：猜密码、寻找有特定要求的数字、最优方案等。

4. 5.贪心算法的核心思想。6.什么是递归什么是迭代两者的区别，举例说明。7.回溯的含义是什么举例

1、贪心算法主要是把问题分成很多局部问题，用局部最优解合成整体最优解。因此使用这种算法需要此问题满足两个条件，一个是能够分成多个能够求解的局部问题，第二个就是局部问题的解能够合成最优解。和动态规划、回溯等相比差别就是再不回溯的前提下找出整体最优解或者接近最优解，速度快但应用有比较大的限制。

2、迭代也叫递推，通过重复执行某一步骤或者函数来求得计算结果
递归是指函数中直接或者间接调用自身
举例：
求a乘以2的10次方等于几
迭代：
for (i=0;i<10;i++)
a *= 2;

递归：
int db(int a,int num)
{
if (num<10)
return 2 * db(a,num+1);
else
return 1;
}

db(a,0);

3、回溯的含义就是在搜索问题的状态过程中，如果不能继续前进，再向后回到岔口，换一条路继续搜索，直到搜索完所有状态或者查找到需要的状态。
举例：（最典型的就是树的深度搜索，下面举一个简单的例子）
int a[10]={5,3,7,9,3,2,5,6,9,1};//从3开始查找1
int read[10]=(0);//是否查找过
int readNum = 0;//查找过的个数
int forward = 1;//1为左，2为右
int tmp = 0,index = 5;

tmp = a[index];
read[index] = 1;
readNum++;
while (tmp != 1 || readNum != 10)
{
if (forward == 1)
index --;
else
index++;
if (!read[index])
{
tmp = a[index];
read[index] = 1;
readNum++;
}

if (index <=0 || index>=9)
forward = 3 - forward;
}

5. 举例说明算法的应用

举例说明算法的应用如下：

1、递推算法（常用级数、数列求和、二分法、梯形积分法、穷举法等）。

2、排序算法（选择法、冒泡法）。

3、查找算法（顺序查找、折半查找）。

4、有序数列的插入、删除操作。

5、初等数论问题求解的有关算法（最大数、最小数、最大公约数、最小公倍数、素数等）。

6、矩阵的处理（生成、交换及基本运算）。

算法雹盯虚中的指令描述的是一个计算，当其运行时能从一个初始状态和（可能为空的）初始输入开始，经过一系列有限而清晰定义的状态，最终产生输出并停止于一个终态。一个状态到另一个状态的转移不一定是确定的。随机则御化算法在内的一些算法，包含了一些随机输入。