이집트 알고리즘 구현하기

Question

덧셈, 뺄셈 및 비교 만 사용하여 자바에서 두 숫자의 곱셈을 재귀 적으로 찾고 싶습니다. 그래서, 나는 봤는데 나는 질문 요구 사항을 충족 Egyptian Algorithm을 발견.

그러나 base case에 도달 한 후에 곱셈 결과를 찾는 방법을 모르겠습니다.

예 :

13 x 30 

1 -- 30 

2 -- 60 

4 -- 120 

8 -- 240 //we stop here because the double of 8 is larger than 13 

우리는 그들이 어떤 30+120+240 = 390을있는 우리가 right column로부터 반대 번호를 추가 반면 그들이 1+4+8 있습니다 (13)과 동일 left column에서와에 번호를 추가 한 결과를 찾으려면 결과.

하지만 이제 프로그래밍 방식으로 마지막 부분을 수행하는 방법은 무엇입니까? 추가 할 숫자를 확인하는 방법은 무엇입니까? 너희들이 내 말을 듣기를 바란다. 힌트는 필요합니다.

Answer 1

좋아, 나는 Brute Force Algorithm을 사용했다. 그것은 BigO- (n)입니다. 나는 그것을 구현하는보다 효율적인 방법이있을 것이라고 확신한다. 지금은. 나는 이것으로 정착하고있다.

고마워요!

Answer 2

때마다, (당신의 multiplicant에 동일한 시작) 당신의 multiplicant 나머지는 왼쪽 열의 수보다 큰 경우에서 왼쪽 열을 빼기 역순으로 생성 된 결과 을 통해 루프를 수행 승수를 곱하고 결과에 오른쪽 열을 추가합니다 (0부터 시작).

Answer 3

이 위키 백과를 발견했을 수 있습니다. article.

"분해"섹션의 마지막 부분을 살펴보십시오. 구현해야하는 하위 알고리즘을 찾을 수 있습니다.

Answer 4

여기서 문제를 해결하기 위해 의사의 대신이 끝날 때까지 기다리는 기본적

function egyptian(left, right) 
    prod := 0 
    while (left > 0) 
    if (left is odd) 
     prod := prod + right 
    left := halve(left) 
    right := double(right) 
    return prod 

을는 그것이 생성 될 때 주형의 각 행을 선택하고 그 출력에 속하는 경우 합계 쉽다. 나는이 알고리즘을 my blog에서 논의한다.