เขียนโปรแกรมทำ 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 ก็เป็นการนับ บรรทัดในไฟล์แทน

เรื่องที่เกี่ยวข้อง

  • ไม่มีเรื่องที่เกี่ยวข้อง

Leave a Reply

You must be logged in to post a comment.