creatio ex nihilo

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

[Profile ทั้งหมด]

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




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

 
ปัญหา Josephus กรณี m = 2 กับ Left circular shift

ผมจะถือว่าคุณรู้จักปัญหา Josephus และรู้ว่า L(n,2) = 1 + 2n - 21+floor(lg(n)) ถ้าคุณไม่รู้หรือไม่แน่ใจ ลองแวะไปอ่านคำอธิบายได้จาก link ด้านล่างครับ

ปัญหา Josephus กรณี m = 2

ในตอนนี้ผมจะนำเสนอวิธีการคำนวณค่า L(n,2) อย่างง่ายด้วยการใช้เทคนิค left circular shift register แต่ก่อนจะพูดถึงปัญหา Josephus เราลองมาทำความรู้จักกับ register กันก่อนสักหน่อยพอหอมปากหอมคอ คุณนึกภาพ register ตัวหนึ่งเก็บข้อมูลขนาด 8 บิต '10010111'

[1][0][0][1][0][1][1][1]

ถ้าคุณต่อวงจรให้มันเป็นรีจีสเตอร์ที่เลื่อนไปทางซ้าย (logical shift left) หลังจากส่งสัญญาณบอกให้มันเลื่อน (เราเรียกสัญญาณนี้ว่าสัญญาณนาฬิกา) มันก็จะเลื่อนบิตที่อยู่ทางซ้ายไปแทนที่บิตที่อยู่ทางขวาของทุกดิจิทพร้อม ๆ กัน หมายความว่าเลข 1 ตัวที่อยู่ซ้ายมือสุดหลุดออกไปจากรีจีสเตอร์นะครับ

1 ‹— [0][0][1][0][1][1][1][ ]

จะเห็นว่าบิตที่อยู่ขวามือสุดโบ๋ โดยทั่วไปเรามีการกำหนดค่า default เอาไว้ว่าขณะที่ทุก ๆ บิตเลื่อนไปทางซ้ายพร้อม ๆ กันนั้น จะให้ '1' หรือ '0' เข้าไปแทนที่บิตขวาสุด สมมติว่าผมกำหนดให้ default คือ '0' ฉะนั้น ทันทีที่ได้รับ clock signal รีจีสเตอร์ [1][0][0][1][0][1][1][1] จะเลื่อนเป็น

1 ‹— [0][0][1][0][1][1][1][0] ‹— [0]

แบบนี้เรียกว่ารีจีสเตอร์เลื่อนไปทางซ้าย (ในเมื่อมันมีเลื่อนซ้าย ก็ต้องมีเลื่อนขวา ผมเชื่อว่าคุณนึกภาพออกอยู่แล้วล่ะ) ทีนี้บิต '1' ที่ถูกผลักออกมาจะเอาไปทิ้งหรือเอาไปทำอะไรก็แล้วแต่ผู้ออกแบบครับ แต่ถ้าเราเอาบิตที่ถูกผลักออกมาจากทางซ้ายย้อนกลับไปป้อนเข้าทางขวา มันจะมีชื่อเรียกใหม่ว่า left circular shift register คำว่า circular ก็คือวน หมายถึงเอาตัวที่ถูกผลักออกมาวนกลับไปต่อท้ายแถวใหม่ ฉะนั้นหากเดิมรีจีสเตอร์วนซ้ายของเราเก็บค่า '10010111' หลังจากได้รับสัญญาณนาฬิกา มันก็จะมีค่าใหม่กลายเป็น '00101111'

ถ้าคุณเคยเรียนวิชาดิจิทัล คุณจะพบว่าการเลื่อนเลขฐานสองนี่มีประโยชน์ในการคำนวณมากทีเดียวครับ การเลื่อนซ้ายหนึ่งบิตที่ป้อน 0 เป็นค่า default เข้าทางขวา และเก็บรักษาบิตแรกที่ถูกผลักออกมาเอาไว้ เท่ากับการคูณค่าเดิมที่อยู่ในรีจีสเตอร์นั้นด้วย 2 เช่น จากตัวอย่างเรามี '10010111' (8 บิต) เมื่อเลื่อนซ้าย ได้ '100101110' (9 บิต เพราะเก็บบิตแรกเอาไว้ด้วย) ฉะนั้นคำว่าเลื่อนซ้ายของผมในความหมายนี้ก็เท่ากับเอา 0 ไปต่อท้ายอีกหนึ่งตัวใช่มั้ยครับ? ค่า (10010111)2 = 151 และ 151 x 2 = 302 ซึ่ง 302 = (100101110)2 และเราสามารถพิสูจน์ได้ง่ายมากว่าทำไม bi...b2b1b0 + bi...b2b1b0 = bi...b2b1b00 (ฝากเป็นการบ้านนะครับ คำใบ้คือ 0+0 = 0 ทด 0, และ 1+1 = 0 ทด 1) ดังนั้นถ้าคุณมีเลขฐานสองขนาด n บิต ต้องการคูณ 2 ก็ให้ shift left ผลลัพธ์ที่ได้จะมีขนาดไม่เกิน n+1 บิต

อีกข้อสังเกตที่คุณควรรู้ก่อนข้ามไปดูปัญหา Josephus ถ้าเราเขียนลำดับ 1, 2, 4, 8, 16, 32, ... ซึ่งก็คือลำดับของ 2x เมื่อ x = 0, 1, 2, 3, ... ด้วยลำดับของเลขฐานสอง เราจะได้ 1, 10, 100, 1000, 10000, ... สรุปว่าเขียน 2x ด้วยเลขฐานสอง คุณจะได้ 1 ตามด้วย 0 จำนวน x ตัว เช่น 210 = (10000000000)2

คราวนี้กลับมาดูปัญหา Josephus กันครับ เรารู้ว่า L(n,2) = 2(n - 2floor(lg(n))) + 1 โดยค่าของ n - 2floor(lg(n)) ก็คือ w เมื่อเราเขียน n ในรูป 2k + w โดยที่ w < 2k ฉะนั้น





เจ้าบิต X...XXX ทั้ง k บิตนั่นก็คือ w สมมติว่าผมเขียนแทน X...XXX ด้วย wk-1...w2w1w0 ถ้าผมอยากได้ 2w ผมก็แค่ shift left จริงมั้ยครับ ได้ wk-1...w2w1w00 ถ้าผมนำ 2w ไปบวกเพิ่มอีก 1 กลายเป็น wk-1...w2w1w01 ซึ่งค่า 2w + 1 คือคำตอบที่เราต้องการ และเมื่อมองดี ๆ จะพบว่า wk-1...w2w1w01 ก็คือ 1X...XXX ที่ถูกทำ left circular shift ให้กลายเป็น X...XXX1 ฉะนั้น L(n,2) เท่ากับค่าของ n หลังจากทำ left circular shift แล้วนั่นเอง

ตัวอย่าง จงหา L(2008,2)

เริ่มจาก n = 2008 = (11111011000)2 จากนั้นทำ left circular shift ได้ (11110110001)2 = 1969 ♣


Create Date : 30 กันยายน 2552
Last Update : 30 กันยายน 2552 20:20:08 น. 0 comments
Counter : 1186 Pageviews.

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