Сообщение Re: двоично-десятичные палиндромы от 16.12.2015 14:30
Изменено 16.12.2015 14:37 Mystic
Здравствуйте, Кодт, Вы писали:
К>Предложите наиболее быстрый способ.
Во первых, палиндром должен быть нечётным.
Во-вторых, перечислять десятичные палиндромы быстрее, их меньше. По сути в обычном порядке мы должны делать инкремент первой половины, а вторую половину палиндрома можно получать зеркально. Например,
12321, какой следующий? Первая половина 123, добавляем единицу получаем 124, строим палиндром 12421. Таким образом мы будем быстро получать десятичные палиндромы в порядке возрастания.
В-третьих, с учётом во-первых, если старший равен четному числу, то его надо увеличить его ещё на единицу.
Осталось только проверить, будет ли палиндром двоичным? Как-то так:
Если 1 или 11, то палиндром (оптимизация)
Обнулить нулевой бит (одна команда)
Получить индекс самого старшего бита (одна машинная инструкция) и обнулить его.
Если получили нуль, то палиндром.
Получить индекс самого младшего установленного бита.
Вычислить индекс бита, который должен быть самым старшим установленным. Например, Если самый старший установленный бит был 12, а новый самый младший 3, то старший будет 9
Далее, проверить, что все биты, старше девятого, установлены в нуль, например, при помощи OR. Если проверка зафейлилась, то не палиндром.
Сдвинуть число вправо на 3 и goto на начало.
К>Предложите наиболее быстрый способ.
Во первых, палиндром должен быть нечётным.
Во-вторых, перечислять десятичные палиндромы быстрее, их меньше. По сути в обычном порядке мы должны делать инкремент первой половины, а вторую половину палиндрома можно получать зеркально. Например,
12321, какой следующий? Первая половина 123, добавляем единицу получаем 124, строим палиндром 12421. Таким образом мы будем быстро получать десятичные палиндромы в порядке возрастания.
В-третьих, с учётом во-первых, если старший равен четному числу, то его надо увеличить его ещё на единицу.
Осталось только проверить, будет ли палиндром двоичным? Как-то так:
Если 1 или 11, то палиндром (оптимизация)
Обнулить нулевой бит (одна команда)
Получить индекс самого старшего бита (одна машинная инструкция) и обнулить его.
Если получили нуль, то палиндром.
Получить индекс самого младшего установленного бита.
Вычислить индекс бита, который должен быть самым старшим установленным. Например, Если самый старший установленный бит был 12, а новый самый младший 3, то старший будет 9
Далее, проверить, что все биты, старше девятого, установлены в нуль, например, при помощи OR. Если проверка зафейлилась, то не палиндром.
Сдвинуть число вправо на 3 и goto на начало.
Re: двоично-десятичные палиндромы
Здравствуйте, Кодт, Вы писали:
К>Предложите наиболее быстрый способ.
Во первых, палиндром должен быть нечётным.
Во-вторых, перечислять десятичные палиндромы быстрее, их меньше. По сути в обычном порядке мы должны делать инкремент первой половины, а вторую половину палиндрома можно получать зеркально. Например,
12321, какой следующий? Первая половина 123, добавляем единицу получаем 124, строим палиндром 12421. Таким образом мы будем быстро получать десятичные палиндромы в порядке возрастания: 12521, 12621, 12721, 12821, 12921, 13031, 13131, ...
В-третьих, с учётом во-первых, если старший равен четному числу, то его надо увеличить его ещё на единицу. Если получили 20002, то переходим на 30003.
Осталось только проверить, будет ли палиндром двоичным? Как-то так:
Если 1 или 11, то палиндром (оптимизация).
Обнулить нулевой бит (одна команда)
Получить индекс самого старшего бита (одна машинная инструкция) и обнулить его.
Если получили нуль, то палиндром.
Получить индекс самого младшего установленного бита.
Вычислить индекс бита, который должен быть самым старшим установленным. Например, Если самый старший установленный бит был 12, а новый самый младший 3, то старший будет 9
Далее, проверить, что все биты, старше девятого, установлены в нуль, например, при помощи OR. Если проверка зафейлилась, то не палиндром.
Сдвинуть число вправо на 3 и goto на начало.
К>Предложите наиболее быстрый способ.
Во первых, палиндром должен быть нечётным.
Во-вторых, перечислять десятичные палиндромы быстрее, их меньше. По сути в обычном порядке мы должны делать инкремент первой половины, а вторую половину палиндрома можно получать зеркально. Например,
12321, какой следующий? Первая половина 123, добавляем единицу получаем 124, строим палиндром 12421. Таким образом мы будем быстро получать десятичные палиндромы в порядке возрастания: 12521, 12621, 12721, 12821, 12921, 13031, 13131, ...
В-третьих, с учётом во-первых, если старший равен четному числу, то его надо увеличить его ещё на единицу. Если получили 20002, то переходим на 30003.
Осталось только проверить, будет ли палиндром двоичным? Как-то так:
Если 1 или 11, то палиндром (оптимизация).
Обнулить нулевой бит (одна команда)
Получить индекс самого старшего бита (одна машинная инструкция) и обнулить его.
Если получили нуль, то палиндром.
Получить индекс самого младшего установленного бита.
Вычислить индекс бита, который должен быть самым старшим установленным. Например, Если самый старший установленный бит был 12, а новый самый младший 3, то старший будет 9
Далее, проверить, что все биты, старше девятого, установлены в нуль, например, при помощи OR. Если проверка зафейлилась, то не палиндром.
Сдвинуть число вправо на 3 и goto на начало.