Python 재 귀 함수 의 정확 한 이해 와 사용

먼저 문 제 를 보 겠 습 니 다.
문제 면 묘사
샤 오 밍 은 수학 을 배 우 는 것 을 좋아 하고 이상 한 문 제 를 푸 는 것 을 좋아한다. 이날 그 는 주어진 N 에 대해 몇 개의 M 이 'M < = N, gcd (N, M) = 1, M 은 짝수' 라 고 만족 하 는 지 알 고 싶 어 한다.당신 이 프로그램 을 써 서 샤 오 밍 이 이 문 제 를 해결 하 는 것 을 도와 주세요.
입력 데이터
데 이 터 를 입력 하 는 첫 번 째 행 위 는 정수 T 로 테스트 데이터 의 그룹 수 를 표시 합 니 다.다음 T 조 테스트 데이터 중 각 조 테스트 데 이 터 는 한 줄 로 하나의 정수 N (1 ≤ T ≤ 100, 1 ≤ N ≤ 10000) 을 포함한다.
출력 데이터
각 그룹 에 데 이 터 를 입력 할 때 단독 줄 에서 'Case \ # id: M' 을 출력 합 니 다. id 그룹 데이터 결 과 는 M 이 고 id 는 1 부터 시작 합 니 다.
샘플 입력
4
1
2
11
23
샘플 출력
Case #1: 0
Case #2: 0
Case #3: 5
Case #4: 11
Hint:
gcd (a, b) = 1 은 a 와 b 의 최대 공약 수 는 1, 즉 a 와 b 의 상호 소 를 나타 낸다.

알고리즘 사고방식 설명

입 출력 과 디 스 플레이 분석

소스 코드 와 재 귀 함수 의 정수 가 있 는 곳

1. 두 개의 수 는 서로 소: 최소 공약 수 는 1 이다.우 리 는 조금 큰 수의% 가 작은 숫자 만 있 으 면 지난 라운드 의 작은 수의% 라 는 나머지 는 또 하나의 여 수 를 얻 고 매번 이 나머지 가 0 인지 1 인지 판단 한다.0 만 나타 나 면 서로 담백 하지 않다.
2. 입력 은 list [] 로 저장 합 니 다.출력의 번 호 는 순환 안에서 계산 할 수 있다.출력 할당: print ('Case \ #% d:% d'% (x, y))
3.

#  ，       ，     
def gcd(x,y):#      
    if x>=y:
        z1=x%y#   
        if z1==0:#    ==0，    0      x,y        。
            return 0
        elif z1==1:#    ==1，    1      x,y       。
            return 1
        else:#           ，    ，       ，    ，      0/1
            return gcd(y,z1)
    else:
        (x,y)=(y,x)
        z1=x%y
        if z1==0:
            return 0
        elif z1==1:
            return 1
        else:
            return gcd(y,z1)
test_nums=int(input())
stores=[]
for ii in range(test_nums):
    stores.append(int(input()))
m=0#  
for i in stores:
    n=0
    m=m+1
    for M in range(2,i+1,2):
        if_is=gcd(i,M)
        if if_is==1:
            n=n+1
    print('Case #%d:'%(m),n)

이곳 의 귀속 함 수 는 사실 비교적 보수적이다.

def get_gcd(a,b):  
    if(a % b) == 0:  
        return b    
    else:    
        return get_gcd(b, a % b) 

이것 은 한 학우 의 개선 으로 재 귀 함수 의 결과 가 1 인지 아 닌 지 를 직접 판단 하 는 것 이다. 1 이면 상호 소 이다.이곳 은 재 귀적 이기 때문에 소수% 가 비교적 크 더 라 도 관계 가 없 으 며, 단지 한 번 재 귀적 하 는 것 일 뿐이다.

>>> 10%3
1
>>> 3%10
3
>>> 10%3
1

재 귀 함수 의 특징: 정 의 된 함수 에서 반드시 return 뒤에서 원 함 수 를 다시 호출 하고 if 함수 의 return 특정한 계 산 된 변 수 를 마지막 결과 로 해 야 합 니 다.안 그러면 끝 이 없어.