王道机试C++第8章递归与分治 Day35和蓝桥杯两道真题程序

第 8 章 递归与分治

递归是指:函数直接或间接调用自身的一种方法,通常可把一个复杂的大型问题层层转化为与原问题相似但规模较小的问题来求解。
递归策略只需少量的程序就可描述解题过程所需的多次重复计算,因此大大减少了程序的代码量。

8.1 递归策略

构成递归需要具备两个条件:
1) 子问题必须与原始问题相同,且规模更小。
2) 不能无限制地调用本身,必须有一个递归出口。

例:n 的阶乘

题目描述:
输入一个整数 n ,输出 n 的阶乘(每组测试用例可能包含多组数据,请注意处理)。
输入: 一个整数 n 1 <=   n <=   20
输出: n 的阶乘
样例输入:
3
样例输出:
6
递归问题思路:
代码表示:
#include <bits/stdc++.h>
using namespace std;

int Factorial(int n){
	if(n==1){
		return 1;
	}
	else{
	return Factorial(n-1)*n;
    }
}
int main() {
    int n;
    scanf("%d",&n);
    printf("%d\n", Factorial(n));
    return 0;
}

例:汉诺塔 III

题目描述:
在一块铜板上有三根杆,最左边的杆自上而下、由小到大顺序串着由 64 个圆盘构成的塔。目的是将最左边杆上的圆盘全部移到右边的杆上条件是一次只能移动一个圆盘,并且不允许大圆盘放在小圆盘的上面。
现在我们改变这个游戏的玩法:不允许直接从最左(右)边移动到最右(左)边(每次移动一定是移到中间杆或从中间杆移出),也不允许大圆盘放到小圆盘的上面。 现在有 N 个圆盘,她至少需要多少次移动才能把这些圆盘从最左边移到最右边?
输入: 包含多组数据,每次输入一个 N 值( 1 <=   N <=  35 )。
输出: 对于每组数据,输出移动最小的次数。
样例输入:
1
3
12
样例输出:
2
26
531440
代码表示:
#include <bits/stdc++.h>
using namespace std;
long long hanoi(int n){
	if(n==1){
		return 2;
	}
	else{
	return 3*hanoi(n-1)+2;
    }
}
int main() {
    int n;
    while (scanf("%d",&n)!=EOF){
    	printf("%lld",hanoi(n));
	}
    return 0;
}

思路提示:

       若从第一根杆上移动 N 个圆盘到第三根杆上需要 F[N] 次移动,那么综上所述 F[N] 的组成方式 如下:先移动 N -1个圆盘到第三根杆上需要 F[N -1] 次移动,然后将最大的圆盘移动到中间杆上需要 1 次移动,再将 N -1个圆盘移动回第一根杆上同样需要 F[N-1] 次移动,移动最大的盘子到第三根杆上需要 1 次移动,最后将 N -1个圆盘移动到第三根杆上需要 F[N -1] 次移动,于是便有了 F[N] = 3F[N -1] + 2 。也就是说,从第一根杆上移动 N 个圆盘到第三根杆上,需要三次从第一根杆上移动 N -1个圆盘到第三根杆上,外加两次对最大圆盘的移动。这样就可以将移动 N 个圆盘的问题转换为问题相同但规模更小的移动 N -1个圆盘的问题。

        递归出口:当 N 1 时,即从第一根杆上移动一个盘子到第三根杆上,所需的移动次数显而易见为 2。移动一个盘子所需次数是最底层的子问题,该子问题不可继续分解且易于求解。这便是递归的出口。


8.2 分治法

分治法字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多个子问题,子问题之间互相独立且与原问题相同或相似。之后再把子问题分成更小的子问题,以此类推,直到最后的子问题可以简单地直接求解,原问题的解即子问题的解的合并。由于分治法产生的子问题往往与原问题相同且模式更小,这就为使用递归策略求解提供了条件。在这种情况下,通过反复利用分治手段,可以使子问题的规模不断缩小,最终缩小到可以直接求解的情况。在从过程中会导致了递归过程的产生。分治与递归就像一对孪生兄弟,经常同时应用在算法设计中,这也是将分治法和递归策略放在同一章中进行讲解的原因。分治法的步骤如下:
1. :将问题分解为规模更小的子问题。
2. :将这些规模更小的子问题逐个击破。
3. :将已解决的子问题合并,最终得出“母”问题的解

例:Fibonacci(上交大复试)

题目描述

斐波那契数列{0,1,1,2,3,5,8,13,21,34,55...}由递归定义: F0=0 F1=1 Fn=Fn-1+Fn-2,n>=2 编写一个程序来计算斐波那契数列。

输入描述:每个情况都包含一个数字 n,您应该计算 Fn.(0<=n<=30) 。

输出描述:对于每种情况,在单独的行上打印一个数字 Fn,这意味着第 n 个斐波那契数列.

