大白糖奶兔的Blog
大白糖奶兔的Blog
Chapter 1-算法之美

1、算法复杂性

#include<iostream>
using namespace std;
int main() {
    int fac(int n);
    int x = 5;
    int result = fac(x);
    cout << "5的阶乘是:" << result;
    return 0;
}
// 递归计算阶乘
int fac(int n) {
    if (n < 0)
        cout << "n < 0,Data Error!";
    else {
        if (n == 0 || n == 1)
            return 1;
        else
            return n * fac(n - 1);
    }
}

https://yczbest.cn/wp-content/uploads/2020/09/wp_editor_md_9d8ccd5336942d2d5e92c4bd074c0d53.jpg

序列问题

https://yczbest.cn/wp-content/uploads/2020/09/wp_editor_md_941fff9b02a85ed969125590868e5fce.jpg

https://yczbest.cn/wp-content/uploads/2020/09/wp_editor_md_686c093607e102430dbccd709f69bce7.jpg

https://yczbest.cn/wp-content/uploads/2020/09/wp_editor_md_8c1c6bd9f5769750a9c4bb7e5b4a0638.jpg

兔子数列(斐波那契数列)

https://yczbest.cn/wp-content/uploads/2020/09/wp_editor_md_ce188963feb23fa0bc779904fad5a273.jpg

– 结论:当月兔子数=上个月兔子数(画圈)+上上个月兔子数(箭头)

https://yczbest.cn/wp-content/uploads/2020/09/wp_editor_md_fd27cc7bbd6b934f321d827fbc8b7757.jpg

代码实现

C++

#include <iostream>
using namespace std;
int main() {
//递归思想解决斐波那契数列
//当n>=3时,F(n) = F(n-1) + F(n-2)
    //当自定义函数在下面要记得在main中声明
    int Fib(int n);
    int n = 6, result;
    result = Fib(n);
    cout << "第" << n << "天有" << result << "只兔子";
    return 0;
}
int Fib(int n) {
    if (n < 0)
        return -1;
    if (n == 1 || n == 2)
        return 1;
    else
        return (Fib(n - 1) + Fib(n - 2));
}

代码优化(时间复杂度O(n))

#include<iostream>
using namespace std;
int Fib(int n) {
    if (n < 1)
        return -1;
    int* a = new int[n];
    a[1] = 1;
    a[2] = 1;
    for (int i = 3; i <= n; i++)
    {
        a[i] = a[i - 1] + a[i - 2];
    }
    return a[n];
}
int main() {
    int num,result;
    cin >> num;
    result = Fib(num);
    cout << result;
    return 0;
}

迭代法

空间复杂度O(1),时间复杂度O(n)

#include<iostream>
using namespace std;
int Fib(int n) {
    if (n < 1)
        return -1;
    if (n == 1 || n == 2)
        return 1;
    int s1, s2;
    s1 = 1;
    s2 = 1;
    for (int i = 3; i <= n; i++) {
        s2 = s1 + s2;
        s1 = s2 - s1;
    }
    return s2;
}
int main() {
    int num;
    cin >> num;
    cout << Fib(num);
    return 0;
}

https://yczbest.cn/wp-content/uploads/2020/09/wp_editor_md_a1de297094ed54e5060328006bef1deb.jpg

数学问题

https://yczbest.cn/wp-content/uploads/2020/09/wp_editor_md_ef0c9afb8fd23ed32ed64c61e6fb101d.jpg

#include<iostream>
using namespace std;
int main() {
	int x, y, z, count = 0;
	cout << "Index\t\tMen\t\tWomen\t\tChildren" << endl;
	cout << "----------------------------------------------------------";
	for (x = 1; x <= 9; x++) {
		y = 20 - 2 * x;
		z = 30 - x - y;
		if (3 * x + 2 * y + z == 50) {
			cout << "\n" << ++count << "\t\t" << x << "\t\t" << y << "\t\t" << z << "\t\t" << endl;
		}
	}
	return 0;
}

由题意,设男人x,女人y,小孩z 可以列出方程

①x+y+z=30

②3x+2y+z=50

②-①消元得③2x+y=20

此时可以使用穷举法,穷举x或者y的值,再由消元后的等式确定另一个变量的值,再根据方程①②进行求解

爱因斯坦阶梯问题

https://yczbest.cn/wp-content/uploads/2020/09/image-1.png
#include<iostream>
using namespace std;
int main() {
	int n = 1;//n为未知数
	while (!((n % 2 == 1) && (n % 3 == 2) && (n % 5 == 4) && (n % 6 == 5) && (n % 7 == 0))) {
		//使用while循环,则满足条件取反才未假,才会停止循环
		n++;
	}
	cout << n;
	return 0;
}
https://yczbest.cn/wp-content/uploads/2020/09/image-2-1024x351.png
https://yczbest.cn/wp-content/uploads/2020/09/image-3-1024x129.png
#include<iostream>
using namespace std;
int main() {
	int n = 7;//n为未知数
	while (!((n % 2 == 1) && (n % 3 == 2) && (n % 5 == 4) && (n % 6 == 5) && (n % 7 == 0))) {
		//使用while循环,则满足条件取反才未假,才会停止循环
		n+=7;
	}
	cout << n;
	return 0;
}
https://yczbest.cn/wp-content/uploads/2020/09/image-4-1024x383.png
#include<iostream>
using namespace std;
int main() {
	int n = 1,t;
	//求最小公倍数
	while (!((n%1==0) && (n%2==0)&& (n%4==0) && (n%5==0)))
	{
		n = n + 1;
	}
	t = n-1;//
	while (!(t%7==0))
	{
		t = t + n;//
	}
	cout << t;
	return 0;
}

发表评论

textsms
account_circle
email

大白糖奶兔的Blog

Chapter 1-算法之美
1、算法复杂性 #include<iostream> using namespace std; int main() { int fac(int n); int x = 5; int result = fac(x); cout << "5的阶乘是:" << …
扫描二维码继续阅读
2020-09-17
Title - Artist
0:00