C語言求最大公約數和最小公倍數
C語言求最大公約數和最小公倍數,下面一起來看看吧。
操作方法
(01)思路:這是一個很基本的問題,最常見的就是兩種方法,輾轉相除法和輾轉相減法。通式分別爲 f(x, y) = f(y, x%y), f(x, y) = f(y, x - y) (x >=y > 0)。根據通式寫出算法不難,這裏就不給出了。這裏給出《編程之美》上的算法,主要是爲了減少迭代的次數。 對於x和y,如果y = k * y1, x= k * x1,那麼f(x, y) = k * f(x1, y1)。另外,如果x = p * x1,假設p爲素數,並且y % p != 0,那麼f(x, y) = f(p * x1, y) = f(x1, y)。取p = 2。
(02)//函數功能: 求最大公約數 //函數參數: x,y爲兩個數 //返回值: 最大公約數 int gcd_solution1(int x, int y) { if(y == 0) return x; else if(x < y) return gcd_solution1(y, x); else { if(x&1) //x是奇數 { if(y&1) //y是奇數 return gcd_solution1(y, x-y); else //y是偶數 return gcd_solution1(x, y>>1); } else //x是偶數 { if(y&1) //y是奇數 return gcd_solution1(x>>1, y); else //y是偶數 return gcd_solution1(x>>1, y>>1) << 1; } } }
(03)求最小公倍數:最常用的是輾轉相除法,有兩整數a和b:① a%b得餘數c② 若c=0,則b即爲兩數的最大公約數③ 若c≠0,則a=b,b=c,再回去執行①
(04)int gcd_solution2(int x, int y) { int result = 1; while(y) { int t = x; if(x&1) { if(y&1) { x = y; y = t % y; } else y >>= 1; } else { if(y&1) x >>= 1; else { x >>= 1; y >>= 1; result <<= 1; } } } return result * x; }
-
世界十大催眠曲:第一公認最有效,第四至今沒有人聽完
導語:催眠曲就是透過音樂來幫助被催眠者進入睡眠的狀態,對於無法入睡的人能起到很好的治療作用,其中著名的世界十大催眠曲則分別是哥德堡變奏曲,weightless,Sleepsong,Dream13,玄祕曲,搖籃曲,月光曲,α腦波音樂,帕赫貝爾的卡農,佛經,下面就跟着探祕志小編一起來看看吧!哥...
-
世界價格最貴的貓:阿什拉貓17萬一只(身高1.2米混血貓)
導語:貓咪是十分惹人喜愛的動物,很多人都對這種動物十分喜愛。關於世界最大的貓,世界最小的貓大家都有所瞭解,那麼世界最貴的貓大家知道嗎?世界上最貴的貓是17萬一只的阿什拉貓,下面和探祕志小編一起來了解一下吧。世界價格最貴的貓:阿什拉貓阿什拉貓是世界上價格最...
-
一個比特幣值多少人民幣?2019突破55285元(最高137177元)
導語:比特幣是一種加密的虛擬數字貨幣,在2017年12月17日曾達到歷史最高價19850美元,但是在2017年9月4日,央行表示禁止虛擬貨幣的交易,並且比特幣在中國是沒有法律上的貨幣地位,不過據國外報價表明,在2019年5月14日,比特幣的價格已經再創新高,突破了8000美元,也就是人民幣...
-
大學裏學分有什麼用
(01)大學裏學分是學生取得學位和畢業證書的重要條件之一。學分是衡量學生學習量和完成學業程度的單位。一個學生要想獲得某個學位,必須先達到該學位所規定的學分要求。學分的作用包括:1.衡量學習量:學分是衡量學生學習量的單位,每個學分對應一定的學習量。(02)學生透過...