上課時提到的問題 可是不知道原理想來詢問一 下
(10m+n)+(m-n)=11m
式子寫成這樣
接下來可利用此式來判斷11是不是他的因數
ie 1331
133 - 1 = 132 //拆成10位數來看 然後減個位數
13 - 2 = 11
因此1331為11的因數
同理也可用在
2(10m+n)+(m-2n)=21m 用來判斷是不是21的因數
ie 2331
233 - 2*1=231
23 - 2*1=21
所以2331為21的因數
雖然看懂規則了 但是搞不懂為何可以一直遞回下去弄出答案
只覺得很神奇
不知道是要從哪個觀點來看? 不懂遞回跟modlue的關係 orz
懇請賜教
2 則留言:
假設 a+b = nk, i.e., a+b=0 mod n =>
1. If b=0 mod n => a=0 mod n
2. 把上述1中的 a改b, b改a,
則 a=0 mod n => b=0 mod n,
所以在這個情況下其實 a=0 iff b=0
令例一中的 10m+n = a, m-n = b, 則
a+b = 11m => a+b = 0 mob 11,
這麼一來我們只到判斷 b 是否為 11 的倍數, 就可以知道 a 是否為 11 的倍數了, 所以這裡利用把 1331 兜成 1331 + 132, 且此數會是 11 的倍數的性質, 就可以拿 132 來判定 1331 是否為 11 的倍數了, 如果 132 是那 1331 也會是 (要判定 132 也可以繼續遞迴用 13-2 來判定, 都是等價的)
也就是說利用
a=0 <=> b=0
把拆出來的數字在分兩個拆下去
無限遞回下去囉
感謝:)
張貼留言