다른 반경의 N 개의 원을 한 줄에 배열 할 수있는 방법의 수

Question

질문 : 한 줄에 M 개의 점이 11 단위로 구분됩니다. 서로 다른 반지름의 N 개의 원이 그려져 교차되거나 겹치지 않도록하거나 여러개의 반지름 중 하나를 그릴 수있는 방법의 수를 찾으십시오. ?? 서클 센터가 MM 포인트 여야합니다.

예 1 : N = 3, M = 6, r1 = 1, r2 = 1, r3 = 1 응답 : 24 가지 방법.

예 2 : N = 2, M = 5, r1 = 1, r2 = 2 답 : 6 가지 방법.

실시 예 3 : N = 1, M = 10, r = 50. 답변 = 10 가지.

온라인에서이 질문을 발견했지만 지금까지 해결할 수 없었습니다. 지금까지는 어떤 서클도 n-rn-r에서 n-2rn-2r까지 공백을 사용할 수있는만큼만 작업 할 수있었습니다. 그러나 다른 문제들 중에서 반경 33의 원이 n-4n-4 번째 점을 취하는 엣지 경우를 조정할 수있는 방법은 무엇입니까? 이제 마지막 점은 그대로 유지되지만 반경이 1보다 큰 원은 배치 할 수 없습니다. 이것에 대한 일반화 된 수학적 해결책을 볼 수 있습니다.

Answer 1

원의 중심이 비 정수 x 및 y 좌표에 배치 될 수있는 경우 길이가 너무 짧거나 불가능하기 때문에 길이가 충분하고 무한히 많은 번역이 있기 때문에 무한히 많습니다.

결과를 계산해야하므로, (M, M)의 좌표는 정수라고 가정합니다.

한 개의 원이있는 경우 솔루션은 원을 합법적으로 배치 할 수있는 포인트의 수입니다.

두 개 이상의 원이있는 경우 직경의 합계를 계산해야하며,이 값이 우리가 말하는 회선 총 길이보다 큰 경우 솔루션이 없습니다. 그렇지 않은 경우, 전체 길이에서 직경의 합계를 뺀 다음 Complementer를 가져와야합니다. 너는 또한 N! 순열을 사용하여 서클의 순서를 계산합니다. 그리고 원 사이에 간격을 분배 할 수있는 Complementer - 1 개의 가능한 위치를 갖게됩니다. 간격의 길이는 G1, ..., GN-1

우리는 알고 G1 + ... + GN-1 = 보수기

G1의 가능 분포의 수 ..., 내지 Gn -1은 D입니다. 따라서 수식은 b

N! * D

나머지 질문은 다음과 같습니다. 어떻게 D를 계산할 수 있습니까?

해결 방법 : 깊이 = 1 DISTR를 호출 할 필요가

function distr(depth, maxDepth, amount) 
    if (depth = maxDepth) then 
     return 1 //we need to put the remaining elements on the last slot 
    end if 
    sum = 1 //if we put amount here, that is a trivial case 
    for i = amount - 1 to 0 do 
     sum = distr(depth + 1, maxDepth, amount - i) 
    end for 
    return sum 
end distr 

, MAXDEPTH = N-1, 당신은 1 개 단위를 뜻 = 보수기