C++ 基础知识——数组、函数算法应用

蔚落 2021-07-25 18:24 406阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNjA4MDAw_size_16_color_FFFFFF_t_70]

--------------------

QQ 1274510382  
Wechat JNZ\_aming  
商业互捧 QQ群538250800  
技术搞事 QQ群599020441  
技术合作 QQ群152889761  
加入我们 QQ群649347320  
纪年科技aming  
网络安全 ,深度学习,嵌入式,机器强化,生物智能,生命科学。

--------------------

### 冒泡法 ###

原理是遍历文件，  
如果相邻的两个元素大小不符合预期，则进行交换，重复直到有序为止。

第一遍时，从左到右比较相邻两个元素，当两个元素中右边的元素较小时，将其与左边的元素进行交换。  
直到最终将最大的元素移到队列的最右边。

第二遍时，将次大的元素放到队列右边的第二位中…

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNjA4MDAw_size_16_color_FFFFFF_t_70 1]

void bubb(int a[],int n)
     
    { 
    	int i,j=0;
    	for(i=0;i<n-1;i++)//n个元素，只需要n-1趟冒泡
    	{ 
    		for(j=1;j<n-i;j++)//j=1,为了和前一个a[j-1]进行比较。n-i表示每趟排序都有一个元素被放置到后面正确的位置，之后不需移动。
    		{ 
    			if(a[j-1] > a[j])
    				swap(&a[j-1],&a[j]);  //swap函数用于交换
    
     swap 包含在命名空间std 里面
    		}
    	}
    	
    	return;
    }

### 选择法排序 ###

思路是从第一个元素开始，将第一个元素依次与剩余的元素比较，记录更大（小）的元素，将整个数组的元素比较完毕，记录下来最大（小）的元素并排列在数组首位。  
然后将剩下的元素进行相同的循环操作，依次放在的前面元素的末尾，直到全部排列结束。

#include<stdio.h>
    int main()
    { void sort(int x[],int n);
    return 0;
    } 
    void sort(int x[],int n){ 
    	int i,j,max,temp;
    	for(i=0;i<n-1;i++){ 
    		k=i;                                               //记录位置
    		for(j=i+1;j<n;j++)
    			if(x[max]<x[j])max=j;        //如果找到更大的元素，则将max记录更大元素的位置
    			if(max!=i)
    			{ temp=x[i];x[i]=x[max];x[max]=temp;}           //交换
    	}	
    }

### 递归函数 ###

（1）什么是递归函数？

我们都知道，一个函数可以调用其他函数。  
如果这个函数在内部调用它自己，那么这个函数就叫递归函数。  
（2）递归函数的作用

举个例子，我们来计算阶乘 n! = 1 \* 2 \* 3 \* … \* n

#不使用递归的方法：
    n=4      #求4的阶乘
    result=1
    i=1
    while i<=4:
        result=result*i
        i+=1
     
    print(result)
    
    #使用递归的方法：
    def test1(n):#定义函数来计算数字n的阶乘
        if n==1:
            return 1
        return n * test1(n-1)
     
    print(test1(5))
    #1在函数的内部调用自己本身
    #2递归函数本质是一个方法的循环调用，注意：有可能出现死循环
    #3一定要定义递归的边界(什么时候退出循环)

![在这里插入图片描述][20200428072547274.png]  
从上面两中方法的对比可以看出，递归函数的作用和循环的方法效果一样，即递归函数本质上是一个方法的循环调用，  
注意：有可能会出现死循环。  
因此，使用递归函数时，一定要定义递归的边界  
（即什么时候退出循环）。

递归函数的另一个案例是斐波纳契数列。

斐波纳契数列：1，1，2，3，5，8，13。。。  
（该数列中，有n个数字，从第三个数字开始：数值 =前一个数字 + 前面一个数字）

即，n=(n-2)+(n-1)

def get_num(n):#获取斐波拉契数列中第n个数字的值
        if n==1 or n==2:
            return 1
        return get_num(n-1) + get_num(n-2)
     
    #把获取的斐波拉契数字存放到列表中
    nums=[]
    for i in range(1,21):
        nums.append(get_num(i))#get_num获得一个斐波拉契数字
     
    print(nums)

![在这里插入图片描述][20200428072628238.png]  
以上两个案例是递归函数的经典案例，需要记住其使用方法。  
注意：在实际使用中，递归函数由于消耗时间比较长  
（相比for循环和while循环），所以很少使用。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNjA4MDAw_size_16_color_FFFFFF_t_70]: /images/20210725/f3961ea3d07743849147014f794d08ac.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNjA4MDAw_size_16_color_FFFFFF_t_70 1]: /images/20210725/86a477f4194749b1b8a6f3dcf5974dad.png
[20200428072547274.png]: /images/20210725/75b3313b3f164edca504e5b8d03309fd.png
[20200428072628238.png]: /images/20210725/a017eb7018fa455bbc878475ec6450e9.png