Чтобы проверить, делится ли десятичное число на 7:
Стереть последнюю цифру. Умножьте это на 2 и вычтите из того, что осталось. Если результат делится на 7, исходное число делится на 7.
(также описано, например, здесь )
Это правило хорошо для ручной проверки делимости. Например:
2016 делится на 7?
Вычесть
6*2
из 201; мы получаем 189. Это делится на 7? Чтобы проверить это, давайте снова применим правило.Вычесть
9*2
из 18; мы получаем 0. Таким образом, 2016 делится на 7.
В этой задаче вы должны применять это правило до тех пор, пока статус делимости не станет очевидным , то есть число не будет больше 70 (однако подробности см. Ниже). Сделать функцию или полную программу.
Входные данные : положительное целое число; Ваш код должен поддерживать ввод до 32767 (поддержка целых чисел произвольной точности является бонусом; см. ниже).
Вывод : целое число (возможно, отрицательное), не превышающее 70, которое является результатом применения правила делимости на 7 ноль или более раз.
Тестовые случаи:
Input Output Alternative output
1 1
10 10 1
100 10 1
13 13 -5
42 42 0
2016 0
9 9
99 -9
9999 -3
12345 3
32767 28 -14
---------- Values below are only relevant for the bonus
700168844221 70 7
36893488147419103232 32 -1
231584178474632390847141970017375815706539969331281128078915168015826259279872 8
Там, где указаны два возможных выхода, любой результат является правильным: второй соответствует применению правила еще раз. Запрещается применять правило к однозначному номеру: если вы удалите цифру, ничего (не 0) не останется.
Бонус : если ваш алгоритм
- Поддерживает целые числа произвольной точности
- Выполняет только один проход на входе
- Имеет сложность пространства
o(n)
(то есть меньше, чемO(n)
); а также - Имеет временную сложность
O(n)
,
где n
число десятичных цифр:
Вычтите 50% из числа байтов вашего кода.
Реальный бонус :
Кроме того, если ваш алгоритм считывает входные данные в нормальном направлении, начиная с самой значащей цифры, еще раз вычтите 50% - ваш счет составляет 25% от вашего количества байтов (это кажется возможным, но я не совсем уверен).
источник
1000000000000000000001
.long long
встроенный s или какой-нибудь эквивалентный тип?Ответы:
Golfscript,
2722 байтаВы можете использовать это так:
объяснение
5 байтов сэкономлено благодаря Денису!
источник
@wizzwizz4
(@
затем мое имя пользователя) в начале (или в любом месте) комментария.{...}{}if
часть как{...}*
, которая будет просто применять нулевой блок кода один раз, в зависимости от значения, выдвинутого>
. Кроме того, нам разрешено выполнить еще одну итерацию (поэтому замена70
на9
экономит байт), и я не думаю, что вам нужно выталкивать блок;
.Haskell, 35 байт
Пример использования:
until(<71)(\n->div n 10-2*mod n 10) 36893488147419103232
->32
.Ничего особенного объяснять, это прямая реализация алгоритма.
источник
Желе, 11 байт
Попробуйте онлайн!
Как это работает
источник
Python 2, 38 байт
Попробуй это здесь !
Простой рекурсивный подход. Печатает x, если его <70 в противном случае применяет правило делимости и вызывает себя с результатом.
источник
)
f=lambda x:x*(x<70)or f(x/10-x%10*2)
x*(x<70) != 0
конечным условием. Если x достигает 0 - как это происходит в 2016 году - конечное условие никогда не происходит.Pyth, 13 байт
Попробуйте онлайн: демонстрация или тестовый набор
Это напечатает все альтернативные ответы.
Объяснение:
источник
Юлия,
2726 байтЭто рекурсивная функция, которая принимает целое число и возвращает a
BigInt
. Если ввод большого числа, как в последнем примере, Джулия анализирует его какBigInt
, поэтому ручное преобразование не требуется.Подход - просто прямая реализация алгоритма. Это произведет альтернативные выходы. Взятие модуля при делении на 10 дает последнюю цифру, а частное от целочисленного деления на 10 - все, кроме последней цифры.
Спас Байт благодаря Денису!
источник
70
на9
экономит байт.Pyth, 17 байт
Попробуй это здесь!
Тот же рекурсивный подход, что и в моем ответе на python . Определяет лямбда ,
y
который называется так:y12345
.Счетчик байтов в онлайн-интерпретаторе показывает 19 байтов, потому что я добавил лямбда-вызов к нему, так что вы можете просто попробовать его, нажав кнопку запуска.
объяснение
источник
CJam - 19 байтов
Версия Do-while:
Попробуйте онлайн или пока версия # 1:
Попробуйте онлайн или пока версия # 2:
Попробуйте онлайн .
источник
Oracle SQL 11.2, 116 байт
Un-golfed
источник
Haskell,
157192184167159147138 + 5 байт - 50% = 71,5 байтO (1) пробел, O (n) время, однопроходный!
Используйте as
0![6,1,0,2]
для применения правила к 2016 году, то есть передайте ему число в виде потока с наименее значащей цифрой в первую очередь. Таким образом, он будет передавать цифру цифра за цифрой, применяя правило с O (1) пространственной сложностью.Код для разгула здесь:
Суть того, как это работает, заключается в том, что он реализует алгоритм вычитания цифра за цифрой , но использует тот факт, что каждое вычитаемое число состоит максимум из 2 цифр, и поэтому мы можем вычесть произвольное количество этих 1- или -значные цифры из основного (а также употребление наименее значимых цифр).
Алгоритм вычитания является O (1) и хранит только текущее значение заимствования. Я изменил это, чтобы добавить дополнительную цифру (0 или 1), и мы заметили, что это значение заимствования ограничено (в пределах диапазона [-2,2], поэтому нам нужно только 3 бита для его хранения).
Другие значения, хранящиеся в памяти, являются временными переменными, представляющими текущее 2-значное число, которое нужно добавить, один прогноз в потоке и применить один шаг алгоритма вычитания (т. Е. Он принимает две цифры и значение заимствования и возвращает одна цифра и новое значение заимствования).
Наконец, в конце он обрабатывает две последние цифры в потоке сразу, чтобы вернуть однозначное число, а не список цифр.
NB
sev
Функция в версии без заглавных букв будет работать надInteger
преобразованием в форму обратного потока.источник
Mod[18 - Quotient[n, 10] - 2*n, 21] - 18 + Quotient[n, 10]
работает эмпирически для n между 10 и 99, но тем сложнее, чем больше цифр n имеет ...0
при вызове вы также должны считать байты начальных!
, например, как раздел(0!)
(+ перевод строки), т.е. +5 байт. С другой стороны вы можете сократить первое совпадение с образцом!
доp![d]=
иp![d,e]=
. Кроме того , использование модель оберегает вместоlet
:p!(d:e:f)|(b,a)<-quotRem(2*d)10,(q,r)<-h$e-a-p=(b+q)!(r:f)
.(0!)
свою собственную линию.(0!)
это функция, которую вы даете в качестве ответа.0
Требуются, но не имеет ничего общего с входом, так что вы не можете Аутсорсинг вызывающего абонента. Конечно, вы также можете использоватьf x=0!x
, но это дольше.GNU dc,
2015 байтЭто определяет мою первую (когда-либо) функцию постоянного тока
F
. Он принимает входные данные в верхней части стека и оставляет выходные данные в верхней части стека. Пример использования:источник
Mathematica,
4744 байтаПростой рекурсивный подход. Возможно, будет дальше в гольф.
источник
#0[{1,-2}.QuotientRemainder[#,10]]
сохраняет байт.R, 43 байта
Объяснение:
Образцы прогонов:
источник
JavaScript ES6, 38 байтСбой с
36893488147419103232
и использование~~(1/10)
также не удастся для700168844221
Тест:
источник
Fail
с ... 70 и 32f=n=>n>70?f((n-n%10*21)/10):n
это более короткая версия, но все еще работает только до2**56
.Mathematica, 33 байта
Прецедент
источник
Perl 5,
4746 байтПришлось использовать
bigint
для последнего теста. (Возвращает 20 без)Не совсем уверен, что это кандидат на премию, поэтому я не учел это. (Я думаю, что это так, но я не очень привык к концепциям)
Попробуй это здесь!
источник
ES6, 108 байт
Работает для 2 ²⁵⁷ и 1000000000000000000001, но может использовать дальнейшую игру в гольф.
источник
JavaScript ES6,
140142 байтаЭто истинная математика с произвольной точностью, даже работает на самом большом тестовом примере.
Эта функция рекурсивно удаляет последнюю цифру из строки, а затем вычитает 2 * последнюю цифру из оставшейся числовой строки, итеративно увеличивая количество цифр для применения к намечаемому значению до тех пор, пока разница не станет положительной. Затем он добавляет эту разницу к концу строки с соответствующим дополнением
0
s и вызывает себя рекурсивно, пока ее числовое значение не станет меньше или равно9
.источник
1000000000000000000001
.s.replace(/.$/,'-$&*2')
. У меня нет никаких очевидных идей для остальных, хотя извините.C #,
111104 байтаисточник
Brain-Flak ,
368360 байтПопробуйте онлайн!
объяснение
Для начала весь код находится в цикле, который выполняется до тех пор, пока вершина стека не станет меньше нуля:
Внутри цикла мы запускаем делимый на семь алгоритм:
Дублируйте вершину стека
Возьмите мод 10 вершины стека (последняя цифра)
Это немного беспорядок, но он выполняет остальную часть алгоритма, я мог бы объяснить это позже, но я не совсем помню, как он работает:
источник
C, 56 байтов - 75% = 14
Хотя это не дает те же цифры, что и в тестовых примерах, оно отвечает духу вопроса (и, возможно, больше). Он правильно идентифицирует точные числа, кратные 7, и дает точный остаток для других чисел (поскольку он никогда не использует отрицательные числа).
В алгоритме нет умножения или деления, только сложение и вычитание, а цифры обрабатываются за один проход слева направо. Работает следующим образом, начиная с 0 в аккумуляторе:
Шаг «умножить на три» записывается так,
n-=-n-n
чтобы сохранить байт и избежать оператора умножения.Когда мы подходим к концу, мы не вычитаем семерки, поэтому результат будет в диапазоне 0-24; если вы хотите , строгий модуль (0-7), суррогат
*c
с*c||n>6
вfor
состоянии петли.Это дает право на расширенный бонус, потому что это
Программа испытаний и результаты
Альтернативная версия
Вот тот, который повторяется (вы захотите, чтобы оптимизация компилятора выполняла преобразование хвостового вызова, или вы можете переполнить свой стек; я использовал
gcc -std=c89 -O3
):Назовите это с '0' как второй аргумент.
Обе версии рассчитывают остаток по модулю семь из 60000-значного числа менее чем за 50 миллисекунд на моей машине.
источник
PHP, 50 байт
использует альтернативный вывод; работает до
PHP_INT_MAX
строковая версия, работает для любого (положительного) числа (64 байта):
источник
Java, 133 байта
Я ненавижу, как многословен
Integer.parseInt
. Ungolfed:источник