递归算法c++

主页:(*´∇｀*) 咦,又好了~ xiaocr_blog

算法概述：递归算法是一种直接或者间接调用自身函数或者方法的算法。说简单了就是程序自身的调用。

算法实质：递归算法就是将原问题不断分解为规模缩小的子问题，然后递归调用方法来表示问题的解。（用同一个方法去解决规模不同的问题）

算法思想：递归算法，顾名思义就是有两个大的阶段：递和归，即就是有去（递去）有回（归来）。

算法设计要素：

  • 明确递归的终止条件
  • 提取重复的逻辑，缩小问题的规模不断递去
  • 给出递归终止时的处理办法

·例题1：简单累和

#include<bits/stdc++.h>
using namespace std;
int get_sum(int n) {
  if (n == 1) {
    return 1;
  }
  return get_sum(n - 1) + n;
}
int main() {
  int n;
  cin >> n;
  cout << "Sum=" << get_sum(n) << endl;

  return 0;
}

·例题2：设有n个数已经按从小到大的顺序排列，现在输入x，判断它是否在这n个数中，如果存在则输出“YES"，否则输出”NO“

#include<bits/stdc++.h>
using namespace std;
int a[101], k;
void search(int a[], int left, int right) {
	if(left<right){
	int mid = (left + right) / 2;
	if (a[mid] == k) { cout << "YES"; return; }
	else if (k < a[mid]) { search(a, mid + 1, right); }
	else{ search(a, left, mid); }
	}
	else {
		cout << "NO" << endl;
	}
}
int main() {
	int n;
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	search(a, 1, n);
	return 0;
}

·例题3：Hanoi汉诺塔问题

#include<bits/stdc++.h>
using namespace std;
void move(char pos1, char pos2) {
	printf("%c-->%c", pos1, pos2);
}
void Hanoi(int n, char pos1, char pos2, char pos3) {
	if (n == 1) {
		move(pos1, pos3);
		cout << "\n";
	}
	else {
		Hanoi(n - 1, pos1, pos3, pos2);
		move(pos1, pos3);
		cout << "\n";
		Hanoi(n - 1, pos2, pos1, pos3);
	}

}
int main() {
	int n;
	cin >> n;
	Hanoi(n, 'A', 'B', 'C');

	return 0;
}

·例题4：斐波那契数列

#include<bits/stdc++.h>
using namespace std;
int f(int n) {
	if (n == 1 || n == 2) { return 1; }
	else {
		return (f(n - 1) + f(n - 2));
	}
}
int main() {
	int n;
	cin >> n;
	cout << f(n);

	return 0;
}

·例题五：集合的划分

描述

设S是一个具有n个元素的集合，S＝〈a1，a2，……，an〉，现将S划分成 k 个满足下列条件的子集合S1，S2，……，Sk，且满足：

1．Si≠∅

2.Si∩Sj＝∅ ( 1≤i，j≤k，i≠j )

3．S1∪S2∪S3∪…∪Sk＝S

则称S1，S2，……，Sk是集合S的一个划分。它相当于把S集合中的n个元素a1，a2，……，an放入k个(0＜k≤n＜30)无标号的盒子中，使得没有一个盒子为空。请你确定n个元素a1，a2，……，an 放入k个无标号盒子中去的划分数S(n,k)。

【输入】

给出n和k。

【输出】

n个元素a1，a2，……，an 放入k个无标号盒子中去的划分数S(n,k)。

#include<bits/stdc++.h>
using namespace std;
int S(int n, int k) {
	if (n < k || k == 0) { return 0; }
	if (k == 1 || k == n) { return 1; }

return (S(n - 1, k - 1) + k * S(n - 1, k));
}int main() {
	int n, k;
	cin >> n >> k;
	cout << S(n, k);
	return 0;
}

·例题六：数的计数

描述

我们要求找出具有下列性质数的个数（包括输入的自然数n）。先输入一个自然数n(n≤1000)，然后对此自然数按照如下方法进行处理：

不作任何处理；

在它的左边加上一个自然数，但该自然数不能超过原数的一半；

加上数后，继续按此规则进行处理，直到不能再加自然数为止。

