[Bài toán] Biểu diễn n thành tổng các số tự nhiên không lớn hơn n.

Bài toán: Cho n là số nguyên dương. Biểu diễn n thành tổng các số tự nhiên không lớn hơn n.

Giải. Hai cách chia được gọi là đồng nhất nếu chúng có cùng các số hạng và chỉ khác nhau

về thứ tự sắp xếp. Bài toán được đặt ra là, cho số tự nhiên n, hãy duyệt mọi cách phân chia số n.

Chọn cách phân chia số n = b1 + b2 +...+bk với b1 > b2 >...> bk, và duyệt theo trình tự từ điển

ngược. Chẳng hạn với n = 7, chúng ta có thứ tự từ điển ngược của các cách phân chia như sau:

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

Như vậy, cách chia đầu tiên chính là n. Cách chia cuối cùng là dãy n số 1. Bây giờ chúng ta chỉ cần xây dựng thuật toán sinh kế tiếp cho mỗi cách phân chia chưa phải là cuối cùng.
Chương trình cài đặt như sau:
 

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define MAX 100
#define TRUE 1
#define FALSE 0
int n, C[MAX], k, count, Stop;
void Init(void){
 printf("\n Nhap n="); scanf("%d", &n);
 k = 1; count = 0; C[k] = n;
}
void Result(void){
 int i; count++;
 printf("\n Cach chia %d:", count);
 for (i = 1; i <= k; i++)
  printf("%3d", C[i]);
}
void Next_Division(void){
 int i, j, R, S, D;
 i = k;
 while (i>0 && C[i] == 1)
  i--;
 if (i>0){
  C[i] = C[i] - 1;
  D = k - i + 1;
  R = D / C[i];
  S = D % C[i];
  k = i;
  if (R>0){
   for (j = i + 1; j <= i + R; j++)
    C[j] = C[i];
   k = k + R;
  }
  if (S>0){
   k = k + 1; C[k] = S;
  }
 }
 else Stop = TRUE;
}
void Division(void){
 Stop = FALSE;
 while (!Stop){
  Result();
  Next_Division();
 }
}void main(void){
 Init();
 Division(); 
 _getch();

}

Cám ơn bạn đã đọc bài viết này. Hãy chia sẻ bài viết và bình luận ý kiến của bạn ở bên dưới.

Share this

Chào mừng bạn đến với SimpleCodeCJava Blog - Mục đích của chúng tôi khi thành lập blog này là muốn chia sẻ những kiến thức và kinh nghiệm lập trình mà chúng tôi đã học được với mong muốn giúp đỡ mọi người, giúp bạn rút ngắn được thời gian tìm hiểu cũng như việc giải quyết những vấn đề trong lập trình C và Java.