本文為大家分享了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;}以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持VEVB武林網。
新聞熱點
疑難解答
