C语言实现分治法实例

2020-01-26 13:39:28

字体：大中小

来源：转载

供稿：网友

本文为大家分享了C语言实现分治法实例代码，供大家参考，具体内容如下

使用分治法求最大值

这个函数将数组a[l]...a[r]分成a[l],...,a[m]和a[m+1],...a[r]两部分,分别求出每一部分的最大元素(递归地),并返回较大的那一个作为整个数组的最大元素.如果数组大小是偶数,则两部分大小相等;如果是奇数,第一部分比第二部分的大小大1.

#include <cstdio>#include <cstdlib>#include <algorithm>#include <malloc.h>using namespace std;#define OK 1#define ERROR -1#define TRUE 1#define FALSE 0typedef int Status; int Max(int a[], int l, int r){  int u, v, m = (l + r) / 2;  //当区间中只有一个元素,递归终止,并将该元素返回  if(l == r)    return a[l];  //递归原区域的左边  u = Max(a, l, m);  //递归原区域的右边  v = Max(a, m+1, r);  //返回最大值  return (u>v)?u:v;}int main(){  //举例验证  int a[7] = {6, 5, 3, 4, 7, 2, 1};  int maxx = Max(a, 0, 6);  printf("%d/n", maxx);  return 0;}

汉诺塔的解

我们把盘子(递归地)移动到c上的方案是,将除了最下面的盘子之外的所有盘子移到b上,然后将做下面的盘子移到c上,然后(递归地)再将其他盘子移回到最下面的盘子上面.

#include <cstdio>#include <cstdlib>#include <algorithm>#include <malloc.h>using namespace std;#define OK 1#define ERROR -1#define TRUE 1#define FALSE 0typedef int Status;//输出盘子的移动void shift(int n, char x, char y){  printf("Move %d disk: %c ---------> %c/n", n, x, y);}void hanoi(int n, char a, char b, char c){  //递归终止的条件  if(n == 1)  {    //将a上最下面的盘子移到c上    shift(n, a, c);    return;  }  //以c为中间轴,将a上的盘子移动到b上  hanoi(n-1, a, c, b);  shift(n, a, c);  //以a为中间轴,将b上的盘子移动到c上  hanoi(n-1, b, a, c);}int main(){  //举例验证  hanoi(4, 'a', 'b', 'c');  return 0;}

使用分治法在尺子上画刻度

要在尺子上画刻度线,我们首先在左半边画刻度线,然后在中间画一条最长的刻度线,最后在右半边画刻度线.

#include <cstdio>#include <cstdlib>#include <algorithm>#include <malloc.h>using namespace std;#define OK 1#define ERROR -1#define TRUE 1#define FALSE 0typedef int Status;//画线void mark(int m, int h){  //由于无法实际表示刻度线之间的高度差,故用实际数字来体现  printf("%d ", h);}//划分该区域内的刻度void rule(int l, int r, int h){  //找到该区域的中间  int m = (l + r) / 2;  //当高度大于0  if(h)  {    //划分小区域    rule(l, m, h-1);    //画线    mark(m, h);    //划分小区域    rule(m+1, r, h-1);  }}int main(){  //举例验证  rule(0, 14, 4);  return 0;}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持武林网。

上一篇：C语言分治法实现归并排序

下一篇：C语言实现快速排序