• 跑步问题 - 暴力法
  • 题目
  • 分析
    • 规律
  • 代码实现
    • 1. 初步框架
    • 2. dfs
    • 3. 补全

跑步问题 - 暴力法

题目

某人准备跑20圈来锻炼自己的身体，他准备分多次(>1)跑完，每次都跑正整数圈，然后休息下再继续跑。 为了有效地提高自己的体能，他决定每次跑的圈数都必须比上次跑的多, 设第一次圈数不能小于0，那么请问他可以有多少种跑完这 20 圈的方案? 输出方案总数，以及每种方案的排序。（比如1,19/ 1,2,17 都是有效方案）

分析

本题用动态规划等方法好做,因为圈数比较小,能够方便使用暴力方案解决;

根据条件:1. 他准备分多次(>1)跑完 2.他决定每次跑的圈数都必须比上次跑的多;分析得出,答案是一系列递增的正数,是排列组合相关问题; 因此大概就是dfs思路了(需要归纳过才好理解,我刚好分析过两篇,有兴趣可以看看;C++算法题解 - 递归实现排列型枚举 - 递归法 (图文) (递归搜索树) - HJfjfK - 博客园 (cnblogs.com));

规律

画出来才清晰

1 2 3 4 5 = 15, +6=21 (不满足)
1 2 3 4 6 = 16,(不满足)
1 2 3 4 7 = 17,(不满足)
1 2 3 4 8 = 18,(不满足)
1 2 3 4 9 = 19,(不满足)
1 2 3 4 10 = 20(满足)

1 2 3 5 6 = 17, +7>20 (不满足)
1 2 3 5 7 = 18,				(不满足)
1 2 3 5 8 = 19,				(不满足)
1 2 3 5 9 = 20(满足)
...
2 3 4 5 6 = 20(满足)
2 3 4 6 = 15, +7=22(不满足)
2 3 4 7 = 16,
...
19,(不满足)
20,(不满足)

代码实现

1. 初步框架

细节处理比较粗糙,看看思路即可

## 命名不够专业,凑合凑合
const int N = 20;       //要跑20圈
int size = 0;           //方案数


dfs(下一次待跑圈数,已跑圈数)		##初步确定dfs递归参数,可以有多种方式,选择自己习惯的

int main() {
    std::vector<int> v; //映射方式;(或用栈或顺序表模拟栈 放入每次待跑圈数)
    v.resize(21, 0);	//扩容并初始化,或者直接使用定长数组

    //第一步的圈数,范围1到20圈
    for (int i = 1; i <= N; i++) {
        dfs(i, 0, v);
    }
    
    std::cout<<"总方案数: "<<size << std::endl;
    return 0;
}

2. dfs

1. 找递归出口,分别是不满足返回,和满足打印并返回
2. 递归遍历(排列组合常用方案)
3. 数组记录; 细节:注意要回溯
4. 边界优化,时间足够的情况下,可以找规律分析分析;时间紧的时候,紧张不好想就直接干了

//dfs(下一次待跑圈数,已跑圈数)
void dfs(int cnt, int ans, std::vector<int>& v) {
    if (ans + cnt  > 20)     //
    {
        出口
    }
    if (ans + cnt == 20) 
    {
        出口
    }

    v[cnt] = 1; //可以跑
    for (int i = cnt+1; i < N-ans; i++)      //在上一段规律细心分析可以发现,小于上一次的就不需要再遍历了,然后继续画下图分析规律,结果只需要遍历大于上一次,小于20的即可;
     /*
     i<N-ans,规律
     (more) (next)
      [1  --  19 =20-1] ->  [1,2 -- 17=20-3]      [1,2,3 -- 14=20-6]  即 ans(已跑圈数) <--> N-ans(要跑圈数)
      2  --  18 
      3  --  17
      ...
    */
   {
        dfs(i, ans+cnt, v); //下一次执行(待跑圈数,已跑圈数);
    }
    v[cnt] = 0; //回溯
}

3. 补全

#include<iostream>
#include<vector>

const int N = 20;       //要跑20圈
int size = 0;           //方案数

void Print(const std::vector<int>& v) {
    for (int i = 1 ; i<v.size();i++) {
        if (v[i] == 1) std::cout << i << " " ;
    }
    std::cout<<std::endl;
}

//dfs(下一次待跑圈数,已跑圈数)
void dfs(int cnt, int ans, std::vector<int>& v) {
    if (ans + cnt  > 20)     //
    {
        return ;
    }
    if (ans + cnt == 20) 
    {
        v[cnt] = 1;
        Print(v);
        v[cnt] = 0; //回溯
        size++;
        return ;
    }

    v[cnt] = 1; //可以跑
    for (int i = cnt+1; i < N-ans; i++)      
    /*
     i<N-ans,规律
     (more) (next)
      1  --  19    1,2 -- 17      1,2,3 -- 14  即 ans(已跑圈数) <--> N-ans(要跑圈数)
      2  --  18 
      3  --  17
      ...
    */
    {
        dfs(i, ans+cnt, v); //下一次执行(待跑圈数,已跑圈数);
    }
    v[cnt] = 0; //回溯
}

int main() {
    std::vector<int> v; //映射方式;(或用栈或顺序表模拟栈)
    v.resize(21, 0);

    //第一步的圈数,范围1到20圈
    for (int i = 1; i <= N; i++) {
        dfs(i, 0, v);
    }
    std::cout<<"总方案数: "<<size << std::endl;
    return 0;
}