Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

Найти минимальное число А, которое нацело делиться на N

85K
24 октября 2012 года
Андрей Соколов
1 / / 24.10.2012
Дано натуральное N (N<1000). Найти минимальное число А, которое нацело делиться на N, и в десятичной записи которого используются лишь 0 и 1.

Например для N=537 A=11010111

Ребята пожалуйста подскажите дельную идею решения через массивы. Если дельная идея то вознаграждение.
43K
24 октября 2012 года
Павел_AF
6 / / 19.10.2008
Ну, можно пойти по таким направлениям:
1) перебора с проверкой на содержание 0 и 1 в числе i*N.
2) перебирать числа, состоящие из 0 и 1, проверяя их делимость на N делением.
3) попробовать перебирать числа, состоящие из 0 и 1(их можно представить и в виде массива), проверяя их делимость на N признаком Паскаля (см. статью в Википедии). Я имею в виду, что после первого применения признака Паскаля порядок проверяемого числа резко снизится и следующая проверка делением даст ответ - делится или нет.

Среди алгоритмов к школьным олимпиадам мне встречался алгоритм увеличения на 1 двоичного числа, представленного массивом из 0 и 1:
1) пусть есть массив x[0..999], x[0] - младший разряд
2) просматриваем x от x[0] до x[999]
Если x=1, то x:=0, переходим к следующему элементу
Если x=0, то x:=1, выходим из цикла
 
Код:
for i:=0 to 999 do
  begin
    if x[i]=1 then
      x[i]:=0;
    else
    begin
      x[i]:=1;
      Break;
    end;
  end;
4) ещё вариант, пришёл на ум. Так я проверял является ли произвольное число числом Фиббоначи. Дело в том, что в пределах разрядной сетки (8, 16, 32 или 64 бит) количество чисел Фиббоначи (ну а в данном случае - состоящих из 0 и 1) очень ограничено, их можно все найти и сохранить в массиве. А дальнейший поиск минимального производить в этом массиве.
Так, например, если разрядная сетка 16 бит (тип Word), то в 10-м представлении это 5 разрядов и всего 2^(5+1)=64 чисел из 0 и 1 - т.е. много меньше ~65000. Такая же тенденция и для других целых типов.

Тут всё зависит от фантазии...

Знаете кого-то, кто может ответить? Поделитесь с ним ссылкой.

Ваш ответ

Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог