Sử dụng thuật toán Back Track để liệt kê các xâu nhị phân độ dài n (C/C++)

Sử dụng thuật toán Back Track để liệt kê các xâu nhị phân độ dài n (C/C++)

Xem lại lý thuyết thuật toán Back Track

>> Lý thuyết về thuật toán quay lui Back Track

Biểu diễn các xâu nhị phân dưới dạng b1, b2,..., bn, trong đó bi∈{0, 1 }. Thủ tục đệ qui Try(i) xác định bi với các giá trị đề cử cho bi là 0 và 1. Các giá trị này mặc nhiên được chấp nhận mà không cần phải thoả mãn điều kiện gì (do đó bài toán không cần đến biến trạng thái). thủ tục Init khởi tạo giá trị n và biến đếm count. thủ tục kết quả in ra dãy nhị phân tìm được. Chẳng hạn với n =3, cây tìm kiếm lời giải được thể hiện như hình.

Liệt kê các xâu nhị phân độ dài n bằng thuật toán Back Track

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

#include <stdio.h>

#include <alloc.h>

#include <conio.h>

#include <stdlib.h>

void Result(int *B, int n){

 int i;

 printf("\n ");

 for (i = 1; i <= n; i++)

  printf("%3d", B[i]);

}

void Init(int *B, int n){

 int i;

 for (i = 1; i <= n; i++)

  B[i] = 0;

}

void Try(int i, int *B, int n){

 int j;

 for (j = 0; j <= 1; j++){

  B[i] = j;

  if (i == n) {

   Result(B, n);

  }

  else Try(i + 1, B, n);

 }

}

void main(void){

 int *B, n; clrscr();

 printf("\n Nhap n=");

 scanf("%d", &n);

 B = (int *)malloc(n*sizeof(int));

 Init(B, n);

 Try(1, B, n);

 free(B);

 getch();

}
Bạn thấy bài viết này như thế nào?: 
Average: 10 (1 vote)
Ả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

 
Xây dựng chiến lược phễu khách hàng từ sự hỗ trợ đa kênh

Xây dựng chiến lược phễu khách hàng từ sự hỗ trợ đa kênh

Viết blog là một trong những điều quan trọng nhất của tiếp thị nội dung. Đây là một chiến lược tập trung vào việc tạo ra nội dung thú vị hoặc có giá trị cho đối tượng được xác định của bạn với mục tiêu thu hút

 Facebook Chat is one of the easiest way to chat with your friends and share your thoughts with your friends and family.

Add Images on Your Facebook Chat With Smileytime

Facebook Chat is one of the easiest way to chat with your friends and share your thoughts with your friends and family. 

[Google] Hướng dẫn đăng ký Google AdSense

[Google] Hướng dẫn đăng ký Google AdSense

Google AdSense là một mạng quảng cáo trung gian uy tín của Google dành cho các Publisher và Advertiser, trong bài viết này mình chỉ đề cập tới Publisher, tức là dành cho các chủ website bán quảng cáo trên trang web của mình.

Tomdesgin.vn

 

Drupal Services