c++ - 给定初始种群 x，达到所需种群 y 的最少步骤是什么

Question

给定初始种群 x 和确切的期望种群 y， 到达 y 的最少步数是多少 使用三个函数 A{x+1}、B{x+2}、C{x+x}

我的方法

#include<iostream>
using namespace std;

int fA (int x)
{
    return x+1;
}
int fB(int x)
{
    return x+2;
}
int fC(int x)
{
    return x+x;
}

int main()
{
    int s, n;
    cin>>s>>n;

    int counter=0;

    while(fC(s)<=n)
    {
        s=fC(s);
        counter++;
    }

    while(fB(s)<=n)
    {
        s=fB(s);
        counter++;
    }

    while(fA(s)<=n)
    {
        s=fA(s);
        counter++;
    }

    cout<<counter;

    return 0;
}

我认为首先从增长最快的函数开始，然后是其他函数的假设是错误的，

欢迎任何帮助。

Answer 1

一个问题是“最快”取决于x。例如，最初使用 x=0 时，x+x 不会增长太多，并且使用 x=1 时，最快的是 x+2，而不是x+x。

我会使用直接完整搜索方法:

int min_steps(int x, int y) {
    std::set<int> active, seen;
    active.insert(x); seen.insert(x);
    int steps = 0;
    while (active.size() && active.find(y) == active.end()) {
        // `active` is the set of all populations that we can
        // reach in `steps` number of steps or less not greater
        // than the target value `y`.
        // The next set is computed by starting from every value
        // and applying every possible growth function.
        // `seen` is the set of all values we saw before to avoid
        // adding a value that has been checked before.
        steps++;
        std::set<int> new_active;
        for (std::set<int>::iterator i=active.begin(),e=active.end();
             i!=e; ++i) {
            for (int f=0; f<3; f++) {
                int z;
                switch(f) {
                    case 0: z = *i + 1; break;
                    case 1: z = *i + 2; break;
                    case 2: z = *i + *i; break;
                }
                if (z <= y && seen.find(z) == seen.end()) {
                    new_active.insert(z);
                    seen.insert(z);
                }
            }
        }
        active = new_active;
    }
    return active.size() ? steps : -1;
}

鉴于 x <= 1000 从 1 到 x 的步数图表的外观，我的疯狂猜测是解决方案有一个封闭形式:看起来不明显但不完全随机...