반전 된 피라미드

Question

나는 거꾸로 된 피라미드가 있습니다. 상단에는 1에서 N의 숫자가 있습니다. 아래에는 두 개의 숫자로 된 숫자 (N-1)가 기록되어 있습니다. 각 행마다 등등. 예 ( N = 4) 용

:

1  2  3  4 
    2  6  12 
     12  72 
      864 

I 최종 번호의 처음 숫자를 찾을 수있다. O (N)에서이 작업을 수행 할 수 있습니까? 특정 알고리즘이있을 수 있습니까?

Answer 1

먼저 당신이 파스칼의 삼각형을 볼 수있는 지수를 보면 요인

1¹   2¹   3¹   4¹ 
    1¹⋅2¹  2¹⋅3¹  3¹⋅4¹ 
     1¹⋅2²⋅3¹ 2¹⋅3²⋅4¹ 
      1¹⋅2³⋅3³⋅4¹ 

에서 봐 가지고 있습니다.

그래서 당신의 곱셈 피라미드의 마지막 요소의 포뮬러는

 
pn = Πk=1,...,n nbinom(n-1,k-1) 

지금 당신이 "전용"결과의 첫 번째 자리 dn를 얻을 수있을 것입니다. 당신은 거대한 숫자를 방지하기 위해

 
dn = floor(pn/10floor(log10(pn))) 
    = floor(10log10(pn)/10floor(log10(pn))) 
    = floor(10log10(pn) - floor(log10(pn))) 

를 계산하여이 작업을 수행 할 수있는 당신은

 
log(pn) = Σk=1,...,n binom(n-1,k-1)⋅log(k) 

예에 의해 직접 log(pn)을 계산할 수 있습니다

 
d₄ = floor(10log₁₀(864) - floor(log₁₀(864))) 
    = floor(102.936513742 - 2) 
    = floor(100.936513742) 
    = floor(8.64) 
    = 8 

당신이 n을해야 할, log(pn)을 계산하려면 곱셈과 n-1 추가. 이 후에는 일정한 수의 작업 만 계산해야하므로 O(n)에서 실행됩니다.