Đệ quy - Liệt kê dãy nhị phân chiều dài n

[guardian0o0]

đề tài : liệt kê dãy nhị phân chiều dài n
em có bài giải này :

#include<iostream.h>#include<conio.h>#include<iomanip.h>int x[1000];int m,dem=0;void xuat();void duyetnhiphan(int i);void main(){   clrscr();    cout<<"nhap m=  ";    cin>>m;    duyetnhiphan(1);    getch();}void xuat(){   int i;    cout<<++dem<<setw(4);    for(i=1;i<=m;i++)   cout<<x[i]<<setw(4);    cout<<endl;}void duyetnhiphan(int i){  for(int j=0;j<=1;j++)    {x[i]=j;    if(i==m)    xuat();    else    duyetnhiphan(i+1);    }}

no' cho kết quả

1   0   0   02   0   0   13   0   1   0   4   0   1   15   1   0   06   1   0   17   1   1   08   1   1   1

thầy chỉ như sau:
đầu tiên duyetnhiiphan(1)
x[1]=0
x[2]=0
x[3]=0
i==m xuất ra 0 0 0
do đệ quy hoạt động theo cơ chế stack
nên típ theo x[3]=1
i==m xuất ra 0 0 1
tưởng hỉu rùi ai ngờ vìa nhà xem lai ko bít bước tip' theo giải thich' sao nữa
mấy anh chi giup dùm

[rox_rook]

Bài này đúng mà, đâu có sai gì đâu nhỉ, mình đọc giải thuật bạn rùi, chỉ có cái khởi tạo mãng theo kiểu pascal index 1 hơi ngượng 1 tí thôi, bắt đầu từ index 0 cũng chẳng sao hết.

1   0   0   02   0   0   13   0   1   0   4   0   1   15   1   0   06   1   0   17   1   1   08   1   1   1

Kết quả không hề sai. À quên nữa, đây là C++ not C, phân biệt cho rõ ràng.
Viết theo C++ phải dùng int main, include <iostream> , kiểu #include <iostream.h> outdated lâu rùi, không nên có biến là global, tập pass vào hàm cho quen. Global scope là rất tồi.

#include <iostream>#include <iomanip> using namespace std; void print(int arr[], int arrSize){  for(int x = 0; x < arrSize; ++x){      cout << arr[x] << setw(3);  }  cout << "\n--------------------\n";} void backtrack(int arr[], int position, int arrSize){  for(int mElem = 0; mElem <= 1; ++mElem){    arr[position] = mElem;    if(position == arrSize - 1){              print(arr, arrSize);    }    else{              backtrack(arr, position + 1, arrSize);    }  }} int main(){  const int arrSize = 100;  int A[arrSize] = {0};  int elem;  cout << "Elements generate : ";  cin >> elem;  backtrack (A, 0, elem);  return 0;}

Chắc nhờ ai move sang box C++ T_T!

[guardian0o0]

biết là đúng nhưng mà em cần hỏi theo cách của em thì đến đó giải thích ra sao cơ em làm đồ án mà nên cần giải thích cơ (theo bài và theo cách em đang giải thích đó huhuhu giúp dùm em cái)

[rox_rook]

biết là đúng nhưng mà em cần hỏi theo cách của em thì đến đó giải thích ra sao cơ em làm đồ án mà nên cần giải thích cơ (theo bài và theo cách em đang giải thích đó huhuhu giúp dùm em cái)

Em cần giải thích cái gì ?

i==m xuất ra 0 0 1
tưởng hỉu rùi ai ngờ vìa nhà xem lai ko bít bước tip' theo giải thich' sao nữa
mấy anh chi giup dùm

Ý tưởng chính của bài này là : cách sinh ra 1 dãy nhị phân là ta gặp số 0 thì gán = 1 chuyển tất cả các phần tử bên phải số đó = 0 cho tới khi toàn dãy = 1. Sách giải thuật của tác giả Lê Minh Hoàng giải thích bài này rất hay.

int main()
{
nếu lười
{ 
     thì vào box giải thuật down về mà đọc;
}
nếu siêng 
{
     Vẽ cái cây ra, mỗi nhánh là các bước lặp của đệ qui, phải suy nghĩ còn không thì làm sao giải thích lại cho thầy ?
Cái ý tưởng anh nêu rõ rồi đó, lấy 1 tờ giấy trắng, chạy tay với n = 3, post lên anh xem ;) anh sẽ giải thích tiếp ;
}
return 0;
} 

[guardian0o0]

đâu có lười đâu anh tại mới học mà ông thầy em theo tiêu chí tự học là chính hix . phần trên em nghe đến đó vìa nhà coi lai bước típ theo :
theo cơ chế stack thì tip theo x[2]=1 .tại sao nó ko len tới x[3]=1 rui i=m mới xuất mà lại xuất ra luôn 0 1 0 tai sao ko là 0 1 1

[rox_rook]

void backtrack(int arr[], int position, int arrSize)
{
  for(int mElem = 0; mElem <= 1; ++mElem){
    arr[position] = mElem;
    if(position == arrSize - 1){        
      print(arr, arrSize);
    }
    else{        
      backtrack(arr, position + 1, arrSize);
    }
  }
} 

Em lấy 1 tờ giấy 1 cây viết ra, chạy tay cho anh là hiểu, hiểu sâu nữa là, tập chạy tay cho quen . Em hiểu cách hàm hoạt động thì mỗi lần gặp lại hàm đó ( đệ qui ) em ghi nó ra đề vào level 1, tiếp thì level 2, chú ý thật kĩ giá trị của vòng lặp for, học 1 bài thật chắc thì mấy bài sau cũng sẽ không phải mệt nữa. Cứ tập trung chạy tay trước đi.

mới xuất mà lại xuất ra luôn 0 1 0 tai sao ko là 0 1 1

Tại vị thứ tự nó gọi là vậy !

[tuan_anhhhh]

anh rook ơi cho em hỏi câu lệnh :
using namespace std;
hàm int main()
có tác dụng gì vậy anh
câu lệnh return 0; trong thân hàm int main() nghĩa là sao vậy anh

[rox_rook]

using namespace std; 

Dùng để sử dụng các thư viện chuẩn của C++ thay vì
std::cout << thì có thể dùng cout << , std::cin >> có thể dùng cin >>.
Program nhỏ thì ok, viết program lớn thì không nên dùng using namespace std, dễ conflict với các namespace khác.

 int main() 

main cũng là hàm, int là kiểu trả về, kiểu trả về của main là 0 vậy thôi. Nhưng đa số complier sau này có hay không có return 0, nó vẫn tự động trả về 0, bỏ vào cũng không sao.
void main() đã bỏ từ lâu rồi, khoảng từ năm 2000. Chuẩn của C++ bắt buộc phải dùng int main().