Сообщение Re[3]: Вопрос на элегантность решения от 02.10.2014 16:46
Изменено 02.10.2014 16:50 vsb
Здравствуйте, 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 сравнений.
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 сравнений.
Здравствуйте, 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]. Собственно по этой позиции и определяется ответ. Можно написать как я сказал, с массивом и т.д., а можно "развернуть" этот поиск в виде кода, будет такая большая (естественно автоматически генерируемая) лапша из нескольких сотен if-ов.
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]. Собственно по этой позиции и определяется ответ. Можно написать как я сказал, с массивом и т.д., а можно "развернуть" этот поиск в виде кода, будет такая большая (естественно автоматически генерируемая) лапша из нескольких сотен if-ов.