news 2026/6/20 10:55:01

C++递归与分治算法原理示例详解

作者头像

张小明

前端开发工程师

1.2k 24
文章封面图
C++递归与分治算法原理示例详解

1. 汉诺塔问题

递归算法，分为 3 步：将 n 个 a 上的盘子借助 c 移动到 b

① 将 n-1 个 a 上的盘子借助 b 移动到 c

② 将 a 上的盘子移动到 b

③ 将 c 上的 n-1 个盘子借助 a 移动到 b

所有盘子都移动到 b 上了

1

2

3

4

5

6

7

8

9

10

11

voidhanoi(intn,chara,charb,charc)//将n个碟子从a借助c 移到b

{

if(n==0)

return;

else

{

hanoi(n-1,a,c,b);

move(a,b);

hanoi(n-1,c,b,a);

｝

｝

2. 全排列问题

问题描述：设R={r1,r2,…,rn}是要进行排列的n个元素，求R的全排列Perm(R)。

算法思路：

① 从 n 个数中取出数列的第一个数，然后不断将数列中剩余的数与第一个数进行交换，计算剩余 n-1 个数的全排列。

② 对 n - 1 个数进行同样的递归操作，当交换的第一个数的下标 k 和 序列末尾的 m 相同时，说明前置所有数都已经交换完成，进行输出。

③ 递归结束后进行状态回调，保证不影响下一次递归的进行。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

voidPerm(intlist[],intk,intm)

{

if(k==m)

{

for(inti=0;i<m;i++）

{

cout<<list[i];

}

cout<<endl;

return;

}

for(inti=k;i<m;i++)

{

swap(list[k], list[i])

Perm(list, k+1, m)

swap(list[k], list[i])

}

}

3. 利用递归与分治策略寻找最大值

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

#include <bits/stdc++.h>

usingnamespacestd;

intfind_max(inta[],intfrom,intto){

if(from>=to)returna[from];

intmid = (from + to)/2;

intv1 = find_max(a, from, mid);

intv2 = find_max(a, mid+1, to);

if(v1<=v2)returnv2;

elsereturnv1;

}

intmain()

{

intn, a[100000];

cin>>n;

for(inti=0;i<n;i++){

cin>>a[i];

}

cout<<find_max(a, 0, n-1);

}

4. 归并排序

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

#include <bits/stdc++.h>

usingnamespacestd;

voidmerge_array(inta[],intfrom,intmid,intto){

inttmp[100000], idx_tmp=0;

inti,j;

for(i=from, j=mid+1; i<=mid && j<=to;){

if(a[i]<=a[j]) tmp[idx_tmp++] = a[i++];

elsetmp[idx_tmp++] = a[j++];

}

while(i<=mid) tmp[idx_tmp++]=a[i++];

while(j<=to) tmp[idx_tmp++]=a[j++];

for(inti=from,j=0; i<=to;i++) a[i] = tmp[j++];

}

voidmerge_sort(inta[],intfrom,intto){

if(from < to){

intmid = (from + to)/2;

merge_sort(a, from, mid);

merge_sort(a, mid+1, to);

merge_array(a, from, mid, to);

}

}

intmain()

{

intn, a[100000];

cin>>n;

for(inti=0;i<n;i++){

cin>>a[i];

}

merge_sort(a, 0, n-1);

for(inti=0;i<n;i++){

printf("%d ", a[i]);

}

}

5. 快速排序

图解快速排序：//www.jb51.net/article/113769.htm

递归 + 交换法

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

#include <bits/stdc++.h>

usingnamespacestd;

intsort_array(inta[],intfrom,intto)

{

intbase = a[from];

inti,j;

for(i=from, j=to; i<j;)

{

while(a[j]>=base && i<j) j--;

while(a[i]<=base && i<j) i++;

//function swap()

if(i<j){

intt=a[i];

a[i]=a[j];

a[j]=t;

}

}

a[from]=a[i];

a[i]=base;

returni;

}

voidquick_sort(inta[],intfrom,intto)

{

if(from>=to)return;

inti = sort_array(a, from, to);

quick_sort(a, from, i-1);

quick_sort(a, i+1, to);

}

intmain()

{

intn, a[100000];

cin>>n;

for(inti=0;i<n;i++){

cin>>a[i];

}

quick_sort(a, 0, n-1);

for(inti=0;i<n;i++){

printf("%d ", a[i]);

}

}

6. 棋盘覆盖问题

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

#include <bits/stdc++.h>

usingnamespacestd;

intnum=0;

inta[1000][1000];

voidmake_chess(intpx,intpy,inttx,intty,intsze){

if(sze==1)return;

num++;

sze/=2;

//左上

if(px<tx+sze && py<ty+sze)

{

a[tx+sze-1][ty+sze]=num;

a[tx+sze][ty+sze-1]=num;

a[tx+sze][ty+sze]=num;

}

//右上

if(px<tx+sze && py>=ty+sze)

{

a[tx+sze-1][ty+sze-1]=num;

a[tx+sze][ty+sze-1]=num;

a[tx+sze][ty+sze]=num;

}

//左下

if(px>=tx+sze && py<ty+sze)

{

a[tx+sze-1][ty+sze-1]=num;

a[tx+sze-1][ty+sze]=num;

a[tx+sze][ty+sze]=num;

}

//右下

if(px>=tx+sze && py>=ty+sze)

{

a[tx+sze-1][ty+sze-1]=num;

a[tx+sze-1][ty+sze]=num;

a[tx+sze][ty+sze-1]=num;

}

//左上

if(px<tx+sze && py<ty+sze) make_chess(px, py, tx, ty, sze);

elsemake_chess(tx+sze-1, ty+sze-1, tx, ty, sze);

//右上

if(px<tx+sze && py>=ty+sze) make_chess(px, py, tx, ty+sze,sze);

elsemake_chess(tx+sze-1, ty+sze, tx, ty+sze,sze);

//左下

if(px>=tx+sze && py<ty+sze) make_chess(px, py, tx+sze, ty,sze);

elsemake_chess(tx+sze, ty+sze-1, tx+sze, ty, sze);

//右下

if(px>=tx+sze && py>=ty+sze) make_chess(px, py, tx+sze, ty+sze, sze);

elsemake_chess(tx+sze, ty+sze, tx+sze, ty+sze, sze);

}

intmain()

{

intk, px, py;

inttx=0, ty=0;

cin>>k>>px>>py;

make_chess(px-1, py-1, tx, ty, k);

for(inti=0; i<k; i++){

for(intj=0; j<k; j++){

printf("%2d ", a[i][j]);

}

cout<<endl;

}

}

以上就是C++递归与分治算法原理示例详解的详细内容

版权声明: 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：809451989@qq.com进行投诉反馈，一经查实，立即删除！
网站建设 2026/6/20 10:45:58

FPGA实战：基于Verilog的直流电机PWM调速系统设计与Quartus II实现

1. 项目背景与核心原理 直流电机控制是嵌入式系统和自动化领域的基础课题&#xff0c;而FPGA凭借其并行处理能力和硬件可编程特性&#xff0c;成为实现高精度电机控制的理想平台。这次我们要做的&#xff0c;是通过Verilog硬件描述语言在Quartus II环境中&#xff0c;构建一个…

作者头像 李华
网站建设 2026/6/20 10:43:58

McMullen曲线与Hodge猜想的代数几何研究

1. McMullen曲线与Hodge猜想的研究背景在代数几何与数论的前沿交叉领域&#xff0c;McMullen曲线与Hodge猜想的关联研究代表了当前数学研究的一个重要方向。这项工作的核心在于理解复流形上调和形式的代数表示问题&#xff0c;特别是通过研究特殊几何结构在Hodge理论中的表现来…

作者头像 李华
网站建设 2026/6/20 10:43:40

四款新锐图像生成模型本地部署与工作流适配实战

1. 项目概述&#xff1a;四款新锐图像生成模型的实战横评&#xff0c;不是参数堆砌&#xff0c;而是真实出图节奏与工作流适配度的硬核拆解最近两周&#xff0c;朋友圈和几个技术群被 Z-Image-Turbo、Flux.2 Dev、Ovis-Image 和 LongCat-Image 这四个名字刷屏了。它们不是又一批…

作者头像 李华
网站建设 2026/6/20 10:42:00

电子书转有声书终极指南：如何用AI技术让文字开口说话

电子书转有声书终极指南&#xff1a;如何用AI技术让文字开口说话 【免费下载链接】ebook2audiobook Generate audiobooks from e-books, voice cloning & 1158 languages! 项目地址: https://gitcode.com/GitHub_Trending/eb/ebook2audiobook 想要将电子书转换为专业…

作者头像 李华
网站建设 2026/6/20 10:41:51

Elsevier投稿状态追踪：3分钟安装Chrome插件，告别手动刷新焦虑

Elsevier投稿状态追踪&#xff1a;3分钟安装Chrome插件&#xff0c;告别手动刷新焦虑 【免费下载链接】Elsevier-Tracker 项目地址: https://gitcode.com/gh_mirrors/el/Elsevier-Tracker 还在为Elsevier投稿系统的繁琐查询而烦恼吗&#xff1f;每次登录系统查看审稿进…

作者头像 李华
网站建设 2026/6/20 10:33:55

MonoScene常见问题解答：从安装错误到性能瓶颈的解决方案

MonoScene常见问题解答&#xff1a;从安装错误到性能瓶颈的解决方案 【免费下载链接】MonoScene [CVPR 2022] "MonoScene: Monocular 3D Semantic Scene Completion": 3D Semantic Occupancy Prediction from a single image 项目地址: https://gitcode.com/gh_mir…

作者头像 李华