输入:1

输出: 1
代码表示
#include <bits/stdc++.h>
using namespace std;
int feibo(int n){
	if(n==0){
		return 0;
	}else if(n==1){
		return 1;
	}else{
		return feibo(n-1)+feibo(n-2);
	}
}
int main() {
    int n;
    while (scanf("%d",&n)!=EOF){
    	printf("%d",feibo(n));
	}
    return 0;
}

例:二叉树(北大上机)

题目描述:
如下所示,由正整数 1,2,3, …组成了一棵特殊二叉树。我们已知这棵二叉树的最后一个结点是 n 。 现在的问题是,结点 m 所在的子树中一共包括多少个结点。比如, n = 12 m = 3 ,那么上图中的结点 13, 14, 15 及后面的结点都是不存在的,结点 m 所在子树中包括的结点有 3, 6, 7, 12 ,因此结点 m 所在的子树中共有 4 个结点。
输入: 输入数据有多行,每行给出一组测试数据,包括两个整数 m n 1 <=   m <= n <=   1000000000 )。
输出: 对于每组测试数据,输出一行,该行包含一个整数,给出结点 m 所在子树中包括的结点的数目。
样例输入:
3 12
样例输出:
4
代码表示:
#include <bits/stdc++.h>
using namespace std;
int tree(int m,int n){
	if(m>n){
		return 0;//边界情况 
	}else{
		return 1+tree(2*m,n)+tree(2*m+1,n);
	}
}
int main() {
    int m,n;
    while (scanf("%d%d",&m,&n)!=EOF){
    	if(m==0){
    		break;
		}
    	printf("%d",tree(m,n));
	}
    return 0;
}


[蓝桥杯 2015 省 B] 移动距离

题目描述

X 星球居民小区的楼房全是一样的,并且按矩阵样式排列。其楼房的编号为1,2,3,⋯ 。当排满一行时,从下一行相邻的楼往反方向排号。

比如:当小区排号宽度为 6 时,开始情形如下:

1  2  3  4  5  6
12 11 10 9  8  7
13 14 15 .....

我们的问题是:已知了两个楼号 m 和 n,需要求出它们之间的最短移动距离。(不能斜线方向移动)

输入格式

输入为 3 个整数w,m,n,空格分开,都在 1到 10000 范围内。w 为排号宽度,m,n 为待计算的楼号。

输出格式

要求输出一个整数,表示 m 与 n 两楼间最短移动距离

代码表示
#include <bits/stdc++.h>
using namespace std;
int w,m,n,kx,ky,x=0,y=1;//m坐标x,y;n坐标kx,ky 
int main()
{
    scanf("%d%d%d",&w,&m,&n);
    if(n>m) swap(n,m);
    for(register int i=1;i<=m;i++)//枚举从1到m所有数的坐标
    {
    	if(y%2==1)//正方向
    	{
    		x++;
    		if(x>w) x=w,y++;
		}
		else    //反方向
		{
			x--;
			if(x<1) x=1,y++;
		}
		if(i==n) kx=x,ky=y;    //记录n的坐标
	}
	printf("%d",abs(kx-x)+abs(ky-y));
    return 0;
}
心得体会:

这个代码很巧妙,实际上所列出的数实际是什么根本就不重要,重要的是这个点所在坐标位置数的大小。以此来求解两坐标的距离。abs(kx - x)用于计算目标位置和当前位置在水平方向上的距离差的绝对值。


[蓝桥杯 2017 省 B] 日期问题

题目描述

小明正在整理一批历史文献。这些历史文献中出现了很多日期。小明知道这些日期都在 1960 年 1 月 1 日至 2059 年 12 月 31 日。令小明头疼的是,这些日期采用的格式非常不统一,有采用年/月/日的,有采用月/日/年的,还有采用日/月/年的。更加麻烦的是,年份也都省略了前两位,使得文献上的一个日期,存在很多可能的日期与其对应。比如 02/03/04,可能是 2002 年 03 月 04 日、2004 年 02 月 03 日或 2004 年 03 月 02 日。给出一个文献上的日期,你能帮助小明判断有哪些可能的日期对其对应吗?

输入格式

一个日期,格式是 AA/BB/CC。(0≤A,B,C≤9)

输出格式

输出若干个不相同的日期,每个日期一行,格式是 yyyy-MM-dd。多个日期按从早到晚排列。

#include <bits/stdc++.h>
using namespace std;

