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

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

 

Đặt Drupal Block vào bên trong một node

This tutorial will show you how to take a block and place it inside a Drupal node.

Thiết kế website: www.gemini-lights.com

Thiết kế website: www.gemini-lights.com

Gemini Lights is a high performance cycling light manufacturer. We design and build a range of bicycle lights to suit commuters, mountain bike buffs, and high-speed racers.

Kaspersky Internet Security, Virus

Cách sử dụng hiệu quả Kaspersky Internet Security 2010

Kaspersky Internet Security 2010 (KIS) ngoài tính năng quét virus mạnh mẽ còn có rất nhiều tiện ích đi kèm mà chưa chắc ai cũng biết tận dụng.

Wordpress Freelancer

 

Wordpress Freelancer