本文共 4617 字，大约阅读时间需要 15 分钟。

斐波那契数列是一个经典的数列问题，它的定义是从前两项都为1开始，每一项等于前两项之和。以下是实现斐波那契数列的一个代码片段：

#include 
   
    #include 
    
     #include 
     
       // 这部分不需要，但就放着备用using namespace std;typedef long long ll;const int N = 10010;ll a[N];int n;int main() {    cin >> n;    a[1] = 1;    a[2] = 1;    for (int i = 3; i <= n + 1; i++) {        a[i] = a[i-1] + a[i-2];        // 以下不需要，防止输出太多        // cout << i << " " << a[i] << endl;    }    cout << a[n+1] << endl;    return 0;}
     
    
   

代金券组合

这是一个经典的背包问题变种，要求在有限的代金券数量内使总金额达到或接近目标。我们需要通过动态规划或深度优先搜索（DFS）来解决这个问题。

代码片段：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;typedef long long ll;const int N = 10010;int a[N];int n, p;int ans = 0x3f3f3f3f;bool f;void dfs(int r, int num) {    if (num >= ans) return;    if (r == 0) {        ans = min(ans, num);    }    if (r < 0) return;    for (int i = 1; i <= n; i++) {        dfs(r - a[i], num + 1);    }    return;}int main() {    while (cin >> p && p) {        cin >> n;        for (int i = 1; i <= n; i++) {            cin >> a[i];        }        sort(a + 1, a + n + 1);        reverse(a + 1, a + n + 1);        dfs(p, 0);    }    cout << ans << endl;    return 0;}
      
     
    
   

完全背包问题

这是一个典型的动态规划问题，需要确定在给定的物品数量和每个物品的价值限制下，如何达到或接近目标金额。

代码片段：

#include 
   
    #include 
    
     #include 
     
      using namespace std;typedef long long ll;const int N = 10010;int a[N];int n, p;int f[N];int main() {    while (cin >> p && p) {        cin >> n;        for (int i = 1; i <= n; i++) {            cin >> a[i];        }        memset(f, 0x3f, sizeof f);        f[0] = 0;        for (int i = 1; i <= n; i++) {            for (int j = a[i]; j <= p; j++) {                if (f[j] > f[j - a[i]] + 1) {                    f[j] = f[j - a[i]] + 1;                }            }        }        if (f[p] > 0x3f3f3f3f / 2) {            cout << "Impossible" << endl;        } else {            cout << f[p] << endl;        }    }    return 0;}
     
    
   

###Ruby迷宫寻路这是一个二维迷宫寻路问题，要求找到从起点到终点的最短路径。

代码片段：

#include 
   
    #include 
    
     #include 
     
      using namespace std;const int N = 110;int a[N][N];int f[N][N];int n, m;int main() {    cin >> n >> m;    for (int i = 1; i <= n; i++) {        for (int j = 1; j <= m; j++) {            cin >> a[i][j];        }    }    memset(f, 0x3f, sizeof f);    f[1][1] = a[1][1];    for (int i = 1; i <= n; i++) {        for (int j = 1; j <= m; j++) {            if (i == 1 && j == 1) continue;            f[i][j] = min(f[i-1][j], f[i][j-1]);            f[i][j] += a[i][j];        }    }    cout << f[n][m] << endl;    return 0;}
     
    
   

星际穿越

这是一个三维扩展迷宫问题，要求在有限的步数内达到最大值。

代码片段：

#include 
   
    #include 
    
     #include 
     
      using namespace std;const int N = 10;int a[10][10][10];bool vis[10][10][10];int n;int xx, yy, zz, maxx = 0;int ans = 0;void dfs(int x, int y, int z, int num) {    ans = max(ans, num);    int fx = x - 1;    int fy = y;    int fz = z;    if (fx >= 0 && fx < n && !vis[fx][fy][fz] && a[fx][fy][fz] < a[x][y][z]) {        vis[fx][fy][fz] = true;        dfs(fx, fy, fz, num + a[fx][fy][fz]);        vis[fx][fy][fz] = false;    }    fx = x + 1;    fy = y;    fz = z;    if (fx >= 0 && fx < n && !vis[fx][fy][fz] && a[fx][fy][fz] < a[x][y][z]) {        vis[fx][fy][fz] = true;        dfs(fx, fy, fz, num + a[fx][fy][fz]);        vis[fx][fy][fz] = false;    }    fx = x;    fy = y - 1;    fz = z;    if (fy >= 0 && fy < n && !vis[fx][fy][fz] && a[fx][fy][fz] < a[x][y][z]) {        vis[fx][fy][fz] = true;        dfs(fx, fy, fz, num + a[fx][fy][fz]);        vis[fx][fy][fz] = false;    }    fx = x;    fy = y + 1;    fz = z;    if (fy >= 0 && fy < n && !vis[fx][fy][fz] && a[fx][fy][fz] < a[x][y][z]) {        vis[fx][fy][fz] = true;        dfs(fx, fy, fz, num + a[fx][fy][fz]);        vis[fx][fy][fz] = false;    }    fx = x;    fy = y;    fz = z - 1;    if (fz >= 0 && fz < n && !vis[fx][fy][fz] && a[fx][fy][fz] < a[x][y][z]) {        vis[fx][fy][fz] = true;        dfs(fx, fy, fz, num + a[fx][fy][fz]);        vis[fx][fy][fz] = false;    }    fx = x;    fy = y;    fz = z + 1;    if (fz >= 0 && fz < n && !vis[fx][fy][fz] && a[fx][fy][fz] < a[x][y][z]) {        vis[fx][fy][fz] = true;        dfs(fx, fy, fz, num + a[fx][fy][fz]);        vis[fx][fy][fz] = false;    }}int main() {    cin >> n;    for (int i = 1; i <= n*n*n; i++) {        int x, y, z;        cin >> x >> y >> z;        int p;        cin >> p;        a[x][y][z] = p;        if (p > maxx) {            xx = x;            yy = y;            zz = z;            maxx = p;        }    }    vis[xx][yy][zz] = true;    dfs(xx, yy, zz, maxx);    cout << ans << endl;    return 0;}