国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

五種最大公約數Python求解總結

89542767 / 652人閱讀


  小編寫這篇文章的主要目的,主要是給大家講解一下,關于最大公約數的求解方法,下面小編集中給大家總結一下,具體操作的五種方法。


  方法一:短除法


  短除法是求最大公因數的一種方法,也可用來求最小公倍數。求幾個數最大公因數的方法,開始時用觀察比較的方法,即:先把每個數的因數找出來,然后再找出公因數,最后在公因數中找出最大公因數。后來,使用分解質因數法來分別分解兩個數的因數,再進行運算。之后又演變為短除法。短除法運算方法是先用一個除數除以能被它除盡的一個質數,以此類推,除到兩個數的商是互質數為止。


  簡單來說就是逐步找出兩個數的所有公約數,再將這些公約數累乘起來,就能得到最大公約數啦!


  a=int(input("please input the first number:"))
  b=int(input("please input the second number:"))
  m,n=a,b#創建兩個變量存儲a和b
  t=1#創建t作為最大公約數的載體
  for i in range(2,min(a,b)):
  while(a%i==0 and b%i==0):
  t*=i#所有公約數累乘起來
  a/=i
  b/=i
  print((f"{m},{n}的最大公約數為:{t}"))


  這種方法雖然有點麻煩,但是邏輯卻很清楚,不容易出錯。


  方法二:歐幾里得算法(輾轉相除法)


  歐幾里得算法是用來求兩個正整數最大公約數的算法。古希臘數學家歐幾里得在其著作《The Elements》中最早描述了這種算法,所以被命名為歐幾里得算法。


  假如需要求1997和615兩個正整數的最大公約數,用歐幾里得算法,是這樣進行的:


  1997/615=3······152


  615/152=4······7


  152/7=21······5


  7/5=1······2


  5/2=2······1


  2/1=2······0


  至此,最大公約數為1


  以除數和余數反復做除法運算,當余數為0時,取當前算式除數為最大公約數,所以就得出了1997和615的最大公約數1。


  明白了這其中的邏輯,我們就可以著手開始寫程序啦!


  a=int(input("please input the first number:"))
  b=int(input("please input the second number:"))
  #首先要給兩數排序,保證大數除以小數
  m=max(a,b)
  n=min(a,b)
  t=m%n
  while t!=0:
  m,n=n,t#仔細觀察不難發現:每個除式的m、n是都是上一個式子的n和余數
  t=m%n#更新余數
  print(f"{a}和{b}的最大公約數為{n}")


  當然了,遞歸方法也能實現歐幾里得算法。


   def GCD(a,b):
  #比較大小,保證大數除以小數
  if a<b:
  a,b=b,a
  #判斷是否能整除,若能整除,直接返回被除數
  if a%b==0:
  return b
  #若不能整除,則返回函數GCD,參數做相應變化
  else:
  return GCD(b,a%b)
  a=int(input("please input the first number:"))
  b=int(input("please input the second number:"))
  gcd=GCD(a,b)
  print(f"{a}和{b}的最大公約數為{gcd}")


  方法三:更相減損術


  更相減損術是出自《九章算術》的一種求最大公約數的算法,它原本是為約分而設計的,但它適用于任何需要求最大公約數的場合。原文是:


  可半者半之,不可半者,副置分母、子之數,以少減多,更相減損,求其等也。以等數約之。


  白話文譯文:


  (如果需要對分數進行約分,那么)可以折半的話,就折半(也就是用2來約分)。如果不可以折半的話,那么就比較分母和分子的大小,用大數減去小數,互相減來減去,一直到減數與差相等為止,用這個相等的數字來約分。


  具體步驟:


  第一步:任意給定兩個正整數;判斷它們是否都是偶數。若是,則用2約簡;若不是則執行第二步。


  第二步:以較大的數減較小的數,接著把所得的差與較小的數比較,并以大數減小數。繼續這個操作,直到所得的減數和差相等為止。


  則第一步中約掉的若干個2的積與第二步中等數的乘積就是所求的最大公約數。


  其中所說的“等數”,就是公約數。求“等數”的辦法是“更相減損”法。


  現在使用更相減損術求98與63的最大公約數。


  解:由于63不是偶數,把98和63以大數減小數,并輾轉相減:


  98-63=35


  63-35=28


  35-28=7


  28-7=21


  21-7=14


  14-7=7


  所以,98和63的最大公約數等于7。


  a=int(input("please input the first number:"))
  b=int(input("please input the second number:"))
  #首先要給兩數排序,保證大數減小數
  m=max(a,b)
  n=min(a,b)
  #判斷兩數是否都是偶數,如果都是偶數就同時除2
  while m%2==0 and n%2==0:
  m,n=m/2,n/2
  t=m-n
  #判斷條件是減數和差相等
  while n!=t:
  m,n=max(n,t),min(n,t)#每減一輪之后,都要重新判斷減數和差的大小,再次以大數減去小數
  t=m-n
  print(f"{a}和{b}的最大公約數為{n}")


  方法四:窮舉法(枚舉法)


  從兩個數中較小數開始,由小到大列舉,找出公約數并保證該公約數也屬于較大數,這些公約數的最大者就是最大公約數;也可以從大到小列舉,直到找出公約數后跳出循環,該公約數即是最大公約數。


  a=int(input("please input the first number:"))
  b=int(input("please input the second number:"))
  p,q=min(a,b),max(a,b)
  lst=[]
  for i in range(1,p+1):
  if p%i==0 and q%i==0:
  lst.append(i)
  gcd=max(lst)
  print(f"{a}和{b}的最大公約數為{gcd}")
  #a=int(input("please input the first number:"))
  #b=int(input("please input the second number:"))
  #p,q=min(a,b),max(a,b)
  #gcd=0
  #for i in range(p,0,-1):
  #if p%i==0 and q%i==0:
  #gcd=i
  #break
  #print(f"{a}和{b}的最大公約數為{gcd}")

  方法五:Stein算法


  Stein算法是一種計算兩個數最大公約數的算法,是針對歐幾里德算法在對大整數進行運算時,需要試商導致增加運算時間的缺陷而提出的改進算法。


  歐幾里得算法缺陷:


  歐幾里德算法是計算兩個數最大公約數的傳統算法,無論從理論還是從實際效率上都是很好的。但是卻有一個致命的缺陷,這個缺陷在素數比較小的時候一般是感覺不到的,只有在大素數時才會顯現出來。


  一般實際應用中的整數很少會超過64位(當然已經允許128位了),對于這樣的整數,計算兩個數之間的模是很簡單的。對于字長為32位的平臺,計算兩個不超過32位的整數的模,只需要一個指令周期,而計算64位以下的整數模,也不過幾個周期而已。但是對于更大的素數,這樣的計算過程就不得不由用戶來設計,為了計算兩個超過64位的整數的模,用戶也許不得不采用類似于多位數除法手算過程中的試商法,這個過程不但復雜,而且消耗了很多CPU時間。對于現代密碼算法,要求計算128位以上的素數的情況比比皆是,設計這樣的程序迫切希望能夠拋棄除法和取模。


  看下面兩個結論:


  gcd(a,a)=a,也就是一個數和其自身的公約數仍是其自身。


  gcd(ka,kb)=k gcd(a,b),也就是最大公約數運算和倍乘運算可以交換。特殊地,當k=2時,說明兩個偶數的最大公約數必然能被2整除。


  當k與b互為質數,gcd(ka,b)=gcd(a,b),也就是約掉兩個數中只有其中一個含有的因子不影響最大公約數。特殊地,當k=2時,說明計算一個偶數和一個奇數的最大公約數時,可以先將偶數除以2。


  :param a:第一個數


  :param b:第二個數


  :return:最大公約數


  def gcd_Stein(a,b):
  #保證b比a小
  if a<b:
  a,b=b,a
  if(0==b):
  return a
  #a、b都是偶數,除2右移一位即可
  if a%2==0 and b%2==0:
  return 2*gcd_Stein(a/2,b/2)
  #a是偶數
  if a%2==0:
  return gcd_Stein(a/2,b)
  #b是偶數
  if b%2==0:
  return gcd_Stein(a,b/2)
  #都是奇數
  return gcd_Stein((a+b)/2,(a-b)/2)
  a=int(input("please input the first number:"))
  b=int(input("please input the second number:"))
  gcd=int(gcd_Stein(a,b))
  print(f"{a}和{b}的最大公約數為{gcd}")


  以上就是小編給大家總結的關于python實現最大公約數的五種具體方法,希望可以給大家帶來幫助。

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/127981.html

