在给定范围内找到4和7的数量乘积最大的数字的算法

Question

我卡在一个问题上，其中给定下限L和上限U。
现在假设在整数X的十进制表示中，数字4出现了A次，数字7出现了B次。
问题是找到L<=X<=U范围内A*B值最大的X。
是否有有效的算法来解决它？

- hell coder

---

可能。你尝试了多少？ - AHungerArtist

@AHungerArtist我无法设计任何可行的算法。由于L和U的限制可以达到10^18，我认为检查L和R之间每个数字的算法是不可行的。请帮我。 - hell coder

Answer 1

如果我正确理解了问题，以下方法应该可以解决：

• 假设所有数字的位数相同（如果例如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。
  • 现在用4和7来填满余下的X，使你在分配了更多的7时选择一个4，反之亦然。

---

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

给定 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

- Philosophus42

Answer 2

看起来你已经想好了算法。只需逐步分解并解决每个部分。我通常会像你那样写注释，然后将其分解，直到它们可以以合理的代码大小编写。

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

- Kristian Moström

---

请您能否再详细解释一下，最好能够举个例子。 - hell coder

这个回答过于笼统，没有价值。 - AHungerArtist