3

我陷入了一个给出下限L和上限的问题U。
现在假设在整数X数字 4 出现A次数和数字 7 出现B次数的十进制表示中。
问题是找出X哪个具有最大值A*Bfor L<=X<=U。
有没有有效的算法来解决它？

4

2 回答 2

5

如果我正确理解了这个问题，以下应该可以工作：

  • 假设所有数字都具有相同的位数（例如，如果L的位数少于U，我们可以只用 0 填充开头）。
  • 让Z = U - L。
  • 现在我们从第一个（/最高/最左边）数字到最后一个数字。如果我们正在查看第i个数字，则令L (i)、U (i)、Z (i) 和X (i) 为对应的数字。
    • 对于所有为 0 的前导Z (i)，我们设置X (i) = L (i)（我们别无选择）。
    • 对于第一个非 0 Z (i) 检查：区间 [ L (i), U (i)-1]中是否有 4 或 7 ？如果是，则令X (i) 为 4 或 7，否则令X (i) = U (i)-1。
    • 现在用 4s 和 7s 填充X的其余部分，这样如果您到目前为止分配了更多的 7s，则选择 4s，反之亦然。

也许一个例子可以帮助理解这一点：

给定U = 5000 和L = 4900。

现在Z = 0100。

从我们设定的算法

  • X (1) = L (1) = 4（我们别无选择）
  • X (2) = U (2)-1 = 9 （Z中的第一个非 0 数字）
  • X (3) = 7（我们已经有了 4）
  • X (4) = 4（可任意选择）

导致X = 4974，目标为 2*1=2

于 2012-06-06T12:22:09.550 回答
-1

看来您已经考虑好了算法。只需将其分解并解决每个部分。我通常会写一些像你在那里所做的评论，然后将它们分解，直到它们达到合理的大小以编写代码。

当你让它工作时，如果需要，你可以优化它。

于 2012-06-05T14:08:42.587 回答