알고리즘 연습

개 수색 에서 온 필기시험 문제
길이 가 n 인 배열 a [0], a [1], a [n - 1].현재 배열 의 이름 요 소 를 업데이트 합 니 다. 즉, a [0] 에서 a [1] 에서 a [0 - 1] 의 적 a [1] 는 a [0] 와 a [2] 에서 a [n - 1] 의 적 으로, a [n - 1] 는 a [0] 에서 a [n - 2] 의 적 으로 변 합 니 다.프로그램 요구: 선형 복잡 도 를 요구 합 니 다.나눗셈 연산 자 를 사용 할 수 없습니다.
우선 이 문제 의 가장 간단 한 방법 은
 

def change(a):

    sum = 1

    size = len(a)

    for i in range(size):

        sum = sum * a[i]

    for i in range(size):

        a[i] = sum / a[i]

 안 타 깝 게 도 이 문 제 는 나눗셈 을 사용 할 수 없어 인터넷 회사 들 은 간단 한 문 제 를 복잡 하 게 만 드 는 것 을 좋아한다.나눗셈 을 사용 할 수 없 는 이상 우 리 는 생각 을 바 꿀 수 밖 에 없다.나눗셈 을 사용 할 수 없고 다른 배열 을 통 해 이 루어 질 수 밖 에 없다.이 문 제 는 배열 의 모든 요소 의 값 을 다른 요소 의 곱 으로 업데이트 하 는 것 을 요구 합 니 다.그래서 우 리 는 하나의 배열 을 사용 합 니 다. 배열 의 모든 요 소 는 다른 요소 의 곱 하기 적 을 저장 하고 알고리즘 은 선형 이 어야 하기 때문에 모든 배열 의 요 소 는 다른 요소 의 곱 하기 를 간단하게 저장 할 수 없습니다. (그러면 하나의 곱 하기 를 저장 할 때마다 전체 배열 을 옮 겨 다 녀 야 하기 때 문 입 니 다) 우 리 는 배열 이 한 번 만 옮 겨 다 닐 수 있다 는 것 을 알 고 있 습 니 다.따라서 모든 요소 저장 값 의 선택 은 두 가지 밖 에 없다. 1. 옮 겨 다 니 는 요소 의 곱 을 저장 하고 2. 보존 기간 에 요소 의 곱 을 옮 겨 다 니 는 값 과 그 자체 의 곱 을 저장 하 는 것 (이런 부적 절 함 이 분명 하 다). 그래서 첫 번 째 방식 으로 곱 을 저장 할 수 밖 에 없다.
우 리 는 뒤에서 옮 겨 다 니 는 것 을 선택 합 니 다. 각 배열 의 요소 의 값 은 그 뒤의 모든 배열 요소 의 곱 과 같 습 니 다. 원래 의 배열 a 가 6 개의 요소 가 있다 고 가정 하면 배열 b [5] = 1, b [4] 입 니 다. = a[5]*b[5],b[3] = b[4]*a[4].....
이렇게 하면 b 배열 의 모든 요소 의 값 은 그 뒤의 모든 요소 의 곱 이지 만 그 앞의 요소 의 곱 은 어떻게 얻 을 수 있 습 니까?이때 우 리 는 예전 부터 a 를 옮 겨 다 니 며 앞 에 있 는 요소 의 곱 을 하나의 값 으로 저장 할 수 있 습 니 다.
예 를 들 어 우 리 는 배열 a 의 세 번 째 값 인 a [2] 를 옮 겨 다 녔 다. 우 리 는 하나의 요소 tmp 로 앞 에 옮 겨 다 니 는 모든 요소 의 곱 하기 즉 tmp = a [0] * a [1] 를 저장 했다. 이렇게 a [2] 를 업데이트 할 때 직접 사용한다.
　　a[2] = tmp * b[2]
알고리즘 은 다음 과 같 습 니 다.

 1 def change(a):

 2     size = len(a)

 3     b    = [1 for i in range(size)]

 4     for i in range(size - 2, -1, -1):

 5         b[i] = b[i + 1] * a[i + 1]

 6     c = 1

 7     for i in range(size):

 8         tmp = a[i]

 9         a[i] = c * b[i]

10         c = c * tmp