次の多項式を見つけるアルゴリズム

Question

2つの正の整数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のある場合、これは動作します：

を x-1を使用して0

y * ((x-1)/y + 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だけで正常に動作するようです。推奨された形式はありませんが、それは私が使用したタイプ（最終製品で使用する必要があるタイプ）のためだけである可能性があります。