เขียนโปรแกรมทำ partition number
สืบเนื่องจากวันนี้ไปในมหาลัย มีเพื่อนคนหนึ่งไว้วานให้เขียนโปรแกรม ที่ทำการหาว่า จำนวนเต็ม 49 สามารถเขียนเป็นผลบวกของจำนวนนับ ไม่เกิน 12 ตัวได้กี่แบบ แล้วมีอะไรบ้าง
เราเขียนเป็นโปรแกรมด้วยภาษา c ได้ดังนี้
#include<stdio.h> #define NUM 49 #define PAR 12 int sum(int *data) { int a; int i; a = 0; for(i=0;i<PAR;i++) a+=data[i]; return a; } int TRY(int *data,int radix,int cur) { int data2[PAR]; int i,j; int sumData2; for(i=0;i<PAR;i++) { data2[i] = data[i]; } sumData2 = sum(data2); for(i=0;(i<=NUM-sumData2)&&(i<=cur);i++) { data2[radix] = i; if(radix<PAR) { TRY(data2,radix+1,i); } else { if(sum(data2)==NUM) { printf("(%d",data2[0]); for(j=1;j<PAR;j++) { printf(",%d",data2[j]); } printf(")\n"); } break; } } } int main() { int data[PAR]; int i; for(i=0;i<PAR;i++) data[i]=0; TRY(data,0,NUM); }
แล้วทดสอบด้วยการพิมพ์คำสั่งดังแสดง
sukoom@sk-laptop:~\$ gcc test.c
sukoom@sk-laptop:~\$ time ./a.out >out.dat
real 0m0.982s
user 0m0.944s
sys 0m0.016s
sukoom@sk-laptop:~\$ wc -l out.dat
85067 out.dat
รวมนับได้ 85067 ตัวพอดี ใช้เวลารัน 0.98 วินาที
คำสั่ง wc เป็นคำสั่งใช้นับคำในไฟล์นะครับ สำหรับบางคนที่ไม่ทราบ wc -l ก็เป็นการนับ บรรทัดในไฟล์แทน
