查找下一個多行的算法

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（這是一個更大的算法的一小部分），但如果它是全數直接數學，僞代碼將同樣有用。

Answer 1

如果x和y是正int當時的這將工作：

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

使用x-1讓您不必擔心特殊情況x是y的倍數。例如，如果y = 5，然後16 <= x <= 20，

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

Answer 2

恩，那麼呢？

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

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）

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; 
     } 

    } 

} 

MyFormula（在這個問題），似乎工作得很好。RecommendedFormula沒有，但這可能只是因爲我使用的類型（這是我需要在成品中使用）。