AI 助理
备案控制台
开发者社区 人工智能 文章 正文

基础算法学习笔记（C++）

2024-04-16 79
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 基础算法学习笔记（C++）

筛法

素数又称质数：

指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。

试除法判定质数

int is_prime(int x)
{
    if(x < 2) return 0;
    for(int i = 2; i <= x; i++)
    {
        if(x % i == 0) return 0;
    }
    return 1;
}

试除法分解质因数

void divide(int x)
{
    for(int i = 2; i < x / i; i++)
        if(x % i == 0)
        {
            int s = 0;
            while(x % i = 0) x /= i,s++;
            cout << i << ' ' << s << endl;
        }
    if(x > 1) cout << x << ' ' << 1 << endl;
    cout << endl;
}

埃式筛法

int primes[N], cnt; //primes[]存储所有素数
bool st[N];  //st[x]存储x是否被筛掉
void get_primes(int n)
{
    for(int i = 2; i <= n; i++)
    {
        if(st[i]) continue;
        primes[cnt++] = i;
        for(int j = i + i; j <= n; j += i)
            st[j] = true;
    }
}

线性筛法

int primes[N], cnt; // primes[]存储所有素数 
bool st[N]; // st[x]存储x是否被筛掉
void get_primes(int n)
{
    for(int i = 2; i <= n; i++)
    {
        if(!st[i]) primes[cnt++] = i;
        for(int j = 0; primes[j] <= n / i; j++)
        {
          st[primes[j] * i] = true;
            if(i % primes[j] == 0) break;
        }
    }
}
#include<bits/stdc++.h>
#define pb push_back;
#define fi first
#define se second
#define pr printf
using namespace std;
typedef long long ll;
//对素数的理解
//实验时N=1e6
//素数的判断方法
//朴素筛法
//埃氏筛法极其终极版本
//欧拉筛法
inline bool isprime(int x)
{
    for(int i = 2; i <= x / i; ++i)
        if(x % i == 0) return 0;
    return 1;
}
int main(){
    //freopen("in.txt","r",stdin);
    int N; cin >> n;
    int count = 0;
    for(int i = 2; i < N; ++i)
    {
        if(isprime(i)) 
            count++;
            cout << count << "\n";
    }
    return 0;
}

埃式筛法

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
bitset<maxn> pri;
//4 = 2 * 2 
int main(){
    int N = 1e6, cnt = 0;
    double s = clock();
    
    for(int i = 2; i <= N; ++i)
    if(!pri[i])
            for(int j = i * i; j <= N; j += i) pri[j] = 1;
   for(int i = 2; i <= N; ++i) 
       if(!pri[i]) cnt++;
    double e = clock();
    printf("%d\ntime = %.01fms", cnt, e-s);
    return 0;
}

欧拉筛法

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
bitset<maxn> pri;//0为素数，1为合数（被晒除）
int primes[maxn],pp = 0;
//1 2 3 4 5 6 7 8 9 10
//primes
//让每一个素数只晒一次，欧拉筛选也叫线性筛
int main(){
    int N = 1e6, cnt = 0;
    double s = clock();
    
    for(int i = 2; i <= N; ++i){
    if(!pri[i]) primes[++ pp] = i; cnt++;
        for(int j = 1; primes[j] * i <= N; ++j){
            pri[primes[j] * i] = 1;
            if(i % primes[j] == 0) break;//key
        }
    }
    double e = clock();
    printf("%d\ntime = %.01fms", cnt, e-s);
    return 0;
}

欧拉线性筛法

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e8 + 10;
bitset<maxn> st;
int primes[maxn],pp = 0;
inline void ola(int x){
    for(int i = 2; i <= x; ++i){
        if(!st[i]) primes[++pp] = i;
        for(int j = 1; primes[j] * i <= x; ++j)
        {
            st[primes[j] * i] = 1;
            if(i % primes[j] == 0) break;
        }
    }
    return;
}
int main(){
    int n, q; cin >> n >> q;
    ola(n);
    while(q--){
        int k; cin >> k;
        cout << primes[k] << endl;
    }
    return 0;
}

前缀和与差分

前缀和板子：

for(int i = 1; i <= n; ++i){
  cin >> a[i];
  pre[i] = pre[i] + a[i];
}

前缀积板子：

