Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > Определить делится ли введённое число n на 15

Автор: AB96 14.12.2015, 21:24

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

Автор: feodorv 14.12.2015, 22:16

http://forum.sources.ru/index.php?showtopic=260233 smile

Автор: xoptov 15.12.2015, 11:15

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

Этот ответ добавлен с нового Винграда - http://ru.vingrad.com/Opredelit-delitsya-li-vvedennoye-chislo-n-na-15-id566f09f7ae2015676f8b4567#findElement_E7045_566fcc08ae20150a4a774490_0

Автор: Ivan. 15.12.2015, 11:25

не 15 % n, а n % 15

Автор: feodorv 15.12.2015, 11:47

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

)

Ну все просто

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

Автор: 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

Автор: Sajtran 15.12.2015, 20:16

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

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

Этот ответ добавлен с нового Винграда - http://ru.vingrad.com/Opredelit-delitsya-li-vvedennoye-chislo-n-na-15-id566f09f7ae2015676f8b4567#findElement_E7045_56704ae0ae20153467774838_0

Автор: Sajtran 15.12.2015, 20:17

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

Этот ответ добавлен с нового Винграда - http://ru.vingrad.com/Opredelit-delitsya-li-vvedennoye-chislo-n-na-15-id566f09f7ae2015676f8b4567#findElement_E7045_56704b41ae20152570774423_0

Автор: Фантом 15.12.2015, 22:03

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

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

Автор: feodorv 15.12.2015, 23:25

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

)

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

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

Автор: math64 16.12.2015, 08:42

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

Цитата(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

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

Код


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

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

Этот ответ добавлен с нового Винграда - http://ru.vingrad.com/Opredelit-delitsya-li-vvedennoye-chislo-n-na-15-id566f09f7ae2015676f8b4567#findElement_E7045_56729624ae2015764c774830_0

Автор: magnet 17.12.2015, 16:00

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

Код


#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://ru.vingrad.com/Opredelit-delitsya-li-vvedennoye-chislo-n-na-15-id566f09f7ae2015676f8b4567#findElement_E7045_5672b1e1ae2015d06a774808_0

Автор: math64 17.12.2015, 16:40

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

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

)

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

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

Автор: Sajtran 17.12.2015, 17:14

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

Этот ответ добавлен с нового Винграда - http://ru.vingrad.com/Opredelit-delitsya-li-vvedennoye-chislo-n-na-15-id566f09f7ae2015676f8b4567#findElement_E7045_5672c361ae2015ad01774382_0

Автор: magnet 18.12.2015, 06:30

math64, в этом и прикол задачи, чтоб не переводя двоичный ряд в число выдать решение. По приведенному мной алгоритму можно вводить сколько угодно большое число сумма байт которого не привысит unsigned int64, т.е. в худщем случае (если все единицы) - это более 70-ти миллионов разрядов. Не хилый такой буфер ввода в 72 мегабайта =)

Вот обновленный код:

Код


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

int main(int argc, char **argv) {
  int count, lngth;
  unsigned long int 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=%lu bit=%d\n",count,digit,(argv[1][count]-48)); // Вывод текущего результата для понимания работы
  }
  printf("\nsumm=%lu\n",digit); // Вывод конечного результата.
  if(digit%15 == 0) printf("Делится на 15\n"); // Если остаток от деления 0, то все число делится на 15
    else printf("Не делится на 15\n"); // или не делится, если есть остаток
  return 0;
}

В старом куда-то форматирование улетело и последние строчки пропали.

Этот ответ добавлен с нового Винграда - http://ru.vingrad.com/Opredelit-delitsya-li-vvedennoye-chislo-n-na-15-id566f09f7ae2015676f8b4567#findElement_E7045_56737de9ae20154b3c774e14_0

Автор: volatile 18.12.2015, 12:10

Цитата(magnet @ 18.12.2015, 06:30

)

Вот обновленный код:

Муть какая-то

Выше, math64, Фантом давали норм. решение.