Вопрос: определить что вторая слева цифра числа делится на 3.

Примеры: 13, 89022 -- делится (3 и 9), 725933 -- не делится (2).

Решение должно быть понятным и быстрым.

Здравствуйте, 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];
— получить значение массива по индексу, равному полученному на первом шаге числу.

Здравствуйте, ry, Вы писали:

А в чём тогда был прикол, если оценил решения? Есть более быстрые решения. В лом думать над ними, если их нет.

Здравствуйте, 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]

Здравствуйте, ry, Вы писали:

ry>А в чём тогда был прикол, если оценил решения? Есть более быстрые решения. В лом думать над ними, если их нет.

Это не этюд а простой вопрос на наиболее практичное решение.

Здравствуйте, 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>Решение должно быть понятным и быстрым.

uint32_t twoM(boost::uint32_t i){
    if(i <= 9999){
        if(i <= 99){
            if(i <= 9)
                throw std::runtime_error("nahuy");
            else
                return i % 10;
        }
        else
            return (i <= 999) ? (i / 10) % 10 : (i / 100) % 10;
    }
    else{
        if(i <= 999999)
            return (i <= 99999) ? (i / 1000) % 10 : (i / 10000) % 10;
        else{
            if (i <= 99999999)
                return (i <= 9999999 ) ? (i / 100000) % 10 : (i / 1000000) % 10;
            else
                return (i <= 999999999 ) ? (i / 10000000) % 10 : (i / 100000000) % 10;
        }
    }
}
bool kaka(uint32_t i)
{
    uint32_t s = twoM(i);
    return !(s % 3);
}

int main()
{
    uint32_t i;
    std::cin >> i;
    if(i < 10)
        return 1;
    std::cout << kaka(i) << std::endl;
    return 0;
}

Здравствуйте, Shmj, Вы писали:

S>Вопрос: определить что вторая слева цифра числа делится на 3.

S>Примеры: 13, 89022 -- делится (3 и 9), 725933 -- не делится (2).

S>Решение должно быть понятным и быстрым.

bool Foo(int num)
{
    if (num > 9)
        return (new[] { '3', '6', '9'}).Contains(num.ToString[1]);
    else
        return false;
}

Здравствуйте, 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);

M>>* чуть быстрее — делить на 10 пока число не станет меньше 10. остаток от последнего деления — искомая цифра.
Н>самое верное, только делить долго
Н>надо от y = 100 проверять, не больше ли число чем y
Н>да — умножаем y*10
Н>нет — берем x = число % 10, а потом bool res = !(x % 3);

+ для менее 10 — сразу false

Здравствуйте, 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-х диапазонов.

Превратить число в строку, взять вторую цифру и проверить.
Все современные языки это умеют.

Менее 10 не подходит по условию задачи.

Здравствуйте, 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 будет быстрей.