pre[0] = 1;//否则全部变成0了
for(int i = 1; i <= n; ++i){
    cin >> a[i];
    pre[i] = pre[i - 1] * a[i] % mod;
}
求[l, R]区间内前缀和
ans = pre[R] + inv(pre[l - 1]);

二维前缀和板子：

for(int i = 1; i <= n; ++i){
  for(int j = 1; j <= m; ++j){
  cin >> a[i][j];
    pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + a[i][j];
    }
}
ans = pre[x2][y2] - pre[x2][y1-1] - pre[x1-1][y2] + pre[x1-1][y1-1];

一维前缀和代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int kN = 1e5;
ll arr[kN],sum[kN];
int main(){
  int n; cin >> n;
    for(int i = 1; i <= n; i++){
    cin >> arr[i];
    }
    for(int i = 1; i <= n; i++){
        sum[i] = sum[i - 1] + arr[i];
    }
    int m; cin >> m;
    while(m--){
        int l,r; cin >> l >> r;
        cout << sum[r] - sum[l - 1] << "\n";
    }
    return 0;
}

二维前缀和

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int kN = 1e5;
ll arr[kN],sum[kN];
int main(){
  int n,m,q; cin >> n >> m >> q;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
          cin >> arr[i][j];   
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
      sum[i][j] = sum[i][j - 1] + sum [i - 1][j] - sum[i - 1][j - 1] + arr[i][j];
        }
    }
    while(q--){
        int x1,y1,x2,y2;
        cin >> x1 >> y1 >> x2 >> y2;
        cout << sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1] << endl;
    }
    return 0;
}

优缺点

优点很显然，就是能快速求出区间或者矩阵的一些信息，例如和、积、疑惑等

缺点也很显然，就是不能在线操作 ，只能离线处理 ，遇到一个动态变化的就不能使用前缀和操作。

差分数组

差分数组的原理和特点

利用差分数组可以实现快速的区间修改，下面是将区间[l,r]都加上x的方法：

diff[l] += x;
diff[r + l] -= x;

在修改完成之后，需要做前缀和恢复为原数组，所以上面这段代码的含义是：

diff[i] += x表示将区间[l,n]都加上x，但是[r+1,n]我们并不想加x,所以再将[r+1,n]减去x即可。

但是注意，差分数组不能实现“边修改边查询（区间和）”，只能实现“多次修改完成后多次查询”。如果要实现“边修改边查询”需要使用树状数组、线性树等数据结构。

差分的实现

直接用循环O(n)实现即可，注意这里建议使得a[0] = 0,下标从1开始：

for(int i = 1; i <= n; i++)
    diff[i] = a[i] - a[i - 1];

将区间[l,r]都加上x：

diff[l] += x;
diff[r + l] -= x;

例题：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 3;
int a[N], d[N];
void solve(int n, int m)
{
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) d[i] = a[i] - a[i - 1];
    
    while(n--){
        int l, r, v; cin >> l >> r >> v;
        d[i] += v, d[r + 1] -= v;
    }
    //复原前缀和
    for(int i = 1; i <= n; i++) a[i] = a[i + 1] + d[i];
    for(int i = 1; i <= n; i++) cout << a[i] << " \n";
}
int main()
{
    int n,m;
    while(cin >> n >> m) 
        solve(n,m);
    return 0;
}

枚举

枚举算法介绍

枚举算法 是一种基本的算法思想，它通过穷举所有可能的情况来解决问题。它的基本思想是将问题的解空间中的每个可能的解都枚举出来，并通过验证和比较 ，找到满足问题条件的最优解或者所有解。

枚举算法适用于问题规模较小、解空间可穷举 的情况。它的优点是简单直观，不需要复杂的数学推导，易于实现。但是，由于需要穷举可能的情况，对于问题规模较大的情况，枚举算法的时间复杂度可能会非常高，效率较低。

解空间的类型

解空间可以是一个范围内的所有数字 （或二元组、字符串等数据），或者满足某个条件的所有数字。

当然也可以是解空间树，一般可分为子集树和排列树，针对解空间树，需要使用回溯法进行枚举（搜索的知识点会讲到）

我们目前仅使用循环暴力枚举空间，具体的解空间类型需要根据题目来理解构造。

循环枚举解空间

  1. 首先确定解空间的维度，即问题中需要枚举的变量个数。
    例如当题目要求的是

例题：

小明对数位中含有2，0，1，9的数字很敏感（不包括前导0），在1到40中这样的数包含1，2，9，10至32，39，40，共28个，他们的和是574.