char a[20];//存储输入的日期 
int M[20]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int main()
{
	int l,i,j,k,x,y,z;
	scanf("%s",a);
	l=strlen(a);
	//解析日期中的年份,日期,月份为整数 
	x=(a[0]-48)*10+a[1]-48;
	y=(a[3]-48)*10+a[4]-48; 
	z=(a[6]-48)*10+a[7]-48;
	for(i=1960;i<=2059;i++)
	{
		if(i%400==0||(i%4==0&&i%100!=0))	//判断闰年
			M[2]=29;//将二月的天数设为29 
		for(j=1;j<=12;j++)//遍历每个月 
		{
			for(k=1;k<=M[j];k++)//遍历每个月的每一天 
//这个i%100也就是遍历到某个四位数的年份取其后两位 
				if((x==i%100&&y==j&&z==k)||(z==i%100&&x==j&&y==k)||(z==i%100&&y==j&&x==k))
				{
					cout<<i<<"-";
					if(j<10)
						cout<<0;
					cout<<j<<"-";
					if(k<10)
						cout<<0;
					cout<<k<<endl;
				}	
		}
		M[2]=28;//别忘了 
	}
}
心得体会:

1、在ASCII编码中,数字字符'0'的ASCII码是48,而其后的字符依次递增。因此,通过将字符'a[0]'减去48,可以得到对应的数字值。在这段代码中,a[0]是输入日期字符串的第一个字符,例如'0'、'1'、'2'等。由于这些字符是ASCII码表中的字符表示形式,而我们需要得到的是其对应的数字值,所以需要将字符'0'的ASCII码值48减去。然后,将结果乘以10,以便处理两位数的年份。接下来,从字符'a[1]'中减去48,再将结果与之前的乘积相加,从而得到两位数的年份值。

2、这道题开始处解析日期的时候就很灵活,后续采用暴力循环,接着写if语句来取不同日期的值。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/461928.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

OLED 菜单操作

本次介绍一款中景园带字库的OLED显示屏&#xff0c;并基于该模块描述一种菜单操作方法&#xff0c;能够极大的减少显示界面开发工作量。 使用的2.08寸OLED显示屏&#xff0c;字库芯片为GT30L32S4W&#xff0c;支持多种字号中英文。 官方提供了很完善的参考资料&#xff0c;包括…

结构体联合体枚举和位段

文章目录 结构体结构体类型的声明特殊的声明 结构的自引用结构体变量的定义和初始化结构体内存对齐为什么要内存对齐结构体传参结构体实现位段&#xff08;位段的填充&可移植性&#xff09;位段位段的内存分配空间如何开辟位段的跨平台问题位段的应用 枚举枚举类型的定义枚…

鸿蒙Harmony应用开发—ArkTS声明式开发(容器组件:Column)

沿垂直方向布局的容器。 说明&#xff1a; 该组件从API Version 7开始支持。后续版本如有新增内容&#xff0c;则采用上角标单独标记该内容的起始版本。 子组件 可以包含子组件。 接口 Column(value?: {space?: string | number}) 从API version 9开始&#xff0c;该接口…

vscode 生成树状图工具:project-tree

按下快捷键“CtrlShiftP”, 在弹框中输入 Project Tree&#xff0c;然后敲回车即会在根目录自动生成README.md&#xff08;如果之前没有的话&#xff09;。

pytorch 入门基础知识二(Pytorch 02)

一 微积分 1.1 导数和微分 微分就是求导&#xff1a; %matplotlib inline import numpy as np from matplotlib_inline import backend_inline from d2l import torch as d2l def f(x):return 3 * x ** 2 - 4 * x 定义&#xff1a; 然后求 f(x) 在 x 1 时的导数&#xff…

HarmonyOS NEXT应用开发—折叠屏音乐播放器方案

介绍 本示例介绍使用ArkUI中的容器组件FolderStack在折叠屏设备中实现音乐播放器场景。 效果图预览 使用说明 播放器预加载了歌曲&#xff0c;支持播放、暂停、重新播放&#xff0c;在折叠屏上&#xff0c;支持横屏悬停态下的组件自适应动态变更。 实现思路 采用MVVM模式进…

【Algorithms 4】算法(第4版)学习笔记 18 - 4.4 最短路径

文章目录 前言参考目录学习笔记0&#xff1a;引入介绍1&#xff1a;APIs1.1&#xff1a;API&#xff1a;加权有向边1.2&#xff1a;Java 实现&#xff1a;加权有向边1.3&#xff1a;API&#xff1a;加权有向图1.4&#xff1a;Java 实现&#xff1a;加权有向图1.5&#xff1a;AP…

Unity类银河恶魔城学习记录10-12 p100 Improve aliments - chill源代码

Alex教程每一P的教程原代码加上我自己的理解初步理解写的注释&#xff0c;可供学习Alex教程的人参考 此代码仅为较上一P有所改变的代码 【Unity教程】从0编程制作类银河恶魔城游戏_哔哩哔哩_bilibili CharacterStats.cs using System.Collections; using System.Collections…

docker容器镜像管理

