ข้อนี้สนุกมาก
สมมติว่าเราเป็นนักเทนนิส ซึ่งจะใช้ไม้เทนนิสของเราตบแมลงวัน
โจทย์จะให้ขนาดของแมลงวัน (f)
ขนาดของไม้ (R)
ความหนาของไม้ (t)
ความหนาของเส้นเอ็น (r)
และความห่างของเส้นเอ็น (g)
โจทย์ให้หาว่า โอกาสที่ไม้เทนนิสจะตบโดนแมลงวันเป็นเท่าไหร่?
อ่านต่อ
ที่นี่ โจทย์ข้อนี้ ใครมานั่งหาสูตรคำนวนพื้นที่ก็อ้วกครับ มานั่งคำนวนเส้นตัดวงกลมทีละช่อง โหดแท้
เนื่องจากโจทย์ไม่ได้ให้คำนวนละเอียดมาก ทศนิยมหกหลัก เราสามารถใช้วิธี
divide and conquer ได้
หลักการคือ แบ่งไม้เป็นสี่ส่วน แล้วก็พิจารณาดูว่าในส่วนนึง มีทั้งเส้นเอ็นและขอบเทนนิสหรือเปล่า
ถ้ามี เราก็แบ่งเป็นสี่ส่วนอีก แบ่งเฉพาะช่องที่มีขอบเทนนิสไปเรื่อยๆ จนทศนิยมไม่เกินหกหลักเราก็หยุด
เริ่มเลยละกัน
let solve f R t r g =
let Rin = R - t - f
let start = -(r + f)
let r = (r + f)*2.0
let g = g - f*2.0
let rg = r + g
วิธีที่จะทำให้คิดง่ายขึ้นคือ เอาขนาดของแมลงวันมาขยายขนาดไม้ แล้วแมลงวันจะเหลือแค่จุดเดียว
Rin คือขนาดไม้ด้านใน (หักขนาดของแมลงวันแล้ว)
start สมมติว่า 0 คือกลางไม้ start คือจุดซ้ายล่างของเส้นเอ็นกลางไม้
r คือ ขนาดของเส้นเอ็น (รวมขนาดของแมลงวันแล้ว)
g คือ ช่องว่างระหว่างเส้นเอ็น (หักขนาดของแมลงวันแล้ว)
rg คือ ความห่างระหว่างจุดศูนย์กลางของเส้นเอ็น
let calculateGap p len =
//calculate head
let num = floor ((p - start) / rg)
let headBlock = start + rg*num
let headTouch = if p - headBlock > r
then 0.0
else min (headBlock + r - p) len
let head = min (headBlock + rg - p) len
//calculate body & tail
let body = len - head
let bodySize = floor (body / rg)
let tail = body - rg*bodySize
//calculate gap & return
let headGap = head - headTouch
let bodyGap = g * bodySize
let tailGap = max 0.0 (tail-r)
headGap + bodyGap + tailGap
อันนี้คือสูตรหาความยาวของช่องว่าง
p คือจุดเริ่มต้น
len คือความยาวของเส้น
concept ในการหาจะมี head, body, tail
head คือ gap ระหว่างขอบจุดเริ่มต้น ไปแต่ขอบเอ็นเส้นแรก
body คือ ขนาดของ gap ระหว่างเส้นเอ็น ภายในเส้นตรง
tail คือ gap ระหว่างขอบเอ็นเส้นสุดท้าย กับจุดสิ้นสุดของเส้นตรง
let touchString (x1,y1) (x2,y2) =
let len = x2 - x1
let gapH = calculateGap x1 len
let gapV = calculateGap y1 len
let untouch = (gapH * gapV) / (len * len)
1.0 - untouch
function นี้ใช้คู่กับ function calculateGap
คือหาพื้นที่ของ gap หารด้วยพื้นที่ของสี่เหลี่ยม
ผลลัพธ์คือ โอกาสที่แมลงวันจะหลุดไปใน gap
let rinMixRate = (r / rg) * 0.5 + 0.5
let getHitRate p1 p2 =
let a = center <-> p1
let b = center <-> p2
if b > R then
if a > R
then (0.0, 0.0), false
else (1.0, 0.5), true
elif b > Rin then
if a > Rin
then (1.0, 1.0), false
else (rinMixRate, 1.0), true
else
(touchString p1 p2, 1.0), false
ถัดมาคือการคำนวน ที่รวมขอบไม้
rinMixRate คือ โอกาสคร่าวๆ ที่แมลงวันจะรอดระหว่างขอบไม้กับเส้นเอ็นได้
p1 p2 คือจุดของสี่เหลี่ยม โดย p1 คือจุดซ้ายล่าง p2 คือ ขวาบน
a กับ b คือ ระยะระหว่าง จุดศูนย์กลางถึง p1 และ p2
operator (<->) คือการหาระยะ อ่าน
ของเก่าดูครับ
function นี้ return โอกาสที่ตีโดนแมลงวัน โอกาสที่อยู่ในไม้ และ สามารถแบ่งออกได้อีกหรือไม่
logic คือ ถ้าทั้ง p1 และ p2 อยู่นอกขอบไม้ โอกาสตีโดนคือ 0 โอกาสอยู่ในไม้คือ 0 และไม่ต้องแบ่งอีกแล้ว
ถ้า p2 อยู่นอกไม้ แต่ p1 อยู่ในไม้ โอกาสตีโดนคือ 1 โอกาสอยู่ในไม้คือ 0.5 และสามารถแบ่งเพื่อคำนวนให้ละเอียดขึ้นได้
ถ้าใน p1 และ p2 อยู่ระหว่างขอบไม้ด้านในกับด้านนอก ก็คือตีโดนแน่นอน
แต่ถ้า p2 อยู่ระหว่างขอบไม้ แต่ p1 อยู่ในวงกลม โอกาสคือ rinMixRate แต่สามารถแบ่งเพื่อคำนวนละเอียดขึ้นได้
สุดท้ายถ้า p1 และ p2 อยู่ในวงกลม ก็ใช้สูตรคำนวน touchString
let epsilon = 0.00000025 * R
let rec divide (x1,y1) (x2,y2) =
let xHalf = (x1 + x2) / 2.0
let yHalf = (y1 + y2) / 2.0
let pos1,area1 = conquer (x1,y1) (xHalf,yHalf)
let pos2,area2 = conquer (x1,yHalf) (xHalf,y2)
let pos3,area3 = conquer (xHalf,y1) (x2,yHalf)
let pos4,area4 = conquer (xHalf,yHalf) (x2,y2)
let area = area1 + area2 + area3 + area4
if area = 0.0
then 0.0, 0.0
else let pos = pos1*area1 + pos2*area2 + pos3*area3 + pos4*area4
pos/area, area/4.0
and conquer (x1,y1) (x2,y2) =
let hitRate,mix = getHitRate (x1,y1) (x2,y2)
if mix && x2-x1 > epsilon
then divide (x1,y1) (x2,y2)
else hitRate
function สุดท้ายละ
epsilon คือ ขนาดที่เล็กที่สุดที่เราจะไม่คำนวนต่อ
divide คือ แบ่งสี่เหลี่ยมเป็นพื้นที่สี่ส่วนย่อย แล้วก็ conquer
ส่วน conquer คือ คำนวนหา hitRate ถ้าสามารถคำนวนละเอียดขึ้นได้ ก็ divide ไปเรื่อยๆ
ด้านบนมีใช้ keyword "and" ใน f# คือ
mutually recursive function ครับ
แล้วก็ print ผลลัพธ์
let pop,_ = if g <= 0.0
then 1.0, 1.0
else conquer center (R,R)
sprintf "%.6f" pop
จบ