Я пишу программу, чтобы проверить, делится ли конкретное число на конкретное число, введенное пользователем.
n = количество введенных чисел
k = число, чтобы проверить, делятся ли числа
Моя программа пока работает довольно хорошо, но она превышает временные рамки. Есть ли более быстрый алгоритм или код, чем этот, чтобы проверить, делится ли число на другое конкретное число?
Решение
Прежде всего, проблема здесь заключается в быстром считывании чисел с ввода, а не делении. Имея это в виду, вот код для быстрого чтения:
vector buffer(n * 10); // allocate a large buffer cin.read( // fill the buffer with chars from input buffer.resize(cin.gcount()); // cut buffer size to number of chars actually read .
Это читает весь входной файл (обратите внимание на размер буфера, который ограничен каждым числом, имеющим менее 10 цифр).
Затем преобразуйте последовательность символов в числа и проверьте каждое число на делимость на k ( num % k != 0 как уже отмечали другие). Код для этого можно найти в «сложном» решении, которое вы разместили (оно занимает всего 1 строку кода).
Семинар 2 — сумма чисел от 1 до 100, которые делятся на 5, но не делятся на 3
Другие решения
Оператор по модулю (%) — это то, что вы хотите. Пример:
if (k != 0) return n % k == 0;
или для космонавтов:
if (k != 0) return !(n % k);
Modulo возвращает остаток от деления между двумя числами, например, 5% 2 возвращает 1. Если остаток равен 0, числа делятся (IE 4% 2 вернет 0).
Вместо этого фрагмента кода
cin >> num; if (num > 99 (num % 10) % k == 0) < //cout else if(num < 100 (num % k) == 0)< //cout
Вы могли бы написать просто
cin >> num; count += num % k == 0;
Суть «проблемы» заключается в том, что стандартные библиотеки ввода / вывода для большинства языков имеют очень общее назначение и, следовательно, могут не являться оптимальными инструментами для чтения или записи данных, когда формат четко определен и производительность критична.
В этом случае вы используете библиотечные функции для чтения из потоков ввода-вывода, которые сильно абстрагированы от базовой системы хранения. Как правило, чем ближе вы подходите к оборудованию, тем быстрее будет работать ваш код.
Я бы начал с того, чтобы попытаться использовать функции ввода-вывода файла C, такие как fopen а также fread чтобы прочитать большой кусок двоичных данных из файла в память, затем обработать эту память «на месте», сканируя числа и считая правильные совпадения. Цикл, пока нет больше строк для обработки, и помните, что это много более эффективно читать большие блоки данных, чем маленькие.
Вместо того, чтобы использовать
если (n% k! = 0)
использовать,
целое = n / k;
если (частное * k == n)
Оператор модуля медленнее, чем второй подход. (Выполнение кода с оператором модуля заняло у меня 4,5 секунды и 1 секунда при втором подходе)
Источник: web-answers.ru
Делится ли нацело одно число на другое. Уроки программирования на С++ для начинающих.
Проверьте, является ли число делимым на 3
Мне нужно определить, делится ли число на 3 без использования % , / или * . Указанный намек заключался в использовании функции atoi() . Любая идея, как это сделать?
ОТВЕТЫ
Ответ 1
Вычтите 3, пока не будете
a) hit 0 — число делится на 3
b) получить число меньше 0 — число не делится
— отредактированная версия для исправления отмеченных проблем
while n > 0: n -= 3 while n < 0: n += 3 return n == 0
Ответ 2
В текущем ответе все сосредоточены на десятичных цифрах, применяя «добавить все цифры и посмотреть, делит ли это на 3». Этот трюк действительно работает и в шестнадцатеричном виде; например 0x12 можно разделить на 3, потому что 0x1 + 0x2 = 0x3. И «преобразование» в шестнадцатеричное намного проще, чем преобразование в десятичную.
int reduce(int i) < if (i >0x10) return reduce((i >> 4) + (i // Reduces 0x102 to 0x12 to 0x3. else return i; // Done. > bool isDiv3(int i)
Вдохновленный R, более быстрая версия (журнал журнала событий N):
int reduce(unsigned i) < if (i >= 6) return reduce((i >> 2) + (i else return i; // Done. > bool isDiv3(unsigned i) < // Do a few big shifts first before recursing. i = (i >> 16) + (i i = (i >> 8) + (i i = (i >> 4) + (i // Because of additive overflow, it possible that i > 0x10 here. No big deal. i = reduce(i); return i==0 || i==3; >
Ответ 3
Разделите число на цифры. Добавьте цифры вместе.
Повторяйте, пока не останется только одна цифра. Если эта цифра равна 3, 6 или 9, число делится на 3. (И не забывайте обрабатывать 0 как частный случай).
Ответ 4
Хотя технология преобразования в строку и добавление десятичных цифр вместе является элегантной, она либо требует деления, либо неэффективна на этапе преобразования в строку. Есть ли способ применить идею непосредственно к двоичному числу без предварительной конвертации в строку десятичных цифр?
Учитывая двоичное число, сумма его нечетных битов минус сумма его четных битов делится на 3, если исходное число делится на 3.
В качестве примера: возьмите число 3726, которое делится на 3. В двоичном формате это 111010001110 . Поэтому мы берем нечетные цифры, начиная с правого и движущегося слева, которые являются [1, 1, 0, 1, 1, 1]; их сумма 5. Четные биты — [0, 1, 0, 0, 0, 1]; их сумма 2. 5 — 2 = 3, из которого можно заключить, что исходное число делится на 3.
Ответ 5
Вопрос о интервью в основном просит вас придумать (или уже известно) сокращение правила делимости с 3 в качестве делителя.
Одно из правил делимости для 3 выглядит следующим образом:
Возьмите любое число и добавьте каждую цифру в число. Затем возьмите эту сумму и определите, делится ли она на 3 (повторяя ту же процедуру, что и требуется). Если конечное число делится на 3, то исходное число делится на 3.
16,499,205,854,376 => 1+6+4+9+9+2+0+5+8+5+4+3+7+6 sums to 69 => 6 + 9 = 15 => 1 + 5 = 6, which is clearly divisible by 3.
См. также
- правило Википедии/делимости — есть много правил для многих делителей
Ответ 6
Число, делящееся на 3, iirc имеет характеристику, что сумма ее разряда делится на 3. Например,
12 -> 1 + 2 = 3 144 -> 1 + 4 + 4 = 9
Ответ 7
Учитывая число x. Преобразуйте x в строку. Разбор символа строки по символу. Преобразуйте каждый проанализированный символ в число (используя atoi()) и добавьте все эти числа в новое число y. Повторяйте процесс до тех пор, пока ваш конечный результирующий номер не будет иметь одну цифру. Если эта цифра равна 3,6 или 9, исходное число x делится на 3.
Ответ 8
Вы не отметили этот C, но, поскольку вы упомянули atoi , я собираюсь дать решение C:
int isdiv3(int x)
Ответ 9
Мое решение в Java работает только для 32-разрядных неподписанных int s.
static boolean isDivisibleBy3(int n) < int x = n; x = (x >>> 16) + (x // max 0x0001fffe x = (x >>> 8) + (x // max 0x02fd x = (x >>> 4) + (x // max 0x003d (for 0x02ef) x = (x >>> 4) + (x // max 0x0011 (for 0x002f) return ((011111111111 >> x) >
Сначала он уменьшает число до числа меньше 32. Последний шаг проверяет делимость, сдвигая маску на соответствующее число раз вправо.
Ответ 10
bool isDiv3(unsigned int n) < unsigned int n_div_3 = n * (unsigned int) 0xaaaaaaab; return (n_div_3 < 0x55555556);//n_div_3 bool isDiv5(unsigned int n) < unsigned int n_div_5 = i * (unsigned int) 0xcccccccd; return (n_div_5 < 0x33333334);//n_div_5
Следуя тому же правилу, чтобы получить результат теста на делимость на ‘n’, мы можем: умножьте число на 0x1 0000 0000 — (1/n) * 0xFFFFFFFF сравните с (1/n) * 0xFFFFFFFF
Другим является то, что для некоторых значений тест не сможет вернуть правильный результат для всех 32-битных чисел, которые вы хотите проверить, например, с делимостью на 7:
Проверьте, делится ли число на 3
мне нужно найти, делится ли число на 3 без использования % , / или * . Намек на использование . Есть идеи, как это сделать?
автор: hichris123
17 ответов
вычесть 3, пока вы либо
a) хит 0-число делится на 3
b) получить число меньше 0-число не делится
— отредактированная версия для исправления отмеченных проблем
while n > 0: n -= 3 while n < 0: n += 3 return n == 0
автор: Forrest Voight
текущие ответы все внимание на десятичные цифры, при применении «добавить все цифры и посмотреть, если это делится на 3». Этот трюк на самом деле работает и в hex; например, 0x12 можно разделить на 3, потому что 0x1 + 0x2 = 0x3. И «преобразование» в hex намного проще, чем преобразование в decimal.
int reduce(int i) < if (i >0x10) return reduce((i >> 4) + (i // Reduces 0x102 to 0x12 to 0x3. else return i; // Done. > bool isDiv3(int i)
[редактирование] Вдохновленный R, более быстрая версия (o log log N):
int reduce(unsigned i) < if (i >= 6) return reduce((i >> 2) + (i else return i; // Done. > bool isDiv3(unsigned i) < // Do a few big shifts first before recursing. i = (i >> 16) + (i i = (i >> 8) + (i i = (i >> 4) + (i // Because of additive overflow, it’s possible that i > 0x10 here. No big deal. i = reduce(i); return i==0 || i==3; >
автор: MSalters
разделить число на цифры. Сложите цифры вместе. Повторяйте, пока не останется только одна цифра.
Если это цифра 3, 6, или 9, то число делится на 3. (И не забудьте обработать 0 как особый случай).
автор: tdammers
хотя метод преобразования в строку, а затем добавления десятичных цифр вместе элегантен, он либо требует деления, либо неэффективен на шаге преобразования в строку. Есть ли способ применить эту идею непосредственно к двоичному числу, без предварительного преобразования в строку десятичных цифр?
учитывая двоичное число, сумма его нечетных битов минус сумма его четных битов делится на 3, если исходное число делится на 3.
в качестве примера: возьмем число 3726, которое делится на 3. В двоичном формате это 111010001110 . Поэтому мы берем нечетные цифры, начиная справа и двигаясь влево, которые [1, 1, 0, 1, 1, 1]; сумма это 5. Даже биты [0, 1, 0, 0, 0, 1]; сумма это 2. 5 — 2 = 3, из чего можно сделать вывод, что исходное число делится на 3.
автор: Tom Crockett
число, делимое на 3, iirc имеет характеристику, что сумма его цифр делится на 3. Например,
12 -> 1 + 2 = 3 144 -> 1 + 4 + 4 = 9
автор: Eugene Yokota
вопрос интервью по существу просит вас придумать (или уже известно) правило делимости стенографии с 3 в качестве делителя.
одно из правил делимости для 3 выглядит следующим образом:
Возьмите любое число и сложите вместе каждую цифру в числе. Затем возьмите эту сумму и определите, делится ли она на 3 (повторяя ту же процедуру, что и необходимо). Если итоговое число делится на 3, то исходное число делится на 3.
16,499,205,854,376 => 1+6+4+9+9+2+0+5+8+5+4+3+7+6 sums to 69 => 6 + 9 = 15 => 1 + 5 = 6, which is clearly divisible by 3.
см. также
- Википедия / правило делимости — имеет много правил для многих делителей
автор: polygenelubricants
задано число x. Преобразуйте x в строку. Разберите строку по символам. Преобразуйте каждый анализируемый символ в число (используя atoi ()) и сложите все эти числа в новое число y. Повторяйте процесс до тех пор, пока конечное результирующее число не станет длиной в одну цифру. Если эта цифра равна 3,6 или 9, исходное число x делится на 3.
автор: Amichai
мое решение на Java работает только для 32-разрядных без подписи int s.
static boolean isDivisibleBy3(int n) < int x = n; x = (x >>> 16) + (x // max 0x0001fffe x = (x >>> 8) + (x // max 0x02fd x = (x >>> 4) + (x // max 0x003d (for 0x02ef) x = (x >>> 4) + (x // max 0x0011 (for 0x002f) return ((011111111111 >> x) >
сначала он уменьшает число до числа менее 32. Последний шаг проверяет делимость, сдвигая маску соответствующее количество раз вправо.
автор: Roland Illig
вы не пометили этот C, но так как вы упомянули atoi , Я собираюсь дать решение C:
int isdiv3(int x)
bool isDiv3(unsigned int n) < unsigned int n_div_3 = n * (unsigned int) 0xaaaaaaab; return (n_div_3 < 0x55555556);//n_div_3 bool isDiv5(unsigned int n) < unsigned int n_div_5 = i * (unsigned int) 0xcccccccd; return (n_div_5 < 0x33333334);//n_div_5
следуя тому же правилу, чтобы получить результат теста делимости на ‘n’ , мы можем : умножьте число на 0x1 0000 0000 — (1 / n) * 0xFFFFFFFF сравните с (1 / n) * 0xFFFFFFFF
аналогом является то, что для некоторых значений тест не сможет вернуть правильный результат для всех 32-битных чисел, которые вы хотите проверить, например, с делимостью на 7 :