Biểu diễn n thành tổng các số tự nhiên không lớn hơn n bằng C/C++

Biểu diễn n thành tổng các số tự nhiên không lớn hơn n bằng C/C++

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 thuật: 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();


}
Bạn thấy bài viết này như thế nào?: 
Average: 9.3 (3 votes)
Ảnh của Tommy Tran

Tommy owner Express Magazine

Drupal Developer having 9+ year experience, implementation and having strong knowledge of technical specifications, workflow development. Ability to perform effectively and efficiently in team and individually. Always enthusiastic and interseted to study new technologies

  • Skype ID: tthanhthuy

Advertisement

 

jobsora

Dich vu khu trung tphcm

Dich vu diet chuot tphcm

Dich vu diet con trung

Quảng Cáo Bài Viết

 
Amazon: 1 triệu thiết bị Kindle được bán ra mỗi tuần

Amazon: 1 triệu thiết bị Kindle được bán ra mỗi tuần

Amazon đang rất thành công với các thiết bị Kindle, đặc biệt là Kindle Fire. Hiện số lượng thiết bị Kindle bán ra mỗi tuần đã tăng lên 1 triệu...

Check log thấy database semaphore đang bị crash và cách repair trong Drupal 7

Check log thấy database semaphore đang bị crash và cách repair trong Drupal 7

Sự cố thường gặp trong Drupal 7 là table semaphore' is marked as crashed and should be repaired. Bạn có thể kiểm tra log lỗi ở đường dẫn /var/lib/mysql file vps15.superdata.vn.err và repair theo hướng dẫn sau :

Add Cool Effects on Your Android Mobile Images with Pho.to Lab app

Add Cool Effects on Your Android Mobile Images with Pho.to Lab app

Are you an Android phone user and want to add some cool effects on your clicked images.

Tomdesgin.vn

 

Drupal Services