Python 이 실현 한 중국 잉여 정리 알고리즘 예시
중국의 잉여 정리(Chinese Remainder Theorem-CRT):손자 정리 라 고도 부 르 는데 수론 중의 한 정리 이다.즉,만약 에 한 사람 이 하나의 수 n 이 여러 개의 정수 에 의 해 제 거 된 나머지 를 알 게 된다 면 이런 제 수 는 두 개의 서로 질 적 인 상황 에서 이 사람 은 이 정수 에 의 해 n 을 곱 하여 얻 은 나머지 를 유일 하 게 확정 할 수 있다.
위 키 피 디 아 에서 위 키 피 디 아:중국의 나머지 정 리 는 숫자 이론의 정리 입 니 다,만약 하나 가 여러 정수 에 의 해 정수의 n 의 부문의 나머지 를 알 고 있다 면,다음 하 나 는 고유 하 게 n 의 분할 의 나머지 를 결정 할 수 있 습 니 다 이러한 정수의 제품 에 의 해,조건 에 따라 divisors 쌍 으로 coprime.
한 수 는 n 이 고,두 번 째 는 1 을 나 누고,세 번 째 는 2 를 나 누고,다섯 번 째 는 4 를 나 누고,여섯 번 째 는 5 를 나 누 었 는데,마침 7 로 나 누 어 이 수 n 을 구 했다.
분석:n 은 2 에서 나머지 1 을 제외 하고 개술 이 최소 1 이 라 고 설명 한 후에 이 조건 이 계속 만족 하기 때문에 더 해 야 할 수 는 반드시 2 의 배수 이다.3 에 의 해 나머지 2,즉(1+2*i)%3=2 를 나 누 었 는데 그 중에서 i 는 정수 이다.이후 이 조건 이 계속 충족 되 기 때문에 더 해 야 할 수 는 반드시 3 의 배수 이 고,또 이전 조건 의 제한 때문에 2 와 3 의 최소 공배수 의 정수 배 이다.한 번 의 유추 로 7 로 나 누 어 진 수 를 찾 을 수 있다.
n=1
while(n%3 != 2):
n += 2
while(n%5 != 4):
n += 6
while(n%6 != 5):
n += 30
while(n%7 != 0):
n += 30
Python 관련 내용 에 관심 이 있 는 독자 들 은 본 사이트 의 주 제 를 볼 수 있 습 니 다.
본 논문 에서 말 한 것 이 여러분 의 Python 프로 그래 밍 에 도움 이 되 기 를 바 랍 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Python의 None과 NULL의 차이점 상세 정보그래서 대상 = 속성 + 방법 (사실 방법도 하나의 속성, 데이터 속성과 구별되는 호출 가능한 속성 같은 속성과 방법을 가진 대상을 클래스, 즉 Classl로 분류할 수 있다.클래스는 하나의 청사진과 같아서 하나의 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
