정수 곱하기 알고리즘

Question

공개이 질문은 CS 수업의 질문을 기반으로합니다. 그래도 그걸 확장하려고합니다.

초기 문제는 단순히 n 정수 세트가 지정되면 (자), (마다 다른 n_i없는) n-1 정수의 n 제품을보고있다. 선형 시간으로 실행하는 것입니다.

예를 들어, {1, 2, 3, 4}의 집합보고 할 2 * 3 * 4, 1 * 3 * 4, 1 * 2 * 4 및 1 * 2 * 3.

내가 생각할 수있는 가장 쉬운 해결책은 모든 개의 정수를 단계별로 처리하고 이들의 곱을 모두 계산하는 것입니다 (1 * 2 * 3 * 4). 그런 다음 두 번째 단계를 거치고 나누기를 사용하여 총 곱을 각 정수로 나눕니다. 매번 솔루션을보고하십시오 (24/1, 24/2, 24/3, 24/4).

위 작업은 선형 시간으로 실행됩니다. 교수는 또한 우리는 분열없이 그것을 할 수있는 방법을 제안했다. 공간 제한이 없으며 선형 시간 제한 만 있습니다. 나는 그것에 대해 생각했지만 빈 그림입니다. 어떤 제안?

Answer 1

먼저 모든 주요 제품을 포함하는 배열을 계산할 수 - 선형 시간 : - 그럼

1 
1 * 2 
1 * 2 * 3 
1 * 2 * 3 * 4 

초 후행 사람이 또한 선형 시간 :

  4 
     3 * 4 
    2 * 3 * 4 
1 * 2 * 3 * 4 

어떤 대답 할 수 직접 찾거나 첫 번째 목록의 한 항목과 두 번째 목록의 한 항목의 결과로 계산됩니다.

   (2 * 3 * 4) 
(1)   *  (3 * 4) 
(1 * 2)  *   (4) 
(1 * 2 * 3) 

Answer 2

그래서이 제품에 대해 정확히 무엇을 원합니까? 예를 들어 우리 제품에 1 * 1의 제품을 사용할 수 있습니까? 그렇다면 배열의 각 숫자를 처음으로 곱하면됩니다.

아니면 예를 들어, 쌍 곱 수 있습니다 : 이것은 배열을 통해 두 가지 요소를 추가, 모드 연산자를 사용하여 수행 할 수 1 * 2, 2 * 3, 3 * 1 .

도우 코드 :

for i = 0 to array.length print array[i] * array [i+1 % array.length]