2

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

我的方法

#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;
}

我假设先从增长最快的函数开始,然后再从其他函数开始是错误的,

欢迎任何帮助。

4

2 回答 2

2

一个问题是,什么是“最快”取决于x. 例如,x=0最初 thenx+x不会增长太多,而且x=1最快的是x+2, not 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 的步数图表的外观,我的疯狂猜测是,解决方案有一个封闭的形式:看起来并不明显但不是完全随机的......

在此处输入图像描述

于 2014-03-19T21:10:34.967 回答
0

我将描述一个一般策略,期望函数应用程序的最大数量。有3例。在所有情况下假设 x < y。将源人口和目标人口数视为位串 X 和 Y。

情况 1 如果 X 和 Y 在最高有效位上逐位一致。

A(x) = x + 1 ----> 如果最低有效位为 0,则将其更改为 1。 C(x) = x + x = 2*x ----> 将 x 位串左移 1

例如

x = 9 and y = 37, so 
X = 1001, Y= 100101

因此,您可以使用 C 两次 9+9 ---> 18 + 18 ---> 36 或 X = 10010 (18) 然后 100100 (36) 将 X 向左移动 2,然后加 1 得到 37。

X = {1001,10010,100100,100101}

所以3个应用程序。所以在案例 1 中,策略将是重复应用 C 和 A 并建立 X 以按位匹配 Y。每次移位需要 1 个 C 操作,生成 1 需要 1 个 A 操作。因此,在情况 1 中,将需要 Length(Y) - Length(X)(C 操作的数量)+ 1 的最低有效位的数量Y 位(A 操作)。在最坏的情况下,它将全为 1 或 2*(Length(Y) - Length(X))。在这种情况下,使用 B 没有帮助。最坏的情况是 O(Length(Y)) = O(log(y))

案例 2 (x < 2)

在这种情况下,使用 B 比 C 更快地添加到 X,并且在某些情况下(如上所述)使用 B 而不是情况 1 的一般策略会更好 1。

所以如果 x = 1 和 y = 7,而不是

X = {1, 10, 11, 110, 111}, you can skip one step by using B
X = {1, 11, 110, 111}

案例 3. X 和 Y 不兼容。

如果 X 和 Y 在最高有效位上不一致,则需要通过应用 B 和 A 来修复 X。

例子

X = 110 (6) Y = 101011 (43)

strat  X = {110,1000,1010,10100,10101,101010,101011}

上面,X 在前 4 位有效位中固定为与 Y 一致,然后一旦完成,就使用案例 1 的策略。宽松的上限将为 x/2(应用 B x/2 次 = x)。

总体而言,预计复杂度为 O(x) + O(log(y)),这似乎与公认答案的图表大致一致。

于 2014-03-19T22:40:24.293 回答