Bài tập Kỹ thuật lập trình - Bài tập 5: Đệ quy, cấp phát động và kiểu con trỏ - Khoa Khoa học và Kỹ thuật máy tính - Đại học BK - ĐHQG TP Hồ Chí Minh

Nội dung text: Bài tập Kỹ thuật lập trình - Bài tập 5: Đệ quy, cấp phát động và kiểu con trỏ - Khoa Khoa học và Kỹ thuật máy tính - Đại học BK - ĐHQG TP Hồ Chí Minh

1. TRƯỜ NG ĐAỊ HOC̣ BÁ CH KHOA TP.HCM Khoa Khoa hoc̣ & Kỹ thuật Máy tính • Tính toán tam giác Pascal đến mức n và lưu vào 1 mảng 2 chiều (Yêu cầu: mảng 2 chiều này phải được cấp phát động vừa đủ với kích thước của tam giác Pascal). • Xuất mảng 2 chiều này ra màn hình. Định nghĩa: Tam giác Pascal chứa các hệ số khi khai triển nhị thức Newton (x + 1)n. Ví dụ: n = 4. Kết quả xuất ra màn hình sẽ là: 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 #include using namespace std; void initpascal(int &a, int n){ a=new int*[n+1]; for(int i=0;i<n+1;i++){ a[i]=new int[i+1]; for(int j=0;j<i+1;j++){ a[i][j]=0; } } } void tamgiacpascal(int &a, int n){ for(int i=0;i<n+1;i++){ a[i][0]=a[i][i]=1; for(int j=1;j<i;j++){ a[i][j]=a[i-1][j-1]+a[i-1][j]; } } } void output(int c, int n) { for (int i = 0; i < n+1; i++) { for (int j = 0; j < i+1; j++) { cout<<c[i][j]<<"\t"; } cout<<endl; } } void deleteMatrix(int d, int n) { for (int i = 0; i < n+1; i++) { delete [] d[i]; } delete []d; } int main() { int n; Kỹ thuật lập trình 501127 – HK2/2011-2012 2
2. TRƯỜ NG ĐAỊ HOC̣ BÁ CH KHOA TP.HCM Khoa Khoa hoc̣ & Kỹ thuật Máy tính transposeMatrix(a, m, n, b); cout<<"The transposing matrix : "<<endl; output(b, n, m); deleteMatrix(a, m); deleteMatrix(b, n); } } Hãy hiện thực hàm init() và hàm transposeMatrix() thỏa mãn các yêu cầu sau: • init(): tạo ra ma trận a (m hàng , n cột) chứa các số nguyên bằng cách cấp phát động cho biến con trỏ a. Sau đó khởi tạo ma trận a chứa các số nguyên ngẫu nhiên từ 0 9 ( Gợi ý : sử dụng hàm rand() trong thư viện stdlib.h đã được include sẵn). • transposeMatrix() : tạo ma trận b (n hàng, m cột) chứa các số nguyên bằng cách cấp phát động cho biến con trỏ b. Sau đó, tạo ra ma trận chuyển vị của ma trận a và chứa vào ma trận b. void init(int &a, int m, int n){ srand(time(NULL)); a=new int*[m]; for(int i=0;i<m;i++){ a[i]=new int[n]; for(int j=0;j<n;j++){ a[i][j]=rand()%10; } } } void transposeMatrix(int a, int m,int n, int &b){ b=new int*[n]; for(int i=0;i<n;i++){ b[i]=new int[m]; for(int j=0;j<m;j++){ b[i][j]=a[j][i]; } } } Bài 6. Viết chương trình giải bài toán tháp Hà Nội. Mô tả: Dạng thường gặp nhất của trò chơi này gồm một bộ các đĩa kích thước khác nhau, có lỗ ở giữa, nằm xuyên trên ba cái cọc. Bài toán đố bắt đầu bằng cách sắp xếp các đĩa theo trật tự kích thước vào một cọc sao cho đĩa nhỏ nhất nằm trên cùng, tức là tạo ra một dạng hình nón. Yêu cầu của trò chơi là di chuyển toàn bộ số đĩa sang một cọc khác, tuân theo các quy tắc sau: một lần chỉ được di chuyển một đĩa một đĩa chỉ có thể được đặt lên một đĩa lớn hơn (không nhất thiết hai đĩa này phải có kích thước liền kề, tức là đĩa nhỏ nhất có thể nằm trên đĩa lớn nhất) Kỹ thuật lập trình 501127 – HK2/2011-2012 4
3. TRƯỜ NG ĐAỊ HOC̣ BÁ CH KHOA TP.HCM Khoa Khoa hoc̣ & Kỹ thuật Máy tính • Xuất ma trận xoắn ốc ra màn hình. Định nghĩa: Ma trận xoắn ốc là ma trận chứa đựng các số từ 1 (m x n) được sắp xếp có thứ tự tăng dần theo hình xoắn ốc. Ví dụ : m = 3, n = 5. Kết quả xuất ra màn hinh sẽ là: 1 2 3 4 5 12 13 14 15 6 11 10 9 8 7 m = 4, n = 4. Kết quả xuất ra màn hình sẽ là: 1 2 3 4 12 13 14 5 11 16 15 6 10 9 8 7 #include using namespace std; void init(int &a, int m, int n){ a=new int*[m]; for(int i=0;i<m;i++){ a[i]=new int[n]; for(int j=0;j<n;j++){ a[i][j]=0; } } } void mtxoanoc(int &a, int m, int n){ int i,j,istart,jstart,inccol,incrow,max; i=j=istart=jstart=0; inccol=1; incrow=0; max=m*n; for(int key=1;key<=max;key++){ a[i][j]=key; i+=incrow; j+=inccol; if(i==istart&&j==jstart){ incrow=0; inccol=1; i=j=++istart; n ; m ; }else if(i==istart&&j==n-1){ incrow=1; inccol=0; }else if(i==m-1&&j==n-1){ incrow=0; Kỹ thuật lập trình 501127 – HK2/2011-2012 6
4. TRƯỜ NG ĐAỊ HOC̣ BÁ CH KHOA TP.HCM Khoa Khoa hoc̣ & Kỹ thuật Máy tính void main() { int m,n; cout >m>>n; if (m n) { cout<<"Invalid input !"<<endl; } else { cout<<"The result is : "<<endl; printCombinations(m,n); } } Hãy hiện thực hàm printCombinations() để sinh ra tất cả các tổ hợp chập m của n phần tử từ 1 n. Yêu cầu trong hàm printCombinations() phải gọi 1 hàm đệ qui để thực hiện việc sinh ra tất cả các tổ hợp này. Ví dụ : m = 2 , n = 4. Kết quả xuất ra màn hình sẽ là: 1 2 1 3 1 4 2 3 2 4 3 4 void generate(int a[], int m, int n, int k){ for(int j=a[k-1]+1;j<=n-m+k;j++){ a[k]=j; if(k==m){ for (int i=1;i<=m;i++) cout<<a[i]<<" "; cout<<endl; }else generate(a,m,n,k+1); } } void printCombinations(int m, int n) { int k=1; int a[m+1]; a[0]=0; generate(a,m,n,k); } Bài 10. Bằng cách sử dụng kỹ thuật hàm đệ quy để viết chương trình kiểm tra xem đảo ngược một chuỗi có phải là chính nó hay không. //returns 1 if a[] is a palindrome, 0 otherwise int ispalindrome(char a[], int n) int ispalindrome(char a[], int n){ static int pos=0; Kỹ thuật lập trình 501127 – HK2/2011-2012 8