请问，在1到n中，所有这样的数的和是多少？

输入描述：

输入格式：
输入一行包含两个整数n（1<=n<=10^4^ )

输出描述：

输出一行，包含一个整数，表示满足条件的数的和。

代码如下：

#include<bits/stdc++.h>
using namespace std;
bool f(int x)
{
  while(x)
    {
        int y = x % 10;
        if(y == 2 || y == 0 || y == 1 || y == 9) 
            return true;
        x /= 10;
    }
    return false;
}
int main()
{
    int m; cin >> m;
    int ans = 0;
    for(int i = 1; i <= n; i++)
    {
    if(f(i)) ans += i;
    }
    cout << ans << "\n";
    return 0;
}

高精度算法

思想

高精度算法本质上是用字符串模拟数字进行计算，再利用类似于数学里的竖式的形式，一位一位进行相关计算

处理

高精度计算中需要处理好以下几个问题：

(一)数据的接收方法 和存储方式

**数据的接收和存储：** 当输入的数很长时，可采用字符串方式输入，这样可输入位数很长的数，利用==字符串函数== 和操作运算，将每一位取出，存入数组中：
void init(int a[]){//传入数组
    string s; cin >> s;
    len = s.length();
    for(int i = 1; i <= len; i++)
        a[i] = s[len - i] - '0';//将字符串s转换为数组a，倒序存储
}

（二）进位、借位 的处理

//加法进位：c[i] = a[i] + b[i]
coed: if(c[i] >= 10){
        c[i] %= 10;
        ++c[i++];
}
//减法进位：c[i] = a[i] - b[i]
coed: if(a[i] < b[i]){
        --a[i+1];
        a[i] += 10;
}
//乘法进位：c[i + j - 1] = a[i]*b[j] + x + c[i + j - 1];
    x = c[i + j - 1]/10;
    c[i + j - 1]%10;

高精度加法

#include<cstdio>
#include<cstring>
using namespace std;
int main(){
    char a1[5005],b1[5005];//用字符存储数字
    int a[5005], b[5005], c[5005];//用c[i] 用来存储每位相加的结果
    int len_a, len_b, len_c = 1, x, i;
    
    memset(a, 0, sizeof(a));
    memset(b, 0, sizeof(b));
    memset(c, 0, sizeof(c));
    
    cin >> a1 >>b1;
    
    len_a = strlen(a1);
    len_b = strlen(b1);
    
    for(int i = 0; i < len_a; i++)
        a[len_a - i] = a1[i] - '0';
    for(int i = 0; i < len_b; i++)
        b[len_b - i] = b1[i] - '0';
    
    x = 0;//x进位
    while(len_c <= len_a || len_c <= len_b){
        c[len_c] = a[len_c] + b[len_c] + x;//两数相加，再加上前两个数进位的
         x = c[len_c] / 10; // 刷新进位
        c[len_c] %= 10; // 进位后剩下的
        len_c++; //位数加1
    }
    c[len_c] = x;
    if(c[len_c] == 0) { //判断首位是否为0
        len_c--; // 不输出此位
    }
 
    for(int i=len_c; i>=1; i--) {
        printf("%d", c[i]); //输出每一位的数
    }
 
    return 0;
}

高精度减法

#include <iostream>
#include <cstring>
 
int main() {
    int a[5005], b[5005], c[5005];
    int lena, lenb, lenc, i;
    char n[5005], n1[5005], n2[5005];
 
    std::memset(a, 0, sizeof(a));
    std::memset(b, 0, sizeof(b));
    std::memset(c, 0, sizeof(c));
 
    std::cin >> n1 >> n2; //输入被减数和减数
 
    lena = std::strlen(n1);
    lenb = std::strlen(n2);
 
    for(i=0; i<lena; i++) a[lena - i] = (int)n1[i] - '0';
    for(i=0; i<lenb; i++) b[lenb - i] = (int)n2[i] - '0'; //逆序存放排列
 
    i = 1;
    while(i <= lena || i <= lenb) {
        if(a[i] < b[i]) {
            c[i] = a[i] + 10 - b[i];
            a[i+1]--; //借位处理
        }
        else {
            c[i] = a[i] - b[i]; 
        }
        i++;
    }
 
    lenc = i;
    while(c[lenc] == 0 && lenc > 1) { //如果最后一位是0，是需要输出的
        lenc--;   // 不输出首位0
    }
 
    for(i=lenc; i>=1; i--) std::cout << c[i];
 
    return 0;
}

高精度乘法

#include <iostream>
#include <cstring>
 
int main() {
  int a[105], b[105], c[10005];
  char n1[105], n2[105], lena, lenb, lenc, j, i, x;
 
  std::memset(a, 0, sizeof(a));
  std::memset(b, 0, sizeof(b));
  std::memset(c, 0, sizeof(c));
  
  std::cin >> n1 >> n2;
  
  lena = std::strlen(n1);
  lenb = std::strlen(n2);
  
  for(i=0; i<=lena-1; i++) a[lena - i] = n1[i] - 48; 
  for(i=0; i<=lenb-1; i++) b[lenb - i] = n2[i] - 48; // 倒序储存
  
  for(i=1; i<=lena; i++) {
    x = 0;
    for(j=1; j<=lenb; j++) {
      c[i + j - 1] = c[i + j - 1] + x + a[i] * b[j];
      x = c[i + j - 1] / 10; // 进位
      c[i + j - 1] %= 10; // 剩余
    }
    c[i + lenb] = x; // 进位的数
  }
  
  lenc = lena + lenb;
  while(c[lenc] == 0 && lenc > 1) {
    lenc--; // 删除前导0
  }
  
  for(i=lenc; i>=1; i--) {
    std::cout << c[i];
  }  // 输出每一位
     
    std::cout << std::endl;
  
  return 0;
}

高精度除法

高精度除以低精度

#include <iostream>
 
int main(){
    char n1[100];
    int a[100], c[100], lena, i, x = 0, lenc, b;
    
    std::memset(a, 0, sizeof(a));
    std::memset(c, 0, sizeof(c));
    
    std::cin >> n1 >> b;  
    lena = strlen(n1);
 
    for(i=1; i<=lena; i++) {
        a[i] = n1[i - 1] - '0'; //除法不需要逆序存放
    }
 
//-------------------------初始化------------------------------
 
    for(i=1; i<=lena; i++) {
        c[i] = (a[i] + x * 10) / b;  // 算上上一位剩下的继续除
        x = (a[i] + 10 * x) % b; // 求余
    }
 
    lenc = 1;
    while(c[lenc] == 0 && lenc < lena) {
        lenc++;
    }
 
    for(i=lenc; i<lena; i++) std::cout << c[i];
 
    return 0;
}

高精度除以高精度

#include <cstdio>
#include <iostream>
#include <cstring>
 
using namespace std;
 
int a[50005], b[50005], c[50005], d;
 
void init(int a[]) {
  char s[50005];
  cin >> s;
  a[0] = strlen(s);   // 字符串存储，表示位数 
  for (int i=1; i<=a[0]; i++) {
    a[i] = s[a[0]-i] - 48;  // 正序储存
  }   
}
 
void print(int a[]) {     
  if (a[0] == 0) {
    cout << 0 << endl;
    return;  // 位数为0，输出0
  }
  for (int i=a[0]; i>=1; i--) {
    cout << a[i];  // 输出函数
  }
  cout << endl;
  return;
} 
 
int compare(int a[], int b[]) { 
  if (a[0] > b[0]) {
    return 1; // 被减数大于减数
  } 
  if (a[0] < b[0]) {
    return -1; // 被减数小于减数
  }
  for (int i=a[0]; i>=1; i--) { 
    if (a[i] > b[i]) {
      return 1;
    } 
    if (a[i] < b[i]) {
      return -1;
    }   // 位数相同，找到第一位不同的进行比较
  } 
  return 0;         
}
 
void numcpy(int p[], int q[], int det) {
  for (int i=1; i<=p[0]; i++) {
    q[i+det-1] = p[i]; //复制p数组到q数组从det开始的地方
  }
  q[0] = p[0] + det - 1;
}
 
void jian(int a[], int b[]) {   
  int flag = compare(a, b);    
  if (flag == 0)  {         
    a[0] = 0;
    return;
  }
  if (flag == 1) {        
    for (int i=1; i<=a[0]; i++) {
      if (a[i] < b[i]) {       
        a[i+1]--;     
        a[i] += 10;
      }
      a[i] -= b[i];
    }
    while (a[0]>0 && a[a[0]]==0) {
      a[0]--;         
    } 
    return; 
  }        
}  // 高精减法
 
