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: 10 (84 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

 
Status trên Facebook lập kỷ lục khó tin

Status trên Facebook lập kỷ lục khó tin

Số ký tự cho phép trong một lần cập nhật trạng thái đã tăng lên ngưỡng 63.206 rồi nhé!

Steve Jobs đã đúng: Google đang đi theo con đường của Microsoft

Steve Jobs đã đúng: Google đang đi theo con đường của Microsoft

Thời điểm năm ngoái, khi Larry Page chuẩn bị nhận trách nhiệm lãnh đạo Google, CEO hiện tại của “gã khổng lồ” đã tới gặp Steve Jobs

Google, Email Quickly

Gmail Tip – Add Multiple attachments on Email Quickly

Gmail is one of the popular email service which has lots of new feature and addons. If you are the Gmail user like us then here a Gmail Tip which allows you to add multiple attachments on Email quickly.

Công ty diệt chuột T&C

 

Diet con trung