程序算法基础知识

第一课 程序基础知识

1、算法的特性

第二章 - 图1

2、算法的复杂度

  • 1、时间复杂度
  • 2、空间复杂度

    3、**常见时间复杂度：

    • 增长越快，复杂度越高；
    • 增长越慢，复杂度越低。 第二章 - 图2

      第二课 C++语言基础

      数据类型

      第二章 - 图3

      函数

      第二章 - 图4

      递归函数

      第二章 - 图5

      递归

      • 示例
      • 题目

        例如编写一求1+2+..+n的值，其中n<=20

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int sum(int n){
  4.     if(n==1){
  5.         return 1;
  6.     }
  7.     return  sum(n-1)+n;
  8. }
  9. int main(){
  10.     cout<<sum(200);
  11.     return 0;
  12. }

[GESP202409 三级] 平衡序列 局部截取_20250711_172440.png

  1. #include<bits/stdc++.h>
  2. using namespace std; 
  3. const int SIZE = 10005;
  4. bool check(){
  5.     int x,arr[SIZE],sum=0,leftsum=0;
  6.     cin>>x;
  7.     for(int i=0;i<x;i++){
  8.         cin>>arr[i];
  9.         sum+=arr[i];
  10.     }
  11.     for(int i=0;i<x;i++){
  12.         leftsum+=arr[i];
  13.         if(sum - leftsum == leftsum){
  14.             return true;
  15.         }
  16.     }
  17.     return false;
  18. }
  19. int main(){
  20.     int n;
  21.     cin>>n;
  22.     while(n--){
  23.         cout<<(check()?"Yes":"No")<<endl;
  24.     }
  25.     return 0;
  26. }

局部截取_20250714_154703.png

基础排序

常见算法复杂度与稳定性

第二章 - 图8

冒泡排序

小的元素会经由交换慢慢“浮”到顶端，就像泡泡一样，故名“冒泡排序”。

  • 它的工作原理是，重复地走访过要排序的元素，依次比较两个相邻的两个元素，如果前面的数比后面的数大就把他们交换过来。

  • 走访元素的工作重复地进行，直到没有相邻元素需要交换

    1. //冒泡排序
    2. #include<bits/stdc++.h>
    3. using namespace std;
    4. const int SIZE = 10;
    5. int arr[SIZE] = {2,7,8,4,36,78,1,91,42,13};
    6. int main(){
    7.  for(int i = 0 ; i < SIZE - 1 ;i++){
    8.      for(int j = 0 ; j < SIZE - 1 - i ; j++){
    9.          if(arr[j] > arr[j+1])
    10.              swap(arr[j],arr[j+1]);
    11.      }
    12.  }
    13.  for(auto x : arr) cout<<x<<" ";
    14.  return 0;
    15. }

    选择排序

    选择排序是第一个数字往后一个一个比较，再到第二个数字一个一个比较，以此类推。

    1. //选择排序
    2. #include<bits/stdc++.h>
    3. using namespace std;
    4. const int SIZE = 10;
    5. int arr[SIZE] = {2,7,8,4,36,78,1,91,42,13};
    6. int main(){
    7.  for(int i = 0 ; i < SIZE - 1 ;i++){
    8.      for(int j = i + 1;j < SIZE;j++){
    9.          if(arr[i] > arr[j]){
    10.              swap(arr[i],arr[j]);
    11.          }
    12.      }
    13.  }
    14.  for(auto x : arr) cout<<x<<" ";
    15.  return 0;
    16. }