Subsets

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: 

Subscribe to RSS - Subsets