Помогал я недавно одному человеку найти решение такой задачи (формулировка отличалась, передаю лишь смысл): «Определить количество экземпляров каждой цифры от 0 до 9, которое понадобится, чтобы записать подряд числа от 1 до N (N вводит пользователь)». Ограничиваемся, понятное дело, десятичной системой счисления.
Простой пример:
Чтобы записать числа от 1 до 10 понадобиться две единицы (одна в 1 и одна в 10, собственно), один нолик, и по одной всех остальных цифр.
Программа должна считать такое для любого целого числа.
|
Естественно, когда меня просили о помощи, крайний срок сдачи работы был позавчера, поэтому я сразу не стал ничего придумывать, а воспользовался небезызвестной поисковой машиной. Почти везде для решения задачи предлагалось вот такое незатейливое, бессмысленное и беспощадное решение: клац. Собственно, это вариант, на коленке адаптированный мной для С++. Оригинал был на делфях.
Что здесь происходит: задаем цикл i : от 1 до N, каждое i переводим в строку и читаем посимвольно (опять в цикле). Каждый символ во внутреннем цикле обратно конвертим в целочисленное и добавляем 1 к соответствующему элементу массива.
|
Задание в таком виде и сдали. Препод остался доволен. Но я — нет. Ну не может такая задача оптимально решаться с использованием стрингов: работает оно очень медленно, да и вообще, выглядит как костыль. Хотя он ничего не подпирает, в отличие от костыля в больших проектах, а просто является монолитным обособленным сферическим костылём в вакууме, который можно, при желании, вставить в проект, где он автоматически превратится в костыль обыкновенный. И вот, неудовлетворенный я, которому, к тому же, часто сейчас нечем заняться на работе, с которой на днях ухожу, решил самостоятельно, без всяких гуглов, найти более оптимальное решение задачи.
|
Святые угодники, чего мне только не приходило в голову... Большинство мыслей крутилось вокруг того, что можно разбить любое число на слагаемые вида  , например, число 2398 можно представить, как  . После этой разбивки я собирался найти какой-то обобщенный алгоритм подсчета цифр в «круглом» числе i-го порядка и просто скормить ему каждое слагаемое поочередно, но у меня ничего не получилось (хотя, не отрицаю, что это было возможно). Потом я пытался изобрести рекуррентный алгоритм, отталкиваясь всё от того же разбиения на слагаемые, но при детальном анализе выяснилось, что рекурсия всё равно сведется к тупому перебору всех циферок, только произойдет это еще и в хрен знает скольки вложенных функциях и съест сотни стека. Ноооо.. это уже таки было решение без стрингов!))
|
И вот только после этого, когда я, расслабившись, закрыв глаза откинулся на спинку стула, выбросил все мысли из головы, попытался ощутить единство с высшей материей, попытался забыть всё, что я знал, и полностью открыть свой разум для свежих идей — только тогда пришло оно. Словно глоток свежего воздуха в жаркий день, подобно отрезвляющему пенделю под отсиженный зад... Короче, вот.
|
Да, вот так тупо и банально. Остаток от целочисленного деления на 10 дает нам последнюю цифру, которую мы суем в индекс массива и инкрементим, затем повторяем операцию деления до тех пор пока не получим нуль.. По сути, это всё тот же перебор в лоб всех чисел от 1 до N, только без использования строк, за счет чего оно работет, минимум, в 20 раз быстрее. И ничего более оптимального я пока что не придумал. И почему это не пришло мне в голову сразу после прочтения строкового решения — тоже остаётся загадкой. Алюминь :3
|