2

初期集団 x と正確な目的の集団 y が与えられた場合、3 つの関数 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

1 つの問題は、何が「最速」であるかに依存することxです。たとえば、x=0最初の thenx+xはあまり成長しません。またx=1、最速の isx+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 に到達するためのステップ数のグラフの外観を考えると、解決策には閉じた形式があると思います。明らかではありませんが、完全にランダムではありません...

ここに画像の説明を入力

于 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 を 2 回 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*(長さ (Y) - 長さ (X)) になります。この場合、B を使用しても役に立ちません。最悪の場合は O(Length(Y)) = O(log(y)) になります

ケース 2 (x < 2)

この場合、B を使用すると C よりも速く X に追加され、場合によっては (上記のように) ケース 1 の一般的な戦略の代わりに B を使用する方が 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 の strat を使用します。緩やかな上限は x/2 になります (B x/2 回 = x を適用します)。

全体的な複雑さは O(x) + O(log(y)) であると予測され、これは一般に受け入れられた回答のグラフと一致しているように見えます。

于 2014-03-19T22:40:24.293 に答える