|
|
|||||||
| สมัครสมาชิก | คู่มือการใช้ | รายชื่อสมาชิก | ปฏิทิน | ค้นหา | ข้อความวันนี้ | ทำเครื่องหมายอ่านทุกห้องแล้ว |
  |
|
|
เครื่องมือของหัวข้อ | ค้นหาในหัวข้อนี้ |
|
#1
11 มกราคม 2007, 15:44
|
|||
|
|||
เลขฐานสองยาว L มีกี่ตัวที่ไม่มี 1x11 อยู่เลย
อยากจะทราบว่าเลขฐานสอง ที่ยาว L จะมีกี่จำนวนที่ไม่มี 1x11 อยู่ในนั้น เมื่อ x เป็นเลขอะไรก็ได้
เคยเห็นแต่โจทย์ที่เป็น 1111 ติดกัน หรือว่าอะไรทำนองนั้นครับ คราวนี้พอมี case ของ 1011 ซึ่งมันจะมีความต่อเนื่องของจำนวนมาเกี่ยวข้อง ก็เลยยังคิดไม่ออกครับ ช่วยชี้แนะแนวทางให้ด้วยครับ แล้วคำตอบจะแตกต่างจากเดิมมั๊ยครับ ถ้าเปลี่ยนจาก 1x11 เป็น 11x1 หรือ 111x ครับ 
|
|
#2
11 มกราคม 2007, 19:18
|
|||
|
|||
 เลขฐาน 2 มีกี่หลักก็ได้ เลขฐานสอง มีตัวเลขแค่ 2 ตัว คือ 0 กับ 1 ไม่จำเป็นต้องมี 4 หลัก เลขแต่ละตัวนำไปใส่ในวงเล็บ เพื่อแปลงเป็นเลขฐานสิบได้ตามรูป เลขไม่ว่าฐานไหน เขียน ไม่เหมือนกันก็แปลว่ามีค่าไม่เท่ากันแล้วครับ  11 มกราคม 2007 19:18 : ข้อความนี้ถูกแก้ไขแล้ว 1 ครั้ง, ครั้งล่าสุดโดยคุณ SeRpEnTSorTia
|
|
#3
11 มกราคม 2007, 23:08
|
|||
|
|||
|
แหะๆ อธิบายโจทย์ไม่ละเอียด
ที่บอกเลขฐานสองยาว L ตัวอย่าง L=5 เช่น 00000 01001 10010 แบบนี้หนะครับ แล้วที่บอกว่าไม่มี 1x11 เนี่ย ตัวอย่าง 11110 มี 1x11 อยู่ 10011 ไม่มี 1x11 อยู่ 11011 มี 1x11 อยู่ อย่างนี้เป็นต้น ไม่ได้สนใจค่าในเชิงเลขคณิต แต่สนใจรูปแบบแสดงค่าของมันหนะครับ เป็นโจทย์ combinatoric ครับผม ตอนนี้ได้วิธีคิดแล้ว แต่ยังไม่สามารถสรุปเป็นสูตรแบบติดค่า L ได้ แต่ละท่านลองคิดสนุกๆก่อนละกันครับ ไว้เดี๋ยวผมจะมาบอกแนวคิดของผมอีกครั้ง
|
|
#4
12 มกราคม 2007, 01:55
|
|||
|
|||
|
อ้างอิง:
จะว่าไปแล้วข้อนี้น่าจะตั้งไว้ที่ ปัญหาคณิตศาสตร์ โอลิมปิก และ อุดมศึกษา นะครับ
|
|
#5
12 มกราคม 2007, 17:42
|
|||
|
|||
|
พิมพ์ถูกแล้วครับ
11110 มีสี่ตัวแรกเป็น 1111 ไงครับ ซึ่งก็เข้าตามกฎที่สนใจการปรากฎของ 1x11 ครับ เราสนใจรูปแบบแสดงค่า (รูปที่เขียนออกมา) หรือว่ามองว่ามันเป็นตัวหนังสือก็ได้ครับ ปล. เรื่องการย้ายที่ไปไว้ในหัวข้ออื่นนี่ทำยังไงอ่ะครับ ผมทำไม่เป็นครับ
|
|
#6
12 มกราคม 2007, 19:16
|
|||
|
|||
อ้าว...แสดงว่าอาการเบลอผมกำเริบอีกแล้วดิ มิน่าถึงดูเรื่องง่ายๆยังไงก็ไม่เข้าใจ โทษทีครับ
 คุณ heng005 พอจะยกตัวอย่างได้มั้ยครับ อย่างเช่นถ้า $L=6$ แล้วคุณ heng005 นับตัวที่ต้องการได้เท่าไหร่ ผมจะได้มั่นใจว่าเข้าใจถูกแล้ว เอ่อ...แล้วนี่เป็นโครงงานหรือการบ้านครับ ผมจะได้ประมาณความยากถูก ส่วนเรื่องการย้ายไปไว้หัวข้ออื่นนี่เป็นเรื่องของคุณ gon/TOP ครับ
