C language implements divide and conquer example

This article shares the C language implementation divide and conquer example code for your reference, specific content is as follows

Use divide and conquer to find the maximum

This function takes the array a[l]... a [r] into a [l],... , a [m] and a [m + 1],... a[r] two parts, find the largest element of each part (recursively), and return the larger one as the largest element of the entire array. If it's odd, part 1 is 1 bigger than part 2.

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <malloc.h>
using namespace std;
#define OK 1
#define ERROR -1
#define TRUE 1
#define FALSE 0
typedef int Status;
 
int Max(int a[], int l, int r)
{
  int u, v, m = (l + r) / 2;
  // When there's only one in the interval 1 An element , The recursion terminates , And returns the element 
  if(l == r)
    return a[l];
  // To the left of the recursion region 
  u = Max(a, l, m);
  // To the right of the recursion region 
  v = Max(a, m+1, r);
  // Return maximum value 
  return (u>v)?u:v;
}
int main()
{
  // For example verification 
  int a[7] = {6, 5, 3, 4, 7, 2, 1};
  int maxx = Max(a, 0, 6);
  printf("%d\n", maxx);
  return 0;
}

The solution to the Tower of Hannot

Our solution for moving plates (recursively) to c is to move all but the bottom plate to b, then move the bottom plate to c, and then (recursively) move the others back to the bottom plate.

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <malloc.h>
using namespace std;
#define OK 1
#define ERROR -1
#define TRUE 1
#define FALSE 0
typedef int Status;
// Output plate movement 
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)
{
  // Conditions for recursive termination 
  if(n == 1)
  {
    // will a Top the bottom plate to move to c on 
    shift(n, a, c);
    return;
  }
  // In order to c As the intermediate shaft , will a The plate moves up to b on 
  hanoi(n-1, a, c, b);
  shift(n, a, c);
  // In order to a As the intermediate shaft , will b The plate moves up to c on 
  hanoi(n-1, b, a, c);
}
int main()
{
  // For example verification 
  hanoi(4, 'a', 'b', 'c');
  return 0;
}

Use divide-and-conquer to draw a scale on a ruler

To draw a scale on a ruler, we first draw a scale on the left half, then the longest scale in the middle, and finally the right half.

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <malloc.h>
using namespace std;
#define OK 1
#define ERROR -1
#define TRUE 1
#define FALSE 0
typedef int Status;
// Line drawing 
void mark(int m, int h)
{
  // It is not possible to actually represent the height difference between the scales , So let's use actual Numbers 
  printf("%d ", h);
}
// Divide the scales within the area 
void rule(int l, int r, int h)
{
  // Find the middle of the area 
  int m = (l + r) / 2;
  // When the height is greater than 0
  if(h)
  {
    // Divide into small areas 
    rule(l, m, h-1);
    // Line drawing 
    mark(m, h);
    // Divide into small areas 
    rule(m+1, r, h-1);
  }
}
int main()
{
  // For example verification 
  rule(0, 14, 4);
  return 0;
}