태그 보관물: number-theory

number-theory

코드를 재사용하십시오! 답이 이깁니다. 이 스크립트 를 사용

이 도전에서 우리는 한 번에 두 가지 중요한 문제를 해결하려고 노력합니다. 그들은:

  1. 정수 a 와 b가 주어지면 , b -1이 소수 인지 알려 주십시오.
  2. 정수 a 와 b가 주어지면 nCr (a, b)를 반환 합니다.

특히, 첫 번째 작업을 수행하는 프로그램과 다른 프로그램을 수행하는 프로그램을 작성해야합니다. 두 문제를 한 번에 해결하려면 두 프로그램에서 동일한 코드를 사용하는 것이 좋습니다.

채점

답의 점수는 두 프로그램 사이의 Levenshtein 거리입니다. 낮은 점수가 좋습니다. 동점 인 경우 두 프로그램 중 가장 짧은 결합 코드를 가진 답이 이깁니다. 이 스크립트 를 사용 하여 솔루션의 점수를 계산할 수 있습니다.

규칙

  1. 위에서 설명한 작업을 해결하는 동일한 언어로 두 개의 프로그램을 작성해야합니다. 원하는 I / O 방법을 사용할 수 있습니다. 작업 1의 경우 참 / 거짓 값을 반환하거나 참과 거짓을 의미하는 두 값을 선택하고 그에 따라 반환 할 수 있습니다. 예 : 당신은 "prime"true를 "not prime"의미하고 false를 선택할 수 있습니다 .
  2. 사용하는 알고리즘은 가능한 모든 입력에 대해 작동해야하지만 사용 된 숫자 유형의 제한으로 인해 코드가 많은 경우 실패합니다. 입력이 유효하다고 가정 할 수 있습니다.

  3. 프로그램의 어떤 부분 집합도 문제를 해결해서는 안됩니다. 문자를 제거하면 코드가 작동하지 않아야합니다. 예를 들어, 다음 코드는 프로그램을 중단하지 않고 사용하지 않은 else-block을 제거 할 수 있기 때문에 유효하지 않습니다.

    if (1) { /* change to 0 to get the second program*/
    ...
} else {
    ...
}

  4. 표준 허점은 허용되지 않습니다.

테스트 사례

a b -1이 소수입니까?

a b
1 1 false
2 3 true
5 2 false
2 5 true
4 3 false
2 7 true

nCr

a b nCr(a,b)
1 1 1
5 2 10
4 3 4
10 7 120
12 5 792

답변

MATLAB, 거리 10

우선 순위 :

function x=f(a,b);x=isprime(a^b-1);

nCr :

function x=f(a,b);x=nchoosek(a,b);

답변

PHP, 거리 29

a^b-1 true로 0을 인쇄하고 false로 0보다 큰 정수 값을 인쇄합니다.

[,$a,$b]=$argv;for($c=-$i=1;$i<=$d=$a**$b-1;$d%++$i?:$c++);echo$c;

nCr(a,b)

[,$a,$b]=$argv;for($c=$i=1;$i<=$a;$c*=$i**(1-($i<=$a-$b)-($i<=$b)),$i++);echo$c;

PHP, 거리 36

a^b-1 true로 1을 인쇄하고 false로 아무것도 표시하지 않습니다.

[,$a,$b]=$argv;for($c=-1,$i=1;$i<=$d=-1+$a**$b;)$d%++$i?:$c++;echo$c<1;

nCr(a,b)

[,$a,$b]=$argv;for($c=$d=$i=1;$i<=$a;$c*=$i++)$d*=$i**(($i<=$a-$b)+($i<=$b));echo$c/$d;

답변

루비, 거리 1, 결합 된 길이 194

프라임 체크 :

->a,b{s='[(a**b-1).prime?,(1..b).inject(1){|m,i|(a+1-i)/i*m}][0]';require'math'<<s.size*2;eval s}

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

nCr :