相關文章

  • 動態規劃法(八)最大子數組問題(maximum subarray problem)

    摘要:動態規劃法用表示最大子數組的結束下標為的情形,則對于,有這樣就有了一個子結構,對于初始情形,遍歷就能得到這個數組,其最大者即可最大子數組的和。動態規劃法想法巧妙,運行效率也高,但是沒有普遍的適用性。 問題簡介 ??本文將介紹計算機算法中的經典問題——最大子數組問題(maximum subarray problem)。所謂的最大子數組問題,指的是:給定一個數組A,尋找A的和最大的非空連續...

    jzman 評論0 收藏0
  • 《Java編程思想》讀后總結(一)

    摘要:前言編程思想這本書,陸陸續續讀了年,終于基本都瀏覽了一遍。每個對象對外暴露接口,程序通過對象暴露的接口向對象發送消息,獲取該對象的服務能力。異常處理異常處理,為編寫程序階段提供了一種預見性的防止程序崩潰的出路。 前言 《Java編程思想》這本書,陸陸續續讀了1年,終于基本都瀏覽了一遍。通過這本書,試圖理解作者的想法,才真的體會到Java思想。感謝本書的作者,不僅講述了java的語法,更...

    hufeng 評論0 收藏0
  • 基于R和Python的極大似然估計的牛頓法實現

    摘要:本文以牛頓法為例給出求解分布分布的極大似然估計參數的理論并使用和實現。如果隨機變量獨立同分布于且已知一組樣本為了估計該分布的參數,可以使用極大似然估計的方法。 目錄 0.前言 1.理論基礎 2.Cauchy分布的極大似然估計 2.1理論基礎 2.2算法 2.2.1R語言實現 2.2.2Py...

    QiuyueZhong 評論0 收藏0
  • Python 進階之路 (九) 再立Flag, 社區最全的itertools深度解析(上)

    摘要:例如,以下對兩個的相應元素求和這個例子很好的解釋了如何構建中所謂的迭代器代數的函數的含義。為簡單起見,假設輸入的長度可被整除。接受兩個參數一個可迭代的正整數最終會在中個元素的所有組合的元組上產生一個迭代器。 前言 大家好,今天想和大家分享一下我的itertools學習體驗及心得,itertools是一個Python的自帶庫,內含多種非常實用的方法,我簡單學習了一下,發現可以大大提升工作...

    tuantuan 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<