태그 보관물: decision-problem

decision-problem

참을성이없는 분열 테스트 전역 상태를 사용하는 경우

당신의 임무는 숫자를 다른 숫자로 나눌 수 있는지 여부를 결정하는 프로그램이나 함수를 작성하는 것입니다. 문제는 숫자의 모든 숫자가 주어지지 않았더라도 가능한 한 빨리 답변을 제공해야 한다는 입니다.

프로그램은 정수 D ≥ 2를 입력 한 다음 일련의 숫자를 입력으로 사용해야 합니다. 이들은 최소 유효 자릿수부터 시작하여 다른 정수 N ≥ 1 의 자릿수를 나타냅니다 . 최초의 시점에서 N 중 하나가 있어야합니다 또는 의한 divisble 수 D , 프로그램 출력해야 적절한 대답 하고 종료합니다. 입력의 끝에 도달하면 전체 ND 로 나눌 수 있는지 여부를 출력해야합니다 .

다음은 N 에 허용되는 입력 형식 목록입니다
(포함되지 않은 것을 허용해야한다고 생각하는 경우 주석 남기기).

  • 표준 입력 : 숫자는 별도의 줄에 제공됩니다.
    입력 끝 은 EOF 또는 특수 값입니다.
    종료 는 함수가 리턴되거나 프로그램이 종료 됨을 의미합니다.

  • 아날로그 입력 : 키 스트로크 또는 각 숫자를 나타내는 10 개의 버튼;
    입력 끝은 특수한 값입니다.
    종료 는 함수가 리턴되거나 프로그램이 종료 됨을 의미합니다.

  • 전역 상태의 함수 : 연속 숫자로 반복해서 호출됩니다.
    입력 끝은 특수한 값입니다.
    종료 는 함수가 널이 아닌 값을 리턴 함을 의미합니다. 전역 상태를 사용하는 경우 , 함수가 여러 번 작동 하도록 값이 리턴 된 후 재설정되거나 그렇지 않으면 재설정 되어야합니다 .

  • Curried function : 다음 숫자 또는 값으로 호출 할 다른 함수를 반환합니다.
    입력 끝은 특별한 값이거나 인수없이 함수를 호출하는 것입니다.
    종료 는 함수가 다른 함수가 아니라 응답을 반환 함을 의미합니다.

  • GUI 프롬프트 또는 유사 : 반복적으로 표시됩니다.
    입력 끝 이 “취소”또는 이와 동등한 값이거나 특수 값입니다.
    종료 는 프롬프트가 중지되는 것을 의미합니다.

  • 반복자 함수 : 입력은 호출 될 때 다음 숫자를 리턴하는 상태 저장 오브젝트 또는 함수
    입니다. 입력 끝은 예외 또는 특수 값입니다.
    종료 는 반복자가 호출을 중지 함을 의미합니다.

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


답변

자바 스크립트 (ES6), 70 바이트

입력 형식 : 카레 기능

−1

0

1
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)

온라인으로 사용해보십시오!

어떻게?

p

q

n

0≤k<p

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

x≥p

m≥1

0≤k<p

x=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

0≤k<p

, it will also be equal to

0

for any

k≥p

and the answer is true.

For the same reason, if

(1)

is greater than

0

for all

0≤k<p

, the answer is false.

If the results of

(1)

혼합되어 있으며 아직 결정할 수 없으며 더 많은 자릿수가 필요합니다.

또는 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
)                            //

답변

배치, 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

r0이 아닌 경우 는 의 인수로 d나누지 n않기 때문에 확실히 나누지 않습니다. 경우 제로 우리는 여부 만 알고 분할 하는 경우 등호 , 그렇지 않은 그렇다면, 루프를 계속합니다.gdrdngd

:g

EOF에서 자릿수 판독 루프를 해제하십시오.

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

결과를 계산하고 암시 적으로 출력합니다.


답변