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 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

 
Google Adsense

Kiếm tiền Google Adsense thành công 100%

Google Adsense (GA) là một dịch vụ miễn phí để các nhà phát triển web kiếm tiền bằng cách hiển thị quảng cáo của Google. GA bao gồm GA Search, GA Content ...

Máy tính Lenovo tại Trần Anh vừa xuất kho đã lỗi

Máy tính Lenovo tại Trần Anh vừa xuất kho đã lỗi

Máy Lenovo G480 vừa xuất tại kho của Công ty Trần Anh đã xuất hiện lỗi sọc đen dài tại màn hình góc phải, dẫn tới sập màn hình không thể cài đặt. Đây là những băn khoăn được khách hàng gửi đến các cơ quan báo chí phản ánh.

Mansour bin Zayed Al Nahyan - chủ tịch tập đoàn Abu Dhabi United Group, sở hữu Man City

Man City khát khao vô địch UEFA Champions League 2020

Man City cùng các nhà tài trợ không ngại thao túng hợp đồng. Khi Chumillas hỏi Pearce rằng liệu họ có thể thay đổi thời gian ký hợp đồng tài trợ,