# Difference between revisions of "Greedy Algorithm"

(Created page with "A Greedy Algorithm is one that always chooses the best immediate option. The advantage is that it usually makes decisions simpler, but it may create problems in the long run. It ...") |
Sweetmango77 (talk | contribs) |
||

Line 1: | Line 1: | ||

A Greedy Algorithm is one that always chooses the best immediate option. The advantage is that it usually makes decisions simpler, but it may create problems in the long run. It is useful for making programs that don't take long to run. Do not use it in your everyday life. | A Greedy Algorithm is one that always chooses the best immediate option. The advantage is that it usually makes decisions simpler, but it may create problems in the long run. It is useful for making programs that don't take long to run. Do not use it in your everyday life. | ||

+ | |||

+ | ===How to use=== | ||

+ | If you're solving a math problem, and it involves something similar or the same as egyptian fractions, | ||

+ | Step 1: Find the largest fraction with a denominator of a positive integer. | ||

+ | Step 2: Subtract the number you got from (1) from the original fraction. | ||

+ | Step 3: Repeat until you get a fraction with numerator 1. | ||

+ | |||

+ | ==Example== | ||

+ | ===Problem=== | ||

+ | If <math>a</math>, <math>b</math>, and <math>c</math> are positive integers, and <math>\frac1a+\frac1b+\frac1c=\frac67</math>, what is <math>a+b+c</math>? | ||

+ | ===Solution using the Greedy Algorithm=== | ||

+ | Let <math>a\leq b\leq c</math>. Obviously, as the denominator decreases, the fraction increases. Therefore, <math>\frac1a\geq\frac1b\geq\frac1c</math>. The least possible value of <math>a</math> is <math>2</math>. Then, <math>\frac67-\frac12=\frac{5}{14}</math>. Again, we find the least possible value of <math>b</math>, which is <math>3</math>. We subtract to get <math>\frac1{42}</math>. Therefore, <math>c=42</math>. Our answer is then <math>2+3+42=\boxed{\textbf{47}}</math>. | ||

==See Also== | ==See Also== | ||

− | [ | + | [https://en.wikipedia.org/wiki/Greedy_algorithm Wikipedia: Greedy Algorithm] |

## Revision as of 01:18, 23 January 2021

A Greedy Algorithm is one that always chooses the best immediate option. The advantage is that it usually makes decisions simpler, but it may create problems in the long run. It is useful for making programs that don't take long to run. Do not use it in your everyday life.

### How to use

If you're solving a math problem, and it involves something similar or the same as egyptian fractions, Step 1: Find the largest fraction with a denominator of a positive integer. Step 2: Subtract the number you got from (1) from the original fraction. Step 3: Repeat until you get a fraction with numerator 1.

## Example

### Problem

If , , and are positive integers, and , what is ?

### Solution using the Greedy Algorithm

Let . Obviously, as the denominator decreases, the fraction increases. Therefore, . The least possible value of is . Then, . Again, we find the least possible value of , which is . We subtract to get . Therefore, . Our answer is then .