寻找下一个倍数的算法

Question

给定两个正整数x和y，我需要找到大于或等于x的下一个倍数为y的数字。

例如：

x=18，y=3 => 18

或者

x=18，y=5 => 20

或者

x=121，y=25 => 125

我的第一个想法是逐渐增加x，直到找到匹配的数字，但对于较高的y值，这可能会变得相当低效。

然后我想到了 x - (x % y) + y ，但如果x是y的倍数，那么这种方法就不起作用了。当然，我可以在公式中使用三元运算符来进行调整 x - ((x % y)==0?y:x % y) + y 。

是否有任何好的、聪明的、简单的建议或比我提到的更好的完整解决方案？在我的逻辑中是否忽略了一些显而易见的事情？

我将使用Java（这是更大算法的一小部分），但伪代码如果只是纯粹的数学也会很有帮助。

- smp7d

---

我其实喜欢你的解决方案。 - Mike Christensen

我凭直觉想出了你的解决方案，可能有其他聪明的技巧，但我怀疑你不会找到更有效的东西了。 - Vincent Savard

你可以考虑在math.stackexchange.com上提问。 - Dan W

n.m.，你应该将其发布为答案！ - Vincent Savard

我们是在谈论正整数吗？ - ThomasMcLeod

你的解决方案很有前景（请查看我的答案中的RecommendedFormula2）。愿意将其作为一个回答加入吗？ - smp7d

Answer 1

如果x和y是正整数，则以下方法可行：

y * ((x-1)/y + 1);

使用 x-1 可以避免在 x 是 y 的倍数时出现特殊情况。例如，如果 y = 5，那么对于 16 <= x <= 20，使用 x-1。

15 <= x-1 <= 19
(x-1)/y == 3
(x-1)/y+1 == 4
y*((x-1)/y+1) == 20

- JohnPS

---

我一直认为 y * ((x+y-1)/y) 比另一种形式更好。数值相同，而且形式稍微更加简洁。 - James Waldby - jwpat7

你的答案在我将其插入到我的测试类中进行测试时表现良好。而且，我比起使用三元运算符的解决方案更喜欢你的答案。我认为这个问题有不止一个正确的答案。 - smp7d

Answer 2

嗯，怎么样？

tmp = ceil(x / y);
result = y * tmp;

- Pateman

---

如果 x 和 y 的类型为 int，那么这个方法行不通。例如，ceil(16/5) == ceil(3) == 3，因此你会得到 5*3 == 15，但实际上应该是 20。 - JohnPS

我已将您的建议添加为我发布的答案中的RecommendedFormula。我认为JohnPS的评论可能是正确的。 - smp7d

Answer 3

假设x和y都大于零。

数学公式非常简单： Ceil(x / y) * y

其中，Ceil(x)是大于或等于指定实数的最小整数值。

在Java中，您可以使用函数Math.ceil()来实现此目的： http://download.oracle.com/javase/1.4.2/docs/api/java/lang/Math.html#ceil(double

- Andrea Angella

---

我已经将您的建议作为RecommendedFormula添加到我发布的答案中（与Pateman的答案相同）。 我只是类型错误了吗？ - smp7d

Answer 4

感谢回复。到目前为止，我只有在原始解决方案上取得了成功，但我仍然希望看到更好的东西。这是一个简单的测试类，我建立它来尝试帮助促进想法：

package com.scratch;

import java.util.ArrayList;
import java.util.List;

public class Test {
    private static class Values {
        long x;
        long y;
        long result;

        Values(long x, long y, long result) {
            this.x = x;
            this.y = y;
            this.result = result;
        }
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        List<Values> list = new ArrayList<Values>();
        Values v1 = new Values(18, 3, 18);
        list.add(v1);
        Values v2 = new Values(18, 5, 20);
        list.add(v2);
        Values v3 = new Values(121, 25, 125);
        list.add(v3);
        Values v4 = new Values(9999999, 10, 10000000);
        list.add(v4);

        Operation operation = new MyFormula();
        // Operation operation = new RecommendedFormula();
            // Operation operation = new RecommendedFormula2();
        for (Values v : list) {
            System.out.println(v.x + ", " + v.y + " => " + v.result + "?");
            long res = operation.perform(v.x, v.y);
            System.out.println(res == v.result ? "worked" : "nope... Expected "
                    + v.result + ", got " + res);
        }
    }

    private static interface Operation {
        long perform(long x, long y);
    }

    private static class MyFormula implements Operation {

        @Override
        public long perform(long x, long y) {
            return x - ((x % y) == 0 ? y : x % y) + y;
        }

    }

    private static class RecommendedFormula implements Operation {

        @Override
        public long perform(long x, long y) {
            return (long) (Math.ceil(x / y) * y);
        }

    }

private static class RecommendedFormula2 implements Operation{

        @Override
        public long perform(long x, long y) {
            return x + (y - x % y) % y;
        }

    }

}

我的公式（在问题中）似乎工作得很好。 推荐的公式不行，但可能只是因为我使用了不同的类型（这是我在最终产品中需要使用的类型）。

- smp7d

---

添加RecommendedFormula2（从问题的评论中）。看起来像是获胜者？ - smp7d

为了让RecommendedFormula正常工作，你必须在除法之前将x和y中的至少一个转换为double类型。即使这样做了，对于大的x和/或y，它仍然会产生错误的结果。 - Daniel Fischer