C语言实现分治法实例

本文为大家分享了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 0
typedef 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 0
typedef 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 0
typedef 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;
}

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

(0)

相关推荐

  • 算法详解之分治法具体实现

    分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题,这些子问题相互独立且与原问题性质相同.求出子问题的解,就可得到原问题的解. 分治法解题的一般步骤: (1)分解,将要解决的问题划分成若干规模较小的同类问题: (2)求解,当子问题划分得足够小时,用较简单的方法解决: (3)合并,按原问题的要求,将子问题的解逐层合并构成原问题的解. 一言以蔽之:分治法的设计思想是,将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之. 在认识分治之前很有必要先了解一下递

  • C语言实现分治法实例

    本文为大家分享了C语言实现分治法实例代码,供大家参考,具体内容如下 使用分治法求最大值 这个函数将数组a[l]...a[r]分成a[l],...,a[m]和a[m+1],...a[r]两部分,分别求出每一部分的最大元素(递归地),并返回较大的那一个作为整个数组的最大元素.如果数组大小是偶数,则两部分大小相等;如果是奇数,第一部分比第二部分的大小大1. #include <cstdio> #include <cstdlib> #include <algorithm> #i

  • C语言分治法实现归并排序

    本文实例为大家分享了C语言实现归并排序的具体代码,供大家参考,具体内容如下 归并排序的基本思想: 将两个及其以上的有序表合并为一张有序表,把待排序序列通过分治法分为若干个有序子序列,然后每两个子序列合并为一个子序列,经过多次合并后整合为一张有序表. 排序过程如图: 代码如下: #include "stdio.h" #define MAX 100 int is1[MAX],is2[MAX];//原数组is1,临时空间数组is2 void merge(int low,int mid,int

  • Python分治法定义与应用实例详解

    本文实例讲述了Python分治法定义与应用.分享给大家供大家参考,具体如下: 分治法所能解决的问题一般具有以下几个特征: 1) 该问题的规模缩小到一定的程度就可以容易地解决 2) 该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质. 3) 利用该问题分解出的子问题的解可以合并为该问题的解: 4) 该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子子问题. 第一条特征是绝大多数问题都可以满足的,因为问题的计算复杂性一般是随着问题规模的增加而增加: 第二条特征是应用

  • Java分治法与二分搜索算法实例分析

    本文实例讲述了Java分治法与二分搜索算法.分享给大家供大家参考,具体如下: 1.分治法 分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题,这些子问题相互独立且与原问题相同.递归的解这些子问题,然后将各子问题的解合并得到原问题的解. 分治法所能解决的问题一般具有以下几个特征: 1) 该问题的规模缩小到一定的程度就可以容易地解决 2) 该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质. 3) 利用该问题分解出的子问题的解可以合并为该问题的解: 4) 该问题所分解

  • python使用分治法实现求解最大值的方法

    本文实例讲述了python使用分治法实现求解最大值的方法.分享给大家供大家参考.具体分析如下: 题目: 给定一个顺序表,编写一个求出其最大值和最小值的分治算法. 分析: 由于顺序表的结构没有给出,作为演示分治法这里从简顺序表取一整形数组数组大小由用户定义,数据随机生成.我们知道如果数组大小为 1 则可以直接给出结果,如果大小为 2则一次比较即可得出结果,于是我们找到求解该问题的子问题即: 数组大小 <= 2.到此我们就可以进行分治运算了,只要求解的问题数组长度比 2 大就继续分治,否则求解子问题

  • Java基于分治法实现的快速排序算法示例

    本文实例讲述了Java基于分治法实现的快速排序算法.分享给大家供大家参考,具体如下: package cn.nwsuaf.quick; /** * 随机产生20个数,并对其进行快速排序 * * @author 刘永浪 * */ public class Quick { /** * 交换函数,实现数组中两个数的交换操作 * * @param array * 待操作数组 * @param i * 交换数组的第一个下标 * @param j * 交换数组的第二个下标 */ public static

  • python分治法求二维数组局部峰值方法

    题目的意思大致是在一个n*m的二维数组中,找到一个局部峰值.峰值要求大于相邻的四个元素(数组边界以外视为负无穷),比如最后我们找到峰值A[j][i],则有A[j][i] > A[j+1][i] && A[j][i] > A[j-1][i] && A[j][i] > A[j][i+1] && A[j][i] > A[j][i-1].返回该峰值的坐标和值. 当然,最简单直接的方法就是遍历所有数组元素,判断是否为峰值,时间复杂度为O(n^2

  • C语言指针基础知识实例讲解

    对程序进行编译的时候,系统会把变量分配在内存单位中,根据不同的变量类型,分配不同的字节大小.比如int整型变量分配4个字节,char字符型变量分配1个字节等等.被分配在内存的变量,可以通过地址去找到,内存区每一个字节都有一个编号,地址也可以形象的理解成我们生活中的住址,通过住址找到每一个人所在的地方.指针作为一个变量用来存放地址,可以通过指针来改动变量. 上图就是一个简单的定义一个一级指针变量和利用指针改变变量数值的过程.int*表示整型指针,*p表示解引用操作,就是利用指针找到a的地址然后再改

  • R语言绘制空间热力图实例讲解

    先上图 R语言的REmap包拥有非常强大的空间热力图以及空间迁移图功能,里面内置了国内外诸多城市坐标数据,使用起来方便快捷. 开始首先安装相关包 install_packages("devtools") install_packages("REmap") library(devtools) library(REmap) 我们来试试其强大的城市坐标获取功能 city<- c("beijing","上海") get_geo_

随机推荐