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 (2 votes)
Ảnh của Tommy Tran

Tommy Tran 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
  • Phone/Zalo: (+84) 944 225 212
  • WhatsApp: (+84) 944 225 212
  • Line Messenger: (+84) 944 225 212
  • Email: [email protected]
  • Telegram Messenger: https:/t.me/tommytran0401

Quảng cáo việc làm

 

Thích hợp các bạn nữ mảng thợ may làm việc tại nước NGA

Đơn hàng Tuyển dụng 100 Thợ may đi Nga(đợt 1 tháng 3.2021, đợt 2 tháng 5.2021). Lương thực lãnh 800 USD, bao ăn ở, vé máy bay và visa, phí xuất cảnh(1800 USD)trả khi đi làm có lương. Bạn có thể liên hệ CÔNG TY qua Phone/Zalo: (+84) 944 225 212. Công ty sẽ tư vấn cho bạn.

Xem chi tiết: >>> https://bit.ly/3o9NOfR

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

 
Google “tẩy chay” với phần mềm gián điệp Carrier IQ

Google “tẩy chay” với phần mềm gián điệp Carrier IQ

Xung quanh những lùm xùm quanh vụ Carrier IQ làm gián điệp trên smartphone, đích thân chủ tịch điều hành của Google, Eric Schmidt tuyên bố ứng dụng Carrier IQ chính là gián điệp, và Google không bao giờ hỗ trợ ứng dụng này.

[Phần 1] Hướng dẫn tạo custom field : Field type

[Phần 1] Hướng dẫn tạo custom field : Field type

I have been experimenting with the Alpha release of Drupal 8 and so I'm sharing some of my experiences so that you can avoid the pitfalls I have encountered.

Google

5 lý do để Apple không kiện Google

Mặc dù Apple đã dành chiến thắng quyết định trong vụ kiện với Samsung, có rất nhiều lý do để họ không tiếp tục tấn công nhà phát triển nền tảng Android là Google.

Wordpress Freelancer

 

Wordpress Freelancer