算法设计与分析

A：动态规划-楼梯问题

题目描述

如果小明每步跨1阶楼梯或2阶楼梯，则爬上n阶楼梯总共有多少种方案。

输入

第1行输入1个正整数n的值。

输出

小明爬上n阶楼梯的总方案数。

样例输入

 复制

3

样例输出

 复制

3

提示

可以用动态规划实现。F(1)=1,F(2)=2;  F(n)=F(n-1)+F(n-2) n>2。
#include "stdio.h"

void f(double a[],int n)
{

}

int main(void)
{
double a[101];
int n;

scanf("%d", &n);

f(a,n);
    
printf("%.lf\n", a[n]);

return 0;
}

#include <stdio.h>  
  
void f(double a[],int n) {  
    if (n <= 0) return; 
    a[1] = 1;
    if (n >= 2) {  
        a[2] = 2; 
        for (int i = 3; i <= n; i++) {  
            a[i] = a[i-1] + a[i-2];   
        }  
    }  
}  
  
int main(void)
{
double a[101];
int n;

scanf("%d", &n);

f(a,n);
    
printf("%.lf\n", a[n]);

return 0;
}

B：回溯法-放烟花问题

题目描述

现有n个炮筒可以独自放烟花，如果因为某种原因造成相邻的两个炮筒不能同时放烟花，则有多少种不同的放烟花方案数目。

输入

第1行输入1个正整数n的值（n<=40）

输出

不同的放烟花方案数目

样例输入

 复制

3

样例输出

 复制

5

提示

可以用回溯法或分枝限界法实现。上面的样例中如果没有两个炮筒不能同时放烟花的约束，则有8种情况；如果有了前面所说的限制条件，则110（前两个炮筒不能同时放烟花）、011（后两个炮筒不能同时放烟花）、111（三个炮筒不能同时放烟花）三种方案不可行。
#include "stdio.h" 

double count = 0; 
int x[41];
int n;


void Backtrack(int i) 
{ 

} 

int main(void) 
{ 

scanf("%d",&n);

Backtrack(1); 

printf("%.0lf", count); 

return 0;

}

#include "stdio.h" 

double count = 0; 
int x[41];  // 用来存放每个炮筒是否放烟花的状态
int n;

// 回溯函数
void Backtrack(int i) 
{ 
    if (i > n) {  // 如果处理完所有炮筒
        count++;  // 找到一种有效方案
        return;
    }

    // 尝试不放烟花
    x[i] = 0;
    Backtrack(i + 1);

    // 尝试放烟花，前提是前一个炮筒没有放烟花
    if (i == 1 || x[i - 1] == 0) {
        x[i] = 1;
        Backtrack(i + 1);
    }
} 

int main(void) 
{ 
    scanf("%d", &n);
    Backtrack(1); 
    printf("%.0lf\n", count); 
    return 0;
}

C：最长有序的子序列问题

<span style="background-color:#ffffff"><span style="color:#333333"><span style="color:#333333"><span style="background-color:#f5f5f5">6
5 2 3 4 1 6</span></span></span></span>

<span style="background-color:#ffffff"><span style="color:#333333"><span style="color:#333333"><span style="background-color:#f5f5f5">3</span></span></span></span>

#include "stdio.h"

void f(int count[], int a[], int n) {
    // 处理特殊情况
    if (n == 0) {
        return;
    }

    int maxLen = 1; // 用于记录最长连续递增子序列的长度
    int currentLen = 1; // 用于记录当前连续递增子序列的长度

    for (int i = 2; i <= n; i++) {
        if (a[i] > a[i-1]) {
            currentLen++;
        } else {
            currentLen = 1;
        }
        if (currentLen > maxLen) {
            maxLen = currentLen;
        }
    }

    count[1] = maxLen; // 只用一个位置存储结果
}

int main(void) {
    int i;
    int a[101];
    int count[101];
    int n;
    scanf("%d", &n);

    for (i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }

    f(count, a, n);

    printf("%d\n", count[1]);

    return 0;
}