Egyptian Fraction Problem
Ancient Egyptians represented each positive fraction as the sum of unique unit fractions. For example, 7/15 = 1/3 + 1/8 + 1/120
, or 2/3 = 1/2 + 1/6
, or 1/7 = 1/7
.
So, your goal is to find such a representation for the number n/m
, m, n>0.
That can be reached by using the Greedy Approach. Each time, try to “bite” the number as big as possible to reduce the current value. Let’s look at the 7/15
:
-
N = 7/15 >= 1/3 – this is the maximum unit fraction we can reach, add it to the answer.
-
Now, update the number we’re solving problem for: N = 7/15 – 1/3 = 2/15.
-
N = 2/15 >= 1/8 – next maximum unit fraction, add to the answer.
-
Update N: N = 2/15 – 1/8 = 1/120.
-
N = 1/120 >= 1/120 - add to the answer.
-
Update N = 0 -> stop the algorithm.
So, to sum up:
-
Check if the current N == 0. If it is, stop the algorithm.
-
Find the biggest unit fraction less than N and add it to the ans
-
Update value of N by reducing.
The answer is an array f
of numbers f[0], f[1], ... , f[t]
, where f[i]
is a divider for fraction 1/f[i]
. For our example, answer is [3, 8, 120]
.
How to find the biggest possible unit fraction It can be easily done for
N = n/m
by calculatingk = math.ceil(m/n)
. Greater values ofk
do not give the maximum unit fraction (since, for example,1/k > 1/(k+1)
).
Swipe to start coding
Add some code to the function and test it.
Merci pour vos commentaires !
single
Demandez à l'IA
Demandez à l'IA
Posez n'importe quelle question ou essayez l'une des questions suggérées pour commencer notre discussion
Résumer ce chapitre
Expliquer le code dans file
Expliquer pourquoi file ne résout pas la tâche
Awesome!
Completion rate improved to 7.69
Egyptian Fraction Problem
Glissez pour afficher le menu
Ancient Egyptians represented each positive fraction as the sum of unique unit fractions. For example, 7/15 = 1/3 + 1/8 + 1/120
, or 2/3 = 1/2 + 1/6
, or 1/7 = 1/7
.
So, your goal is to find such a representation for the number n/m
, m, n>0.
That can be reached by using the Greedy Approach. Each time, try to “bite” the number as big as possible to reduce the current value. Let’s look at the 7/15
:
-
N = 7/15 >= 1/3 – this is the maximum unit fraction we can reach, add it to the answer.
-
Now, update the number we’re solving problem for: N = 7/15 – 1/3 = 2/15.
-
N = 2/15 >= 1/8 – next maximum unit fraction, add to the answer.
-
Update N: N = 2/15 – 1/8 = 1/120.
-
N = 1/120 >= 1/120 - add to the answer.
-
Update N = 0 -> stop the algorithm.
So, to sum up:
-
Check if the current N == 0. If it is, stop the algorithm.
-
Find the biggest unit fraction less than N and add it to the ans
-
Update value of N by reducing.
The answer is an array f
of numbers f[0], f[1], ... , f[t]
, where f[i]
is a divider for fraction 1/f[i]
. For our example, answer is [3, 8, 120]
.
How to find the biggest possible unit fraction It can be easily done for
N = n/m
by calculatingk = math.ceil(m/n)
. Greater values ofk
do not give the maximum unit fraction (since, for example,1/k > 1/(k+1)
).
Swipe to start coding
Add some code to the function and test it.
Merci pour vos commentaires !
Awesome!
Completion rate improved to 7.69single