Acm入门1:模拟、枚举、递推、递归(第二篇博客)

模拟:顾名思义,写程序来模拟题目中所要求的操作,只要按照题目意思来写即可。

例1:回文串

输入一个字符串,判断这个字符串是不是回文串,如果是,输出Yes,否则输出No。

回文串是一个正读反读都一样的字符串。

比如level、noon,但是windows不是。

#include //万能头文件
using namespace std;//命名空间
int main(int argc, char** argv) {
	string s;
	cin>>s;
	int n=s.length(); 
	bool is=true;//先假设对称
	for(int i=0;i 
例2:旋转吧! 雪花。
 
给出一个大小为n的数组,输出以第m个数为起点,循环遍历数组一周的结果。
 
如:数组a为2 4 3 1 5,起点为第2个数,那么循环遍历的结果为: 4 3 1 5 2
 
#include
using namespace std;
int main() {
	freopen("in.txt", "r", stdin);
	int n;
	cin >> n;
	int a[n]{};//下标是从0到n-1
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	int b;
	cin >> b;
	--b;
	
	for (int i = 0; i < n; i++) {
		cout << a[(b + i) % n] << ' ';
	}
	return 0;
}

//本代码无法通过,正在改
 
二:枚举 
根据题意,枚举所有可能的状态,并用题目中给定的条件来判断哪些是需要的,哪些是不需要的。
 
例题1:百钱买百鸡
 
我国古代数学家张丘建在《算经》一书中提到的一个数学问题:鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一， 百钱买百鸡，问鸡翁，鸡母，鸡雏各几何?
 
O(n3)解:
 
#include 
using namespace std;
int main() {
	for (int i = 0; i <= 100; i++) {
		for (int j = 0; j <= 100; j++) {
			for (int k = 0; k <= 100; k++) {
				if (k % 3 == 0 and 5 * i < +3 * j + k / 3 == 100 and i + j + k == 100)
				{
					cout << i << ' ' << j << ' ' << k << endl;
				}

			}
		}

		}
	}
	
 
可以减少枚举变量,继续优化
 
例题2:This year’s substring
 
一个字符串能否去掉中间的某一段，使得余下的首尾相接恰为2021
 如:200021去掉中间的00后刚好是2021
 
枚举去掉字符串的起点终点 O(n^2) 算法
 
#include 
using namespace std;
int main(int argc, char** argv) {
	string s;
	cin >> s;
	int n = s.length();
	bool ok = false;
	for (int i = 0; i < n; i++) {//去掉的起点 
		for (int j = i; j < n; j++) {//去掉的终点 
			//去掉字符串下标的范围为[i,j] 
			string t = s.substr(0, i) + s.substr(j + 1);
			if (t == "2021")
				ok = true;
		}
	}
	cout << (ok ? "Yes" : "No") << endl;
	return 0;
}
 
 例题3:   校园活动(牛客网 FGA)
 
将一个数字字符串分为连续的一些组， 使得每个组内的数字之和相等，最多可以分为几组？ 如:31113 最多可以分为3组:3 111 3 。
 
思路:求和:3+3+3=9
 
枚举剩下多少组:[1,n]
 
#include 
using namespace std;
int main() {
	int n;
	cin >> n;
	string s;
	cin >> s;
	int sum = 0;
	for (int i = 0; i < n; i++) {	//对字符串求和 
		sum += s[i] - '0';
	}
	for (int i = n; i >= 2; i--) {	//枚举可以分为多少组 
		if (sum % i == 0) {
			bool ok = true; //能否恰好分为i组 
			int ave = sum / i;//每组的和 
			int cur = 0;//现在的和
			for (int j = 0; j < n; j++) {
				cur += s[j] - '0';
				if (cur > ave) {
					ok = false;
					break;
				}
				else if (cur == ave) {
					cur = 0;
				}
			}
			if (ok) {
				cout << i << endl;
				return 0;
			}
			else {
				cout << -1 << endl;
				return 0;
			}
		}
	}
	return 0;
}
 
三:递推 
通常用于序列计算,序列中的每一项依赖于前面一个或者多个项的值
 
四:递归 
一个函数调用自己就是递归
 
递归递推区别:而这对问题的求解本质上是一样的,但是求解次序不同;
 
从前往后是递推,从后往前是递归;
 
有已知到未知是递推,由未知到已知是递归。
 
例题1:计算20内某个数的阶乘
 
递推:
 
#include 
using namespace std;
int main(int argc, char** argv) {
	int n;
	cin >> n;
	long long fac[n + 1]{};
	fac[0] = fac[1] = 1;//初始化
	for (int i = 2; i <= n; i++) {
		fac[i] = fac[i - 1] * i;
	}
	cout << fac[n] << "n";
	return 0;
}
 
递归:
 
#include 
using namespace std;
long long fac(int n) {
	if (n == 0) {
		return 1;
	}
	else {
		return n * fac(n - 1);
	}
}
	cout << fac(n) <<"n";
	return 0;
}
 
例题2:兔子兔子
 
开始时有一对小兔，小兔出生后第3个月每月 都会再生一对小兔，问第n个月有多少对兔子?
 
思路:f[n]=f[n-1]+f[n-2]
 
1:1
 
2:1
 
3:2
 
4:3
 
5:5
 
递推
 
斐波纳契数列
 
#include 
using namespace std;
int main() {
	int n;
	cin >> n;
	long long f[n + 1]{};
	f[1] = f[2] = 1;
	for (int i = 3; i <= n; i++)
	{
		f[i] = f[i - 1] + f[i - 2];
	}
	cout << f[n] << endl;
	return 0;
}
 
递归:
 
#include 
using namespace std;
long long fib(long long n) {
	if (n == 1 or n == 2) {
		return 1;
	}
	else {
		return fib(n - 1) + fib(n - 2);
	}
}
int main(int argc, char** argv) {
	long long n;
	cin >> n;
	cout << fib(n) << endl;
	return 0;
}
 
例3:
 
碎梦
 
窗台上有n(1<=n<=100)堆纸飞机,数目分别为1,2,..,n 每次可以选择一个数x,然后从所以纸飞机数目大于等于x 的堆中各掷出x只纸飞机,最少要选择多少次才能将所有纸飞机掷出?
 
思路:递归比较容易
 
先找中间值
 
#include 
using namespace std;
int solve(int n) {
	if (n == 1) {
		return 1;//终止条件
	}
	if (n % 2) {
		return 1 + solve((n - 1) / 2);//注意不要写错
	}
	else {
		return 1 + solve(n / 2);
	}
}
int main() {//输出结果
	int n;
	cin >> n;
	cout << solve(n) << endl;
	return 0;
}
 
递推:
 
f[n]=1+f[n/2]