#include<bits/stdc++.h>
using namespace std;
int ans;
void f(int n) {
	ans++;
	for (int i = 1; i <= n/2; i++) {
		f(i);
	}
}
int main() {
	int n;
	cin >> n;
	f(n);
	cout << ans;
	return 0;
}

习题：

全排列

给定一个由不同的小写字母组成的字符串，输出这个字符串的所有全排列。

我们假设对于小写字母有‘a’ <‘b’ < ... <‘y’<‘z’，而且给定的字符串中的字母已经按照从小到大的顺序排列。

【输入】

只有一行，是一个由不同的小写字母组成的字符串，已知字符串的长度在1到6之间。

【输出】

输出这个字符串的所有排列方式，每行一个排列。要求字母序比较小的排列在前面。字母序如下定义：

已知S=s1s2...sk,T=t1t2...tkS=s1s2...sk,T=t1t2...tk，则S<T等价于，存在p(1<=p<=k)，使得s1=t1,s2=t2,...,sp−1=tp−1,sp<tps1=t1,s2=t2,...,sp−1=tp−1,sp<tp成立。

#include<bits/stdc++.h>
using namespace std;
char a[10], ans[10];
bool v[10];
int len;
void f(int pos) {
	if (pos == len) { 
		for (int i = 0; i < len; i++) {
			cout << ans[i];
		}
		cout << endl;
		return; }
	else {
		for (int i = 0; i < len; i++) {
			if(v[i]==0){
				v[i] = 1;
				ans[pos] = a[i];
				f(pos + 1);
				v[i] = 0;
			}
		}

	}
}
int main() {
	cin >> a;
	len = strlen(a);
	f(0);
	return 0;
}

分解因数

题目描述】给出一个正整数aa，要求分解成若干个正整数的乘积，即a=a1×a2×a3×...×an，并且1<a1≤a2≤a3≤...≤an，问这样的分解的种数有多少。注意到a=a也是一种分解。

#include<bits/stdc++.h>
using namespace std;
int a,n,ans;
void f(int a, int k) {
	if (k >= a) { return; }
	for (int i = k; i <= a / i; i++) {
		if (a % i == 0) {
			ans++;
			f(a / i, i);
		}
	}
}
int main() {
	cin>> n;
	//n代表测试组数
	while (n--) {
		cin >> a;
		ans = 1;
		f(a, 2);
		cout << ans << endl;
	}

	return 0;
}

pell数列

【题目描述】

Pell数列a1,a2,a3,...的定义是这样的，a1=1,a2=2,...,an=2an−1+an−2(n>2)。

给出一个正整数 k，要求Pell数列的第 k项模上 32767

是多少。

【输入】

第1行是测试数据的组数 n，后面跟着 n行输入。每组测试数据占 1行，包括一个正整数k(1≤k<1000000)。

#include<bits/stdc++.h>
using namespace std;
int pell(long long  n) {
	if (n == 1) { return 1; }
	if (n == 2) { return 2; }
	return (2 * pell(n - 1) + pell(n - 2));
}
int main() {
	int n;
	cin >> n;
	while(n--){
	int k;
	cin >> k;
	cout << pell(k) % 32767 << endl;}
	return 0;
}

爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

#include<bits/stdc++.h>
using namespace std;
int palouti(int n) {
	if (n == 1) { return 1; }
	if (n == 2) { return 2; }
	return palouti(n - 1) + palouti(n - 2);

}
int main() {
	int n;
	while (cin >> n) {
		cout << palouti(n) << endl;
	}
	return 0;
}

放苹果

把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。

【输入】

第一行是测试数据的数目t（0<=t<=20）。以下每行均包含二个整数M和N，以空格分开。1<=M，N<=10。

【输出】

对输入的每组数据M和N，用一行输出相应的K。

/*
递归边界：盘子数目和苹果数目相同||盘子数目就一个
第一种情况：盘子数目比苹果数目多-->多出来的盘子数无用
第一种可转换为第二种
第二种情况：苹果数目大于等于盘子数目-->也分为两种情况：有盘子空余和无盘子空余
*/
#include<bits/stdc++.h>
using namespace std;
int apple, plate;
int f(int apple, int plate) {
	if (apple == 0|| plate == 1) { return 1; }
	if (plate > apple) { return f(apple, apple); }
	if (apple >= plate) {
		return f(apple, plate - 1) + f(apple - plate, plate);

	}
}
int main() {
	cin >> apple >> plate;
	cout<<f(apple, plate);
	return 0;
}

