Нужна функция, которая бы быстро могла найти самое круглое целое число между двумя заданными. Например:
f(9, 11) = 10;
f(121, 199) = 150;
f(1, 9999) = 5000;
есть моя медленная реализация (долго на больших, сильно удаленных друг от друга числах):
int round(const int &I1, const int &I2)
{
register int i1 = I1;
register int i2 = I2;
int result = -1;
//основа всех круглых чисел
register int cel[3];
cel[0] = 1;
cel[1] = 2;
cel[2] = 5;
int znak = 1;
if(i2<0)
{
int sw = i1;
i1 = -i2;
i2 = -sw;
znak = -1;
}
// ноль - самое круглое число
if(i1 < 0 && i2 > 0 || i1 == 0 || i2 == 0 )
result = 0;
else
{
// в общем случае делим каждое из чисел, расположенных
//между заданными, на круглые из массива (пока делятся)
register int count = 0;
register int j=0;
do
{
register int i = i1;
register int cnt = 0;
do
{
if(i%cel[j] == 0)
{
cnt ++;
result = i;
}
i++;
count = cnt;
} while (cnt < 1 && i < i2);
j++;
if(j == 3)
{
for(int k=0; k<3; k++)
cel[k] *= 10;
j=0;
}
} while (count > 0);
}
return result*znak;
}
f(121, 199) = 150;
А в этом случае ответ точно должен быть 150, а не 160?
Что должна вернуть функция, при:
f(22, 23) = ?
Если работать с целыми числами, то я бы начал пробовать с этого:
int round( int I1, int I2 )
{
return ((I1 + I2) / 2) / 10 * 10;
}
int round( int I1, int I2 )
{
return ((I1 + I2) / 2) / 10 * 10;
}
Все равно я не очень понял.
А напиши ряд круглых чисел:
10, 20, 50, ...
или как он должен выглядеть?
(121, 199) = 150
А (121, 202) = ? Чему должен быть равен?
int round( int I1, int I2 )
{
return ((I1 + I2) / 2) / 10 * 10;
}
ну, во первых, расмотрим, к примеру, делитель 5. если число не делится на 5, то он не делится на 50, 500 и т.д. следовательно, можно сначала просто проверять делимость на 5. очевидно, что каждое пятое число натурального ряда делится на 5.
так что можно для начала делить, скажем, на 5 и смещаться по единице. в пределах первых пяти чисел будет найдено число, которое будет делиться на пять. далее, найдя это число, которое делится на 5, его можно проверить на делимость на 50, 500 и т.д, и после него уже можно идти не со смещением +1, а со смещением +5. так как между ними уже гарантированно ничего на 5 не делится. аналогично и с двойкой и прочими числами. так что это можно сразу отсекать и даже не проверять. уже экономия операций.
на основе делимости можно изобрести более хитрый алгоритм. скажем, обнаружив, что мы можем идти со смещением не +5, а +50 или +500 - сначала двигаться с таким смещением, пока не выйдем за пределы интервала.
аналогично, в несколько проходов, проверять остальные числа ряда А, порождённые основаниями 1 и 2.
int round(int i1, int i2)// 0<= i1 < i2
{
int result;
int cel[3];
cel[0] = 1;
cel[1] = 2;
cel[2] = 5;
bool in = true;
while(in)
{
int i=0;
while(i<3)
{
int d = cel[i];
int c = i2/d*d; // главная мысль!
if(c < i1) //
{
if(i == 0)
result = cel[0]/2;
else
result = cel[i-1];
in = false;
break;
}
i++;
}
for(int j=0; j<3; j++)
cel[j]*=10;
}
return i2/result*result;
}
но только ты удостоверься, что компилер правильно понимает твою конструкцию:
int c = i2/d*d;
а то он может и соптимизировать так что лучше сначала подели и приведи к целому, а потом умножай.
Форум Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)