Алгоритм поиска следующего кратного

Question

Учитывая два положительных целых числа x и y, мне нужно найти следующее число, большее или равное x, кратное y.

Например:

х = 18, у = 3 => 18

или

х = 18, у = 5 => 20

или

х = 121, у = 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 - нет, но это может быть только из-за типов, которые я использовал (это то, что мне нужно будет использовать в готовом продукте).