알고리즘 분석 및 디자인 실험 - 최대 공약수
함수 이름을 gcd(a,b)로 하고 a&b로 가정합니다
방법1: 폭력 구해법
위조 코드:
gcd(a,b)
for 1←b to i
if (a mod i==0) and (b mod i==0)
return i
C++ 코드:
#include
using namespace std;
int min(int a,int b){
return a>b?b:a;
}
int gcd(int a,int b){
for(int i=min(a,b);i>=1;i--){
if(a%i==0&&b%i==0){
return i;
}
}
}
int main(){
int a,b;
cin>>a>>b;
cout< 이 방법은 만력사상을 채택하여 a, b에서 비교적 소수에서 점차 줄어들기 시작하고 같은 두 수의 인수가 나타나면 gcd함수는 이 인수를 되돌려준다.a&b로 가정하면 최악의 시간 복잡도는 O(b)입니다.
또한 다음과 같이 손쉽게 최적화할 수 있습니다.
gcd(a,b)
for 1←b/2 to i
if (a mod i==0) and (b mod i==0)
return i
순환 시작값을 b/2로 설정하면 순환 횟수를 줄일 수 있고 데이터가 비교적 크면 시간을 약간 절약할 수 있다.
방법2: 전전 상제법
gcd(a,b)
while temp!=0 do
temp=a mod b
a=b
b=temp
return a
전전 상제법은 유클리드 알고리즘이라고도 하는데 C++ 코드는 다음과 같다(gcd 함수만).
int gcd(int a,int b){
int temp;
while(temp!=0){
temp=a%b;
a=b;
b=temp;
}
return a;
}또한 이 함수는 반복을 사용하여 단순화할 수도 있습니다.
int gcd(int a,int b){
return a%b==0?b:gcd(b,a%b);
}이 방법의 시간 복잡도는 O(lgb)로 만력법에 비해 많은 시간을 절약했다.그러나 데이터가 너무 크면 추출 연산 성능이 떨어지기 때문에 대수의 최대 공약수로 값을 구하는 것은 적합하지 않다.
방법3: 경상감손법
위조 코드:
gcd(a,b)
if a==b
return a
if a
return gcd(b-a,a)
else
return gcd(a-b,b)
C++ 코드(gcd 함수만):
int gcd(int a,int b){
if(a==b) return a;
if(a이 방법은 두 수의 차이를 구하는 방법을 운용하여 대수 연산시의 성능을 최적화시킨다.그러나 두 수의 크기가 너무 크면 이 방법의 효율은 매우 떨어진다. 예를 들어 a=1, b=100일 때 99번의 귀속을 진행하고 최악의 시간 복잡도는 심지어 O(a)에 가깝고 귀속 횟수가 너무 많으면 너무 많은 창고를 차지하기 때문에 불안정하다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
두 갈래 나무의 매 결점의 왼쪽 아이와 오른쪽 아이를 교환하여 ~2020.8.13~ 학습노트두 갈래 체인 시계를 두 갈래 나무의 저장 구조로 삼아 두 갈래 나무의 각 결점의 왼쪽 아이와 오른쪽 아이를 교환한다. 두 갈래 나무의 순서를 입력하십시오.알림: 두 갈래 나무의 순서 서열은 문자열입니다. 문자가'#...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
