Эффективный алгоритм получения наибольшей мощности 10, который может делить целое число

Я хочу найти наибольшую мощность 10, которая может делить заданное целое число.Эффективный алгоритм получения наибольшей мощности 10, который может делить целое число

У меня есть упрощенно реализацию на текущий

int factorBase10Exp(int number){ 
//... 
int mBase10Exp = 0; 
while(number%10 == 0 && number != 0) 
    { 
     number /= 10; mBase10Exp++; 
    } 
//... 
return mBase10Exp; 
}

Ожидаемый выход

factorBase10Exp(3000) = 3 
factorBase10Exp(333) = 0

Я не могу использовать зЬй :: log10, как log10 (333) = 2.522, что дало бы неправильно результаты в моем случае использования.

Что я могу сделать, чтобы сделать это более эффективным?

источник

2014-10-09 VGigs

Вам нужно сделать это более эффективным? Требуется ли кто-то/что-то? Если ваш код работает медленно, не ожидайте, что подобные вещи станут узким местом, сначала начнется оценка – Creris

. Вы можете использовать двоичный поиск, но для 32 бит я нахожу его излишним. –

Вы не получите ничего разумного быстрее для 'int'. Теперь у вас есть O (бит), вы можете легко опуститься до O (ln (бит)), но я не уверен, что постоянные факторы не будут использовать разницу для небольших чисел. – luk32

Вы можете использовать серию делений, каждая из которых имеет половину числа цифр, как указано выше. Это дает вам двоякий поиск по числу нулей.

if (number % 100000000 == 0) 
{ 
    number /= 100000000; 
    mBase10Exp += 8; 
} 
if (number % 10000 == 0) 
{ 
    number /= 10000; 
    mBase10Exp += 4; 
} 
if (number % 100 == 0) 
{ 
    number /= 100; 
    mBase10Exp += 2; 
} 
if (number % 10 == 0) 
{ 
    number /= 10; 
    mBase10Exp++; 
}

Первое подразделение должно быть достаточно большим, чтобы покрыть более половины наибольшей мощности 10 вашего целых чисел.

источник

2014-10-09 15:20:37

Упрощение, потому что ответ умный, но все же думаю, что переход от не более 9 итераций к 4 не стоит количества кода. –

@JuanLopes: Это, скорее всего, будет зависеть от распределения вашего ввода. – tmyklebu

@JuanLopes Я не принимаю суждений о необходимости использования этого кода. И тот же принцип появляется в других контекстах, хорошо знать об этом методе. –

Итак, вы действительно хотите измерить, сколько нулей в конце вашего номера записано в десятичной форме. Если вы можете найти быстрый алгоритм преобразования своего номера в строку, вы можете просто подсчитать нули.

источник

2014-10-09 15:36:24 Cantfindname

Эффективный алгоритм получения наибольшей мощности 10, который может делить целое число

ответ

Смежные вопросы