피보나치의 알고리즘을 사용한 이집트 분수

Question

피보나치의 알고리즘을 사용하여 이집트의 분수를 찾으려고하는이 문제가 있습니다. 분자의 경우 항상 1과 같아야합니다. 그런 다음 바닥이 실용적인 숫자인지 확인해야합니다.

우리는 이미 유리수의 바닥 번호가 실제 번호가 있는지 여부를 확인하는 방법을 발견했다

(즉 양수 여야합니다) 그들이 우리에게 번호를 제공하는 사용자로부터 입력 2가 .. (위대한 모범적 인 예 : Practical Number) 그러나 나는 이집트 분수로 그것을 변환하는 방법에 길을 잃었다.

지침에 따르면 프랙 터 목록을 기반으로 가장 큰 부분을 찾아야한다고 나와 있습니다. 예 : 합리적인 숫자가 5/8 인 경우 8의 인수는 [1,2,4]입니다. 이것에서 뺄 수있는 가장 큰 부분은 1/2입니다.

나는이 변환으로 어디서부터 시작해야할지조차 모른다. 난 그냥 사용자 입력에서 두 번째 숫자는 실제 번호가있는 경우, 내가 동등한 이집트 비율을 계산해야한다는 것을 알고 ..

이에와 비슷하게 실행해야 출력 :

이

Num1 : 7 
Num 2: 8 
Denomiator factors: [1,2,4,8] 
Num 2 is a practical number. 
Fraction can be represented by: 
1/2 + 1/4 + 1/8 

모든 시작 도움이 될 것 고맙습니다. 나는 진실로 개념을 이해하고 그것이 무엇을 요구하는지 - 나는 단지 어디서부터 시작해야 할까? 예제 코드는 큰 도움이 될 것입니다.

Answer 1

좋아요 ... 예 7/8을 사용하여 방금 말씀하신 내용을 반향시킵니다.

1. 시작 부분의 두 부분으로 : numer에 = 7 denom = 8
2. 은 denom 실용적인 수 있는지 결정하고; 이것은 그 요인을 되 돌리는 것을 포함한다 [1, 2, 4, 8].
3. 순서대로 요인을 정렬하십시오. 분수가 항상 1 미만이라고 보장되면 요소를 삭제할 수 있습니다.
4. 한 번에 한 요소 씩 목록을 반복하여 이집트 분수 조항을 작성하십시오.

의사 코드 : StackOverflow의에

for factor in factor_list: 
    weight = denom/factor 
    while weight < numer: 
     # Add the fraction 1/factor to the solution; 
     # reduce numer by weight (subtracting that fraction) 
# When you exit these loops, 
# numer should be 0, and 
#  you should have accumulated all of 
#  the "1/factor" fractions in your solution.