Проверить делимость на число 3, используя только сложение и битовые оп

Тема в разделе "Общие вопросы по С и С++", создана пользователем temster, 30 окт 2007.

Статус темы:
Закрыта.
  1. temster

    temster Гость

    Предисловие. Не так давно столкнулся с задачей, которая сформулирована в заголовке поста. Если бы в задании не содержалось части после запятой все понятно: в языке С++ есть операция % - взятие остатка от деления, если остаток 0, то делится, иначе нет….., но! Как же это реализовать используя только сложение и побитовые операции… После часа раздумий вместе с великим мозгом по имени Интернет, у меня на листке созрел алгоритм. Вот его реализация: http://temster.ru/?p=7#more-7
     
  2. grigsoft

    grigsoft Well-Known Member

    Регистрация:
    15 ноя 2005
    Сообщения:
    735
    Симпатии:
    0
    Традиционный метод - если сумма цифр делится на 3. У тебя - аналогичное, но число раскладывается по степеням 4. Доказательство тоже аналогичное - остаток от деления любой степени 4 на 3 - всегда 1, так что делимость определяется суммой коэффициентов разложения. Единственно, что у тебя считается не 219 -> 2+1+9, а 219 -> 21+9, но с точки зрения математики сути это не меняет.
     
Загрузка...
Статус темы:
Закрыта.

Поделиться этой страницей