Generating Subsets

มีหลายปัญหาในการเขียนโปรแกรมที่เราจะต้องแก้ด้วยการสร้างซับเซตทั้งหมดที่เป็นไปได้ขึ้นมา เพื่อทดสอบวิธีที่เป็นไปได้ทั้งหมด ปัญหาที่เกิดขึ้นคือจะสร้างซับเซตได้อย่างไร?

ความรู้แรกที่ทุกคนน่าจะมีเกี่ยวกับซับเซตทั้งหมดของเซตหนึ่งๆคือ ซับเซตทั้งหมดจะมี $2^n$ แบบ (เมื่อเซตนั้นมีสมาชิก n ตัว) เช่น เซต $\{1, 2, 3\}$ มีซับเซตที่เป็นไปได้ทั้งหมด 8 ตัวได้แก่ $\{\}, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}$ และ $\{1,2,3\}$

ทีนี้เราจะใช้เลขฐานสองเข้ามาช่วยในการสร้างซับเซตทั้งหมดแล้วครับ ลองดูเลขฐานสองของ 0 จนถึง 7 ดูครับ

Taxonomy upgrade extras: 

Unified Solution - โปรแกรมเดียวที่แก้ได้ทุกปัญหา

เคยรู้สึกกันมั้ยครับว่าทำไมเราต้องเขียนโปรแกรมซ้ำไปซ้ำมา ปัญหา (Problem) บางอย่างที่คล้ายๆกันก็มีออกมากมาย แต่เราก็ยังจำเป็นต้องใช้วิธีที่ต่างกันออกไปในการแก้ ไม่มีวิธีอะไรเลยหรือที่สามารถแก้หลายๆปัญหาได้ในคราวเดียว ผมเคยมีความรู้สึกนี้อยู่ช่วงนึง จนกระทั่งได้เรียนรู้เรื่องของการลดรูปของปัญหาว่ามีหลายปัญหาที่สามารถเปลี่ยนไปเป็นอีกปัญหานึงได้ อย่างเช่น Clique, Independent Set หรือ 3-SAT ฯลฯ

Taxonomy upgrade extras: 

CUDA Tutorial: ภาคติดตั้ง

กลับมาพบกับภาคต่อของ CUDA Tutorial กันแล้วนะครับ จากตอนก่อนที่อธิบายถึงว่า CUDA คืออะไร ตอนนี้เราจะมาดูกันว่าถ้าอยากจะลองเล่นต้องเริ่มต้นติดตั้งอะไรบ้าง ถ้ายังไม่ได้อ่านตอนแรกแนะนำให้ลองอ่านดูก่อนนะครับ กับ CUDA Tutorial: ภาคปฐมบท - CUDA คืออะไรหว่า

Taxonomy upgrade extras: 

CUDA Tutorial: ภาคปฐมบท - CUDA คืออะไรหว่า

คิดว่าหลายคนคงจะเคยผ่านหูผ่านตากับคำว่า CUDA กันมาบ้าง ไม่มากก็น้อย ซึ่งวันนี้ผมจะมาแนะนำกันครับว่า CUDA คืออะไร แล้วมันมีประโยชน์ยังไง ทำไมถึงมีหลายคนพูดถึงกันมากเหลือเกิน

Taxonomy upgrade extras: 

ทำไมต้อง Case-sensitive

สองสามอาทิตย์ก่อนมีรุ่นน้องมาถามผมว่า ภาษาที่เป็น Case-sensitive มีข้อดียังไง โอ ผมฟังคำถามแล้วก็แอบอึ้งไปสักพักเหมือนกัน เขียนโปรแกรมมาห้าปี ไม่เคยสงสัยเหมือนกันว่ามันมีดีหรือไม่ดีต่างกันยังไง (แต่ผมเข้าใจว่าคำถามนี้น่าจะเป็นการบ้าน มากกว่าข้อสงสัยนะครับ)

ผมเลยลองค้นข้อมูลดูก็เลยได้คำตอบมาดังนี้ครับ

1. คอมไพเลอร์ทำงานได้เร็วกว่า เนื่องจากไม่ต้องเสียเวลามาคอยเปลี่ยนตัวอักษรก่อนที่จะเอามาเปรียบเทียบกัน ข้อนี้ก็ดู make sense ดีครับ แต่ก็มีหลายคนแย้งว่า จริงๆแล้วแค่เปลี่ยนตัวอักษรให้เหมือนกัน แล้วค่อยเอามาเทียบก็ไม่น่าจะยากแล้วก็ช้าลงมากมายไม่ใช่หรอ

Taxonomy upgrade extras: 

N! มีกี่หลักกันหนอ

มีปัญหาของการเขียนโปรแกรมเพื่อหาจำนวนหลักของ $N!$ อยู่ โดยที่ $N$ นั้นมีค่าเป็นจำนวนมาก จะต้องเขียนโปรแกรมอย่างไรดี? วิธีการทั่วไปก็คือหาค่าของ $N!$ แล้วก็มานับจำนวนหลัก ด้วยการหาร 10 ไปเรื่อยๆแล้วดูว่ามีทั้งหมดกี่หลัก ตามโค้ดด้านล่างนี้

Taxonomy upgrade extras: 

นับจำนวนที่หาร N ลงตัวแบบเร็วๆ ตอนที่ 2 (เร็วกว่าเดิม ง่ายกว่าเดิม)

พอดีเมื่อวานผมเปิดอ่านหนังสือ Combinatorics ก็เห็นตัวอย่างโจทย์นับจำนวนที่หารลงตัวก็เลยบ้าจี้ลองเขียนโปรแกรมตามดู ซึ่งจริงๆแล้วเรามีวิธีที่สามารถคำนวนจำนวนที่หาร $N$ ลงตัวได้เร็วกว่า แล้วก็ง่ายกว่าด้วยครับ ไม่ต้องมานั่งหา prime ฮินดูอะไรนั่น เรียกได้ว่าสูงสุดคืนสู่สามัญจริงๆ ลองมาดูกันเลยครับ

วิธีนี้ก็จะประยุกต์จากเทคนิคที่ใช้หาค่า prime ในคราวก่อน นั่นคือวนรอบเท่ากับจำนวน $sqrt(N)$ ลองดูตัวอย่าง จำนวนที่หาร $N$ ลงตัวในแต่ละตัวดูครับ

Taxonomy upgrade extras: 

นับจำนวนที่หาร N ลงตัวแบบเร็วๆ

สมมติว่าเราต้องการหาว่าจำนวนทั้งหมดที่หาร N ลงตัวมีกี่จำนวน เช่น จำนวนที่หาร 10 ลงตัวมี 4 จำนวน ได้แก่ 1, 2, 5 และ 10 และจำนวนที่หาร 25 ลงตัวมีทั้งหมด 3 จำนวน ได้แก่ 1, 5, 25 วิธีที่ง่ายที่สุดก็คือการวนรอบตั้งแต่ค่า 1 จนถึง N แล้วดูว่ามีจำนวนใดบ้างที่หาร N ลงตัวก็จะนับเพิ่ม 1 ครั้ง ซึ่งก็จะได้โค้ดออกมาหน้าตาประมาณนี้ครับ

Taxonomy upgrade extras: 

Pages

Subscribe to remixman.net RSS