歐幾里得演算法(輾轉相除法)

Поделиться
HTML-код
  • Опубликовано: 17 сен 2024
  • 所謂的 "歐幾里得演算法",也就是一般大家所說的 "輾轉相除法",是一套可以用來求出最大公因數的算法。這個算法最早被記載在歐幾里得(Euclid)所寫的 [幾何原本] 的第七卷,所以也稱為Euclidean Algorithm。本短片透過 "鋪排磁磚" 以及 "直式運算" 兩種方式來詳述這個演算法的操作步驟,並進一步解釋為什麼透過這些步驟,可以得到兩個數之間的最大公因數。

Комментарии • 79

  • @kys5335
    @kys5335 4 года назад +7

    不好意思想請問一下,在9:40時您說「因為a,b,q是整數,所以這三個數做加減乘除後都是整數」,但實際上整數除整數後所得到的不一定會是整數吧?

    • @stepp.academy
      @stepp.academy  4 года назад +15

      沒錯,我在這裡說錯了。
      但是由於整個式子當中其實並沒有除法,所以" a - bq是整數 " 這個推論仍然是正確的。
      十分感謝你的提醒~~

    • @Thousand1982
      @Thousand1982 4 года назад

      @@stepp.academy 謝謝老師

    • @familychu2785
      @familychu2785 4 года назад

      ㅑ서대어내

  • @陳威丞-d3i
    @陳威丞-d3i 4 года назад +11

    講得好啊 最近在學遞洄演算法一直搞不懂輾轉相除的運作 看一次就學會了

  • @SunnySmile0420
    @SunnySmile0420 6 месяцев назад

    從小學就弄不懂的東西終於在大學畢業後的今天弄懂了,太感謝您了!

  • @o_o208
    @o_o208 5 лет назад +5

    講解得非常清楚!

  • @bolongbrian4579
    @bolongbrian4579 4 года назад +2

    講解原理淺顯易懂!

  • @senderron6614
    @senderron6614 4 года назад +2

    图文并茂的教学令人醍醐灌顶

  • @yen_s_life
    @yen_s_life 3 года назад +1

    感謝教學,十分清晰明瞭

  • @agent_lemmy_furry
    @agent_lemmy_furry Год назад

    用這個數學解法,在多大的數字都可以解出來。謝謝你教會我這個數學解法

  • @Legendfound-x8e
    @Legendfound-x8e 10 месяцев назад

    好難得,最後有證明題。謝謝老師!

  • @張泊浩
    @張泊浩 5 лет назад +6

    教的太棒了 簡易好懂

    • @stepp.academy
      @stepp.academy  5 лет назад +2

      謝謝支持 ! (感動得流淚了...)

  • @user-vy6rq6kz6d
    @user-vy6rq6kz6d 5 лет назад +6

    非常感謝!!真的教得很好!

  • @DingYiLin-h9l
    @DingYiLin-h9l 2 месяца назад

    謝謝你,我三十歲了
    重新複習這個東西
    太讚啦

  • @user-dc9jk3ni7v
    @user-dc9jk3ni7v 4 года назад +2

    謝謝你 這樣超級好理解 終於不用亂背了

  • @hsh0615
    @hsh0615 5 лет назад +7

    厲害了這影片

  • @lilylily6123
    @lilylily6123 4 года назад +7

    好奇老師是數學系的嗎?還是平常的業餘就會來研究數學,講得真的超詳細,幫助超大

    • @stepp.academy
      @stepp.academy  4 года назад +12

      我是學理工的但不是數學系,大學的時期因為對數學原理以及邏輯感到好奇,所以花了不少時間去研究。謝謝你對頻道的肯定~

    • @點線面-x1d
      @點線面-x1d 3 года назад +3

      真正數學教的非常好的,往往不是數學系畢業,而是熱愛教數學,研究數學教法,口語表達能力又好的強者,就像這位老師一樣。

  • @mahxylim7983
    @mahxylim7983 2 года назад +1

    An excellent explanation! Thank you!

  • @wucongjian8337
    @wucongjian8337 3 года назад

    做得非常用心,感谢!

  • @CT-bq4wp
    @CT-bq4wp 4 года назад +1

    Highly recommended. 👍👍👍👍👍👍from Silicon Valley.

  • @LJHuang-jn8bj
    @LJHuang-jn8bj 5 лет назад +3

    Very clear

  • @smallbird9016
    @smallbird9016 5 лет назад +3

    超感謝!!!

  • @shchen16
    @shchen16 4 года назад

    受益良多 謝謝你

  • @rainforest6407
    @rainforest6407 5 лет назад +3

    Thanks : )

  • @CurbyWang
    @CurbyWang 5 лет назад +3

    推~~

  • @snowman6246
    @snowman6246 Год назад

    講的很好

  • @Ian-bb7vv
    @Ian-bb7vv 2 года назад

    講的好,感謝

  • @jameschen4519
    @jameschen4519 11 месяцев назад

    謝謝!

  • @tomatokiller7762
    @tomatokiller7762 Год назад

    😳好強

  • @user-wu1bs1cn7r
    @user-wu1bs1cn7r 3 года назад

    谢谢讲解

  • @hsiaoaz961
    @hsiaoaz961 4 дня назад

    字好漂亮...🥹

  • @mandyhuang2158
    @mandyhuang2158 3 года назад

    very good!

  • @teacherbug3565
    @teacherbug3565 12 дней назад

    老師你用的白板工具是什麼?

  • @陳文-j6o
    @陳文-j6o 4 года назад

    讚👍

  • @guildwars2013
    @guildwars2013 5 лет назад +1

    你好,我有個疑問
    為什麼已經證明了a,b任意U的公因數也等於b,r,這裡不就可以推定兩者最大公因數也會相等嗎?
    為何還需要反推一次呢 (V的部分)? 謝謝

    • @stepp.academy
      @stepp.academy  5 лет назад +4

      Hi G,我用一個比喻來做回答 :
      假設有某國中,它A班裡面的每一個學生,都是一年級的學生。那麼從這一段資訊是否可以推理出 : 只要在A班裡最高的一位,就一定是一年級當中最高的? 我想這樣的推理並不正確。除非同時滿足第二個條件 : 凡是一年級的學生,則必定是A班的學生。那麼這就代表了這所國中的一年級只有唯一一個班: A班,所以兩者的成員才會一致,在兩個不同的群組中,最高的那一個也才會相同。希望這個比喻可以讓你明白~

    • @Thousand1982
      @Thousand1982 4 года назад

      @@stepp.academy 請問老師,上面網友所說的「任意U的公因數」,上下引號內的文字是否有點問題?
      因為U是指最大公因數,並非指所有因數。

  • @chinjunyuan1720
    @chinjunyuan1720 3 года назад

    这个方法可以用来找多过2个数的最大公因数吗

  • @kuoyutai
    @kuoyutai 4 года назад

    (A, B) = (B, R) 這個討論會有種無法推廣到最後的卡點。因為依照計算下一步應該會想寫下 (73,0),但好像無法用餘數不得為0來畫下句點 ? (畢竟我們會說餘數為0表示整除)影片稍後的討論如果A=Bq也就是R為0的話,那其實u是多少也沒關係。即使u不是個整數...? 這邊有點卡住,希望可幫忙解答~~~

    • @stepp.academy
      @stepp.academy  4 года назад +4

      事實上輾轉相除法的最後一個步驟一定會出現0,而出現0的前一個數字(這裡的例子是73),就是最大公因數。而這是因為,任何自然數A和0的最大公因數都是A,也就是(A,0)=A (此為一個定裡),原因是0可以被任何自然數整除,或者說,0=0*A,所以任何A>0都是0的因數,於是(A,0)=A。不過我為了讓篇幅簡短和單純一點,所以沒有把這個定理檯面化。

    • @kuoyutai
      @kuoyutai 4 года назад +2

      @@stepp.academy 謝謝說明!!!我覺得可以不用提(A, 0) = A為一個定理,也不用特地寫下。但是感覺還是可以寫到(73, 0) = 73,然後用口頭解說任何自然數A和0的最大公因數都是A。這樣在理解上會更容易~~~不然沒來由的中斷,聽者會覺得沒做完~~~這是我看影片的感覺^^

    • @stepp.academy
      @stepp.academy  4 года назад +4

      謝謝你真誠的回饋,我會試著讓解說做得更好

    • @kuoyutai
      @kuoyutai 4 года назад +1

      @@stepp.academy 辛苦你了~~~因為一直有在教數學。所以每次看教學影片,我都會想我是學生的話會想問什麼問題@@ 這樣也可以讓自己更了解在解說上哪裡可能會有學生卡住的盲點!辛苦囉^^"

  • @zerobit778
    @zerobit778 2 года назад

    10:12 开始就进行反向推导了
    想请问一下, 如果在开始预设 u 时, 直接把 u 预设成最大公约数, 那是不是可以不需要再反向推理了?

    • @住一下這要怎麼唱
      @住一下這要怎麼唱 Год назад

      不行吧,你預設u為gcd也只是A和B的gcd,
      你單方向推導只能知道u也是B和R的公因數,
      但你不能說這個公因數一定就是最大公因數。

  • @h.j.5902
    @h.j.5902 Год назад

    歐幾里得演算法可以用在2個數以上嗎

    • @stepp.academy
      @stepp.academy  Год назад +3

      先做任兩個數的輾轉相除,再用該結果和第三個數做第二次輾轉相除即可

  • @haohaohao6188
    @haohaohao6188 4 года назад

    有没有A和B的最大公因数会大于B和R的最大公因数的可能发生?

    • @stepp.academy
      @stepp.academy  4 года назад +4

      不會,這是整個輾轉相除法的根基,如果(A,B) 不等於(B,R),輾轉相除法就不成立了。

    • @ettsoc9018
      @ettsoc9018 Год назад +1

      不會的,假設(A,B)=u1,(B,r) = v1,因為u1整除A-Bq =r,所以有u1整除B和r,那麼這裡就回答了u1是不可能大於(B,r)=v1,所以得u1≤ v1,然後我們反過來推又可以得到v1≤u1,結合得到v1=u1,也就是說A和B的最大公因數與B和r的最大公因數是只會是相等的。

  • @harrischen9621
    @harrischen9621 4 года назад

    我想问问stepp使用的写字软件是什么?

    • @stepp.academy
      @stepp.academy  4 года назад +1

      記得沒錯的話應該是思源黑體。
      網路上有一些可商用的開源字體,google搜尋即可。

    • @harrischen9621
      @harrischen9621 4 года назад

      十分感谢!!!

  • @user-tk8js8bp1e
    @user-tk8js8bp1e 3 года назад

    我還是不會

  • @familychu2785
    @familychu2785 4 года назад

    애어ㅐ어낻나너너어ㅓ얻

  • @banana_jio
    @banana_jio 2 года назад

    看完這影片完全不知道我們教授在教什麼....