|
|
#7
12 มกราคม 2007, 22:46
|
|||
|
|||
|
ถ้าความยาวเป็น 6 จะได้ว่า
มีกรณีที่มี 1x11 19 กรณี กรณีที่ไม่มี 1x11 45 กรณี อันนี้ไม่ได้เป็นการบ้านหรือโครงการครับ พอดีผมทำ thesis เกี่ยวกับ number system อันนึงอยู่ แล้วมันมีส่วนหนึ่งของงานมีการคำนวณพวกนี้อยู่ ตอนแรกคิดว่ามันจะง่ายๆ แต่คิดไปคิดมามันไม่ง่ายอย่างนั้นแฮะ คิดยังไงก็คิดไม่ออก แล้วผมก็ไปปรึกษากับเพื่อน ปรากฎว่าได้ใช้ความรู้ของวิชาอื่นๆที่เรียนมาช่วยด้วย นอกจากเลขล้วน เห็นว่ามันน่าสนใจ ก็เลยมาถามดูครับ กรณีมี ได้แก่ 001011 001111 010110 010111 011011 011110 011111 101011 101100 101101 101110 101111 110110 110111 111011 111100 111101 111110 111111 ครับ
|
|
#8
13 มกราคม 2007, 00:30
|
|||
|
|||
โอเคแล้วครับ
ถ้างั้นให้ $a_n$ แทนจำนวนเลขฐานสองที่ยาว $L=n$ ที่ไม่มี $1x11$ อยู่ในนั้น เราจะได้ว่า $$ a_1=2, a_2=4, a_3=8, a_4=14, a_5=25 $$ และ $$ a_n= a_{n-1}+ a_{n-2}+ a_{n-4}+ a_{n-5}, \quad n\ge6 $$ ดังนั้น sequence ของ $a_n$ (เริ่มที่ $n=1$) คือ 2, 4, 8, 14, 25, 45, 82, 149, 270, 489, 886, 1606, 2911, 5276, 9562, 17330, 31409, 56926, 103173, 186991, 338903, 614229, 1113231, 2017624, 3656749, 6627505, 12011714, 21770074, 39456161, 71510489, ... ซึ่งผมมั่นใจในผลการคำนวณของผมมาก แต่การพิสูจน์อย่าง rigorous นั้นคงต้องใช้ความสามารถของคุณ heng005 เองล่ะครับ เพราะผมแทบไม่มีความรู้ทางด้าน combinatorics เลย ถ้าเปลี่ยนจาก $1x11$ เป็น $11x1$ คำตอบก็ยังคงเดิม แต่ถ้าเปลี่ยนเป็น $111x$ คำตอบจะเปลี่ยนไปครับ
|
|
#9
13 มกราคม 2007, 09:50
|
|||
|
|||
|
โอ้ว เห็นคำตอบของคุณ warut แล้วก็ถึงกับตะลึงครับ
เพราะเป็นคำตอบที่ถูกต้องแถมง่ายซะด้วย ขอทราบที่มาด้วยได้รึเปล่าครับ ปล. เดี๋ยวผมจะคิดต่อไปพลางๆ ปล2. ผมควรจะบอกวิธีของผมในตอนนี้เลยรึเปล่าครับ หรือว่าควรรอผู้สนใจอีกซักหนอ่ย
|
|
#10
13 มกราคม 2007, 15:54
|
||||
|
||||
|
จากคำตอบของคุณ warut ผมแกะรอยย้อนกลับได้ดังนี้
 สังเกตว่า เลขฐาน 2 ที่มี 1x11 อยู่ในนั้น เมื่อนำมาเพิ่ม 0 หรือ 1 เข้าไปตรงหัวหรือท้าย จะได้เลขที่มี 1x11 อยู่ในนั้นเสมอ นั่นก็แสดงว่า เลขฐาน 2 ที่ไม่มี 1x11 อยู่ในนั้น ต้องสร้าง(เพิ่ม 0 หรือ 1 เข้าไปตรงหัวหรือท้าย) มาจากเลขฐาน 2 ที่ไม่มี 1x11 อยู่ในนั้น เท่านั้น ผมเลือกวิธีสร้างโดยการเพิ่ม 0 หรือ 1 เข้าไปท้ายตัวเลขนะครับ ให้ $m_n$ แทนสมาชิกในเซตของเลขฐาน 2 ที่ยาว n และไม่มี 1x11 อยู่ในนั้น