->a,b{s='[(a**b-1).prime?,(1..b).inject(1){|m,i|(a+1-i)/i*m}][1]';require'math'<<s.size*2;eval s}

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

의견에서 예측 한 바와 같이, 일부 저크는 항상 문제의 정신에 반대해야합니다. 그래도 해결 방법을 찾는 것이 재미있었습니다! 작동 방식은 다음과 같습니다. 문제에 대한 두 가지 별도의 솔루션이 있습니다. 우리는 둘 다 실행하고 배열에 넣은 다음 편집 거리 1에 대해 0 번째 요소 또는 첫 번째 요소를 선택합니다. 원하는 계산 이외의 모든 것을 삭제할 수 있고 여전히 작동하기 때문에 일반적으로 불법입니다 . 그러나 각 코드 스 니펫은 동일한 표준 라이브러리의로드에 의존하도록 작성되었습니다 'mathn'.

  • 첫 번째는 내장을 사용합니다 prime?
  • 두 번째는 mathn나눗셈의 작동 방식 을 변경하는 것입니다.로드하기 전에로 3/4평가 0하고 그 후에는 분수로 평가합니다 (3/4). 의 중간 결과 (a+1-i)/i가 항상 정수가 아니기 때문에 라이브러리가 없으면 전체 결과가 잘못됩니다.

이제 수정되지 않은 나머지 코드에 라이브러리를 로딩해야합니다. 우리는 나머지 메인 코드의 문자 길이를 사용하여 mathn이라는 이름을 생성하여이 작업을 수행합니다. 결합 된 계산의 길이는 55로, 두 배는 110으로 두 배가되며 ASCII 값은 ‘n’입니다. 따라서 이것을 문자열 ‘math’에 연결하면 원하는 라이브러리가 제공됩니다.

또한 라이브러리 종속성을 도입하면 코드를 적절한 시간 내에 실행할 수 있습니다. 특히, nCr에 대한 순진한 접근법은 부분 중간 결과를 생성하지 않을 것이다.

답변

05AB1E , 거리 3

nCr

sc

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

isPrime (a ^ b-1)

m<p

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

답변

쌓인 거리 13

[([@.!]$/{%y!x y-!*})fork!]
[^#-:([]1/$%{!n 1-!})fork!=]

온라인으로 사용해보십시오! 첫 번째는 Wilson의 정리를 사용하여 두 번째 우선 순위 인 nCr을 계산합니다.

(f g h) fork!N스택에서 args를 팝업 (호출 a0 ... aN)하고 적용 a0 ... aN f a0 ... aN h g합니다.

첫 번째 프로그램의 경우 :

[([@.!]$/{%y!x y-!*})fork!]
[(                  )fork!]  apply the fork of:
  [@.!]                      equiv. { x y : x ! } => `x!`
       $/                    divided by
         {%        }         two-arg function
           y!                y!
             x y-                 (x - y)!
                 *              *

그리고 두 번째로 :

[^#-:([]1/$%{!n 1-!})fork!=]
[^                         ]  exponentiate  (a^b)
  #-                          decrement     (a^b-1)
    :                         duplicate     (a^b-1 a^b-1)
     (              )fork!    apply the fork to:
      []1/                    1-arg identity function
          $%                  modulus by
            {!     }          1-arg with `n`:
              n 1-             (n-1)
                  !                 !
                          =   check for equality

답변

파이썬 2 , 거리 15 , 길이 172

작업 1

D=lambda k:max(k-1,1)
P=lambda n,k=0:n<k or P(n-1,k)*n/k
lambda a,b:P(a**b-2)**2%D(a**b)

작업 2

D=lambda k:max(k-1,1)
P=lambda n,k=1:n<k or P(n-1,D(k))*n/k
lambda a,b:P(a,b)/P(a-b)

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

답변

매스 매 티카, 거리 10

작업 1 : PrimeQ[#2^#-1]&

작업 2 : Binomial[#2,#]&

두 기능 모두 순서대로 입력을 b,a받습니다.