{"id":5235,"date":"2022-03-08T00:01:16","date_gmt":"2022-03-08T08:01:16","guid":{"rendered":"https:\/\/c-for-dummies.com\/blog\/?p=5235"},"modified":"2022-03-05T08:47:35","modified_gmt":"2022-03-05T16:47:35","slug":"simplifying-fractions-solution","status":"publish","type":"post","link":"https:\/\/c-for-dummies.com\/blog\/?p=5235","title":{"rendered":"Simplifying Fractions – Solution"},"content":{"rendered":"

This month’s Exercise<\/a> both terrified and enticed me. Yes, I code these solutions myself after I think up the challenges. No cheating here! This particular puzzle was more fun than I imagined, but also required a lot of mental work.
\n
\nThe first thing I did was to look up the three steps to simplify a fraction: Discover the common factors, obtain the greatest common denominator (GCD), and then divide the numerator and denominator by the GCD. This approach required a lot of code.<\/p>\n

Here is the main()<\/em> function from my first solution, which you can find on Github<\/a>:<\/p>\n

\r\nint main()\r\n{\r\n    const int size = 7;\r\n    int numerator[size] = { 28, 13, 14, 1, 9, 276, 4 };\r\n    int denominator[size] = { 42, 52, 91, 50, 15, 23, 100 };\r\n    int numerator_factors[BUFFER_LIMIT];\r\n    int denominator_factors[BUFFER_LIMIT];\r\n    int x,m;\r\n\r\n    for( x=0; x<size; x++ )\r\n    {\r\n        \/* output the original fraction *\/<\/span>\r\n        printf(\"%d\/%d \",numerator[x],denominator[x]);\r\n\r\n        \/* obtain factors for the numerator and denominator *\/<\/span>\r\n        factors(numerator_factors,numerator[x]);\r\n        factors(denominator_factors,denominator[x]);\r\n\r\n        \/* obtain the maximum common factor *\/<\/span>\r\n        m = maxfactor(numerator_factors,denominator_factors);\r\n\r\n        if( m )\r\n        {\r\n            \/* reduce the fraction *\/<\/span>\r\n            printf(\"is simplified to %d\/%d\\n\",\r\n                    numerator[x]\/m,\r\n                    denominator[x]\/m\r\n                  );\r\n        }\r\n        else\r\n        {\r\n            \/* the fraction cannot be reduced *\/<\/span>\r\n            puts(\"cannot be simplified\");\r\n        }\r\n    }\r\n\r\n    return(0);\r\n}<\/pre>\n
The defined constant BUFFER_LIMIT<\/code> equals 100, which is a guess of how many factors are possible for a given value. This is the kludgiest part of this solution; a number could have more factors than 100, but I didn’t want to manipulate a dynamic array to store them.<\/p>\n
A for<\/em> loop processes each of the fractions, which are output as was done in the skeleton code. Within the loop, the factors()<\/em> function obtains the factors for numerator[x]<\/code> and denominator[x]<\/code>. The results are stored in the numerator_factors[]<\/code> and denominator_factors[]<\/code> arrays. See this Lesson<\/a> for more details on finding factors.<\/p>\n
The maxfactor()<\/em> (heh) function returns the maximum shared factor value between the two arrays, numerator_factors[]<\/code> and denominator_factors[]<\/code>. I use a bubble sort to compare the values and find the maximum, which is returned in variable m<\/code>.<\/p>\n
If variable m<\/code> isn’t zero, its value divides both numerator[x]<\/code> and denominator[x]<\/code> to output the simplified fraction. Otherwise, the fraction cannot be simplified.<\/p>\n
Here’s a sample run:<\/p>\n
28\/42 is simplified to 2\/3
\n13\/52 is simplified to 1\/4
\n14\/91 is simplified to 2\/13
\n1\/50 cannot be simplified
\n9\/15 is simplified to 3\/5
\n276\/23 is simplified to 12\/1
\n4\/100 is simplified to 1\/25<\/code><\/p>\n
My second solution uses Euclid’s algorithm to reduce the numerator and denominator values by their differences. The algorithm is quite clever, and I need not repeat the details or fancy graphics from the Wikipedia page<\/a>. Here is the entirety of my second solution:<\/p>\n
2022_03-Exercise-b.c<\/a><\/h3>\n
\r\n#include <stdio.h>\r\n#include <stdlib.h>\r\n\r\nint main()\r\n{\r\n    const int size = 7;\r\n    int numerator[size] = { 28, 13, 14, 1, 9, 276, 4 };\r\n    int denominator[size] = { 42, 52, 91, 50, 15, 23, 100 };\r\n    int x,diff,larger,smaller;\r\n\r\n    for( x=0; x<size; x++ )\r\n    {\r\n        \/* output the original fraction *\/<\/span>\r\n        printf(\"%d\/%d \",numerator[x],denominator[x]);\r\n\r\n        \/* calculate differences between the larger and smaller values *\/<\/span>\r\n        larger = numerator[x]>denominator[x] ? numerator[x] : denominator[x];\r\n        smaller = numerator[x]<denominator[x] ? numerator[x] : denominator[x];\r\n        diff = larger-smaller;\r\n        \/* keep calculating until the common denominator is found *\/<\/span>\r\n        while( diff!=larger )\r\n        {\r\n            larger = smaller>diff ? smaller : diff;\r\n            smaller = smaller==larger ? diff : smaller;\r\n            diff = larger-smaller;\r\n        }\r\n\r\n        \/* if the difference is more than 1, the fraction can be reduced *\/<\/span>\r\n        if( diff>1 )\r\n        {\r\n            printf(\"is simplified to %d\/%d\\n\",\r\n                    numerator[x]\/diff,\r\n                    denominator[x]\/diff\r\n                  );\r\n        }\r\n        else\r\n        {\r\n            \/* the fraction cannot be reduced *\/<\/span>\r\n            puts(\"cannot be simplified\");\r\n        }\r\n    }\r\n\r\n    return(0);\r\n}<\/pre>\n
Not being Euclid, I would have never thought of this approach. Yet it works beautifully: The algorithm starts at Lines 17 through 19, then repeats in a while<\/em> loop until the GCD is found. The output is the same, but I admire this code far better than my first, plodding solution.<\/p>\n
Whether you tried one solution or both, I hope you met with success. And I further hope I never have to type the word denominator<\/em> so many times again in my life.<\/p>\n","protected":false},"excerpt":{"rendered":"
This month’s Exercise both terrified and enticed me. Yes, I code these solutions myself after I think up the challenges. No cheating here! This particular puzzle was more fun than I imagined, but also required a lot of mental work.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5],"tags":[],"class_list":["post-5235","post","type-post","status-publish","format-standard","hentry","category-solution"],"_links":{"self":[{"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/5235","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=5235"}],"version-history":[{"count":5,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/5235\/revisions"}],"predecessor-version":[{"id":5251,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/5235\/revisions\/5251"}],"wp:attachment":[{"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=5235"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=5235"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=5235"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}