分治算法设计

1、福建工程学院计算机与信息科学系实验报告2010-2011学年第 一 学期 任课老师： 实验题目设计程序利用分治策略求n个数 的最大值和最小值。利用分治策略，在n个不同元素 中找出第k个最小元素。实验时间实验开始日期： 报告提交日期：实验目的、要求一、算法设计技术当我们求解某些问题时，由于这些问题要处理的数据相当多，或求解过程相当复杂，使得直接求解法在 时间上相当长，或者根本无法直接求出。对于这类问题，我们往往先把它分解成几个子问题，找到求出这几 个子问题的解法后，再找到合适的方法，把它们组合成求整个问题的解法。如果这些子问题还较大，难以解 决，可以再把它们分成几个更小的子问题，以此类推，直至可

2、以直接求出解为止。这就是分治策略的基本思 想。下面通过实例加以说明。【例】在n个元素中找出最大元素和最小元素。我们可以把这n个元素放在一个数组中，用直接比较法 求出。算法如下：void maxmin1(int A,int n,int *max,int *min) int i;*min=*max=A0;for(i=2;i *max) *max= Ai;if(Ai Aj)*max=Ai;*min=Aj; else *max=Aj;*min=Ai; return ;mid=(i+j)/2;maxmin2(A,mid+1,j,&max2,&min2);maxmin2(A,i,mid,&max1,&mi

3、n1);*max=max1max2?max1:max2;*min=min1high ) return 0;if(low=high) return low;s0=slow;while (low high) while (low s0) high-;if (low high) slow+ = shigh;while (low high & slow s0) low+;if (low high) shigh- = slow;slow = s0;return low;/分治找 K-th Numberint Select(int s, int low, int high, int k) /得到中间数的下

4、标int i = partition(s, low, high);/j为左区间长度int j = i - low + 1;/位置大就在左区间找，否则就在右区间找if (j = k)return si;else if (kmax2?max1:max2;*min=min1min2?min1:min2;实验结果记录以及与预期结果比较以及分析1清问有多傍卜巍播五厂扃输人数据：5523仔S：l I06清输入篥几个最傩*4个最小的敝为P1-OGES8 returned U cxecmtion tine : 10.893 sPfe兮弓k曰事 to continLie .由实验截图可知，实验结果与预期结果基本

5、相同。总结以及心得体会这次的分治设计是一次比较综合的训练。它考察了数组的操作，排序以及递归的思想。其中的递归对我 来说还是有些难度的，在这方面还是没有彻底掌握。通过这次课程设计，使我对以前学过的知识有重新复习 了一遍，解决了一些以前不懂得问题，使我懂得了理论与实际相结合是很重要的，从而提高自己的实际动手 编程能力和独立思考的能力。指导老师评阅意见/maxmin2( A,i,mid, &max1, &min1);/求 imid之间的最大最小值分别为maxi, mini;/ maxmin2( A,mid+1,j, &max2,& min2);/求mid+1j之间的最大最小值分别为max2, min

6、2;/比较max1和max2,大的就是最大值；/比较min1和min2,小的就是最小值；int main()(int i,n;int A100;int max, min;printf厂请输入数据个数:);scanf(%d,&n);for (i=0;in;i+)scanf(%d,&Ai);printf厂您输入的数据为:n);for (i=0;in;i+)printf(%dn,Ai);printf(n);maxmin2( A, 0,n-1,&max,&min);printf(最大值为：%dn 最小值为：d,max,min);2 .利用分治策略，在n个不同元素中找出第k个最小元素。#include

7、/一次快速排序int partition(int s, int low, int high)(if (low high ) return 0;if(low=high) return low;s0=slow;while (low high)(while (low s0) high-;if (low high) slow+ = shigh;while (low high & slow s0) low+;if (low high) shigh- = slow;slow = s0;return low;/分治找 K-th Numberint Select(int s, int low, int hig

8、h, int k)(/得到中间数的下标int i = partition(s, low, high);/j为左区间长度int j = i - low + 1;/位置大就在左区间找，否则就在右区间找if (j = k)return si;else if (kj)return Select(s, low, i, k);else return Select(s, i+1, high, k-j);int main()(int n;int low, high, k;int a20;printf(请问有多少个数要输入？n);scanf(%d,&n);printf(请输入数据:n);for (int i =

9、 1; i = n; i+)scanf(%d,&ai);printf(n);printf(请输入第几个最小值：n);scanf(%d,&k);printf(第%d 个最小的数为：d,k,Select(a, 1, n, k);指导老师：年 月 日1.设计程序利用分治策略求n个数的最大值和最小值。#includevoid maxmin2(int A,int i,int j,int * *max,int *min)/*A存放输入的数据，i，j存放数据的范围，初值为0， n-1，*max,int *min存放最大和最小值*/ (int mid,max1,max2,min1,min2;if (i=j)*max=*min=Ai=Aj;return;if (j-1=i)if (AiAj)*max=Ai;*min=Aj