Just algorithm!
Numbers



ข้อนี้ให้หา 3 หลักสุดท้ายก่อนจุดทศนิยมของ (3 + √5)n


เช่น (3 + √5)5 = 3935.73982... ก็ให้ตอบ 935



ข้อนี้ถ้าคูณธรรมดาผิดแน่นอนครับ ใน large set ยกกำลังถึง 2,000,000,000

precision ไม่พอแน่นอน



ทีนี้ลองแทนค่า √5 ด้วย x และแทนตัวบวกตัวคูณเป็น a กับ b


ก็จะเป็น a + bx



ทีนี้ function คูณก็จะง่ายแล้ว (a1 + b1x) * (a2 + b2x) เขียนเป็น function ได้ดังนี้
let (.*.) (a1, b1) (a2, b2) =
    a1*a2 + b1*b2*5, a1*b2 + a2*b1

เรารู้อยู่แล้วว่า x^2 จะได้ 5 จึงแทนค่าด้วย 5 ได้เลย



อีก function นึงสำหรับ mod
let (.%.) (a, b) m =
    a % m, b % m

ไม่มีอะไร แค่ mod a และ b



ถัดมาเป็น function สำหรับทำ modPow
let rec modPow num = function
    | 1   -> num
    | exp -> let result = modPow (num .*. num .%. 1000) (exp >>> 1)
             if exp &&& 1 = 1
             then num .*. result .%. 1000
             else result

อันนี้ค่อนข้างตรงสูตร ลองอ่านเพิ่มเติมใน wiki ดูนะครับ



ถัดมา หลังจากได้คำตอบแล้วจะถอดออกมาอย่างไร เช่น

(3 + √5)2 จะได้ 14 + 6x


ถึงตอนนี้ เราจะแทน x ด้วย √5 ตรงๆ ไม่ได้เพราะ 6 ถูก mod มาก่อนหน้าแล้ว

ซึ่งอาจจะมีค่าเป็น 1006 ก็ได้



ทีนี้ลองพิจารณา conjugate ของ 3 + √5 ซึ่งก็คือ 3 - √5

3 - √5 มีค่าเท่ากับ 0.76... ซึ่งเมื่อยกกำลังไปเรื่อยๆ ก็มีค่าไม่เกิน 0

ดังนั้นคำตอบเท่ากับ




= (3 + √5)n + (3 - √5)n - (3 - √5)n        


= (a + bx) + (a - bx) - 1

= 2a - 1



(3 - √5)n เราแปลงเป็น 1 ไปเลยเพราะเราไม่สนใจเศษทศนิยม

เอา 2a - 1 มาเป็น function คำตอบ
let solve exp =
    let a, _ = modPow (3,1) exp
    (a*2 + 999% 1000 |> sprintf "%03d"

เราเปลี่ยน -1 เป็น 999 เพราะมี mod มาเกี่ยวข้อง


ดังนั้นเมื่อ a เป็น 0 จะได้ 999 ไม่ใช่ -1



จบ






Create Date : 15 พฤศจิกายน 2557
Last Update : 15 พฤศจิกายน 2557 20:11:45 น. 0 comments
Counter : 145 Pageviews.

ชื่อ : * blog นี้ comment ได้เฉพาะสมาชิก
Comment :
  *ส่วน comment ไม่สามารถใช้ javascript และ style sheet
 

chaowman
Location :
กรุงเทพฯ Thailand

[Profile ทั้งหมด]

ให้ทิปเจ้าของ Blog [?]
ฝากข้อความหลังไมค์
Rss Feed
Smember
ผู้ติดตามบล็อก : 8 คน [?]









New Comments
Group Blog
 
All Blogs
 
Friends' blogs
[Add chaowman's blog to your web]
Links
 

 Pantip.com | PantipMarket.com | Pantown.com | © 2004 BlogGang.com allrights reserved.