求最大公约数

#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b){
	return b == 0 ? a : gcd(b, a % b);
}
int main() {
	int a, b;
	cin >> a >> b;
	cout << gcd(a, b);
	return 0;
}

2的幂次方表示

任何一个正整数都可以用2的幂次方表示。例如：

137=27+23+20

同时约定方次用括号来表示，即ab可表示为a(b)。由此可知，137可表示为：

2(7)+2(3)+2(0)

进一步：7=22+2+20（21用2表示）

3=2+20

所以最后137可表示为：

2(2(2)+2+2(0))+2(2+2(0))+2(0)

又如：

1315=210+28+25+2+1

所以1315最后可表示为：

2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0）

#include<bits/stdc++.h>
using namespace std;
void f(int n) {
	int c = 0;
	while (pow(2, c)<=n) {
		c++;
	}
	c--;
	if (c == 0) {
		cout << "2(" << c << ")";
	}else if (c == 1) {
		cout << "2(" << c << ")";
	}else {
		cout << "2(";
		f(c);
		cout<< ")";
	}
	int other = n - pow(2, c);
	if (other) {
		cout << "+";
		f(other);
	}

}
int main() {
	int num;
	cin >> num;
	f(num);

}

分数求和

#include<bits/stdc++.h>
using namespace std;
int gcd(int n, int m) {
	return m == 0 ? n : gcd(m, n % m);
}
int main() {
	int a, b, c, d, e, f, n;
	scanf_s("%d%d/%d", &n, &a, &b);
	for (int i = 2; i <= n; i++) {
		scanf_s("%d/%d", &c, &d);
		e = (b * d) / gcd(b, d);
		a *= e / b;  b = e;
		a += c * (e / d);
	}
	int k = gcd(a, b);
	if (a % k == 0) {
		printf("%d/%d", a / k, b / k);
	}
	else {
		printf("%d/%d", a, b);
	}
	return 0;
}

因子分解

#include<bits/stdc++.h>
using namespace std;
void fact(int n, int a) {
	int b = 0;
	while (n == 0 || a > n) {
		return;
	}
	while (n % a == 0) {
		b++;
		n /= a;
	}
	if (b >= 1) {
		if (b == 1) {
			printf("%d", a);
		}
		else {
			printf("%d^%d", a, b);
		}
		if (n > a) {
		cout << "*";
	}
	}
	
	fact(n , a + 1);
}
int  main() {
	int n;
	cin >> n;
	fact(n,2);

}

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

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

相关文章

[C语言]指针详解一、数组指针、二维数组传参、函数指针

[C语言]指针详解一、数组指针、二维数组传参、函数指针

一、数组指针 对一个数组&#xff0c;如果我们想要让一个指针指向这个数组&#xff0c;我们应该如何定义呢?我们知道一个数组定义本来就是一个指针&#xff0c;那为何要多定义一个数组指针呢?我们来看看下面这个代码就理解了 #include <stdio.h> int main() {int arr…
阅读更多...
Docker与containerd：容器技术的双璧

Docker与containerd：容器技术的双璧

&#x1f407;明明跟你说过&#xff1a;个人主页 &#x1f3c5;个人专栏&#xff1a;《Docker幻想曲&#xff1a;从零开始&#xff0c;征服容器宇宙》 &#x1f3c5; &#x1f516;行路有良友&#xff0c;便是天堂&#x1f516; 目录 一、前言 1、Docker和containerd的背景…
阅读更多...
SpringBoot如何优雅实现远程调用

SpringBoot如何优雅实现远程调用

微服务之间的通信方式 常见的方式有两种&#xff1a; RPC——代表-dubbo HTTP——代表-SpringCloud 在SpringCloud中&#xff0c;默认是使用http来进行微服务的通信&#xff0c;最常用的实现形式有两种&#xff1a; RestTemplate Feign
阅读更多...
深度学习_ResNet_5

深度学习_ResNet_5

