creatio ex nihilo

ศล
Location :
กรุงเทพ Thailand

[Profile ทั้งหมด]

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




Group Blog
 
All Blogs
 
Friends' blogs
[Add ศล's blog to your web]
Links
 

 
Babylonian Method

ก่อนมิดเทอมที่ผ่านมา เพื่อนที่ไปเป็นอาจารย์พิเศษมหา'ลัยแห่งหนึ่งขอให้ช่วยออกโจทย์ภาษา C ให้หนึ่งข้อ คิดอะไรไม่ออกครับ ความรู้ภาษา C ของผมก็มีน้อยนิด จึงส่งโจทย์ไปแบบนี้

float a,b,e=0.00001,p,k;

a=k;
p=a*a;
while (p-k>=e)
{
    b=(a+(k/a))/2;
    a=b;
    p=a*a;
}

จากโค้ด เมื่อผู้ใช้ป้อน input ซึ่งเป็นค่า k (จำนวนจริง) นักเรียนคิดว่าลูป while จะมีโอกาสวนลูปตลอดกาลหรือไม่? เพราะเหตุใด? ถ้าลูป while สิ้นสุด และโปรแกรมรีเทิร์นค่า a นักเรียนคิดว่า k กับ a มีความสัมพันธ์กันอย่างไร? อธิบายแนวคิด


ใครเก่ง math หน่อยตอบได้สบาย หรือใช้กึ๋นเล็กน้อยจะพบว่า p-k ลดลงเรื่อย จนน้อยกว่า e ทำให้หลุดจากลูป ตอบคำถามตามโจทย์นี้ไม่ยากครับ ที่อยากนำมาเล่าไว้เป็นเกร็ดคือกระบวนวิธีดังกล่าวเป็นวิธีที่ชาวบาบิโลเนียนใช้หาค่ารากที่สองของจำนวน รู้จักกันในนาม Babylonian method (ซึ่งถ้าคุณรู้จัก Newton's method คุณก็สามารถแสดงย้อนกลับไปพิสูจน์กระบวนวิธีบาบิโลเนียนได้) concept มันสวยและ make sense สมมติเราอยากหาค่ารากที่สองของ k คุณสมมติขึ้นมาตัวหนึ่งคือ a ซึ่ง a2 อาจจะไม่เท่ากับ k ก็ได้เพราะคุณแค่สมมติมันขึ้นมา แต่ที่แน่ ๆ a x (k/a) = k หมายความว่าทั้ง a และ k/a ต่างเป็นค่าประมาณขั้นที่หนึ่งของรากที่สองของ k ซึ่งค่ารากที่สองของ k จะไม่มากกว่า a และน้อยไปกว่า k/a ดังนั้นค่าเฉลี่ยเลขคณิตระหว่างทั้ง 2 ค่าย่อมเป็นค่าประมาณที่ดีกว่า (ค่าประมาณขั้นที่ 2) เราก็ได้ค่าประมาณขั้นที่สองเท่ากับ (a+(k/a))/2 สมมติเรียกมันว่า b และรู้แน่ ๆ อีกเช่นกันว่า b x (k/b) = k ดังนั้นใช้ค่าเฉลี่ยเลขคณิตของ b กับ k/b เป็นค่าประมาณขั้นที่สาม วนไปเรื่อย ๆ เราก็จะได้ค่าประมาณของรากที่สองของ k

ตัวอย่าง อยากหาค่ารากที่สองของ 17 (k = 17) เราสมมติค่าประมาณขั้นแรกคือ 4 ดังนั้นค่าประมาณขั้นที่สองคือค่าเฉลี่ยของ 4 กับ 17/4 เท่ากับ 33/8 ค่าประมาณขั้นที่สามคือค่าเฉลี่ยของ 33/8 กับ 17/(33/8) ประมาณเท่ากับ 4.123 แค่ทำสองรอบ เราก็ได้ค่าใกล้เคียงกับรากที่สองของ 17 มากแล้วเห็นมั้ยครับ (รากที่สองของ 17 ประมาณ 4.1231056)

ทีนี้ลองมองย้อนกลับไปดูโค้ด


Create Date : 24 กุมภาพันธ์ 2553
Last Update : 24 กุมภาพันธ์ 2553 21:18:58 น. 0 comments
Counter : 1117 Pageviews.

ชื่อ : * blog นี้ comment ได้เฉพาะสมาชิก
Comment :
  *ส่วน comment ไม่สามารถใช้ javascript และ style sheet
 
 Pantip.com | PantipMarket.com | Pantown.com | © 2004 BlogGang.com allrights reserved.