仅使用A乘以2的最小步数，或将A除以2或将A加1以从A数变为B数 [英] Minimum number of steps using only multiply A by 2, or divide A by 2 or increment A by one to go from number A to B

问题描述

给定两个数字A和B，将数字A转换为数字B的最少步骤是多少？ 当且仅当A为偶数时，步骤可以是A *= 2、A++或A /= 2。

实现这一目标的最有效算法是什么？ 假设A和B可以是非常大的数字。

推荐答案

这是我用C#完成的摘录。

var a = 2;
var b = 15;

var found = new HashSet<int>() { a };

var operations = new (string operation, Func<int, bool> condition, Func<int, int> projection)[]
{
    ("/2", x => x % 2 == 0, x => x / 2),
    ("*2", x => x <= int.MaxValue / 2, x => x *2),
    ("+1", x => true, x => x + 1),
};

IEnumerable<(int count, string operations, int value)> Project((int count, string operations, int value) current)
{
    foreach (var operation in operations)
    {
        if (operation.condition(current.value))
        {
            var value = operation.projection(current.value);
            if (!found.Contains(value))
            {
                found.Add(value);
                yield return (current.count + 1, $"{current.operations}, {operation.operation}", value);
            }
        }
    }
}

var candidates = new[] { (count: 0, operations: $"{a}", value: a) };

while (!found.Contains(b))
{
    candidates =
        candidates
            .SelectMany(c => Project(c))
            .ToArray();
}

var result = candidates.Where(x => x.value == b).First();

Console.WriteLine($"{result.count} operations: {result.operations} = {result.value}");

输出：

5 operations: 2, +1, *2, +1, *2, +1 = 15

基本上，这是从第零步的a开始。然后，它采用这一代，并从操作中产生所有可能的值，以创建下一代。如果它产生了一个它已经看到的值，它会丢弃该值，因为有一个相等或更快的操作来产生该值。它一直重复，直到找到b。

这篇关于仅使用A乘以2的最小步数，或将A除以2或将A加1以从A数变为B数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！