найти самое круглое число между двумя заданными |
Здравствуйте, гость ( Вход | Регистрация )
найти самое круглое число между двумя заданными |
mezmay |
20.3.2010, 16:35
Сообщение
#1
|
Активный участник Группа: Участник Сообщений: 272 Регистрация: 13.7.2009 Из: Ростов-на-Дону Пользователь №: 904 Спасибо сказали: 16 раз(а) Репутация: 1 |
Нужна функция, которая бы быстро могла найти самое круглое целое число между двумя заданными. Например:
f(9, 11) = 10; f(121, 199) = 150; f(1, 9999) = 5000; есть моя медленная реализация (долго на больших, сильно удаленных друг от друга числах):
вопрос - КАК сделать это быстрее? |
|
|
maint |
20.3.2010, 17:22
Сообщение
#2
|
Участник Группа: Участник Сообщений: 235 Регистрация: 3.8.2009 Из: Иркутск Пользователь №: 982 Спасибо сказали: 28 раз(а) Репутация: 2 |
|
|
|
BRE |
20.3.2010, 17:23
Сообщение
#3
|
Профессионал Группа: Участник Сообщений: 1112 Регистрация: 6.3.2009 Из: Ростов-на-Дону Пользователь №: 591 Спасибо сказали: 264 раз(а) Репутация: 44 |
f(121, 199) = 150;
А в этом случае ответ точно должен быть 150, а не 160? Что должна вернуть функция, при: f(22, 23) = ? Если работать с целыми числами, то я бы начал пробовать с этого:
Опиши подробней свойства функции. Сообщение отредактировал BRE - 20.3.2010, 17:54 |
|
|
mezmay |
20.3.2010, 18:27
Сообщение
#4
|
Активный участник Группа: Участник Сообщений: 272 Регистрация: 13.7.2009 Из: Ростов-на-Дону Пользователь №: 904 Спасибо сказали: 16 раз(а) Репутация: 1 |
f(121, 199) = 150; А в этом случае ответ точно должен быть 150, а не 160? Что должна вернуть функция, при: f(22, 23) = ? Если работать с целыми числами, то я бы начал пробовать с этого:
Опиши подробней свойства функции. В идеале функция должна возвращать те же значения, которые выдает моя. Опищу свойства этого самого требуемого круглого числа: на примере (121, 199): как в исходнике написано, основа всех круглых чисел - числа 1,2,5, потом они умножаются на 10 и получается тройка 10, 20, 50, ... 1000, 2000, 50000, ... Итак, нам на вход поступили числа 121 и 199. Рассматриваем все числа в заданном диапазоне. Делим каждое из них на 1, на 2 , на 5, потом умножаем массив на 10 и делим каждое уже на 10, 20, на 50. на 100 ни одно из чисел заданного диапазона не делится, следовательно, самое большое число, на которое разделилось одно из чисел диапазона - 50. Ему соответствует значение 150. его и возвращаем! Функция f(22, 23) должна вернуть 22 |
|
|
BRE |
20.3.2010, 18:56
Сообщение
#5
|
Профессионал Группа: Участник Сообщений: 1112 Регистрация: 6.3.2009 Из: Ростов-на-Дону Пользователь №: 591 Спасибо сказали: 264 раз(а) Репутация: 44 |
Все равно я не очень понял.
А напиши ряд круглых чисел: 10, 20, 50, ... или как он должен выглядеть? (121, 199) = 150 А (121, 202) = ? Чему должен быть равен? |
|
|
mezmay |
20.3.2010, 19:14
Сообщение
#6
|
Активный участник Группа: Участник Сообщений: 272 Регистрация: 13.7.2009 Из: Ростов-на-Дону Пользователь №: 904 Спасибо сказали: 16 раз(а) Репутация: 1 |
Все равно я не очень понял. А напиши ряд круглых чисел: 10, 20, 50, ... или как он должен выглядеть? (121, 199) = 150 А (121, 202) = ? Чему должен быть равен? ... 10, 20, 50, ... - это не все круглые числа, а как бы основа всех круглых...)) Короче передо мной стояла задача найти самое круглое число между двумя заданными. Первый вопрос который у меня возник - "а что такое круглое число ваще??" Я попытался формализовать это понятие так: Определение. "Даны два целых числа а и в. Дан числовой ряд А: 1, 2, 5, 10, 20, 50, 100, 200, 500, .... САМЫМ КРУГЛЫМ ЧИСЛОМ МЕЖДУ ДВУМЯ ЗАДАННЫМИ называется такое число с, которое делится на член ряда А с максимальным номером. Ряд А формируется умножением массива 1,2,5 на 10 на 100 на 1000 и так далее" f(121, 202) будет число 200, так как оно делится аж на 200 Сообщение отредактировал mezmay - 20.3.2010, 19:15 |
|
|
mezmay |
20.3.2010, 20:20
Сообщение
#7
|
Активный участник Группа: Участник Сообщений: 272 Регистрация: 13.7.2009 Из: Ростов-на-Дону Пользователь №: 904 Спасибо сказали: 16 раз(а) Репутация: 1 |
|
|
|
Iron Bug |
20.3.2010, 20:33
Сообщение
#8
|
Профессионал Группа: Модератор Сообщений: 1611 Регистрация: 6.2.2009 Из: Yekaterinburg Пользователь №: 533 Спасибо сказали: 219 раз(а) Репутация: 12 |
ну, во первых, расмотрим, к примеру, делитель 5. если число не делится на 5, то он не делится на 50, 500 и т.д. следовательно, можно сначала просто проверять делимость на 5. очевидно, что каждое пятое число натурального ряда делится на 5.
так что можно для начала делить, скажем, на 5 и смещаться по единице. в пределах первых пяти чисел будет найдено число, которое будет делиться на пять. далее, найдя это число, которое делится на 5, его можно проверить на делимость на 50, 500 и т.д, и после него уже можно идти не со смещением +1, а со смещением +5. так как между ними уже гарантированно ничего на 5 не делится. аналогично и с двойкой и прочими числами. так что это можно сразу отсекать и даже не проверять. уже экономия операций. на основе делимости можно изобрести более хитрый алгоритм. скажем, обнаружив, что мы можем идти со смещением не +5, а +50 или +500 - сначала двигаться с таким смещением, пока не выйдем за пределы интервала. аналогично, в несколько проходов, проверять остальные числа ряда А, порождённые основаниями 1 и 2. |
|
|
mezmay |
20.3.2010, 20:46
Сообщение
#9
|
Активный участник Группа: Участник Сообщений: 272 Регистрация: 13.7.2009 Из: Ростов-на-Дону Пользователь №: 904 Спасибо сказали: 16 раз(а) Репутация: 1 |
есть!!! Сообщение отредактировал mezmay - 20.3.2010, 20:53 |
|
|
Iron Bug |
20.3.2010, 20:57
Сообщение
#10
|
Профессионал Группа: Модератор Сообщений: 1611 Регистрация: 6.2.2009 Из: Yekaterinburg Пользователь №: 533 Спасибо сказали: 219 раз(а) Репутация: 12 |
но только ты удостоверься, что компилер правильно понимает твою конструкцию:
int c = i2/d*d; а то он может и соптимизировать так что лучше сначала подели и приведи к целому, а потом умножай. |
|
|
Текстовая версия | Сейчас: 7.10.2024, 11:09 |