Нетерпеливый тест делимости

14

Ваша задача - написать программу или функцию, которая определяет, делится ли число на другое. Подвох в том, что он должен дать ответ как можно скорее , даже если не все цифры номера были даны.

Ваша программа должна принимать целое число D ≥ 2 и затем последовательность цифр в качестве входных данных. Они представляют собой цифры другого целого числа N ≥ 1, начиная с наименее значащей цифры. В первой точке , что N либо должен или не должен быть divisble на D , ваша программа должна вывести соответствующий ответ и выход. Если достигнут конец ввода, он должен вывести, делится ли полное N на D .

Вот список допустимых форматов ввода для N (оставьте комментарий, если вы считаете, что то, что не включено, должно быть разрешено):

  • Стандартный ввод : цифры даны в отдельных строках; конец ввода - EOF или специальное значение; Выход означает, что функция возвращается или программа завершается.

  • Аналоговый ввод : например, нажатием клавиш или десятью кнопками, представляющими каждую цифру; конец ввода является специальным значением; Выход означает, что функция возвращается или программа завершается.

  • Функция с глобальным состоянием : вызывается повторно с последовательными цифрами; конец ввода является специальным значением; Выход означает, что функция возвращает ненулевое значение. Обратите внимание, что если вы используете глобальное состояние, оно должно быть очищено после того, как значение возвращено, или иначе сброшено , чтобы функция работала несколько раз .

  • Curried function : возвращает либо другую функцию, которая будет вызвана со следующей цифрой, либо значением; конец ввода - это специальное значение или вызов функции без аргумента; Выход означает, что функция возвращает ответ, а не другую функцию.

  • Приглашение GUI или подобное : отображается повторно; конец ввода «отмена» или эквивалентный, или специальное значение; Выход означает, что запросы перестают появляться.

  • Функция итератора : input - это объект или функция с состоянием, который возвращает следующую цифру при вызове, end of input - исключение или специальное значение; Выход означает, что итератор перестает вызываться.

Ввод для D и вывод может быть через любой приемлемый стандартный метод .

Тестовые случаи:

2;   6               => true
5;   6               => false
20;  0 3             => false
20;  0 4             => true
100; 1               => false
100; 0 0             => true
100; 0 2             => false
4;   2 4             => false
4;   2 5             => true
4;   2 [eof]         => false
4;   4 [eof]         => true
625; 5 5             => false
625; 5 7 2           => false
625; 5 7 3 6         => false
625; 5 7 3 4         => true
7;   9 3 4 [eof]     => false
7;   9 3 4 5 [eof]   => true
140; 0 3             => false
140; 0 4 5 [eof]     => false
140; 0 4 5 1 [eof]   => true
14;  4 5 1 4 [eof]   => false
14;  4 5 1 4 1 [eof] => true
Дверная ручка
источник
Я думаю, что мы должны предполагать, что одна цифра будет даваться каждый раз, когда наше решение запрашивает ввод, верно? И это должна быть полная программа, так как это объективный способ гарантировать, что ввод дается цифра за цифрой, не так ли? (В задании говорится «программа или функция», хм ...)
Эрик Аутгольфер
1
@EriktheOutgolfer Формат ввода подробно объяснен в маркированном списке в вопросе.
Ручка
1
Я просто думал о том, насколько объективными могут быть эти форматы ... Думаю, я просто перестану придираться и начну на самом деле решать эту проблему . :-)
Эрик Outgolfer
1
Что-то не так с простым списком в качестве digitsвходных данных со специальным значением для EOF?
Джонатан Аллан
1
@EriktheOutgolfer нет, если есть значение EOF, если я что-то не так понял. Для примера предположим, что вся ценность 132 и потенциальный делитель 4 , то []и [2]возвращение ничего, кроме falseили true( в том числе и самой функции и т.д. ...) в то время как [2,3], [2,3,1]и [2,3,1,EOF]возвращение true. Мне кажется, что это близко к глобальному состоянию.
Джонатан Аллан

Ответы:

9

JavaScript (ES6), 70 байт

Формат ввода: функция Curried

101

p=>(q='',g=(d,t=k=z=!~d||(q=d+q,p))=>k--?g(d,t-=(k+q)%p<1):t?t-z&&g:1)

Попробуйте онлайн!

Как?

pqn0k<p

(1)k×10n+q(modp)

xpm10k<px=mp+k

x×10n+q(modp)=(mp+k)×10n+q(modp)=(mp×10n(modp))+(k×10n+q(modp))(modp)=0+(k×10n+q(modp))(modp)=k×10n+q(modp)

Therefore, if (1) is equal to 0 for all 0k<p, it will also be equal to 0 for any kp and the answer is true.

For the same reason, if (1) is greater than 0 for all 0k<p, the answer is false.

If the results of (1) are mixed, we can't decide yet and need either more digits of q или уведомление EOF.

комментарии

p => (                       // p = divisor
  q = '',                    // q = dividend stored as a string, initially empty
  g = (                      // g() = curried function taking:
    d,                       //   d = next digit
    t =                      //   t = number of iterations yielding a non-zero value
    k =                      //   k = total number of iterations to process
    z =                      //   z = copy of k
      !~d ||                 //   if d == -1 (meaning EOF), use only 1 iteration
                             //   so that we simply test the current value of q
      (q = d + q, p)         //   otherwise, prepend d to q and use p iterations
  ) =>                       //
    k-- ?                    //   decrement k; if it was not equal to zero:
      g(                     //     do a recursive call to g():
        d,                   //       pass the current value of d (will be ignored anyway)
        t -= (k + q) % p < 1 //       test (k + q) % p and update t accordingly
      )                      //     end of recursive call
    :                        //   else:
      t ?                    //     if t is greater than 0:
        t - z && g           //       return 0 if t == z, or g otherwise
      :                      //     else:
        1                    //       return 1
)                            //
Arnauld
источник
2

Пакет, 177 169 байт

@set n=
@set g=1
:l
@set/ps=
@if %s%==- goto g
@set n=%s%%n%
@set/ae=%1/g,g*=2-e%%2,g*=1+4*!(e%%5),r=n%%g
@if %g% neq %1 if %r%==0 goto l
:g
@cmd/cset/a!(n%%%1)

Принимает dв качестве параметра командной строки и считывает цифры в nотдельных строках -как маркер EOF. Выходы 1делятся, 0если нет. Объяснение:

@set n=

Инициализируйте nпустую строку.

@set g=1

g является gcd(d, 10**len(n))

:l

Начните цикл чтения цифр.

@set/ps=

Прочитайте следующую цифру.

@if %s%==- goto g

Остановить обработку в EOF.

@set n=%s%%n%

Добавьте следующую цифру к n.

@set/ae=%1/g,g*=2-e%%2,g*=1+4*!(e%%5),r=n%%g

Обновите gсейчас, что len(n)увеличилось и рассчитать n%g.

@if %g% neq %1 if %r%==0 goto l

Если rне ноль, то dопределенно не делит n, потому что g, фактор d, не делит . Если rноль, то мы знаем только, dделит ли, nесли gравен d, поэтому, если это не так, продолжайте цикл.

:g

Вырваться из цикла чтения цифр здесь, на EOF.

@cmd/cset/a!(n%%%1)

Рассчитать и неявно вывести результат.

Нил
источник