假設這個function的prototype為int GCD(int a, int b)，a和b是輸入的兩個正整數，而我們在這個function要回傳的是a和b的GCD。
最簡單的想法就是，我們直接 ...
Skiptocontent
HomeGreatestcommondivisor(GCD)in C++
求最大公因數(Greatestcommondivisor(GCD))是面試常考的問題之一，打字猴面試時也遇過幾次，最近有空把這個常考的問題好好地整理一下。
假設這個function的prototype為intGCD(inta,intb)，a和b是輸入的兩個正整數，而我們在這個function要回傳的是a和b的GCD。
最簡單的想法就是，我們直接從1開始一路找到min(a,b)，最大的可以整除a和b的即為所求，所以第一版的程式將會是：
#include
#include
namespace
{
intGCD(inta,intb){
intd=1;
for(inti=2;i<=std::min(a,b);++i) {
if(0==a%i&&0==b%i){
d=i;
}
}
returnd;
}
}
TEST(TestGCD_1,TestAll){
EXPECT_EQ(5,GCD(10,15));
EXPECT_EQ(5,GCD(15,10));
EXPECT_EQ(1,GCD(3,5));
EXPECT_EQ(5,GCD(5,15));
EXPECT_EQ(6,GCD(18,24));
}
我們將透過GoogleUnitTestFramework來幫我們驗證這個GCD的正確性。
GoogleUnitTestFramework的相關教學請參考其他文章。
另外值得一提的就是，我們透過unnamednamespace來幫我們限制該GCDfunction的scope，因為我們將會在其他的.cppfiles中改良這個GCDfunction。
第一版的程式有個缺點，因為它會一路從1enumerate到min(a,b)，但實際上我們找的是最大公因數，如果從min(a,b)開始往下找，找到第一個可以整除a和b的數即可停止。
所以我們可以做一個改良，還可以省下一個變數的空間。
#include
#include
namespace
{
intGCD(inta,intb){
intd=std::min(a,b);
for(;d>1;--d){
if(0==a%d&&0==b%d){
returnd;
}
}
return1;
}
}
TEST(TestGCD_2,TestAll){
EXPECT_EQ(5,GCD(10,15));
EXPECT_EQ(5,GCD(15,10));
EXPECT_EQ(1,GCD(3,5));
EXPECT_EQ(5,GCD(5,15));
EXPECT_EQ(6,GCD(18,24));
}
如果你還記得小學時候學的輾轉相除法的話(GCD(a,b)==GCD(b,r)，其中r為a除b的餘數)，我們就不需要把每個小於min(a,b)的數做enumerate。
輾轉相除法的最直覺的寫法是遞迴的版本，所以我們把上面的程式改為下面第三版的程式：
#include
namespace
{
intGCD(inta,intb){
if(a
namespace
{
intGCD(inta,intb){
if(a%b==0){
returnb;
}else{
returnGCD(b,a%b);
}
}
}
TEST(TestGCD_4,TestAll)
{
EXPECT_EQ(5,GCD(10,15));
EXPECT_EQ(5,GCD(15,10));
EXPECT_EQ(1,GCD(3,5));
EXPECT_EQ(5,GCD(5,15));
EXPECT_EQ(6,GCD(18,24));
}
為什麼在第四版程式中，我們可以不必加這一個(a
namespace
{
intGCD(inta,intb){
return(b==0)?a:GCD(b,a%b);
}
}
TEST(TestGCD_5,TestAll)
{
EXPECT_EQ(5,GCD(10,15));
EXPECT_EQ(5,GCD(15,10));
EXPECT_EQ(1,GCD(3,5));
EXPECT_EQ(5,GCD(5,15));
EXPECT_EQ(6,GCD(18,24));
}
第五版的程式，GCDfunction一行搞定，真是太酷了。
最後呢，因為遞迴有損效能，打字猴待過的部門有些codingstandard會規定禁止寫遞迴，所以就提供了一個非遞迴版本的GCD給大家：
#include
namespace
{
intGCD(inta,intb){
while(b>0){
intr=a%b;
a=b;
b=r;
}
returna;
}
}
TEST(TestGCD_6TestAll)
{
EXPECT_EQ(5,GCD(10,15));
EXPECT_EQ(5,GCD(15,10));
EXPECT_EQ(1,GCD(3,5));
EXPECT_EQ(5,GCD(5,15));
EXPECT_EQ(6,GCD(18,24));
}
Sharethis:TwitterFacebookLikethis:LikeLoading...
Related
Postnavigation
←DeclarationandDefinitionin C++ HelloSQLiteCommandLine Shell→
LeaveaReplyCancelreply
Enteryourcommenthere...
Fillinyourdetailsbeloworclickanicontologin:
Email(required)(Addressnevermadepublic)
Name(required)
Website
YouarecommentingusingyourWordPress.comaccount.
( Log Out /
Change )
YouarecommentingusingyourGoogleaccount.
( Log Out /
Change )
YouarecommentingusingyourTwitteraccount.
( Log Out /
Change )
YouarecommentingusingyourFacebookaccount.
( Log Out /
Change )
Cancel
Connectingto%s
Notifymeofnewcommentsviaemail.Notifymeofnewpostsviaemail.
Δ
Searchfor:
RecentPosts
Helloactivator
Add3rdpartylibrarytoascalaprojectwith sbt
Buildascalaprojectwith sbt
BuildJavaProjectswith ANT
Buildajavaprojectwith3rdparty.jarusingcommand line
RecentComments
什麼是UnitTest|打字猴onProsandConsofUnit Tes…什麼是UnitTest|打字猴on為什麼要做UnitTestUnitTestOverview|…on在VS2008Express中使用GoogleUnit…UnitTestOverview|…onGoogleUnitTest Framewor…UnitTestOverview|…on為什麼要做UnitTest
Archives
April2017 (1)
February2017 (2)
December2016 (4)
November2016 (12)
October2016 (18)
September2016 (9)
July2016 (1)
June2016 (11)
May2016 (3)
April2016 (12)
March2016 (1)
February2016 (8)
January2016 (7)
December2015 (6)
November2015 (6)
October2015 (1)
August2015 (10)
June2015 (1)
May2015 (7)
April2015 (13)
March2015 (8)
October2014 (1)
September2014 (2)
August2014 (18)
BlogStats
131,305hits
TagsAlgorithm
ASP.NET
Automation
C#
C++11
cppcheck
cpplint
C\C++
database
DesignPattern
executionplan
GoogleC++StyleGuide
GoogleUnitTestFramework
Java
Javascript
Jenkins
MongoDB
NoSQL
NuGet
opensource
php
Scala
Softwaredistribution
sqlite
staticcodeanalysistool
T-SQL
UnitTest
UniversalPrinciplesofDesign
WebApplicationTopPosts&Pages
在C++中取得Array的長度
InitializeanarrayinC\C++
tupleinC++11
BinarySearchinC++
Greatestcommondivisor(GCD)inC++
ConvertrowstocolumnsinT-SQL
DeclarationandDefinitioninC++
std::arrayinC++11
ifanumberisprimeinC++
SOAPWebService
Privacy&Cookies:Thissiteusescookies.Bycontinuingtousethiswebsite,youagreetotheiruse.
Tofindoutmore,includinghowtocontrolcookies,seehere:
CookiePolicy
Follow
Following
打字猴
Signmeup
AlreadyhaveaWordPress.comaccount?Loginnow.
打字猴
Customize
Follow
Following
Signup
Login
Copyshortlink
Reportthiscontent
ViewpostinReader
Managesubscriptions
Collapsethisbar
%dbloggerslikethis:
