VPF::Определить делится ли введённое число n на 15

AB96

Дата 14.12.2015, 21:24 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 1
Регистрация: 14.12.2015

Репутация: нет
Всего: нет

Здравствуйте! В общем, у меня такая ситуация, я могу получить автомат за экзамен по C. Осталось решить три задания. Два решил, с одним заданием возникли сложности. Условие задания: Число n вводится своим двоичным представлением (длина числа не превышает 100 двоичных разрядов). Необходимо определить делится ли введённое число n на 15. Прошу Вас, помогите! Заранее спасибо!

feodorv

Дата 14.12.2015, 22:16 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

Репутация: 11
Всего: 45

Здесь

--------------------

Напильник, велосипед, грабли и костыли - основные инструменты программиста...

xoptov

Дата 15.12.2015, 11:15 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 17
Регистрация: 16.2.2008

Репутация: нет
Всего: нет

Ну все просто если есть остаток от опирации 15 % n то число n не кратно 15, а если 15 % n не имеет остатка то есть возвращает 0 то n кратно 15

Этот ответ добавлен с нового Винграда - http://vingrad.com

Ivan.

Дата 15.12.2015, 11:25 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 291
Регистрация: 2.11.2004

Репутация: 1
Всего: 2

не 15 % n, а n % 15

--------------------

Я могу ВСЁ, вопрос - сколько времени у меня это займет!

feodorv

Дата 15.12.2015, 11:47 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

Репутация: 11
Всего: 45

Цитата(xoptov @ 15.12.2015, 11:15

)

Ну все просто

Да уж. А если число изначально задано в двоичной системе счисления (т.е. строковое представление) и состоит из множества разрядов (100 - это отнюдь не предел), то всё ещё проще, да?

--------------------

Напильник, велосипед, грабли и костыли - основные инструменты программиста...

math64

Дата 15.12.2015, 11:57 (ссылка)

(голосов:1)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2505
Регистрация: 12.4.2007

Репутация: 8
Всего: 72

Код


int divider = 15;
int base = 2;
int remainder = 0;
while(hasNextDigit()) {
  int digit = getNextDigit();
  remainder = (remainder * base + digit) % divider;
}
return remainder == 0;

Для любых divider и base если divider*base влезает в int

Это сообщение отредактировал(а) math64 - 15.12.2015, 12:32

Sajtran

Дата 15.12.2015, 20:16 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 10
Регистрация: 15.10.2008
Где: Мегион

Репутация: нет
Всего: 2

если число делится на 15, то оно должно делиться и на 5 и на 3
в десятичной системе, признаки деления
на 3 - сумма чисел кратна трём
на 5 - заканчивается на 0 или на 5

запрашиваете число в виде строки и проверяете эти два условия

Этот ответ добавлен с нового Винграда - http://vingrad.com

Sajtran

Дата 15.12.2015, 20:17 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 10
Регистрация: 15.10.2008
Где: Мегион

Репутация: нет
Всего: 2

опс, надо найти те же правила для двоичной системы

Этот ответ добавлен с нового Винграда - http://vingrad.com

Фантом

Дата 15.12.2015, 22:03 (ссылка)

(нет голосов)

Загрузка ...

Вы это прекратите!

Профиль
Группа: Участник Клуба
Сообщений: 1516
Регистрация: 23.3.2008

Репутация: нет
Всего: 49

Есть такое полезное утверждение: в системе счисления с основанием n число делится на n-1 тогда и только тогда, когда сумма его цифр (цифры, разумеется, тоже надо брать в соответствующей системе счисления) делится на n-1. Доказательство элементарно.

Отсюда вариант (не единственно возможный, но все же). Переведите число в 16-ричную запись (это тривиально - каждый блок по четыре двоичных цифры соответствует одной 16-ричной)... Дальше продолжать? smile

feodorv

Дата 15.12.2015, 23:25 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

Репутация: 11
Всего: 45

Цитата(Фантом @ 15.12.2015, 22:03

)

Отсюда вариант (не единственно возможный, но все же).

На подобный вариант я ссылку давал. Но я за решение от math64, оно более общее, прозрачное и проще реализуемое. Предлагаемый Вами вариант - это просто частный случай этого решения smile

--------------------

Напильник, велосипед, грабли и костыли - основные инструменты программиста...

math64

Дата 16.12.2015, 08:42 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2505
Регистрация: 12.4.2007

Репутация: 8
Всего: 72

Для тех кто пользуется новым винградом:

Цитата(math64 @ 15.12.2015, 11:57

)

Код


int divider = 15;
int base = 2;
int remainder = 0;
while(hasNextDigit()) {
  int digit = getNextDigit();
  remainder = (remainder * base + digit) % divider;
}
return remainder == 0;

Для любых divider и base если divider*base влезает в int

Я правил своё сообщение - в новом винграде виден только первоначальный вариант.

magnet

Дата 17.12.2015, 14:01 (ссылка)

(голосов: 0)

Загрузка ...

Unregistered

В каком формате представлены входные данные - не понятно. Так что сам озаботься, а я приведу пару строчек:

Код


int div15(unsigned long int digit) {
  while (digit>15) digit = (digit >> 4) + (digit & 15);
  return digit / 15;
}

Это алгоритм.
Если число будет вводиться с клавиатуры, то нужно подумать..

Этот ответ добавлен с нового Винграда - http://vingrad.com

magnet

Дата 17.12.2015, 16:00 (ссылка)

(голосов: 0)

Загрузка ...

Unregistered

Ну, собственно, вот классический Цэ:

Код


#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv) {
  int count, lngth, digit;
  
  if (argc<2) { printf("Binary digit expected\n"); return -1; } // Необходим хотя бы один аргумент
  for(count=0;count<100;count++) if(argv[1][count]!='0' && argv[1][count]!='1') break; // Длина числа до первого символа, отличного от 0 или 1
  if (count<1) { printf("Binary digit expected\n"); return -1; } // Если введено не двоичное число
  printf("Length=%d\n",count); // Вывод полученной длины числа
  lngth = count; // Запомним длину числа
  while(--count>=0) { // Разбираем каждый символ, начиная с конца строки
    digit = digit + ((argv[1][count] - 48) << (lngth-count-1)%4); // Преобразование строки побайтно. Суммирование всех байтов.
      printf("count=%d digit=%d bit=%d\n",count,digit,(argv[1][count]-48)); // Вывод текущего результата для понимания работы
  }
  printf("\nsumm=%d\n",digit); // Вывод конечного результата.
  if(digit%15 == 0) printf("Делится на 15\n"); // Если остаток от деления 0, то все число делится на 15
    else printf("Не делится на 15\n"); // или не делится, если есть остаток
  return 0;
}

Подробно тебе всё закомментировал и натыкал принтов, чтоб было видно, как оно работает.

Этот ответ добавлен с нового Винграда - http://vingrad.com

math64

Дата 17.12.2015, 16:40 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2505
Регистрация: 12.4.2007

Репутация: 8
Всего: 72

magnet, Вы обратили внимание на:

Цитата(AB96 @ 14.12.2015, 21:24

)

длина числа не превышает 100 двоичных разрядов

Такое число не влезет не только в int, но даже в int64

Sajtran

Дата 17.12.2015, 17:14 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 10
Регистрация: 15.10.2008
Где: Мегион

Репутация: нет
Всего: 2

ну если после этого ответа ТС не получил автомат, то он его не заслуживает :-)

Этот ответ добавлен с нового Винграда - http://vingrad.com

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »