零基础看算法（第一天）

短命女 2023-02-16 06:52 26阅读 0赞

*  ## (a+b)问题 ##

#include <iostream>
    #include <string>
    using namespace std;	//std表示标准库定义的名字都在命名空间std中
    void f(int a,int b){
        
    	cout << a + b << endl;	// <<是输入运算符，将a+b的值送进箭头所指的count，并返回运算后的结果返回箭头所指的对象
    							//endl是一个操作符，结束当前行，清除缓存
    }
    int main(){
        
    	int a,b;
    	int T;
    	cin>>T;		//当cin中遇到了一个无效输入时，就会返回一个无效状态，再接下来的>>也输入不了，或者文件符结尾时，也会返回一个无效的状态。
    	for(int i = 0;i < T;i++){
        
    	cin>>a>>b;
    	f(a,b);
    	a = 0; b = 0;
    	}
    	return 0;
    }

*  ## 斐波那契数列的各种算法 ##
    
    由于斐波纳挈数列是以兔子的繁殖引入的，因此也叫“兔子数列”。它指的是这样一个数列：0,1,1,2,3,5,8,13…从这组数可以很明显看出这样一个规律：从第三个数开始，后边一个数一定是在其之前两个数的和。在数学上，斐波纳挈数列可以以这样的公式表示：F(0) = 0 F(1) = 1 F(n) = F(n-1) + F(n-2),(n>=2)  
    利用递归的方法  
    并由一直公式：F(n) = F(n-1) + F(n-2) （n>=2）

long long Fib1 (long long num){
        
    	assert(num>=0)		//关键字assert：如果参数的表达式结果为真，assert不执行任何操作；如果结果为假，通过abort来终止程序运行，assert()将在stderr上显示错误信息并终止程序运行
    						//头文件使用<assert.h> assert为断言语句
    	if((num == 1) || (num == 0))
    	{
        
    		return num;
    	}
    	return Fib1(num - 1) + Fib1(num - 2);
    }

//或者
    long long Fib2(long long num){
        
    	assert(num >= 0);
    	return num < 2 ? num:(Fib2(num - 1) + Fib2(num - 2));
    }

## 算法的时间复杂度为O（2^N）,如果递归的深度越深，则二叉树深度遍历会进行更多次，同一结果被反复计算，造成空间上的浪费。 ##

//优化
    //借助两个变量 first 和 second ，每次将 first 和 second 相加后赋给 third ，再将 second 赋给 first ，third 赋给 second，如此循环。
    long long Fib3(long long num){
        
    	assert (num >= 0);
    	long long first = 0;
    	long long second = 1;
    	long long third = 0;
    	{
        
    		for(int i = 2;i <= num;i++){
        
    		third = first + second;
    		first = second;
    		second = third;
    		}
    		return third;
    	}
    }

## 该过程的时间复杂度为O（N），空间复杂度为O（1） ##

完整代码

#include<iostream>
    #include<string>
    #include<assert.h>
    using namepace std;
    #define maxn 1000000007
    
    //赋值法
    long long Fib(long long num){
        
    	assert (num>=0);
    	long long first = 0;
    	long long second = 1;
    	long long third = 0;
    	for(long long i = 2; i <num ;i++){
        
    		third = (first + second)%maxn;
    		first = second % maxn;
    		second = third%maxn;
    	}
    	return third %maxn;
    }
    
    //数组法
    long long Fib(long long num){
        
    	assert(num>=0);
    	long long *array = new long long[num + 1];
    	array[0] = 0;
    	array[1] = 1;
    	for(int i=2;i<= num;i++){
        
     	array[i] = array[i-1]+array[i-2];
     }
     return array;
    }