[Bài toán] Liệt kê các tập con k phần tử của tập n phần tử bằng thuật toán Back Track

Lý thuyết Back Track bạn có thể xem thêm ở đây.
     Biểu diễn tập con k phần tử dưới dạng c1, c2,.., ck, trong đó 1< c1các giá trị đề cử cho ci là từ ci-1+ 1 cho đến n - k + i. Cần thêm vào c0= 0. Các giá trị đề cử này
mặc nhiên được chấp nhận mà không cần phải thêm điều kiện gì. 

Chương trình cài đặt:

#include <conio.h> 
#include <stdio.h> 
#include <stdlib.h> 
#define MAX  100 
int B[MAX], n, k, count = 0;
void Init(void){
 printf("\n Nhap n="); scanf("%d", &n);
 printf("\n Nhap k="); scanf("%d", &k);
 B[0] = 0;
}
void Result(void){
 int i; count++;
 printf("\n Tap thu %d:", count);
 for (i = 1; i <= k; i++){
  printf("%3d", B[i]);
 }
 getch();
}
void Try(int i){
 int j;
 for (j = B[i - 1] + 1; j <= (n - k + i); j++){
  B[i] = j;
  if (i == k) Result();
  else Try(i + 1);
 }
}
void main(void){
 clrscr();
 Init();
 Try(1);
}

Cám ơn bạn đã đọc bài viết này. Hãy chia sẻ bài viết và bình luận ý kiến của bạn ở bên dưới.

Share this

Chào mừng bạn đến với SimpleCodeCJava Blog - Mục đích của chúng tôi khi thành lập blog này là muốn chia sẻ những kiến thức và kinh nghiệm lập trình mà chúng tôi đã học được với mong muốn giúp đỡ mọi người, giúp bạn rút ngắn được thời gian tìm hiểu cũng như việc giải quyết những vấn đề trong lập trình C và Java.