1算法与数据结构

算法与数据结构综合应用。

数值计算问题：

1、打印所有的“水仙花数”，所谓“水仙花数”是指一个三位数，其各位数字立方和等于该数字本身，例如：

2、一个数如果恰好等于它的因子之和，这个数就称为“完数”。例如：6的因子为，而6＝1＋2＋3，因此6是“完数”。编程序找出1000以内的所有完数。

3、已知四位数3025有一个待殊性质：它的前两位数字30和后两位数字25的和是55,而55的平方刚好等于该数(552=3025)。试编一程序打印具有这种性质的所有四位数。

分析：从32至99之间的数的平方是四位数，满足题目条件的数必须在这些四位数之内选择。分别把它们按前两位数后两位数进行分离，验证分离后的两个两位数之和的平方是否等于分离前的那个四位数，若等于即打印输出，否则放弃。

4、求两个自然数，其和是667，最小公倍数与最大公约数之比是120：1。（例如：115，552）

穷举搜索法。

穷举法也叫枚举法，它的基本思想是依题目的部分条件确定答案的大致范围，在此范围内对所有可能的情况逐一验证，直到全部情况验证完。若某个情况经验证符合题目的全部条件，则为本题的一个答案。若全部情况经验证后都不符合题目的全部条件，则本题无答案。

用穷举法解题时，答案所在的范围总是要求是有限的，怎样才能使我们不重复的、一个不漏、一个不增的逐个列举答案所在范围的所有情况，就是本节所讲的“列举方法”。

列举方法按答案的数据类型，常用的有下面三种。

顺序列举：顺序列举是指答案范围内的各种情况很容易与自然数对应甚至就是自然数，可以按自然数的变化顺序去列举。

排列列举：有时答案的数据形式是一组数的排列，列举出所有答案所在范围内的排列，称为排列列举。

组合列举：（参考组合数学知识）当答案的数据形式为一些元素的组合时，往往需要用组合列举。从几个不同的元素中任取m(m n)个元素组成的一组，就叫做从n个元素取m个元素的一个组合。

组合是无序的，如：123，132，321，312，213，231是同一个组合（但是6个不同的排列）。

例题：问题提出】

找出n个自然数（1，2，3，4，…n）中r个数的组合。例如n=3,r=2，所有的组合为：12,13,23；n＝5，r＝3，所有的情况为：

123，124，125，134，135，145，234，235，245，345。

算法】当r＝3时用3重循环实现。

for i=5 to1

for j=5 to1

for k=5 to 1

if i<>j and i!=k and j<>k and i>j and j>k

print i,j,k

练习：1、求出具有下列两个性质的最小自然数n：

1）、n是个6位数。

2）、若将n的各位数移到其余各位之前，所得的新数是n的4倍。

递推法：例题：

运动会连续开了n天，一共发了m枚奖章，第一天发1枚并剩下（m－1）枚的1/7，第二天发2枚并剩下的1/7，以后每天按规律发放奖章，在最后一天即第n天发剩下的n枚奖章。问运动会一共开了多少天？一共发了几枚奖章？

贪心算法一、算法思想。

贪心法的基本思路：

—从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。

该算法存在问题：

1. 不能保证求得的最后解是最佳的；

2. 不能用来求最大或最小解问题；

3. 只能求满足某些约束条件的可行解的范围。

实现该算法的过程：

从问题的某一初始解出发；

while 能朝给定总目标前进一步 do

求出可行解的一个解元素；

由所有解元素组合成问题的一个可行解；

二、例题分析。

1、[背包问题]有一个背包，背包容量是m=150。有7个物品，物品可以分割成任意大小。

要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。

分析：目标函数： ∑pi最大。

约束条件是装入的物品总重量不超过背包容量：∑wi<=m( m=150)

1）根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？

2）每次挑选所占空间最小的物品装入是否能得到最优解？

3）每次选取单位容量价值最大的物品，成为解本题的策略。

简单背包问题。