และเนื่องจาก $\{m_{n-1} + "0"\} ,\,\ \{m_{n-2} + "01"\} ,\,\ \{m_{n-4} + "0011"\} ,\,\ \{m_{n-5} + "00111"\}$ ไม่มีสมาชิกร่วมกันเลย ดังนั้น $a_n = a_{n-1} + a_{n-2} + a_{n-4} + a_{n-5}$ เมื่อ $n > 5$
__________________
The difference between school and life? In school, you're taught a lesson and then given a test. In life, you're given a test that teaches you a lesson.
|
|
#12
13 มกราคม 2007, 23:17
|
|||
|
|||
เยี่ยมจริงๆ คุณ TOP ฝีมือไม่เคยตกเลยนะครับ เสียดายที่เดี๋ยวนี้ไม่ค่อยมีโอกาสได้เห็นบ่อยๆเหมือนแต่ก่อน
ผมทำไม่ได้หรอกครับข้อนี้ ที่เขียนไปเป็นเพียงข้อคาดเดา จากประสพการณ์ของผมบอกว่า คำตอบของโจทย์แนวนี้มักจะสอดคล้องกับ linear recurrence relation ดังนั้นผมจึงเขียนโปรแกรมนับในกรณีที่ $L=1-20$ แล้วเอาผลที่ได้มาคำนวณหาความสัมพันธ์ ปกติเวลาแก้โจทย์ยากๆผมมักพยายามหาคำตอบก่อน พอได้แล้วก็ค่อยมาคิดว่ามันควรจะพิสูจน์ยังไงให้ได้คำตอบนั้น (แบบเดียวกับที่คุณ TOP ทำนั่นแหละครับ) แต่โจทย์ข้อนี้มาในช่วงที่ผมล้าจากการที่เจอแต่โจทย์ยากๆเต็มไปหมด อีกทั้ง combinatorics ไม่ใช่รสนิยมของผม เลยขี้เกียจพยายามหาวิธีพิสูจน์อย่าง rigorous น่ะครับ โชคดีมีคุณ TOP มาช่วยจัดการต่อให้ ขอบคุณมากครับ ถ้าคุณ heng005 อยากแสดงวิธีทำตามสไตล์ของคุณ heng005 เองก็เชิญได้เลยครับ
|
|
#13
14 มกราคม 2007, 11:31
|
|||
|
|||
|
วิธีของผมนั้นใช้ finite state machine มาช่วยครับ (ท่านใดที่ไม่รู้จักอยากให้อธิบายเพิ่มก็บอกมาได้นะครับ)
fsm มันเหมือนกับตารางการเปลี่ยนสถานะครับ ถ้าเอามาใช้กับ binary string ไอ้เจ้า fsm ตัวนี้จะบอกว่า string ของเราตอนนี้อยู่ในสถานะใด ถ้ามีการเพิ่มข้อมูลตัวใหม่เข้ามา จะไปอยู่ในสถานะใด วงกลมวงนึง แทนสถานะนึง โดยวงกลมที่มีสองวงซ้อนกันให้แทนสถานะที่ต้องการ ในที่นี้ก็คือตรงกับเงื่อนไง ไม่มี 1x11 เส้นเชื่อมวงกลม แทนการเติมข้อมูลเข้ามาอีกหนึ่งตัว ทำให้เกิดการเปลี่ยนสถานะ สำหรับ fsm ของ binary string นี้จะเป็นดังรูป 
|
|
#14
14 มกราคม 2007, 11:54
|
|||
|
|||
|
เมื่อมี fsm ที่ถูกต้องแล้ว ก็สามารถมองได้ว่า สถานะหนึ่งๆ สามารถเปลี่ยนแปลงไปยังสถานะอื่น ได้สองแบบ คือเติม 0 และ เติม 1
โดยโอกาสที่เติม 0 กับ 1 นั้นเท่าๆกัน ทำให้สามารถคิดความน่าจะเป็นได้ว่าแต่ละแบบมีโอกาสเป็น 0.5 คราวนี้ก็ใช้ความรู้เกี่ยวกับ markov chain ซึ่งเป็นวิธีการหาความน่าจะเป็นสำหรับเหตุการณ์ที่เกิดต่อเนื่องกัน และขึ้นต่อกันและกัน ขั้นตอนแรกให้สร้าง matrix ขนาด mดm โดยที่ m เป็นจำนวนสถานะ ให้สถานะ 0 เป็น row,column 0 1 เป็น row,column 1 10 เป็น row,column 2 11 เป็น row,column 3 1x1 เป็น row,column 4 1x11 เป็น row,column 5 ส่วนค่าที่ใส่ไปใน matrix ใน แถวที่ m หลักที่ n นั้นคือ ความน่าจะเป็นในการเปลี่ยนสถานะจากสถานะ m ไปยัง สถานะ n นั่นเอง เช่น การเปลี่ยนจาก สถานะ 0 ไปยังสถานะ 1 จะเขียนลงไปในช่องที่ 0,1 มีค่าเป็น 0.5 matrix ที่ได้เป็นดังนี้ $$ \bmatrix{0.5 & 0.5 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0.5 & 0.5 & 0 & 0 \\ 0.5 & 0 & 0 & 0 & 0.5 & 0 \\ 0 & 0 & 0.5 & 0 & 0.5 & 0 \\ 0 & 0 & 0.5 & 0 & 0 & 0.5 \\ 0 & 0 & 0 & 0 & 0 & 1} $$ ถ้านำ matrix นี้มายกกำลัง L ค่าในช่อง (m,n) จะเป็นความน่าจะเป็นในการเปลี่ยนสถานะ จาก m ไปยัง n เมื่อมีการเปลี่ยนสถานะ L ครั้ง เมื่อเอามาจับกับปัญหา binary string นี้ L ก็คือความยาว string ที่ต้องการ ค่าของช่อง (0,5) คือความน่าจะเป็นที่ string ยาว L จะมี 1x11 อยู่ในนั้น ปัญหานี้ไม่จำเป็นต้องคูณ matrix ทั้งอัน เพราะยังไง สถานะเริ่มต้น ต้องเริ่มจาก สถานะ 0 อยู่แล้ว ดังนั้น เราจึงสามารถคูณเพื่อ หาค่าของ แถวแรกเพียงแถวเดียวได้ ทดลองดูนะครับ ถ้า L ที่ต้องการเป็น 1 ตัว ก็ยกกำลัง 1 ได้ผลของแถวแรกเป็น$$ \bmatrix{0.5 & 0.5 & 0 & 0 & 0 & 0} $$แปลความหมายได้ว่า ถ้า string ยาว 1 ตัว มีโอกาสจบใน state 0,1 เป็น 0.5 เท่ากัน ถ้า L เป็น 4 หรือว่า string ยาว 4 ค่าที่ได้จะเป็น$$ \bmatrix{\frac{4}{16} & \frac{2}{16} & \frac{4}{16} & \frac{1}{16} & \frac{3}{16} & \frac{2}{16}} $$นำมาแปลผล ข้อมูลที่ได้บอกว่า ถ้า string ยาว 4 จะมีโอกาสที่มี 1x11 อยู่ $ \frac{2}{16} $ ซึ่งก็คือ 2 กรณีนั่นเอง ถ้าคูณไปเรื่อยๆ ก็จะคิดความยาวเป็นเท่าไรก็ได้ 14 มกราคม 2007 12:02 : ข้อความนี้ถูกแก้ไขแล้ว 1 ครั้ง, ครั้งล่าสุดโดยคุณ heng005
|
| |
| เครื่องมือของหัวข้อ | ค้นหาในหัวข้อนี้ |
|
|
