Added article on Euclid's algorithm #129
Conversation
added new line to correct formatting of main page.
# Conflicts: # src/index.md
Intial version.
Updated formatting, grammar etc.
Copied images from emaxx.ru
Updated image links to root
Added basic problem and updated link in index.
|
@RodionGork @tcNickolas Is there any issue/change required? Why is this not being merged? |
|
Sorry for the delay, but this project has only two maintainers, who are both busy people and struggle to carve out some time for reviews. I'm reviewing it now |
|
|
||
| Given two non-negative integers $a$ and $b$, we require the greater common divisor i.e. the largest number which is a divisor of $a$ and $b$ simultaneously. It's common denoted by $gcd$. | ||
|
|
||
|  |
There was a problem hiding this comment.
Please use formulas instead of images.
| ```cpp | ||
| int gcd (int a, int b) { | ||
| while (b) { | ||
| a %= b; |
There was a problem hiding this comment.
Please fix indentation on lines 47 and 48
|
|
||
| For the proof of correctness, we need to show $gcd(a, b) = gcd(b, a\mod b)$ for all $a \geq 0$, $b > 0$. | ||
|
|
||
| We will show that the quantity on the left side of the equation, can be written as the value on the left. Obviously, this would mean that the left and right sides are the same and prove Euclid's algorithm. |
There was a problem hiding this comment.
In the original text, the proof shows that the expression of the left side of the equation divides the expression on the right side and vise versa. Let's keep this meaning.
|
|
||
| - Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein. Algorithms: Construction and analysis [2005] | ||
|
|
||
| ## Problems |
There was a problem hiding this comment.
Please use the same format as other articles "## Practice Problems"
|
|
||
| - [GCD and LCM[easy]](https://www.codechef.com/problems/FLOW016) | ||
|
|
||
| ####Note: Translated by [NibNalin](http://codeforces.com/profile/NibNalin) |
There was a problem hiding this comment.
Per https://e-maxx-eng.appspot.com/contrib.html, we've agreed to track authorship of pages not with sole author but using Github edits history. Let's remove this line. You can add link to your CF profile in your Github profile if you want to preserve your CF persona.
|
@tcNickolas Please review. I have corrected whatever you requested. Let me know in case of anything else. I have tried to not let errors creep in this time. :) |
|
Thanks for finishing this pull request! Nice work on the formulas :-) |
I have translated and added the article on Euclid's algorithm. There are a number of images which have been put in the
imgdirectory as well. A link to a straightforward GCD and LCM calculation problem has been added at bottom. The page has also been added to the index. Let me know if any more work is needed :)