Здравствуйте, Shmj, Вы писали:
S>Вопрос: определить что вторая слева цифра числа делится на 3.
S>Примеры: 13, 89022 -- делится (3 и 9), 725933 -- не делится (2).
S>Решение должно быть понятным и быстрым.
Первый вариант.
— сдвигать заданное число вправо, пока оно не попадёт в диапазон [10, 99];
— полученное число разделить на 10;
— остаток от деления проверить на делимость на 3 без остатка.
Второй вариант:
начальные данные: массив А, содержащий числа 13, 16, 19,..., 93, 96, 99.
— сдвигать заданное число вправо, пока оно не попадёт в диапазон [10, 99];
— проверить, содержится ли полученное число в массиве А.
Третий вариант:
Более правильный алгоритм второго варианта.
начальные данные: массив А размером 100, в индексах 13, 16, 19,..., 93, 96, 99 записана 1, в остальных — 0.
— сдвигать заданное число вправо, пока оно не попадёт в диапазон [10, 99];
— получить значение массива по индексу, равному полученному на первом шаге числу.
Здравствуйте, Shmj, Вы писали:
S>Вопрос: определить что вторая слева цифра числа делится на 3.
S>Примеры: 13, 89022 -- делится (3 и 9), 725933 -- не делится (2).
S>Решение должно быть понятным и быстрым.
А в чем вопрос то? в определении второй слева цифры?
* самый простой и понятный — ToString()[1]
* чуть быстрее — делить на 10 пока число не станет меньше 10. остаток от последнего деления — искомая цифра.
Здравствуйте, Shmj, Вы писали:
S>Вопрос: определить что вторая слева цифра числа делится на 3.
S>Примеры: 13, 89022 -- делится (3 и 9), 725933 -- не делится (2).
S>Решение должно быть понятным и быстрым.
1) проверяем что у число больше 9
2) пока число больше 127, сдвигаем число на 1 бит и считаем количество бит.
получаем число в форме x + 2^n + ε, x < 128
3) по таблице находим делится цифра или нет: table[x][n]
Здравствуйте, mogikanin, Вы писали:
M>Здравствуйте, Shmj, Вы писали:
S>>Вопрос: определить что вторая слева цифра числа делится на 3.
S>>Примеры: 13, 89022 -- делится (3 и 9), 725933 -- не делится (2).
S>>Решение должно быть понятным и быстрым.
M>А в чем вопрос то? в определении второй слева цифры? M>* самый простой и понятный — ToString()[1]
Ну как бы это — не комильфо. Сначала преобразуешь к строке, потом надо будет найденный символ преобразовывать обратно в число.
M>* чуть быстрее — делить на 10 пока число не станет меньше 10. остаток от последнего деления — искомая цифра.
Возьми любое из приведённых чисел, кроме 13, и проверь. Например, остаток от деления числа 89022 по твоему алгоритму будет 9022.
Здравствуйте, Shmj, Вы писали:
S>Вопрос: определить что вторая слева цифра числа делится на 3.
S>Примеры: 13, 89022 -- делится (3 и 9), 725933 -- не делится (2).
S>Решение должно быть понятным и быстрым.
Здравствуйте, mogikanin, Вы писали:
M>Здравствуйте, Shmj, Вы писали:
S>>Вопрос: определить что вторая слева цифра числа делится на 3.
S>>Примеры: 13, 89022 -- делится (3 и 9), 725933 -- не делится (2).
S>>Решение должно быть понятным и быстрым.
M>А в чем вопрос то? в определении второй слева цифры? M>* самый простой и понятный — ToString()[1]
много преобразований
M>* чуть быстрее — делить на 10 пока число не станет меньше 10. остаток от последнего деления — искомая цифра.
самое верное, только делить долго
надо от y = 100 проверять, не больше ли число чем y
да — умножаем y*10
нет — берем x = число % 10, а потом bool res = !(x % 3);
80% людей оценивают свое мастерство выше среднего...
M>>* чуть быстрее — делить на 10 пока число не станет меньше 10. остаток от последнего деления — искомая цифра. Н>самое верное, только делить долго Н>надо от y = 100 проверять, не больше ли число чем y Н>да — умножаем y*10 Н>нет — берем x = число % 10, а потом bool res = !(x % 3);
+ для менее 10 — сразу false
80% людей оценивают свое мастерство выше среднего...
Здравствуйте, ry, Вы писали:
ry>Здравствуйте, mogikanin, Вы писали:
M>>Здравствуйте, Shmj, Вы писали:
S>>>Вопрос: определить что вторая слева цифра числа делится на 3.
S>>>Примеры: 13, 89022 -- делится (3 и 9), 725933 -- не делится (2).
S>>>Решение должно быть понятным и быстрым.
M>>А в чем вопрос то? в определении второй слева цифры? M>>* самый простой и понятный — ToString()[1] ry>Ну как бы это — не комильфо. Сначала преобразуешь к строке, потом надо будет найденный символ преобразовывать обратно в число.
M>>* чуть быстрее — делить на 10 пока число не станет меньше 10. остаток от последнего деления — искомая цифра. ry>Возьми любое из приведённых чисел, кроме 13, и проверь. Например, остаток от деления числа 89022 по твоему алгоритму будет 9022.
сам возьми и проверь, молодой человек.
если нужно такие очевидные вещи объяснять, то я не знаю, как вы вообще в программистах оказались
89022 / 10 -> 8902
8902 / 10 -> 890
и т.д. пока не получится 8, остаток будет 9
Здравствуйте, mogikanin, Вы писали:
ry>>Возьми любое из приведённых чисел, кроме 13, и проверь. Например, остаток от деления числа 89022 по твоему алгоритму будет 9022. M>сам возьми и проверь, молодой человек. M>если нужно такие очевидные вещи объяснять, то я не знаю, как вы вообще в программистах оказались M>89022 / 10 -> 8902 M>8902 / 10 -> 890 M>и т.д. пока не получится 8, остаток будет 9
В таком случае остаток у тебя будет 0, а не 9.
Здравствуйте, mogikanin, Вы писали:
M>>>* чуть быстрее — делить на 10 пока число не станет меньше 10. остаток от последнего деления — искомая цифра. ry>>Возьми любое из приведённых чисел, кроме 13, и проверь. Например, остаток от деления числа 89022 по твоему алгоритму будет 9022. M>сам возьми и проверь, молодой человек. M>если нужно такие очевидные вещи объяснять, то я не знаю, как вы вообще в программистах оказались M>89022 / 10 -> 8902 M>8902 / 10 -> 890 M>и т.д. пока не получится 8, остаток будет 9
Признаю, был неправ.
Это следующие числа:
Двузначные: 13, 16, 19, 23, 26, 29, ..., 93, 96, 99.
Трёхзначные: 130-139, 160-169, ..., 960-969, 990-999.
И так далее. Если входное число до одного миллиарда, то максимальная длина числа будет 130 000 000 — 139 999 999, ...
Собственно решение — дерево сравнений. Будет максимум 5 сравнений.
Это на мой взгляд будет самое быстрое решение.
Самое элегантное — toString[1] in ('3', '6', '9').
Здравствуйте, vsb, Вы писали:
vsb>Это следующие числа: vsb>Двузначные: 13, 16, 19, 23, 26, 29, ..., 93, 96, 99. vsb>Трёхзначные: 130-139, 160-169, ..., 960-969, 990-999. vsb>И так далее. Если входное число до одного миллиарда, то максимальная длина числа будет 130 000 000 — 139 999 999, ...
vsb>Собственно решение — дерево сравнений. Будет максимум 5 сравнений.
Наверное худший случай все же не 5, а что-то в районе 16? 10 на неудачные сравнения длины, и внутри еще 6 — проверки начала и конца 3-х диапазонов.
Здравствуйте, ry, Вы писали: M>>А в чем вопрос то? в определении второй слева цифры? M>>* самый простой и понятный — ToString()[1] ry>Ну как бы это — не комильфо. Сначала преобразуешь к строке, потом надо будет найденный символ преобразовывать обратно в число.
Лучшее решение — преобразование к строке. Тоже самое что и второе, так как мы все равно по числу бегаем, но пишется в одну строчку и понятно с первого взгляда.
Здравствуйте, AlexRK, Вы писали:
ARK>Здравствуйте, vsb, Вы писали:
vsb>>Это следующие числа: vsb>>Двузначные: 13, 16, 19, 23, 26, 29, ..., 93, 96, 99. vsb>>Трёхзначные: 130-139, 160-169, ..., 960-969, 990-999. vsb>>И так далее. Если входное число до одного миллиарда, то максимальная длина числа будет 130 000 000 — 139 999 999, ...
vsb>>Собственно решение — дерево сравнений. Будет максимум 5 сравнений.
ARK>Наверное худший случай все же не 5, а что-то в районе 16? 10 на неудачные сравнения длины, и внутри еще 6 — проверки начала и конца 3-х диапазонов.
Я нолик упустил. Рассуждения такие. Все эти цифры делят всю числовую прямую на отрезки. Если у нас числа от 0 до 999 999 999, то будет 8 * 27 * 2 = 432 точек, разбивающих числовую прямую на отрезки (для 13, 16, 19 это "вырожденный" отрезок, там надо будет проверять на равенство, но сути не меняет). Каждый отрезок это или "попадание", т.е. выдаём true, или непопадание, т.е. выдаём "false". Каждое сравнение отсекает половину точек, так что будет по идее не более 9 сравнений.
Если будет понятней — то суть алгоритма такая. Все числа выписываем в массив. nums = [130, 139, 160, 169, 190, 199, ..., 990, 999, 1300, 1399, 1600, 1699, ..., 9600, 9699, 9900, 9999, 13000, 13999, ..., 130_000_000, 139_999_999, 160_000_000, 169_999_99, ..., 990_000_000, 999_999_999]. В этом массиве будет 378 элементов. Мы ищем позицию в этом массиве nums[i] <= x <= nums[i + 1]. Собственно по этой позиции и определяется ответ. Ищем методом деления пополам, должно найтись за не более 9 сравнений. Можно написать как я сказал, с массивом и т.д., а можно "развернуть" этот поиск в виде кода, будет такая большая (естественно автоматически генерируемая) лапша из нескольких сотен if-ов.
Как отнесётся современный процессор к такому коду, с его branch predictions, я не совсем понимаю и было бы интересно услышать. Вполне может быть, что поиск второй цифры делениями на 10 будет быстрей.
Здравствуйте, vsb, Вы писали:
vsb>Я нолик упустил. Рассуждения такие. Все эти цифры делят всю числовую прямую на отрезки. Если у нас числа от 0 до 999 999 999, то будет 8 * 27 * 2 = 432 точек, разбивающих числовую прямую на отрезки (для 13, 16, 19 это "вырожденный" отрезок, там надо будет проверять на равенство, но сути не меняет). Каждый отрезок это или "попадание", т.е. выдаём true, или непопадание, т.е. выдаём "false". Каждое сравнение отсекает половину точек, так что будет по идее не более 9 сравнений.
Здравствуйте, -n1l-, Вы писали:
M>>>* самый простой и понятный — ToString()[1] ry>>Ну как бы это — не комильфо. Сначала преобразуешь к строке, потом надо будет найденный символ преобразовывать обратно в число.
N>Лучшее решение — преобразование к строке. Тоже самое что и второе, так как мы все равно по числу бегаем, но пишется в одну строчку и понятно с первого взгляда.
То, что оно просто, понятно. А по скорости как?
Здравствуйте, Shmj, Вы писали:
S>Вопрос: определить что вторая слева цифра числа делится на 3.
S>Примеры: 13, 89022 -- делится (3 и 9), 725933 -- не делится (2).
S>Решение должно быть понятным и быстрым.
function f(x){
var mod = x%10;
var div = x/10;
return div==0 ? false : (div>9 ? f(div) : (mod % 3 == 0));
Здравствуйте, mogikanin, Вы писали:
M>Здравствуйте, Shmj, Вы писали:
S>>Вопрос: определить что вторая слева цифра числа делится на 3.
S>>Примеры: 13, 89022 -- делится (3 и 9), 725933 -- не делится (2).
S>>Решение должно быть понятным и быстрым.
M>А в чем вопрос то? в определении второй слева цифры? M>* самый простой и понятный — ToString()[1] M>* чуть быстрее — делить на 10 пока число не станет меньше 10. остаток от последнего деления — искомая цифра.
в первом варианте много лишних преобразований и по сути внутри мы будем иметь реализацию второго решения
char *itoa(i) int i;
{
/* Room for INT_DIGITS digits, — and '\0' */
static char buf[INT_DIGITS + 2];
char *p = buf + INT_DIGITS + 1; /* points to terminating '\0' */
if (i >= 0) {
do {
*--p = '0' + (i % 10);
i /= 10;
} while (i != 0);
return p;
}
else { /* i < 0 */
do {
*--p = '0' — (i % 10);
i /= 10;
} while (i != 0);
*--p = '-';
}
return p;
}
80% людей оценивают свое мастерство выше среднего...
Здравствуйте, ry, Вы писали: ry>То, что оно просто, понятно. А по скорости как?
Да говорю же тоже самое. Можно посмотреть примерный вариант в K&R.
Точно так же идем по числу(делим/сдвигаем) и получаем строку.
Ну у нас еще нужно будет char перевести в число, так это дело одной операции.
Так что скорость в норме.
Здравствуйте, -n1l-, Вы писали:
ry>>То, что оно просто, понятно. А по скорости как? N>Да говорю же тоже самое. Можно посмотреть примерный вариант в K&R. N>Точно так же идем по числу(делим/сдвигаем) и получаем строку. N>Ну у нас еще нужно будет char перевести в число, так это дело одной операции. N>Так что скорость в норме.
Не очень понятно, почему скорость в норме.
Сдвиги производятся в регистрах процессора, а преобразования к строке в ОЗУ. Скорость доступа к этой памяти несопоставима. Или я опять ошибаюсь?
Здравствуйте, ry, Вы писали:
ry>Не очень понятно, почему скорость в норме. ry>Сдвиги производятся в регистрах процессора, а преобразования к строке в ОЗУ. Скорость доступа к этой памяти несопоставима. Или я опять ошибаюсь?
Ошибаетесь, строка из числа получается при операции деления(K&R) такие операции проводятся в регистрах процессора тоже.
S>Вопрос: определить что вторая слева цифра числа делится на 3. S>Примеры: 13, 89022 -- делится (3 и 9), 725933 -- не делится (2).
S>Решение должно быть понятным и быстрым.
Здравствуйте, ononim, Вы писали:
S>>Вопрос: определить что вторая слева цифра числа делится на 3. S>>Примеры: 13, 89022 -- делится (3 и 9), 725933 -- не делится (2).
S>>Решение должно быть понятным и быстрым. O>
S>>>Вопрос: определить что вторая слева цифра числа делится на 3. S>>>Примеры: 13, 89022 -- делится (3 и 9), 725933 -- не делится (2). S>>>Решение должно быть понятным и быстрым. O>>
O>>хинди руси пхай пхай!
ARK>На входе число, а не строка.
В
естественной форме
(или в форме с фиксированной точкой) число представляется последовательностью десятичных цифр со знаком плюс или минус. Знак плюс можно опускать. Для отделения целой части числа от дробной используется не запятая, а точка. Ноль целых можно опускат
А вот если бы было сказано на входе int, или long, или binary-coded decimal — ответ был бы другой, или третий. Я это к тому что если просишь элегантное решение — элегантно формулируй задание.
Как много веселых ребят, и все делают велосипед...
Здравствуйте, Shmj, Вы писали:
S>Вопрос: определить что вторая слева цифра числа делится на 3.
S>Примеры: 13, 89022 -- делится (3 и 9), 725933 -- не делится (2).
S>Решение должно быть понятным и быстрым.
if (i >= 100000000) i /= 100000000;
if (i >= 10000) i /= 10000;
if (i >= 100) i /= 100;
if (i >= 10) i /= 10; // тут имеем число из 2 левых цифр
i = i % 10; // тут вторая слева цифраif (i % 3 == 0) {
// вторая слева цифра числа делится на 3
} else {
// вторая слева цифра числа НЕ делится на 3
}
Решение можно приспособить к int64 и int128 парой сточек кода.
Здравствуйте, vsb, Вы писали:
vsb>И так далее. Если входное число до одного миллиарда, то максимальная длина числа будет 130 000 000 — 139 999 999, ...
vsb>Собственно решение — дерево сравнений. Будет максимум 5 сравнений.
vsb>Это на мой взгляд будет самое быстрое решение.
будешь смеяться, но выгодней сделать последовательный поиск, а не двочный. каждый неверно предсказанный переход — ~15 тактов, предсказанный верно — меньше одного такта
Здравствуйте, vsb, Вы писали:
vsb>Как отнесётся современный процессор к такому коду, с его branch predictions, я не совсем понимаю и было бы интересно услышать. Вполне может быть, что поиск второй цифры делениями на 10 будет быстрей.
деление ещё хуже (10-100 тактов), умножения будут лучше. Edit: на самом деле деление на константу реализуется умнодением на обратное число, так что будет однофигственно. но задержка умножения — 3 такта, что явно не сравнить с поиском по степеням 10 или 100
но лучше использовать твой подход, только с линейным поиском. тогда у нас будет всего один ошибочно предсказанный переход (выход из цикла), и 5-10 удлачно предсказанных, которые обойдутся в 0.5-1 такта на переход
Здравствуйте, ry, Вы писали:
N>>Точно так же идем по числу(делим/сдвигаем) и получаем строку. N>>Ну у нас еще нужно будет char перевести в число, так это дело одной операции.
какой char? он как раз и получается из числа. ты сначала будешь добавлять '0', а затем вычитать его?
ry>Не очень понятно, почему скорость в норме. ry>Сдвиги производятся в регистрах процессора, а преобразования к строке в ОЗУ. Скорость доступа к этой памяти несопоставима. Или я опять ошибаюсь?
данные кешируются, обращение к L1$ — 4 такта, но часто эта задержка скрывается за общей конвейеризацией операций (ядро буферизует примерно 100 последних операций и выполняет их по мере готовности операндов)
Здравствуйте, vpchelko, Вы писали:
V>Самое быстрое и в принципе понятное будет:
1. неясно на каком проце тестировали
2. данные генерятся равномерно-распределёнными. дальше сами сообразите, как сделать код, который будет ещё быстрее на этих данных
V>if (i >= 100000000) i /= 100000000;
V>if (i >= 10000) i /= 10000;
V>if (i >= 100) i /= 100;
V>if (i >= 10) i /= 10; // тут имеем число из 2 левых цифр
V>i = i % 10; // тут вторая слева цифра
V>if (i % 3 == 0) {
V> // вторая слева цифра числа делится на 3
V>} else {
V> // вторая слева цифра числа НЕ делится на 3
V>}
V>
Делений многовато для самого быстрого решения.
Я бы сделал что-то вроде:
int64_t divisor[1<<4] = { 1, 10, 100, 10*100, 10000, 10*10000, 100*10000, 10*100*10000, 100000000, 10*100000000, 100*100000000, 10*100*100000000, 10000*100000000, 10*10000*100000000, 100*10000*100000000, 10*100*10000*100000000, };
size_t mask = 0;
if (i >= 100000000) mask |= (1<<3);
if (i >= 10000) mask |= (1<<2);
if (i >= 100) mask |= (1<<1);
if (i >= 10) mask |= (1<<0);
i = i/divisor[mask];
int32_t divisible_by_3[100] = {1,0,0,1,0,0,1,0,0,1,...........};
if (divisible_by_3[i]) {
// вторая слева цифра числа делится на 3
} else {
// вторая слева цифра числа НЕ делится на 3
}
Здравствуйте, Muxa, Вы писали:
M>Делений многовато для самого быстрого решения.
M>Я бы сделал что-то вроде: M>if (i >= 100000000) mask |= (1<<3); M>if (i >= 10000) mask |= (1<<2); M>if (i >= 100) mask |= (1<<1); M>if (i >= 10) mask |= (1<<0);
тут две ошибки. во-первых, для поиска делением диапазона пополам надо пересчитывать i после каждого сравнения. иначе для числа больше 100000000 у тебя сработают все if
M>i = i/divisor[mask];
во-вторых исходный код на самом деле вместо деления на константу компилируется в умножение на обратное число. а у тебя таки будет одно деление, и оно будет медленней даже 4 умножений
Здравствуйте, Shmj, Вы писали:
S>Вопрос: определить что вторая слева цифра числа делится на 3.
S>Примеры: 13, 89022 -- делится (3 и 9), 725933 -- не делится (2).
S>Решение должно быть понятным и быстрым.
Мне кажется многие утонули в деталях. Давайте сверху вниз:
2) Теперь нам нужны быстрые реализации для ulen и upow. Это полезные повторно используемые абстракции, с ними уже можно развернуться:
unsigned
upow(unsigned base, unsigned exp)
{
unsigned result = 1;
while (exp)
{
if (exp & 1)
result *= base;
exp >>= 1;
base *= base;
}
return result;
}
и соответственно:
unsigned
ulen (unsigned x)
{
if (x < 10) return 1;
if (x < 100) return 2;
if (x < 1000) return 3;
if (x < 10000) return 4;
if (x < 100000) return 5;
if (x < 1000000) return 6;
return 7;
}
3) Поскольку ответ я набивал прямо тут и даже не компилировал теперь нужны тесты на всякие граничные случаи: скажем когда верхняя децимальная граница перекрывает UINT_MAX и т.п. Всё это долго пишется и отлаживается и делает код чуть более уродливым.
4) Зато на выходе мы получаем искомую second_digit в меньше 10 строк и плюс две полезные функции в библиотеку
BZ>тут две ошибки. во-первых, для поиска делением диапазона пополам надо пересчитывать i после каждого сравнения. иначе для числа больше 100000000 у тебя сработают все if
Согласен, я затупил.
BZ>во-вторых исходный код на самом деле вместо деления на константу компилируется в умножение на обратное число. а у тебя таки будет одно деление, и оно будет медленней даже 4 умножений
В интах-то?
Насколько я знал такое может быть только при делении на float константу, а вот сейчас смотрю ассемблер — так оно и есть: деление на константу реализовано через умножение-сдвиг и какие-то таблицы.
Здравствуйте, Muxa, Вы писали:
M>В интах-то? M>Насколько я знал такое может быть только при делении на float константу
Забавно, но вот как раз с float так не всегда получается — если вместо деления на d делать умножение на (1.0/d), то результат, как правило, отличается от результата простого деления и обладает худшей точностью. Это связано с тем, что происходит лишнее округление при вычислении константы (1.0/d), ведь, как правило, это число не представимо точно. Так что обычно компиляторы вычисляют выражения с плавающей запятой практически ровно как они записаны, ведь даже внешне незначительные преобразования, вроде изменения порядка слагаемых в сумме, порой приводят к значительному изменению результата. И у компилятора недостаточно знаний о том, действительно-ли в данной формуле нужно строго соблюдать порядок операций или можно её преобразовать ради увеличения скорости. Собственно, тут всё решает программист и только он может сообщить компилятору, что (a/b) == a*(1/b) (например, путём указания соответствующих опций вроде ключа -ffast-math в gcc).
А вот с делением целого на целочисленную константу такого выбора не стоит — там всегда достигается истинный результат.
Здравствуйте, Shmj, Вы писали:
S>Вопрос: определить что вторая слева цифра числа делится на 3.
S>Примеры: 13, 89022 -- делится (3 и 9), 725933 -- не делится (2).
S>Решение должно быть понятным и быстрым.
Можно найти вторую цифру без строк через log10() и pow(). Плавающая математика у Интел очень быстрая.
int SecondDigit( int v ) // v - наше число
{
if ( v < 0 ) v = -v;
if ( v < 10 ) return -1; // второй цифры нет - вернуть -1 для примераint n = (int)log10((double) v); //число цифр -1 return v / (int)pow(10.0, n - 1) % 10;
}