Делится ли введённое число n на 15

[AB96]

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

[Poma][a]

Задание прекрасно
Переводите в 16-те ричную и смотрите на остаток от деления на 15 суммы

[Аватар]

Наверно без длиной арифметики не обойтись, преобразуя в массив десятичных цифр. А потом если сумма цифр делится на 3 и последняя 0 или 5, то делится на 15

[Poma][a]

Ну неее.
Ей Богу так работает.. Помните вы меня учили доказывать что число делится на 9 если сумма цифр делится на 9? Тут точно также. Число K в системе счисления с основанием N будет делиться на N-1 тогда и только тогда, когда сумма цифр делится на N-1

А у нас в 2. Переводим в 16 заменяя тетрады

[Аватар]

Наверно. А еще вспомнил, что есть признаки делимости двоичного числа на 3 и 5. Только их найти нужно. Этого тоже достаточно будет

[AB96]

Что-то не очень понял...

Это, наверное, неверно?

#include <stdio.h>
#define MAX 100

int main()
{
    int bin[MAX], i, nym, x = 0, sum = 0, z=0;
    for (i = 0; i < MAX; ++i) 
	{
        nym = getchar() - '0';
        if (nym == 0 || nym == 1)
		{
            *(bin + i) = nym;
		}
        else
		{
            break;
		}
    }
    while (--i >= 0) 
	{
        nym = 1;        
        for (int z = 1; z <= i; ++z)
		{
			nym *= 2;
		}

        nym *= *(bin + x++);
        sum += nym;
    }

    if (sum % 15)
	{
        printf("%d / 15 No\n", sum);
	}
    else
	{
        printf("%d / 15 Yes\n", sum);
	}
    return 0;
}

[Poma][a]

не..
Предлагаю так. Заполняем массив 0\1 с конца. В какой-то момент получили массив длины K. До тех пор - пока K%4 != 0 добавляем 0 в конец массива. Как только закончили - идем по 4-кам (с начала -с конца - пофигу). Четыре 0\1 преобразуем в 16-ричное число. И прибавляем его к sum. В конце все зависит от sum%15

[taras-proger]

Число делится на 15, если оно делится на 3 и на 5. В десятичном представлении признак делимости на 3 - делимость суммы цифр на 3, многозначная сумма цифр проверяется по тому же признаку, а среди однозначных делятся: 3, 6 и 9. Признак же делимости на 5 - окончание записи числа на 0, или на 5. Но в двоичном не знаю.

Нашёл. Если знакопеременная сумма цифр числа делится на число, на 1 большее основания, то и само число делится на число, на 1 большее основания. В двоичной системе по этому признаку можно проверить делимость на 3, а в четвертичной - на 5, при этом перевод в из двоичной системы в четвертичную не требует фактического преобразования, так как смешанная двоично-четвертичная эквивалентна двоичной, то есть просто сгруппируй биты по два и получишь двоичную запись четвертичных цифр и складывай их, как числа с чередованием знака. При получении суммы с более чем двумя значащими цифрами делимость проверяется рекурсивно, то есть делимость знакопеременной суммы цифр проверятся по тому же самому признаку, что и делимость самого числа. Если число делится на 3 и на 5, значит оно делится на 15.

[Serge_Bliznykov]

Poma][a, а зачем так сложно то?

Тут же уже неоднократно предлагали простейший алгоритм
вводим строку.
Если длина строчки меньше двух - выход с сообщением, что число НЕ ДЕЛИТСЯ на 15
Если длина строки равна двум - перевод строки в число, проверяем остаток от деления на 15 - если он равен нулю - число ДЕЛИТСЯ на 15, иначе, если остаток не равен нулю - число НЕ ДЕЛИТСЯ на 15
Если длина строки больше двух:
находим сумму всех цифр строки.
если сумма_всех_цифр_строки делится на 3 и последнюю цифра строки равна 0 или 5 - тогда ДЕЛИТСЯ на 15
иначе - число НЕ ДЕЛИТСЯ на 15

всё.

в коде это будет короче, чем я тут расписывал!

[taras-proger]

1. Сколько времени уйдёт на парсинг записи числа, для которого нужны 100 бит? А я парсить не предлагаю.
2. Сколько времени уйдёт на деление стабитного числа? А сколько на 50 инкрементов и 50 декрементов в цикле?
3. Какова сложность парсинга записи числа, для которого нужны 100 бит? А я парсить не предлагаю.
4. Какова сложность реализации длинного деления? А какова сложность использования готовых инкремента и декремента и реализации простейшего цикла?
Строка как раз не дана, а дано стобитное число, которое ещё перевести надо в строчную форму.
5. Сколько времени уйдёт на перевод стабитного числа в строчную форму? А я ничего переводить в строчную форму не предлагаю.
6. Какова сложность реализации перевода стабитного числа в строчную форму? А я ничего переводить в строчную форму не предлагаю.
Так что Ваш алгоритм монструозен, а мой примитивен.