ResNet学习目标 什么是ResNet为什么要引入ResNet&#xff1f;ResNet网络结构的特点利用ResNet完成图像分类 什么是ResNet&#xff1f; ResNet&#xff08;Residual Network&#xff09;是一种深度残差网络&#xff0c;由何凯明等人在2015年提出&#xff0c;是深度学习领域中一…
阅读更多...
Gartner发布安全运营指南：迈向卓越安全运营的 5 项举措

Gartner发布安全运营指南：迈向卓越安全运营的 5 项举措

顶级组织通常会实施一套通用的安全运营活动&#xff0c;以实现成熟&#xff0c;但是&#xff0c;他们在应对快速发展的威胁方面仍然面临挑战。安全和风险管理领导者可以利用这五项举措来加强他们的网络防御工作&#xff0c;同时促进安全投资的更大回报。 主要发现 旨在提升威胁…
阅读更多...
【Java多线程】面试常考 —— JUC(java.util.concurrent) 的常见类

【Java多线程】面试常考 —— JUC(java.util.concurrent) 的常见类

目录 1、JUC&#xff08;java.util.concurrent&#xff09; 1.1、Callable 接口 1.2、ReentrantLock 可重入锁 1.3、Semaphore 信号量 1.4、CountDownLatch 1、JUC&#xff08;java.util.concurrent&#xff09; 这是java中的一个包&#xff0c;存放着多线程编程中常见的…
阅读更多...
电机学（笔记一）

电机学（笔记一）

磁极对数p&#xff1a; 直流电机的磁极对数是指电机定子的磁极对数&#xff0c;也等于电机电刷的对数。它与电机的转速和扭矩有直接关系。一般来说&#xff0c;极对数越多&#xff0c;电机转速越低&#xff0c;扭矩越大&#xff0c;适用于低速、高扭矩的场合&#xff1b;相反&…
阅读更多...
MATLAB的使用(一）

MATLAB的使用(一）

一&#xff0c;MATLAB的编程特点 a,语法高度简化&#xff1b; b,脚本式解释型语言&#xff1b; c,针对矩阵的高性能运算&#xff1b; d,丰富的函数工具箱支持&#xff1b; e,通过matlab本体构建跨平台&#xff1b; 二&#xff0c;MATLAB的界面 工具栏:提供快捷操作编辑器…
阅读更多...
HCIP的学习（2）

HCIP的学习（2）

TCP----传输控制协议 是一种面向连接的可靠传输协议。 注&#xff1a;与我之前博客HCIA的学习&#xff08;2&#xff09;结合一起看 面向连接&#xff1a;数据传输前收发双方建立一条逻辑通路 特点&#xff1a; TCP是一种面向连接的传输协议每一条TCP连接有且只能存在两个端…
阅读更多...
kafka2.x版本配置SSL进行加密和身份验证

kafka2.x版本配置SSL进行加密和身份验证

背景&#xff1a;找了一圈资料&#xff0c;都是东讲讲西讲讲&#xff0c;最后我还没搞好&#xff0c;最终决定参考官网说明。 官网指导手册地址&#xff1a;Apache Kafka 先只看SSL安全机制方式。 Apache Kafka 允许客户端通过 SSL 进行连接。默认情况下&#xff0c;SSL 处于…
阅读更多...
婴儿专用洗衣机哪个牌子比较好？热诚安利五大出类拔萃婴儿洗衣机

婴儿专用洗衣机哪个牌子比较好？热诚安利五大出类拔萃婴儿洗衣机

婴儿洗衣机可以用于单独清洗宝宝的衣物&#xff0c;可以有效避免了与大人衣物一起混洗带来的细菌交叉感染。毕竟&#xff0c;在婴儿吃奶或者接触其他材料时&#xff0c;其抵抗力是比较弱的&#xff0c;再加上普通洗衣机无法对婴儿的衣物进行有效的消毒处理&#xff0c;轻则会对…
阅读更多...
SpringCache和redis区别？什么是SpringCache？

SpringCache和redis区别？什么是SpringCache？

目录 一、Redis介绍1.1 Redis缓存1.2 redis缓存使用前提1.3 redis使用缓存的时机 二、实际操作案例2.1 常规准备工作2.2 引入配置redis2.2.1 引入redis的启动依赖2.2.2 在application.yml里面配置redis的地址信息等2.2.3 创建redisTemplate的配置类&#xff0c;指定键值序列化方…
阅读更多...
探索区块链世界：从加密货币到去中心化应用

探索区块链世界：从加密货币到去中心化应用

相信提到区块链&#xff0c;很多人会想到比特币这样的加密货币&#xff0c;但实际上&#xff0c;区块链技术远不止于此&#xff0c;它正在深刻地改变我们的生活和商业。 首先&#xff0c;让我们来简单了解一下什么是区块链。区块链是一种分布式数据库技术&#xff0c;它通过将…
阅读更多...
Linux docker1--环境及docker安装

Linux docker1--环境及docker安装

一、基础环境要求 Docker分为ce版本&#xff08;免费&#xff0c;试用7个月&#xff09;和ee版本&#xff08;收费&#xff09;。 最低配置要求&#xff1a;64位操作系统&#xff0c;centOS 7及以上&#xff0c;内核版本不低于3.10 二、部署docker 1、查看服务的基础环境是否满…
阅读更多...
MVC接收请求教程

MVC接收请求教程

mvc接收各种请求 1-环境搭建 1.1-准备apifox发送请求 1.2-项目搭建 ①创建Web骨架的Maven项目 ​ --打开2023-IDEA &#xff0c;选择New Project ​ --选择Maven Archetype ​ --注意点&#xff1a;Catalog默认就行了 ​ --Archetype选择webapp ​ --JDK跟着黑马敲最好…
阅读更多...
情感书单图片怎么制作？书单制作教程分享

情感书单图片怎么制作？书单制作教程分享

情感书单图片怎么制作&#xff1f;情感书单图片制作是一项富有创意和挑战性的任务&#xff0c;它要求我们不仅要有对书籍的热爱&#xff0c;还要有一定的审美和设计能力。幸运的是&#xff0c;现在市面上有许多专业的软件可以帮助我们实现这一目标&#xff0c;让情感书单图片的…
阅读更多...
好书推荐 《ARM汇编与逆向工程 蓝狐卷 基础知识》

好书推荐 《ARM汇编与逆向工程 蓝狐卷 基础知识》

《ARM 汇编与逆向工程　蓝狐卷 基础知识》 与传统的 CISC&#xff08;Complex Instruction Set Computer&#xff0c;复杂指令集计算机&#xff09;架构相比&#xff0c;Arm 架构的指令集更加简洁明了&#xff0c;指令执行效率更高&#xff0c;能够在更低的功耗下完成同样的计…
阅读更多...
并发编程Semaphore（信号量）浅析

并发编程Semaphore（信号量）浅析

目录 一、简介二、API三、使用3.1 demo13.1 demo2 四、适用场景 一、简介 Semaphore&#xff08;信号量&#xff09;是 Java 中用于控制同时访问特定资源的线程数量的工具类。Semaphore 维护了一组许可证&#xff0c;线程在访问资源之前必须先获取许可证&#xff0c;访问完毕后…
阅读更多...
【ADF4351】使用FPGA进行SPI寄存器配置、使用FPGA计算各个频率的频点，ADF4351配置程序

【ADF4351】使用FPGA进行SPI寄存器配置、使用FPGA计算各个频率的频点，ADF4351配置程序

简介 特性 输出频率范围&#xff1a;35 MHz至4,400 MHz 小数N分频频率合成器和整数N分频频率合成器 具有低相位噪声的VCO 可编程的1/2/4/8/16/32/64分频输出 典型抖动&#xff1a;0.3 ps rms EVM(典型值&#xff0c;2.1 GHz)&#xff1a; 0.4% 电源&#xff1a;3.0 V至3.6 V …
阅读更多...
Acwing.2060 奶牛选美(DFS)

Acwing.2060 奶牛选美(DFS)

题目 听说最近两斑点的奶牛最受欢迎&#xff0c;约翰立即购进了一批两斑点牛。 不幸的是&#xff0c;时尚潮流往往变化很快&#xff0c;当前最受欢迎的牛变成了一斑点牛。 约翰希望通过给每头奶牛涂色&#xff0c;使得它们身上的两个斑点能够合为一个斑点&#xff0c;让它们…
阅读更多...
最新文章

Copyright @ 2022~2023