Thuật Toán Sinh Kế Tiếp – Next Generation | **Xuân Thanh**

Trang chủ » Sinh Kế Tiếp » Thuật Toán Sinh Kế Tiếp – Next Generation | **Xuân Thanh**

Có thể bạn quan tâm

1.Định nghĩa: Thuật toán sinh kế tiếp dùng để giải quyết các bái toán thỏa mãn các điều kiện:

– Xác định được trật tự các nghiệm.Biết được nghiệm đầu và nghiệm cuối cùng. – Xây dựng được thuật toán tử một nghiệm(cấu hình) chưa phải là nghiệm cuối cùng ta đều sinh ra một cấu hình đứng sau nó.(Next generation) 2.Thuật toán: procedure NextGeneration; beginwhile(cấu hình chưa phải là cuối cùng) do begin <Đưa ra cấu hình hiện tại> <Sinh ra cấu hình kế tiếp> end end;

Algorithms in C++, Parts 1-4 The Algorithm Design Manual

3.Bài toán thí dụ Thuật toán sinh kế được áp dụng vào giải rất nhiều bài toán.Một thí dụ điển hình là liệt kê dãy nhị phân có độ dài biết trước. (1).Ta dễ dàng xác định được cấu hình đầu tiên là 0000….0(độ dài n) và dãy cuối cùng là 1111…1.Để xác định được dãy nhị phân đứng sau ta lấy dãy nhị phân hiện tại + 1(bit 1).Ví dụ: dãy nhị phân hiện tại 000 —> dãy kế tiếp 000+1=001. =>Thỏa mãn điều kiện thứ nhất. (2).Xây dựng thuật toán sinh kế tiếp: – khởi tạo dãy nhị phân ban đầu là 000…0 – Duyệt dãy nhị phân từ cuối, nếu phần tử cuối là bit 0 thì thay nó bằng bit 1.Còn các bit khác được duyệt qua được gán =1.(Next generation) while(chưa về đầu dãy nhị phân) do i=n; while(s[i]==1) do begin s[i]=0; i– end s[i]=1; end;

Code viết bằng C:

#include<stdio.h> #define MAX 100 int s[MAX]; int i,n,ok=1; void init(){ puts("Nhap vao do dai day nhi phan:"); scanf("%d",&n); for(i=1;i<=n;i++){ s[i]=0; } } void next_string(){ i=n; while(s[i]==1){s[i]=0;i--;}//Duyet qua cac phan tu con lai neu la 1 thi doi thanh 0 if(i==0){ok=0;} s[i]=1;//Neu phan tu dau la 0 thi doi sang 1 } void result(){   for(i=1;i<=n;i++){ printf("%4d",s[i]); } printf("\n"); } int main(){ init();//Thiet lap cau hinh ban dau while(ok){ result();//dua ra cau hinh hien tai next_string();//Sinh ra cau hinh ke tiep } } Algorithms in C++, Parts 1-4 The Algorithm Design Manual

Technorati Tags: Thuật toán

Chia sẻ:

  • Facebook
  • X
  • Reddit
Thích Đang tải...

Có liên quan

Từ khóa » Sinh Kế Tiếp