นี่คือโปรแกรม C++ สำหรับแยกส่วนจำนวนเต็ม (Integer Partition) สำหรับกรณีเฉพาะ ในโปรแกรมนี้ จะมีจำนวนเต็มบวก n ให้ และต้องสร้างวิธีที่เป็นเอกลักษณ์ทั้งหมด เพื่อนำเสนอ n เป็นผลรวมของจำนวนเต็มบวก
อัลกอริทึม
เริ่มต้น ฟังก์ชัน displayAllUniqueParts(int m): 1) ตั้งค่าดัชนีขององค์ประกอบสุดท้าย k ใน partition เป็น 0 2) เริ่มต้น partition แรกเป็นตัวเลขเอง p[k]=m 3) สร้างลูป while ที่พิมพ์ partition ปัจจุบันก่อน แล้วสร้าง partition ถัดไป ลูปหยุด เมื่อ partition ปัจจุบันมีค่าเป็น 1 ทั้งหมด 4) แสดง partition ปัจจุบันเป็น displayArray(p, k + 1) 5) สร้าง partition ถัดไป: 6) เริ่มต้น val = 0 หาค่าที่ไม่ใช่ 1 ขวามือสุดใน p[] อัปเดต val เพื่อรู้ว่าสามารถรองรับค่าได้เท่าไหร่ ถ้า k < 0 ค่าทั้งหมดเป็น 1 ไม่มี partition อีกแล้ว ลด p[k] ที่พบข้างต้นและปรับ val 7) ถ้า val มากกว่า ลำดับการเรียงจะถูกละเมิด แบ่ง val เป็นค่าต่างๆ ขนาด p[k] และคัดลอกค่าเหล่านี้ ที่ตำแหน่งต่างๆ หลัง p[k] คัดลอก val ไปตำแหน่งถัดไปและเพิ่มตำแหน่ง จบ
ตัวอย่างโค้ด
#include<iostream> using namespace std; void displayArray(int p[], int m) { //พิมพ์อาร์เรย์ for (int i = 0; i < m; i++) cout << p[i] << " "; cout << endl; } void displayAllUniqueParts(int m) { int p[m]; int k = 0; p[k] = m; while (true) { displayArray(p, k + 1); int val = 0; // เริ่มต้น val while (k >= 0 && p[k] == 1) { val += p[k]; // อัปเดต val k--; } if (k < 0) return; p[k]--; val++; //ถ้า val มากกว่า while (val > p[k]) { p[k + 1] = p[k]; val = val - p[k]; k++; } p[k + 1] = val; k++; } } int main() { cout << "Display All Unique Partitions of integer:7\n"; displayAllUniqueParts(7); return 0; }
ผลลัพธ์
Display All Unique Partitions of integer:7 7 6 1 5 2 5 1 1 4 3 4 2 1 4 1 1 1 3 3 1 3 2 2 3 2 1 1 3 1 1 1 1 2 2 2 1 2 2 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1