void chugao(int a[], int b[], int c[]) {
  int tmp[50005];
  c[0] = a[0] - b[0] + 1;
  for (int i=c[0]; i>0; i--) {
    memset(tmp, 0, sizeof(tmp));  
    numcpy(b, tmp, i);// 清零
    while (compare(a, tmp) >= 0) {
      c[i]++;
      jian(a, tmp); // 用减法模拟    
    } 
  }
  while (c[0] > 0 && c[c[0]] == 0) {
    c[0]--;
  }
  return;
}
 
int main() {
  memset(a, 0, sizeof(a));
  memset(b, 0, sizeof(b));
  memset(c, 0, sizeof(c));
  
  init(a);
  init(b);
  chugao(a,b,c);
  print(c); 
  
  return 0;
}

二分

二分法的简介

二分法是一种高效的查找方法，它通过将问题的搜索范围一分为二 （两边具有明显的区别），迭代地缩小搜索范围，直到找到目标或确定目标不存在。

二分法适用于有序数据集合 ，并且每次迭代可以将搜索范围缩小一半 。

二分法的本质上也是枚举 ，但和暴力枚举不同，二分法利用数据结构的单调性 减少了很多不必要的枚举，从而极大提高了效率，一般可以将O(n)的枚举优化到O(logn)。

常见的二分类型有：

（一）整数二分

（二）浮点二分

（三）二分答案（最常见）

二分法简介- 解题步骤
  1. 研究并发现数据结构（或答案变量）的单调性
  2. 确定最大区间[1,r],确保分界点一定在里面，具体有一些细节：若以r作为答案，那么答案区间在[1+1,r]，若以1作为答案，那么答案区间在[1,r-1]。
  3. 确定check函数 ，一般为传入mid（区间中某个下标），返回mid所属区域 或返回一个值，当check函数较简单时可以直接判断。
  4. 计算中点mid=（1+r）/2 ,用check判断该移动1或r指针 ,具体移动哪个需要根据单调性以及要求答案来判断。
  5. 返回1或r,根据题意判断

整数二分

整数二分就是在一个已有的有序数组 上，进行二分查找，一般为找出某个值的位置，或者是找出分界点。

这个数组肯定是开的下的，其数组大小一般在le6以内。

区域划分如下图：

整数二分模板

//找到升序数组a中的x第一次出现的位置
int l = 0, r = le9;
//注意这里的判断条件，这样可以保证l,r最终一定收敛到分界点
while(l + 1 != r)
{
    int mid = (1 + r) / 2;
    
    //如果a为升序，说明mid偏大了，需要减小mid，就只能将r变小，即r=mid
    if(a[mid] >= x)  r = mid;
    else l = mid;
}
  cout << r << endl;

求大于等于所求值的最大值

int binary(){
    int l = 0,r =INF,mid;
    while(l < r){
        mid = (l + r) >> 1;
        if(check(mid)) r = mid;
        else l = mid +1;
    }
    return l;
}

求小于等于所求值的最大值

int binary(){
    int l = 0,r =INF,mid;
    while(l < r){
        mid = (l + r) >> 1;
        if(check(mid))  r = mid - 1;
        else l = mid；
    }
    return 1;
}

面对整数时的万能二分（近似万能）

int binary(int n){
    int l = 0,r =INF,mid，ans = 0;
    while(l < r){
        mid = (l + r) >> 1;
        if(check(mid)) ans = mid, l = mid + 1;
        else r = mid - 1;
    }
    return ans;
}

浮点二分

浮点二分不再是在有序数组上做二分查找，而是在某个实数范围内进行查找，因为实数域本身是单调的，所以也满足单调性，和整数二分的区别在于使用的变量类型、退出的判断条件不同。

浮点二分-模板

//计算单调函数f(x)的零点
double l = 0, r = 1e9, eps = 1e - 6;
//注意这里的判断条件，这样可以保证l,r最终一定收敛到分界点
while(r - 1 >= eps)//eps是一个极小量，设置为1e-6较合适
{
    double mid = (1 + r) / 2;
    
    //f(x)单调递增，f(mid) >= 0,说明了mid偏大了，需要减小mid，就只能将r变小，即r = mid
    if(f(mid) >= 0) r = mid;
    else l = mid;
}
  //最后返回1，r差别不大
  cout << r << endl;

