Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

About the Egyptian fraction:How to prove that the greedy algorithm is right/wrong?

Правка en1, от HiCode2009, 2022-11-11 15:58:50

As we know,each fraction can be expressed as the sum of multiple unit fractions.

$$$\frac{p}{q}=\frac{1}{a_1}+\frac{1}{a_2}+...+\frac{1}{a_n}$$$

When we want to express a fraction as the sum of multiple unit fractions,we can use a greedy algorithm invented by Fibonacci,subtract the maximum unit fraction which is smaller than this fraction from this fraction.For example,$$$\frac{13}{14}=\frac{1}{2}+\frac{1}{3}+\frac{1}{11}+\frac{1}{231}$$$.

But when we want to find out the minimum value of $$$n$$$,things may be different.Can Fibonacci's greedy algorithm still work?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский HiCode2009 2022-11-11 15:58:50 649 Initial revision (published)