총 저장 용량은 1 ~ 40 억입니다.

Question

이 질문에 영감을 얻었습니다 (Find an integer not among four billion given ones).

1에서 40 억까지의 정수를 저장하는 데 필요한 저장 공간은 어느 정도입니까?

예를 들어, 1 + 2 + 3 + 4 + 5 = 15. 1 백만 분의 합계 = 500000500000 분.

Here

는

Answer 1

당신이 연결 기능은 1부터 n까지 n 개의 자연수의 합으로 정의 된 n 번째 Triangular Number을 발견하는 방법을 설명하는 데 도움이 될 수 있습니다 알고리즘이다. 함수에 n은 40 억 대입

는

8000000002000000000. 표현하는 준다 비트 수의 값의베이스 2 로그를 취하고 반올림하여 작업 할 수있는 - (

CEIL을 log (8000000002000000000)/log (2)) = 63

따라서 63 비트의 저장 공간이 필요합니다.

Answer 2

In [12]: import math 

In [13]: n=4000000000 

In [15]: sumn = n*(n+1)/2 

In [16]: sumn 
Out[16]: 8000000002000000000L 

In [24]: math.log(sumn)/math.log(2) 
Out[24]: 62.794705708333197 

답변 : 63 비트.

Answer 3

정수에 적합한 인코딩을 선택하면 1 비트가 많습니다. 당신이 잠재적으로 저장해야 할 수 더 N^2 이상의 가능한 값이있는 경우

는 만 이상의 N 비트가 필요합니다. 여기에 저장할 수있는 유일한 가치가 있습니다.