เลขฐานสองยาว L มีกี่ตัวที่ไม่มี 1x11 อยู่เลย

[heng005]

อุ้ย มีคนมาอ่านซะแล้ว คุยซักแป๊บเดี๋ยวพิมพ์วิธีที่ง่ายขึ้นอีกรอบ
มันเป็นการผสมกันระหว่างวิชา theroy of computation กับ วิชาของพวกนักลงทุนเค้าอ่ะครับ

theory of computation สอนให้ผมวาด finite state machine เป็น วิชานี้พูดจริงๆ ผมก็ยังไม่รู้ว่าเรียนแล้วใช้อะไรได้เหมือนกัน
วิชานี้จะพูดเกี่ยวกับภาษาชนิดต่างๆ ทั้ง regular language, context free language อะไรทำนองนี้ครับ
ข้อมูลเพิ่มเติมอ่านได้จาก http://en.wikipedia.org/wiki/Formal_language

ส่วนเพื่อนผมเค้าทำวิจัยเกี่ยวกับพวกการลงทุนอะไรทำนองนี้ ก็เลยได้ศึกษา model ต่างๆที่เอามาวิเคราะห์ความเสี่ยง
ซึ่งการลงทุนมันก็จะมีการใช้ความน่าจะเป็นมาเกี่ยวข้องเยอะพอควร พอเค้ามาเป็น fsm ของผม เค้าก็บอกว่า มันเป็น markov chain นิ แล้วก็คิดได้เลย
ข้อมูลเพิ่มเติม เกี่ยวกับ markov chain http://en.wikipedia.org/wiki/Markov_chain

[heng005]

วิธีที่ง่ายขึ้น ผมดัดแปลงมาจากวิธีเมื่อกี้ครับ โดยที่แทนที่จะสนใจความน่าจะเป็น ก็สนใจแค่กรณีของมันแทน

ค่าใน matrix ก็เขียนว่า สถานะ m สามารถเปลี่ยนไปยังสถานะ n ได้กี่วิธี แล้วก็ตัดสถานะที่เราไม่สนใจทิ้งไป
นั่นก็คือตัดแถว กับหลักที่ 5 หรือ 1x11 ทิ้งไปซะ ละเขียนข้อมูลใหม่เป็นแบบนี้$$ \bmatrix{1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0} $$matrix นี้บอกว่า สถานะ 0 เปลี่ยนไปยัง 0 ได้ 1 วิธี ไป 1 ได้ 1 วิธี
สถานะ 1 ไปยัง 2 กับ 3 ได้สถานะละวิธี ....

การหาคำตอบ ก็ทำเหมือนเดิม เอา matrix นี้มายกกำลัง L โดยที่ L เป็นความยาว string ที่ต้องการ ละหาคำตอบเฉพาะ แถวแรกก็พอ

เมื่อ L เป็น 4 จะได้คำตอบเป็น$$ \bmatrix{4 & 2 & 4 & 1 & 3} $$จำนวน case ที่ไม่มี 1x11 ก็คือผลรวมของเลขทั้งหมด เป็น 14 พอดีครับ
เมื่อ L เป็น 5 จะได้คำตอบเป็น$$ \bmatrix{8 & 4 & 6 & 2 & 5} $$จำนวน case ที่ไม่มี 1x11 เป็น 25

จะเห็นว่าวิธีนี้มันง่ายกว่า เพราะว่ามีแต่จำนวนเต็มหนะครับ

สรุปทั้งหมด วิธีการหาแบบนี้สามารถใช้ได้กับโจทย์ประเภทนี้ทั้งหมดได้ ไม่ว่าจะสนใจ L เท่าใด หรือว่า case ที่ต้องการจะยาวเท่าไร เป็น 1x1x1 ก็หาได้
เพียงแต่ต้องเขียน fsm ให้ถูกต้อง ซึ่งการเขียน fsm นี้ก็ใช้ความชำนาญเหมือนกัน แต่ก็ทำให้เชี่ยวชาญได้ไม่ยากนักครับ

