โจทย์
กำหนดจำนวนเต็ม n ให้พิมพ์ตัวเลขที่ประกอบด้วยหลัก 0 และ 1 เท่านั้น (เช่น 1, 10, 11) ซึ่งผลรวมเท่ากับ n
ตัวอย่าง
Input: 31 Output: 10 10 10 1 (10+10+10+1 = 31) Input: 35 Output: 10 10 1 1 1 1 11 (10+10+1+1+1+1+11 = 35)
อัลกอริทึม
ใช้วิธี Greedy: ลบ 10 ทีละอันจนเหลือ ≤ 20 แล้วลบ 11 ถ้าได้ 0 มิฉะนั้นลบ 1 ทีละอัน
- m = n % 10, a = n
- while (a > 0):
- ถ้า a/10 > 0 และ a > 20: a -= 10, พิมพ์ "10"
- ถ้า a - 11 == 0: a -= 11, พิมพ์ "11"
- มิฉะนั้น: พิมพ์ "1", a--
โค้ดภาษา C
#include <stdio.h>
int findNumbers(int n) {
int m = n % 10, a = n;
while (a > 0) {
if (a / 10 > 0 && a > 20) {
a = a - 10;
printf("10 ");
} else if (a - 11 == 0) {
a = a - 11;
printf("11 ");
} else {
printf("1 ");
a--;
}
}
return 0;
}
int main() {
int N = 35;
findNumbers(N);
return 0;
}ผลลัพธ์
10 10 1 1 1 1 11
หมายเหตุ: อัลกอริทึมนี้ให้คำตอบหนึ่งคำตอบที่เป็นไปได้ ไม่ได้ค้นหาทุกคำตอบที่เป็นไปได้
