제로 부터 데이터 구조 와 알고리즘 의 아름다움 체험 (1) - 기초 수학 지식

2017 년 에 자신 에 게 몇 가지 임 무 를 열 거 했 는데 그 중 하 나 는 바로 데이터 구 조 를 다시 공부 하 는 것 이다. 본 고 에서 시 작 된 일련의 글 은 모두 자신 이 을 연구 한 학습 소감 이다. 그 중에서 편 파 적 이 고 심지어 천박한 점 이 있 을 것 이다. 언제든지 지적 을 환영 하고 감사합니다!
기초 수학 지식 은 주로 지수, 대수, 급수 와 증명 방법 을 사 용 했 습 니 다. 내용 이 지루 하고 제 가 쓴 것 도 고 통 스 럽 지만 이런 지식 들 은 어쨌든 유용 합 니 다. 데이터 구조 와 알고리즘 을 공부 할 때 도 필요 하기 때문에 저 는 억지로 다 먹 었 습 니 다.그 중에서 많은 공식 들 이 고등학교 의 지식 (이과) 이 었 습 니 다. 손 가 는 대로 집어 들 었 습 니 다. 지금 은 많은 공식 과 정 리 를 종이 위 에서 한참 동안 유 도 했 습 니 다. 약간 안 타 깝 습 니 다.............................................
사용 하 는 사이트: 수학 공식 편집기
지수
공식.

​

​

​

​ 

​

대수
1. 정의
만약 X 의 A 차 멱 이 B 라면, A 를 X 를 밑 으로 하 는 B 라 고 하 는 대수 가 컴퓨터 과학 에 있 고, 특별한 성명 이 없 으 면 대 수 는 일반적으로 2 를 밑 으로 한다
2. 정리

​ 

​ 

급수
공식.

​

​

​ }{2}\approx \frac{N^{2}}{2})

​ (2N+1)}{6}\approx \frac{N^{3}}{3})

​ 

k = - 1 시 이 공식 은 성립 되 지 않 습 니 다.이때 우 리 는 아래 의 공식 이 필요 하 다. Hn 을 조화 수 라 고 부 르 고 이것 을 조화 라 고 부른다.이 근사 식 중의 오 차 는 0.57721566 로 오 라 상수 라 고 불 린 다γ。 
4. 모드 연산
정의.
N 이 A - B 를 제거 하면 A 와 B 모델 N 이 같다 고 말 하고 기억 하 세 요 는 직관 적 으로 보면 A 든 B 든 N 에 의 해 제거 되 고 소득 여 수 는 같다 는 것 이다.
알다 시 피 수학 에서 A / B 는 A 가 B 로 나 뉘 거나 B 가 A 로 나 뉜 다.그러면 N 이 A - B 를 제거 하 는 것 은 A% N = B% N 을 의미 합 니 다. 예 를 들 어
)
증명 방법
귀납법
귀납법 으로 진 행 된 증명 에는 두 가지 표준 부분 이 있다.첫 번 째 단 계 는 기준 상황 을 증명 하 는 것 이다. 바로 정리 가 특정한 (일부) 작은 값 에 대한 정확성 을 확정 하 는 것 이다.이 단 계 는 거의 항상 간단 하 다.이어서 귀납 적 가설 을 진행 하 다.일반적으로 이 는 가설 정리 가 특정한 유한 수 k 까지 의 모든 상황 이 성립 될 때 까지 가설 하 는 것 을 말한다.그리고 이 가설 을 사용 하여 정리 가 다음 값 (보통 k + 1) 에 대해 서도 성립 되 었 다 는 것 을 증명 한다.이로써 정리 가 입증 되 었 다.
이제 다음 급수 중의 공식 4 를 증명 합 시다 (2N + 1)} {6}; N \ \ geqslant 1) 우선 기준 상황 을 쉽게 볼 수 있 습 니 다. N = 1 시 에 성립 됩 니 다.그리고 정리 가 1 & lt; = k & gt; = N 에 성립 된다 고 가정 한 다음 에 우 리 는 이 가설 이 성립 된 상황 에서 N + 1 에 대해 서도 성립 되 었 다 는 것 을 증명 한다.저 희 는 있어 요. ^2)
(2N+1)}{6}+(N+1)^2)
[\frac{N(2N+1)}{6}+(N+1)])
\frac{2N^2+7N+6}{6})
(N+2)(2N+3)}{6})
[(N+1)+1][2(N+1)+1]}{6})
정리 가 입증 되다

반 례 법
반 례 를 하나 들 면 된다.

반증 법
반증 법 은 가설 정 리 를 통 해 성립 되 지 않 는 다 는 것 을 증명 한 다음 에 이 가설 이 이미 알 고 있 는 성질 이 성립 되 지 않 는 다 는 것 을 증명 하고 원래 의 가설 이 잘못된 것 임 을 증명 한다.
하나의 전형 적 인 예 는 무한 한 소수 가 존재 한 다 는 것 을 증명 하 는 것 이다.이 결론 을 증명 하기 위해 서 우 리 는 정리 가 성립 되 지 않 는 다 고 가정한다.그래서 가장 큰 소수 Pk 가 존재 합 니 다.P1, P2,..., Pk 는 순서대로 배 열 된 모든 소수 이 며 고려 합 니 다.

분명히 N 은 Pk 보다 큰 숫자 이 고 가설 에 따 르 면 N 은 소수 가 아니 라 Pk 가 가장 큰 소수 이기 때문이다.그러나 P1, P2,........................................................................이것 은 하나의 모순 이 생 긴 다. 왜냐하면 모든 정수 나 소수 또는 소수 의 곱셈 이기 때문이다.따라서 Pk 가 최대 소수 라 는 원래 가설 은 성립 되 지 않 기 때문에 정리 가 성립 된다.