จบแล้วครับ ใครมีคำถาม ผมจะเข้ามาตอบเรื่อยๆนะครับ ขอบคุณที่ร่วมสนุกกันมาครับ

[warut]

ยังไม่ได้อ่านละเอียดนะครับ แต่มีจุดนึงที่ผมสังเกตเห็น ไม่ทราบว่าคุณ heng005 เห็นมาก่อนแล้วรึเปล่า คือ characteristic polynomial ของ matrix อันนั้นคือ $$x^5-x^4-x^3-x-1$$ ซึ่งเมื่อตีความแล้วมันก็จะนำไปสู่ linear recurrence equation อันข้างบนนั่นเองครับ

ขอบคุณมากนะครับสำหรับข้อมูลทางวิชาการที่น่าสนใจแบบนี้

[nooonuii]

Markov chian เป็นเครื่องมือที่ถูกพัฒนาขึ้นมาจาก Probability Theory ครับ มีการนำไปประยุกต์ใช้กันอย่างกว้างขวาง โดยเฉพาะในศาสตร์ที่เกี่ยวกับการเงินและการลงทุน ยากกว่านี้ก็จะเป็น Stochastic Process ครับ

ป.ล. characteristic polynomial ไม่น่าจะมีเทอม $x^2$ โผล่มานะครับ

[warut]

จริงด้วย ผมพิมพ์ผิดครับ (พิมพ์เพลินไปหน่อย - ใส่มันครบทุกกำลังเลย ) แก้ไขให้แล้ว ขอบคุณครับ

[heng005]

เจอสาขาที่ไม่รู้จักเข้าไปเหมือนกันครับ
พึ่งไปเปิด wiki แวบๆ ว่าเกี่ยวกะ linear algebra ซึ่งเป็นอีกศาสตร์ที่ผมไม่เคยแตะเลย

ใครรู้จักทั้งสองศาสตร์ช่วยอธิบายคร่าวๆหน่อยนะครับ ว่ามันเกี่ยวกันยังไงบ้าง

[M@gpie]

เหอ มี Finite State machine ด้วยเหรอครับ ไม่เคยรู้ว่าเป็นวิชาทางคณิตศาสตร์แหะๆ
ผมเคยเจอตอนเรียนวิชา Digital Electronics ครับ เอามาใช้ในการออกแบบวงจรดิจิตอล เครื่องขายน้ำผลไม้ก็ใช้การออกแบบ Finite state machine ได้นะครับ แต่ให้ผมทำตอนนี้คงไม่เป็นแล้วครับ 55

[nooonuii]

ข้อความเดิมของคุณ heng005:
เจอสาขาที่ไม่รู้จักเข้าไปเหมือนกันครับ
พึ่งไปเปิด wiki แวบๆ ว่าเกี่ยวกะ linear algebra ซึ่งเป็นอีกศาสตร์ที่ผมไม่เคยแตะเลย

ใครรู้จักทั้งสองศาสตร์ช่วยอธิบายคร่าวๆหน่อยนะครับ ว่ามันเกี่ยวกันยังไงบ้าง

linear algebra ที่เกี่ยวกับเรื่องนี้ก็คงจะเป็น คุณสมบัติของ matrix ที่เราเรียกว่า stochastic matrix ครับ เป็น matrix ที่ทุกสมาชิกมีค่ามากกว่าหรือเท่ากับศูนย์และผลรวมของสมาชิกในแต่ละแถวมีค่าเท่ากับหนึ่ง matrix ชนิดนี้มีคุณสมบัติที่น่าสนใจอยู่หลายอย่างโดยเฉพาะที่เกี่ยวกับ eigenvalue และ eigenvector matrix ที่เราได้จาก markov chain ก็เป็น matrix ชนิดนี้ครับ

[heng005]

ขอบคุณทุกๆคนครับ