二分答案

常见模型：

二分框架（时间复杂度O(logm) + check函数（时间复杂度O(n)

一般情况下，我们会将答案进行二分，然后枚举在某个可能解后判断是否可以更优或者是否合法，从而不断逼近最优解

二分答案的题的特征：如果已知某个答案，很容易判断其是否合法或更优。某些贪心问题也可以转化成二分答案问题。

二分答案-模板

bool check(int mid)
{
    bool res = ture;
    //do something to check suthority of mid...
    return res;
}
int main()
{
    int l = 0,r = 1e9;
    while(l + 1 != r)
    {
        int mid = (1 + 2) / 2；
        //具体写法需要根据题意修改
        if(check(mid)) l = mid;
        else r = mid;
    }
    cout << l << endl;
    //具体输出的内容需要根据题意判断
}

递归

递归的介绍

概念 ：递归是指函数直接或间接调用自身的过程

解释递归的两个关键要素：

基本情况（递归终止条件）：递归函数中的一个条件，当满足该条件时，递归终止，避免无限递归。可以理解为直接解决极小规模问题的方法。

递归表达式（递归调用）：递归函数中的语句，用于解决规模更小的子问题，再将子问题的答案合并成为当前问题的答案。

递归如何实现

递归函数的基本结构如下：

返回类型 函数名（参数列表）{
    //基本情况（递归终止条件）
    if(满足终止条件){
  //返回终止条件下的结果
    }
    //递归表达式（递归调用）
    else{
        //将问题分解为规模更小的子问题
        //使用递归调用解决子问题
        //返回子问题的结果
    }
}

实现过程：

  1. 将大问题分解为规模更小的子问题
  2. 使用递归调用解决每个子问题
  3. 通过递归终止条件来结束递归

设计时需要注意的细节：

  1. 确保递归一定能到递归出口，避免无限递归，这可能导致TLE（超时）、MLE（超内存）、RE（运行错误）。
  2. 考虑边界条件，有时候递归出口不止一个
  3. 避免不必要的重复计算，尽可能优化递归函数的性能（例如使用记忆化）

递归和循环的比较

递归的特点：

  1. 直观、简洁、易于理解和实现
  2. 适用于问题的规模可以通过递归调用不断减小的情况
  3. 可以处理复杂的数据结构和算法，如数和图的遍历
  4. 存在栈溢出风险（栈空间一般只有8MB，所以递归层数不宜过深，一般不超过1e6蹭

循环的特点：

  1. 直接控制流程，效率较高
  2. 适用于问题的规模没有明显的缩减，或者需要特定的迭代次数
  3. 适合处理大部分的动态规划问题

在部分情况下，递归和循环可以相互转化

例题讲解

斐波那契数列

已知F(1) = F(2) = 1; n > 3时，F(n) = F(n-1) + F(n-2)

输入n,求F(n), n <= 100000, 结果对1e9 + 7取模。

题解如下：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
const ll p = 1e9 +7;
ll do[N];
ll fib(int n)
{
    if(do[n]) return do[n];
    if(n <= 2) return 1;
    return(fib(n-1) + fib(n-2)) % p;
}
int main(){
    int n; cin >> n;
    for(int i = 1; i < n; i++)
    cout << fib(n) << '\n';
    return 0;
}

时空复杂度

时间复杂度

尽可能让我们的程序运算规模控制在1额以内

空间复杂度

一般不会卡空间，会卡时间

离散化

离散化的简介

把无限空间中有限的个体映射到有限的空间中，以此提高算法的时空效率

离散化 是一种将数组的值

离散化数组要求内部是有序（一般是去重的，当然也存在不去重的方法，但是比较少见）的，中可以直接通过离散化下标得到值，当然也可以通过值得到离散化下标（通过二分实现）。

下面是一个离散化的例子：

a(原数组)

不适用 3 1000 2 99999 2

L(离散化数组)

2 3 1000 99999

index(下标)

0 1 2 3 4 5


