Блог

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

Если x и y являются положительными int s, то это сработает:

 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
  

Хм, а как насчет?

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

Предполагая, что 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 (двойной)

Спасибо за ответы. Пока мне везло только с моим оригинальным решением, но я все равно хотел бы увидеть что-нибудь получше. Вот простой тестовый класс, который я создал, чтобы попытаться облегчить реализацию идей:

 package com.scratch;

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

public class Test {
    private static class Values {
        long x;
        long y;
        long resu<

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

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