나는 최근에 창의적 기반에서 숫자의 영리한 사용을 부분적으로 또는 전체적으로 기반으로하는 수많은 알고리즘이 있다는 것을 알게되었습니다. 예를 들면 :
- 이항 힙은 이진수를 기반으로하고 더 복잡한 스큐 이항 힙은 스큐 이진수를 기반으로합니다.
- 사전 순으로 정렬 된 순열을 생성하는 일부 알고리즘은 팩 토라 딕 숫자 시스템을 기반으로합니다.
- 시도는 적절한 기준에 대해 한 번에 문자열의 한 자리를 보는 트리로 생각할 수 있습니다.
- Huffman 인코딩 트리는 트리의 각 에지가 일부 이진 표현에서 0 또는 1을 인코딩하도록 설계되었습니다.
- 피보나치 코딩은 피보나치 검색에 사용되며 특정 유형의 로그를 반전하는 데 사용됩니다.
제 질문은 : 직관이나 증명의 핵심 단계로 영리한 숫자 체계를 사용하는 다른 알고리즘이 있습니까? . 나는 주제에 대한 강연을 모으는 것에 대해 생각하고있다. 그래서 더 많은 예를 얻어야할수록 좋다.
답변
Chris Okasaki는 그의 저서 Purely Functional Data Structures 에서 “Numerical Representations”에 대해 아주 좋은 장을 가지고 있습니다. 본질적으로 숫자의 일부 표현을 취하여 데이터 구조로 변환합니다. 풍미를 제공하기 위해 해당 장의 섹션은 다음과 같습니다.
- 위치 번호 체계
- 이진 숫자 (이진 랜덤 액세스 목록, 제로리스 표현, 게으른 표현, 세그먼트 표현)
- 이진 숫자 기울이기 (이진 임의 액세스 목록 기울이기, 이항 힙 기울이기)
- 삼진 및 사진 숫자
몇 가지 최고의 트릭은 다음과 같습니다.
- 구별 밀도 및 스파 스 (일반적으로이 행렬 또는 그래프에서 볼하지만 너무 숫자에 적용 할 수있어!) 숫자의 표현
- 중복 번호 체계 (숫자를 두 개 이상 표시하는 시스템)가 유용합니다.
- 첫 번째 숫자를 0이 아니도록 배열하거나 0이없는 표현을 사용하면 데이터 구조의 헤드를 검색하는 것이 효율적일 수 있습니다.
- 데이터 구조 를 세분화 하여 계단식 차용 (목록의 끝 부분을 가져옴) 및 전달 (목록에 대한 고려에서)을 피하십시오.
다음은 해당 장에 대한 참조 목록입니다.
- Guibas, McCreight, Plass 및 Roberts : 선형 목록에 대한 새로운 표현.
- Myers : 적용 가능한 랜덤 액세스 스택
- Carlsson, Munro, Poblete : 삽입 시간이 일정한 암시 적 이항 대기열.
- Kaplan, Tarjan : 순전히 기능적 목록이며 재귀 적 속도 저하를 통해 연결됩니다.
답변
“삼진 숫자는 Sierpinski Triangle이나 Cantor 세트와 같은 자기 유사 구조를 편리하게 전달하는 데 사용할 수 있습니다.” 출처
“2D 힐베르트 곡선의 표현에는 4 진수가 사용됩니다.” 출처
“쿼터-허수 시스템은 1955 년 Donald Knuth가 고등학교 과학 재능 검색에 제출하여 처음 제안했습니다. 허수 2i를 기본으로 사용하는 비표준 위치 숫자 시스템입니다. 숫자 0, 1, 2, 3 만 사용하여 모든 복소수를 나타냅니다. ” 출처
“로마 숫자는 이분법입니다.” 출처
“Senary는 소수 연구에서 유용한 것으로 간주 될 수 있습니다. 2와 3을 제외한 모든 소수는 1 또는 5를 마지막 숫자로 갖기 때문입니다.” 출처
“Sexagesimal (기본 60)은 60을 기본으로하는 숫자 체계입니다. 기원전 3 천년에 고대 수메르 인에서 시작되었으며 고대 바빌로니아 인에게 전 해졌고 여전히 수정 된 형태로 측정에 사용됩니다. 각도 인 시간, 각도, 지리적 좌표. ” 출처
기타…
이 목록 은 좋은 출발점입니다.
답변
지난번에 귀하의 질문을 읽었으며 오늘 문제에 직면했습니다. 집합의 모든 분할을 어떻게 생성합니까? 나에게 발생한 해결책과 내가 사용한 (아마도 귀하의 질문을 읽었 기 때문에) 다음과 같습니다.
(p) 파티션이 필요한 (n) 요소가있는 집합의 경우 기본 (p)의 모든 (n) 자리 숫자를 세어보세요.
각 숫자는 분할에 해당합니다. 각 숫자는 세트의 요소에 해당하며 숫자 값은 요소를 넣을 파티션을 알려줍니다.
놀랍지는 않지만 깔끔합니다. 완전하고 중복이 발생하지 않으며 임의의 기반을 사용합니다. 사용하는 기준은 특정 파티션 문제에 따라 다릅니다.
답변
저는 최근에 0과 2n -1 사이의 숫자에 대한 이진 표현을 기반으로 사전 식 순서로 하위 집합을 생성하는 멋진 알고리즘을 발견했습니다.이 알고리즘 은 숫자 비트를 사용하여 집합에 대해 선택해야하는 요소를 결정하고 로컬로 재정렬해야합니다. 사전 순서로 가져 오기 위해 생성 된 세트. 궁금하다면 여기에 글을 게시 했습니다 .
또한 많은 알고리즘이 스케일링 (예 : Ford-Fulkerson max-flow 알고리즘의 약한 다항식 버전)을 기반으로하며, 입력 문제에서 숫자의 이진 표현을 사용하여 대략적인 근사를 완전한 솔루션으로 점진적으로 정제합니다.
답변
정확히 영리한 기본 시스템은 아니지만 기본 시스템의 영리한 사용 : Van der Corput 시퀀스는 숫자의 base-n 표현을 반대로하여 형성된 낮은 불일치 시퀀스 입니다. 그들은 2-D 구성하는 데 사용하고 홀턴 시퀀스 종류 등으로 볼 이 .
답변
매트릭스 곱셈의 속도를 높이기 위해 이중 기본 시스템에 대해 모호하게 기억합니다.
이중베이스 시스템은 하나의 번호에 두 개의베이스를 사용하는 중복 시스템입니다.
n = Sum(i=1 --> l){ c_i * 2^{a_i} * 3 ^ {b_i}, where c in {-1,1}
중복은 하나의 숫자를 여러 방법으로 지정할 수 있음을 의미합니다.
Todor Cooklev의 Vassil Dimitrov의 “행렬 다항식 계산을위한 하이브리드 알고리즘”기사를 찾을 수 있습니다.
내가 할 수있는 가장 짧은 개요를 제공하려고합니다.
그들은 행렬 다항식을 계산하려고했습니다 G(N,A) = I + A + ... + A^{N-1}.
Supoosing N은 복합 G(N,A) = G(J,A) * G(K, A^J)이며 J = 2를 신청하면 다음을 얻습니다.
/ (I + A) * G(K, A^2) , if N = 2K
G(N,A) = |
\ I + (A + A^2) * G(K, A^2) , if N = 2K + 1
또한,
/ (I + A + A^2) * G(K, A^3) , if N = 3K
G(N,A) = | I + (A + A^2 + A^3) * G(K, A^3) , if N = 3K + 1
\ I + A * (A + A^2 + A^3) * G(K, A^3) , if N = 3K + 2
이러한 방정식 중 일부는 첫 번째 시스템에서 빠르고 일부는 두 번째 시스템에서 더 낫다는 것이 “분명한”(농담으로)이므로에 따라 가장 좋은 것을 선택하는 것이 좋습니다 N. 그러나 이것은 2와 3 모두에 대해 빠른 모듈로 연산이 필요합니다. 이중베이스가 들어오는 이유는 다음과 같습니다. 기본적으로 둘 다에 대해 모듈로 연산을 빠르게 수행하여 결합 된 시스템을 제공 할 수 있습니다.
/ (I + A + A^2) * G(K, A^3) , if N = 0 or 3 mod 6
G(N,A) = | I + (A + A^2 + A^3) * G(K, A^3) , if N = 1 or 4 mod 6
| (I + A) * G(3K + 1, A^2) , if N = 2 mod 6
\ I + (A + A^2) * G(3K + 2, A^2) , if N = 5 mod 6
나는이 분야의 전문가가 아니기 때문에 더 나은 설명을 위해 기사를보십시오.
답변
RadixSort는 다양한 숫자 기반을 사용할 수 있습니다.
http://en.wikipedia.org/wiki/Radix_sort
bucketSort의 꽤 흥미로운 구현입니다.