问题描述] 背包是一个简单的递归问题，要求是从n件物品中抽取几件，使之质量一定。该程序只求一组解。

输入：[keyboard] 输出：[screen]

no answer!

问题分析] 使用递归算法完成。每件物品只有放入，不放入两种情况。

program knapprog;

constm = 5;

varitem: array[1..m] of integer;

i, w: integer;

function knap(a, b: integer): boolean;

beginif item[a] =b then

beginknap :=true; write(item[a]: 8);

exit;end;

if ((item[a] >b) and (a = m)) then

beginknap :=false;

exit;end;

if knap(a + 1, b - item[a]) then

beginknap :=true; write(item[a]: 8);

exit;end;

if not knap(a + 1, b) then knap :=false;

end;begin

writeln('please input item weights:')

for i :=1 to m do

read(item[i]);

writeln('total weight:')

readln(w);

writeln;

if not knap(1, w) then writeln('no answer!!'

readln;

end. 快速排序。

快速排序是基于分治策略的一个排序算法。按照分治法的思想分析快速排序：

1）分解(divide) 以元素a[p]为基准元素将a[p：q-1]划分为三段a[p：q-1]，a[q]和a[q+1：

r]，使得a[p：q-1]中任何一个元素都小于a[q]，a[q+1：r]中任何一个元素大于等于a[q]，下标q在划分中确定。

2）递归求解(conquer) 通过递归调用快速排序算法分别对a[p:q-1] 和a[q+1:r]进行排序。

3）合并(merge) 由于a[p:q-1] 和a[q+1:r]的排序都是在原位置进行的，所以不必进行任何合并操作就已经排好序了。

在上面三个步骤中，第一步：分解是关键。一次快速排序确定划分元素的位置，具体参见排序算法---快速排序

模拟。随机函数及其应用：

解决有些问题需要有一个产生随机数的函数。如果你使用的机器的pascal未提供产生随机数的标准函数，这里就向你介绍一个实现这个要求的函数，并举若干应用例子。

假定问题要在整区间[a··b]集合中随机的选取一个整数r。如[1··2]上表示掷一枚硬币的正面或反面的结果；[1··6]上表示投一粒骰子的面值等。连续掷币，或连续投骰子得到的结果序列：

r1， r2， …称为随机序列。程序不能严格地产生[a··b]上的随机序列，但能用数学方法产生满足应用上所要求的近似随机序列的随机数，通常称为伪随机数。程序产生伪随机数的最通常的方法是线性同余法。

下面函数randomint就是这一方法编制的产生[a··b]上伪随机数的函数。

function randomint(a , b: integer) :integer;

产生区间[a··b]上的一个整数，使用并改变整体变量seed}

constmaxseed = 65536;

multiplier = 25173;

adder = 13849;

beginseed: =multiplier * seed+ adder) mod maxseed;

randomint :=a + seed *(b-a +1) div maxseed

end;函数randomint通过保留一个整体变量seed而产生伪随机数。变量seed由主程序提供初值。为了产生一个伪随机数，应用线性同余法改变seed的值。

seed 的取值范围0··maxseed被分成(b-a+1)等分，每个等分内的值代表[a··b]上的一个数。

函数randomint不满足前面建议的“函数不应改变整体量值”这一规则。但是，为了满足每次调用randomint能得到一个不同的值，这又是必需的。

例1：利用函数randomint编制的一个20以内整数加法教学程序。计算机随机产生两个整数，让学生回答。

简单的算法分析：

a.产生第一个随机数x，x:=randomint(1,19)以保证两个数相加不超过20。

b.产生第二个随机数y，y:=randomint(1,20-x)以保证两个数相加不超过20。

源程序：xoi00_

program ******drill(input,output);

varseed,i:integer;

x,y,answer:integer;

function randomint(a,b:integer):integer;

constmaxseed=65536;

multiplier=25173;

adder=13849;

1算法与数据结构

1 数据结构与算法

算法与数据结构 1 1

考点1数据结构与算法

其他用户还读了