Algorithms The Running Problem - The Violent Method

Running Problems - The Violent Method

title

A man is going to run 20 laps to improve his fitness. He is going to do this in several (>1) laps, each time running a positive integer number of laps, and then resting before continuing. In order to effectively improve his physical fitness, he decided that the number of laps must be more than the last time he ran, let the first time the number of laps can not be less than 0, then ask him how many kinds of running the 20 laps of the program? Output the total number of scenarios and the ordering of each scenario. (e.g. 1,19/ 1,2,17 are all valid solutions)

analyze

This problem is good to do with dynamic programming and other methods, because the number of circles is relatively small, and can be easily solved by using violent programs.

According to the conditions.1. he was going to run the race in multiple (>1) runs 2. he decided that each run had to be more laps than the last runThe analysis shows that the answer is a series of increasing positive numbers, which is a permutation-related problem; therefore, it is probably the dfs idea (which needs to be summarized in order to be well understood, and I have just analyzed two of them, so you can take a look at them if you're interested).C++ Algorithm Problem Solving - Recursive Implementation of Permutation Enumeration - Recursive Method (Graphic) (Recursive Search Tree) - HJfjfK - Blogland ());

rule (e.g. of science)

It's only clear when it's drawn.

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

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

code implementation

1. Preliminary framework

The details are rough, just look at the idea.

## Naming is not professional enough, make do with what you have
const int N = 20; //to run 20 laps
int size = 0; // program number


dfs (next to run laps, has run laps) ## preliminary determination of dfs recursive parameters, there can be a variety of ways, choose your own customary

int main() {
    std::vector<int> v; //mapping method;(or use a stack or sequential table to simulate a stack and put in the number of laps to be run each time)
    (21, 0); //expand and initialize, or just use a fixed length array

    //First step of the number of laps, the range of 1 to 20 laps
    for (int i = 1; i <= N; i++) {
        dfs(i, 0, v); }
    }

    std::cout<< "Total number of programs:"<<size << std::endl;
    return 0;
}

2. dfs

1. Find the recursive exit, which is return if not satisfied, and print and return if satisfied.
2. Recursive traversal (common scheme for permutations)
3. Array of records.Details:Be careful to backtrack
4. Boundary optimization, enough time in the case, you can find the law analysis analysis; time is tight, tension is not good to think directly dry

//dfs(next pending laps, number of laps run)
void dfs(int cnt, int ans, std::vector<int>& v) {
    if (ans + cnt > 20) //
    {
        Exit
    }
    if (ans + cnt == 20)
    {
        Exit
    }

    v[cnt] = 1; //can run
    for (int i = cnt+1; i < N-ans; i++) //in the previous paragraph of the law can be found in the careful analysis, less than the last time you do not need to traverse, and then continue to draw the next figure to analyze the law, the results only need to be traversed greater than the last time, less than 20 can be; /* /> the last time you can run, you can run; /* /* /* the last time you can run; /* /* the last time you can run; /* the last time you can run
     /*The result is that you only need to iterate over the last one, which is less than 20.
     i<N-ans, law
     (more) (next)
      [1 -- 19 =20-1] -> [1,2 -- 17=20-3] [1,2,3 -- 14=20-6] i.e. ans(number of laps run) <--> N-ans(number of laps to be run)
      2 -- 18
      3 -- 17
      ...
    */
   {
        dfs(i, ans+cnt, v); // next execution (number of laps to be run, number of laps run).
    }
    v[cnt] = 0; // backtracking
}

3. Completion

#include<iostream>
#include<vector>

const int N = 20; //run away20pen (pig)
int size = 0; //Number of programs

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

//dfs(下一次待跑pen (pig)数,已跑pen (pig)数)
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; //look back upon
        size++;
        return ;
    }

    v[cnt] = 1; //You can run.
    for (int i = cnt+1; i < N-ans; i++)
    /*
     i<N-ans,rule (e.g. of science)
     (more) (next)
      1 -- 19 1,2 -- 17 1,2,3 -- 14 assume (office) ans(已跑pen (pig)数) <--> N-ans(run awaypen (pig)数)
      2 -- 18
      3 -- 17
      ...
    */
    {
        dfs(i, ans+cnt, v); //Next execution(待跑pen (pig)数,已跑pen (pig)数);
    }
    v[cnt] = 0; //look back upon
}

int main() {
    std::vector<int> v; //mapping method;(Or simulate a stack with a stack or sequential table)
    (21, 0);

    //第一步的pen (pig)数,realm1until (a time)20pen (pig)
    for (int i = 1; i <= N; i++) {
        dfs(i, 0, v);
    }
    std::cout<<"总Number of programs: "<<size << std::endl;
    return 0;
}