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: asaleotestf@gmail.com
  • 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

 
Quảng cáo tìm kiếm tại VN: Sơ khai nhưng tiềm năng

Quảng cáo tìm kiếm tại VN: Sơ khai nhưng tiềm năng

Dung lượng thị trường Quảng cáo Tìm kiếm Việt Nam vào khoảng 100 triệu USD. Hiện tại, năm 2010 doanh số ngành mới chiếm khoảng 5 triệu USD. Vì vậy có thể nói tiềm năng thị trường còn rất lớn.

www.OSTraining.com miễn phí 1 tháng học Drupal

www.OSTraining.com miễn phí 1 tháng học Drupal

Drupal Global Training Days is an initiative by the Drupal Association (D.A.) to introduce new and beginning users to Drupal.

Pin nhiên liệu sẽ là lựa chọn mới cho thiết bị di động

Pin nhiên liệu sẽ là lựa chọn mới cho thiết bị di động

Một nghiên cứu mới đây về pin nhiên liệu được ước tính, sẽ có gần 5 triệu pin dùng hydro hoặc methanol cho điện thoại di động và máy tính bảng vào năm 2017.