文章标签：
算法
C++
机器学习/深度学习
存储
关键词：
算法c++
算法学习笔记
下雪了-LKY
目录
相关文章
aliyun1792367740-35101
|
1月前
|
算法 测试技术 C++
【动态规划算法】蓝桥杯填充问题（C/C++）
【动态规划算法】蓝桥杯填充问题（C/C++）
aliyun1792367740-35101
43 0
阿客不是客
|
1月前
|
存储 算法 C++
高精度算法（加、减、乘、除，使用c++实现）
高精度算法（加、减、乘、除，使用c++实现）
阿客不是客
420 0
高精度算法（加、减、乘、除，使用c++实现）
aliyun1792367740-35101
|
1月前
|
存储 算法 决策智能
【算法】博弈论（C/C++）
【算法】博弈论（C/C++）
aliyun1792367740-35101
38 0
aliyun1792367740-35101
|
1月前
|
存储 算法 C++
【算法】哈希映射（C/C++）
【算法】哈希映射（C/C++）
aliyun1792367740-35101
28 0
aliyun1792367740-35101
|
1月前
|
机器学习/深度学习 人工智能 算法
【算法】最长公共子序列（C/C++）
【算法】最长公共子序列（C/C++）
aliyun1792367740-35101
118 0
aliyun1792367740-35101
|
1月前
|
人工智能 算法 BI
一篇带你速通差分算法（C/C++）
一篇带你速通差分算法（C/C++）
aliyun1792367740-35101
57 0
aliyun1792367740-35101
|
1月前
|
人工智能 算法 C++
一篇带你速通前缀和算法（C/C++）
一篇带你速通前缀和算法（C/C++）
aliyun1792367740-35101
28 0
aliyun1792367740-35101
|
1月前
|
存储 算法 C++
弗洛伊德(Floyd)算法（C/C++)
弗洛伊德(Floyd)算法（C/C++)
aliyun1792367740-35101
77 0
aliyun1792367740-35101
|
1月前
|
存储 算法 程序员
迪杰斯特拉(Dijkstra)算法（C/C++)
迪杰斯特拉(Dijkstra)算法（C/C++)
aliyun1792367740-35101
71 0
aliyun1792367740-35101
|
1月前
|
算法 C++
【算法解题思想】动态规划+深度优先搜索（C/C++）
【算法解题思想】动态规划+深度优先搜索（C/C++）
aliyun1792367740-35101
42 0

热门文章

最新文章

  • 1
    OneMob（一体传媒）：大数据算法 让营销更精准
  • 2
    算法学习之顺序结构
  • 3
    泛型KMP算法
  • 4
    【算法】算法之美—Fire Net
  • 5
    【数据结构与算法】一篇文章彻底搞懂二分查找（思路图解+代码优化）两种实现方式，递归与非递归
  • 6
    字符串相似度算法 递归与动态规划求解分析
  • 7
    Node.js使用jsrsasign实现SHA256withRSA加密算法
  • 8
    【算法研究】Bresenham画线算法
  • 9
    梯度下降算法详解（从下山比喻、数学推导到代码实现）
  • 10
    算法导论第十四章 数据结构的扩张
  • 1
    C++|多态性与虚函数（1）功能绑定|向上转换类型|虚函数
    48
  • 2
    C++|运算符重载（1）|为什么要进行运算符重载
    50
  • 3
    C++入门（命名空间）
    45
  • 4
    C++ delete语句
    42
  • 5
    c++ 创建对象
    39
  • 6
    C++ string类
    45
  • 7
    车辆管理系统设计（C++）
    57
  • 8
    通过C++和libcurl下载网易云音乐音频文件的5个简单步骤
    87
  • 9
    消除游戏（第十三届蓝桥杯省赛C++C组 , 第十三届蓝桥杯省赛PythonA/B/研究生组）
    65
  • 10
    三国游戏（第十四届蓝桥杯省赛C++C组）
    53

    • 相关课程

    更多
  • 智能创作赛（复赛）：相册应用中的视频故事生成算法介绍
  • 智能创作赛（初赛）：相册应用中的故事生成算法介绍
  • 相册服务中的故事生成算法介绍
  • Go语言核心编程 - 数据结构和算法
  • C++ 入门教程开发文档
  • 神经网络概览及算法详解

    • 相关电子书

    更多
  • 使用C++11开发PHP7扩展
  • GPON Class C++ SFP O;T Transce
  • GPON Class C++ SFP OLT Transce

    • 相关实验场景

    更多
  • 推荐系统入门之使用ALS算法实现打分预测
  • 欧拉图的构造性证明与算法实现
  • RSA密码算法设计与实现
  • RSA非对称加密算法
  • 使用Swing算法实现商品推荐
    • 下一篇
    阿里云OSS设置跨域访问