经典算法设计题目(二)

《经典算法设计题目(二)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、算法设计（2）张健13880954950一、计数、求和、求阶乘等简单算法此类问题都要使用循环，要注意根据问题确定循环变量的初值、终值或结束条件，更要注意用来表示计数、和、阶乘的变量的初值。一、计数、求和、求阶乘等简单算法例：用随机函数产生100个[0，99]范围内的随机整数，统计个位上的数字分别为1，2，3，4，5，6，7，8，9，0的数的个数并打印出来。本题使用数组来处理，用数组a[100]存放产生的确100个随机整数，数组x[10]来存放个位上的数字分别为1，2，3，4，5，6，7，8，9，0的数的个数。即个位是1的个数存放在

2、x[1]中，个位是2的个数存放在x[2]中……个位是0的个数存放在x[10]。二、求两个整数的最大公约数、最小公倍数分析：求最大公约数的算法思想：(最小公倍数=两个整数之积/最大公约数)(1)对于已知两数m，n，使得m>n；(2)m除以n得余数r；(3)若r=0，则n为求得的最大公约数，算法结束；否则执行(4)；(4)m←n，n←r，再重复执行(2)。例如:求m=14,n=6的最大公约数.mnr1462620三、排序问题1．选择法排序（升序）基本算法：1）对有n个数的序列（存放在数组a(n)中），从中选出最小的数，与第1个

3、数交换位置；2）除第1个数外，其余n-1个数中选最小的数，与第2个数交换位置；3）依次类推，选择了n-1次后，这个数列已按升序排列。三、排序问题2．冒泡法排序（升序）基本算法：(将相邻两个数比较，小的调到前头)1）有n个数（存放在数组a(n)中），第一趟将每相邻两个数比较，小的调到前头，经n-1次两两相邻比较后，最大的数已“沉底”，放在最后一个位置，小数上升“浮起”；2）第二趟对余下的n-1个数（最大的数已“沉底”）按上法比较，经n-2次两两相邻比较后得次大的数；3）依次类推，n个数共进行n-1趟比较，在第j趟中要进行n-j次两

4、两比较。三、排序问题3．合并法排序（将两个有序数组A、B合并成另一个有序的数组C，升序）基本算法：1）先在A、B数组中各取第一个元素进行比较，将小的元素放入C数组；2）取小的元素所在数组的下一个元素与另一数组中上次比较后较大的元素比较，重复上述比较过程，直到某个数组被先排完；3）将另一个数组剩余元素抄入C数组，合并排序完成。四、查找问题1．顺序查找法（在一列数中查找某数x）基本算法：一列数放在数组a[1]---a[n]中，待查找的数放在x中，把x与a数组中的元素从头到尾一一进行比较查找。用变量p表示a数组元素下标，p初值为1，使

5、x与a[p]比较，如果x不等于a[p]，则使p=p+1，不断重复这个过程；一旦x等于a[p]则退出循环；另外，如果p大于数组长度，循环也应该停止。四、查找问题思考：将上面程序改写一查找函数Find，若找到则返回下标值，找不到返回-1基本算法：一列数放在数组a[1]---a[n]中，待查找的关键值为key，把key与a数组中的元素从头到尾一一进行比较查找，若相同，查找成功，若找不到，则查找失败。四、查找问题2．折半查找法（只能对有序数列进行查找）基本思想：设n个有序数（从小到大）存放在数组a[1]----a[n]中，要查找的数为x。

6、用变量bot、top、mid分别表示查找数据范围的底部（数组下界）、顶部（数组的上界）和中间，mid=(top+bot)/2，折半查找的算法如下：（1）x=a(mid)，则已找到退出循环，否则进行下面的判断；（2）xa(mid)，x必定落在mid+1和top的范围之内，即bot=mid+1；（4）在确定了新的查找范围后，重复进行以上比较，直到找到或者bot>=top。五、插入法把一个数插到有序数列中，插入后数列仍然有序基本算法：n个有序

7、数（从小到大）存放在数组a(1)—a(n)中，要插入的数x。首先应确定x插在数组中的位置P。六、迭代法算法思想：对于一个问题的求解x，可由给定的一个初值x0，根据某一迭代公式得到一个新的值x1，这个新值x1比初值x0更接近要求的值x；再以新值作为初值，即：x1→x0,重新按原来的方法求x1,重复这一过和直到

8、x1-x0

9、<ε(某一给定的精度)。此时可将x1作为问题的解。例：用迭代法求某个数的平方根。已知求平方根的迭代公式为：七、穷举法穷举法（又称“枚举法”）的基本算法思想是：一一列举各种可能的情况，并判断哪一种可能是符合要求的解，

10、这是一种“在没有其它办法的情况的方法”，是一种最“笨”的方法，然而对一些无法用解析法求解的问题往往能奏效，通常采用循环来处理穷举问题。例：将一张面值为100元的人民币等值换成100张5元、1元和0.5元的零钞，要求每种零钞不少于1张