目录 一、 Docker的基本组成 二、 容器和镜像的关系 2.1 面向对象角度 2.2 从镜像容器角度 三、镜像命令 3.1 查看当前已有镜像 3.2 查看已有的全部镜像 3.3 查看镜像ID 3.4 镜像删除 四、 容器命令 4.1 下载镜像 4.2 新建和启动容器 run 4.3 交互式 4.…

探讨大世界游戏的制作流程及技术——大场景制作技术概况篇

接上文&#xff0c;我们接下来了解一下大世界场景制作技术有哪些&#xff0c;本篇旨在给大家过一遍目前业界的做法&#xff0c;能让大家有一个宏观的知识蓝图。实际上&#xff0c;针对不同的游戏类型和美术风格&#xff0c;制作技术在细节上有着非常大的不同&#xff0c;业界目…

【UE5】持枪状态站立移动的动画混合空间

项目资源文末百度网盘自取 创建角色在持枪状态站立移动的动画混合空间 在BlendSpace文件夹中单击右键选择动画(Animation)中的混合空间(Blend Space) 选择SK_Female_Skeleton 命名为BS_RifleStand 打开 水平轴表示角色的方向&#xff0c;命名为Direction&#xff0c;方…

SD-WAN技术助力跨境电商网络搭建的解决方案

随着全球贸易的蓬勃发展&#xff0c;跨境电商成为了商业领域中的一个重要组成部分。然而&#xff0c;跨境电商面临着网络搭建和管理的复杂性&#xff0c;而SD-WAN技术的引入为解决这些问题提供了一种创新的方法。本文将深入探讨SD-WAN如何有效解决跨境电商行业的网络搭建问题。…

UE5.1 iClone8 正确导入角色骨骼与动作

使用iClone8插件Auto Setup 附录下载链接 里面有两个文件夹,使用Auto Setup C:\Program Files\Reallusion\Shared Plugins 在UE内新建Plugins,把插件复制进去 在工具栏出现这三个人物的图标就安装成功了 iClone选择角色,导入动作 选择导出FBX UE内直接导入 会出现是否启动插件…

同城预约上门服务APP小程序开发 打造快捷便利生活

随着移动互联网的快速发展&#xff0c;人们的生活方式正在发生深刻的变化。特别是在城市生活中&#xff0c;人们越来越依赖移动应用来解决日常生活中的各种问题。其中&#xff0c;同城预约上门服务APP正成为一种新型的生活服务平台&#xff0c;为人们提供了更加便利和快捷的服务…

RTC的Google拥塞控制算法 rmcat-gcc-02

摘要 本文档描述了使用时的两种拥塞控制方法万维网&#xff08;RTCWEB&#xff09;上的实时通信&#xff1b;一种算法是基于延迟策略&#xff0c;一种算法是基于丢包策略。 1.简介 拥塞控制是所有共享网络的应用程序的要求互联网资源 [RFC2914]。 实时媒体的拥塞控制对于许…

2023年总结:一个普通程序员如何挑选出价值千万的职业赛道

​​​​​​​ 引言 随着2023年的序幕缓缓落下&#xff0c;我终于在岁月的流转中捕捉到了一条隐秘而又公开的真理。它悄然告诉我们&#xff0c;成功并非单纯由勤劳的双手雕琢&#xff0c;一份耕耘未必有一份收获&#xff0c;而是在于我们如何在命运的十字路口作出关键选择。那…

Linux/secret

Enumeration nmap 第一次扫描发现系统对外开放了22&#xff0c;80和3000端口&#xff0c;端口详细信息如下 可以看到22端口对应的是ssh服务&#xff0c;80和3000都是http服务&#xff0c;80端口使用nginx&#xff0c;3000使用了Node.js TCP/80 可以先从80端口开始探索&…

滑动窗口和螺旋矩阵

209. 长度最小的子数组 题目 给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其总和大于等于 target 的长度最小的 连续 子数组 [numsl, numsl1, ..., numsr-1, numsr] &#xff0c;并返回其长度**。**如果不存在符合条件的子数组&#xff0c;返回…

R统计学3 - 数据分析入门问题41-60

往期R统计学文章: R统计学1 - 基础操作入门问题1-20 R统计学2 - 数据分析入门问题21-40 41. R 语言如何做双坐标图? # 创建模拟数据 year <- 2014:2024 gdp <- data.frame(year, GDP = sort(rnorm(11, 1000, 100))) ur <- data.frame(year, UR = rnorm(11, 5, 1…

微信小程序原生<map>地图实现标记多个位置以及map 组件 callout 自定义气泡

老规矩先上效果图: 1 、在pages文件夹下新建image文件夹用来存放标记的图片。 2、代码片段 也可以参考小程序文档:https://developers.weixin.qq.com/miniprogram/dev/component/map.html index.wxml代码 <mapid="map"style="width: 100%; height:100%;&…