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語言實現快速排序