Bài tập nhóm môn Toán rời rạc phần 1 | Học viện Công nghệ Bưu chính Viễn thông

lOMoARcPSD| 37922327 lOMoARcPSD| 37922327 1.Ví dụ 2:
1.1. Đề bài: Liệt kê (duyệt) các xâu nhị phân có ộ dài n. 1.2. Sơ ồ thuật toán:
- Sơ ồ hàm sinh nhị phân: - Sơ ồ hàm main: lOMoARcPSD| 37922327 1.3. Viết code: - Hàm sinh nhị phân: lOMoARcPSD| 37922327 #include using namespace std; int n,k,a[100]; bool ok; void ktao(){ for(int i=1;i<=n;i++){ a[i]=0; } } void sinh(){ int i=n;
while(i>=1&&a[i]==1){ a[i]=0; --i; } if(i==0) ok=false; else a[i]=1; } 1.4. Kết quả: - Trường hợp n=4: lOMoARcPSD| 37922327 2.Bài tập 1:
2.1. Đề bài: Cho một hình chữ nhật gồm nxm hình vuông ơn vị. Hãy
liệt kê tất cả các ường i từ ỉnh cuối của ô vuông cuối cùng phía
bên trái ến ỉnh ầu của ô vuông trên cùng phía bên phải. Biết mỗi
bước i chỉ ược phép dịch chuyển sang bên phải hoặc lên trên
theo các cạnh của hình vuông ơn vị. 2.2. Sơ ồ thuật toán: lOMoARcPSD| 37922327 2.3. Viết code: - Hàm kiểm tra: lOMoARcPSD| 37922327 #include using namespace std; #define ll long long int n, m;
int dx[2] = {0, -1}, dy[2] = {1, 0}; int kq[105]; bool checkOut(int x, int y){ if
(x < 0 || y > m) return false; return true; } - Hàm xử lý: lOMoARcPSD| 37922327
void ql(int x, int y, int count){
if (x == 0 && y == m){ for
(int i = 0; i < count; i++){ if
(kq[i] == 1) cout << "L "; else cout << "P "; } cout << endl; return; }
for (int i = 0; i < 2; i++){ int newx = x + dx[i]; int newy = y + dy[i]; if (checkOut(newx, newy) == true){ kq[count] = i; count++; ql(newx, newy, count); count--; } } } - Hàm main: lOMoARcPSD| 37922327 int main(){
cin >> n >> m; ql(n, 0, 0); return 0; } 2.4. Kết quả: - Trường hợp n=4, m=4: 3. Bài tập 2:
3.1. Đề bài: Hãy liệt kê tất cả các xâu nhị phân có ộ dài n sao cho mỗi
xâu nhị phân có duy nhất một dãy k bit 1 liên tiếp. 3.2. Sơ ồ thuật toán:
- Sơ ồ hàm sinh nhị phân: lOMoARcPSD| 37922327
- Sơ ồ hàm kiểm tra k bit 1: lOMoARcPSD| 37922327 - Sơ ồ hàm main: lOMoARcPSD| 37922327 lOMoARcPSD| 37922327 Hàm sinh nhị phân: #include lOMoARcPSD| 37922327
- Hàm kiểm tra k bit 1 liên tiếp: bool check(){ bool check1=false; for(int i=1;i int dem=0; if(a[i]==1){ dem=1; for(int j=i+1;j<=n;j++){ if(a[i]==a[j]) dem++; if(a[i]!=a[j]||j==n){ i=j; break; } } } if(dem==k) check1=true; } if(check1) return true; else return false; } - Hàm main: lOMoARcPSD| 37922327 int main(){ cin >> n >> k; ktao(); ok=true; while(ok){ if(check()){ for(int i=1;i<=n;i++){ cout << a[i]; } cout << endl; } sinh(); } } lOMoARcPSD| 37922327 3.4. Kết quả:
- Trường hợp n=5 và k=3:
- Trường hợp n=6 và k=4: