Đề tài Trình bày về nội dung vận dụng những kiến thức về phương pháp luận, sáng tạo để giải quyết một vấn đề nào đó trong tin học

Trường Đại học Công Nghệ Thông Tin Đại học Quốc gia Hồ Chí Minh ------------------ Bộ môn: Phương pháp luận sáng tạo khoa học Bài luận : Trình bày về nội dung vận dụng những kiến thức về phương pháp luận, sáng tạo để giải quyết một vấn đề nào đó trong tin học. GVHD: GS.TSKH Hoàng Văn Kiếm Sinh viên: Nghiêm Xuân Hiệp MSSV: 06520155 Khoa: MMT&TT 01 I. Bài toán : Trong bài toán Josephus, một nhóm binh sĩ bị kẻ thù bao vây và một binh sĩ được chọn để đi cầu cứu. Việc chọn thực hiện theo cách sau: Một số nguyên n và một binh sĩ được chọn một cách ngẫu nhiên. Các binh sĩ được sắp xếp theo vòng tròn, và họ đếm bắt đầu từ binh sĩ được chọn ngẫu nhiên. Khi đạt đến n, binh sĩ tương ứng được lấy ra khỏi vòng và việc đếm lại bắt đầu từ binh sĩ tiếp theo. Quá trình này cứ tiếp tục cho đến khi chỉ còn lại một binh sĩ. Đó là người sẽ được chọn để đi cầu cứu. Viết thuật toán cài đặt cách chọn và tìm ra binh sĩ sẽ được chọn. II. Giải quyết bài toán: 1. Phân tích bài toán: Binh sĩ 3 Binh sĩ 2 Binh sĩ 6 Binh sĩ 5 Binh sĩ 4 Binh sĩ 1 Binh sĩ 7 Binh sĩ m Binh sĩ ….. Các binh sĩ được sắp xếp đứng thành vòng tròn và có thứ tự lần lượt từ 1 đến m (với m là số binh sĩ). Binh sĩ 3 Binh sĩ 2 Binh sĩ 6 Binh sĩ 2 Binh sĩ 5 Binh sĩ 4 Binh sĩ 1 Binh sĩ 7 Binh sĩ m Binh sĩ ….. Chọn n = 3 Binh sĩ thứ 2 được chọn ngẫu nhiên Binh sĩ thứ 4 sẽ bị loại sau khi đếm đến n. Binh sĩ thứ 7 sẽ bị loại sau khi đếm đến n. : Binh sĩ thứ n bị loại ra. Chọn n là một số ngẫu nhiên và chọn một binh sĩ ngẫu nhiên (n nguyên dương) - Chọn n là một số ngẫu nhiên và chọn một binh sĩ ngẫu nhiên (n nguyên dương). - Đếm lần lượt từ vị trí binh sĩ ngẫu nhiên đầu tiên được chọn cho đến vị trí của binh sĩ thứ n thì loại binh sĩ đó ra, và tiếp tục đếm từ binh sĩ kế tiếp cho đến vị trí thứ n tiếp theo..... - Khi đó binh sĩ nào là người cuối cùng còn lại sẽ là người được chọn để đi cầu cứu. 2. Giải quyết vấn đề - bài toán trong tin học: Đối với bài toán này, điều ta quan tâm là số lượng các binh sĩ, số thứ tự các binh sĩ, số thứ tự của binh sĩ đầu tiên được chọn, một số n nguyên dương ngẫu nhiên với điều kiện n phải nhỏ hơn hoặc bằng số lượng các binh sĩ, và cuối cùng là tìm ra phần tử (binh sĩ) cuối cùng. ­ Dùng phương pháp trực tiếp cùng với các nguyên lý, nguyên tắc để giải quyết bài toán trên. Đặc điểm của cách giải quyết này là đều xác định trực tiếp được lời giải qua một thủ tục tính toán (công thức, hệ thức, định luật,…) hoặc qua các bước căn bản để có được lời giải. Đối với phương pháp này, việc giải quyết bài toán trên máy tính chỉ là thao tác lập trình hay là sự chuyển đổi lời giải từ ngôn ngữ bên ngoài sang các ngôn ngữ được sử dụng trong máy tính. Với bài toán này, ta sẽ dùng ngôn ngữ lập trình thông dụng là C để giải quyết bài toán trên máy tính. Để thực hiện tốt phương pháp trực tiếp, chúng ta áp dụng các nguyên lý sau: Nguyên lý 1: Chuyển đổi dữ liệu bài toán thành dữ liệu của chương trình, có nghĩa là “Dữ liệu của bài toán sẽ được biểu diễn lại dưới dạng các biến của chương trình thông qua các quy tắc xác định của ngôn ngữ lập trình”. Gọi số lượng các binh sĩ là : m. Số thứ tự (vị trí) của các binh sĩ : sẽ được biểu diễn dưới dạng 1 danh sách ta sẽ phân tích ở dưới. Trong đó mỗi binh sĩ là 1 phần tử element_type và số thứ tự này sẽ đại diện cho mỗi element_type đó. Số thứ tự của binh sĩ được chọn ngẫu nhiên đầu tiên : k. Một số đếm n ngẫu nhiên : n. Phần tử cuối cùng được chọn trong danh sách chính là binh sĩ được chọn : element. m, k, n, element_type, element đều là các số nguyên dương. Nguyên lý 2: Chuyển đổi quá trình tính toán của bài toán thành các cấu trúc của chương trình, có nghĩa là “Mọi quá trình tính toán đều có thể mô tả và thực hiện dựa trên ba cấu trúc cơ bản: Cấu trúc tuần tự, cấu trúc rẽ nhánh và cấu trúc lặp”. Ở đây ta sẽ sử dụng cấu trúc tuần tự: để biểu diễn các phần tử (binh sĩ) ta dùng một list (danh sách) dạng : node. Trong node ta quan tâm đến phần tử đầu tiên và phần tử cuối cùng: first và last. first (element_type) next (element_type) last (element_type) ........ ........ Cấu trúc node Nguyên lý 5 : Phân chia bài toán đầu thành những bài toán nhỏ hơn, có nghĩa là “Mọi vấn đề bài toán đều có thể giải quyết bằng cách phân chia thành những vấn đề bài toán nhỏ hơn”. Đối với bài toán trên việc phân nhỏ bài toán thành từng phần (thành các hàm) thay vì xử lý chúng chỉ trong 1 hàm void() là rất cần thiết không những có ý nghĩa về mặt trình bày một đoạn code dễ nhìn mà còn có nhiều ý nghĩa khác kể cả việc sữa chữa một cách dễ dàng.... void khoi_tao_ds(struct node **first, struct node **last) void insert( element_type e, struct node **first, struct node **last) void xoa_ds( struct node **first, struct node ** last) void tao_ds( struct node **first, struct node **last, int n) void print_ds( struct node *first) void Josephus( struct node **first, struct node ** last, int m, int n, int k) void main() Nguyên lý 3: Biểu diễn các tính toán chính xác, có nghĩa là “Chương trình tính toán theo các biểu thức chính xác không đồng nhất với quá trình tính toán chính xác về mặt hình thức”. Thay vì thực tế con người sẽ đếm lần lượt và loại dần các binh sĩ thứ n cho đến khi còn lại binh sĩ cuối cùng, ở đây ta thấy hàm Josephus sẽ chạy vòng lặp (cho đến khi m = 1) và so sánh các điều kiện để cuối cùng tìm ra được phần tử còn lại duy nhất. void Josephus( struct node **first, struct node **last, int n, int m, int k) { struct node *tmp, *b; int i; tmp = *first; for( i = 0; i<k; i++) tmp = tmp -> next; do{ for(i = 0; i<n-2; i++) if( tmp -> next != NULL) tmp = tmp -> next; else tmp = *first; if( tmp ->next == NULL) { tmp = (*first) -> next; free(first); *first = tmp; } else { b = tmp -> next; if( tmp -> next -> next != NULL) { tmp -> next = tmp -> next -> next; tmp = tmp -> next; } else { tmp -> next = NULL; tmp = *first; } free(b); // xoa node b } m--; // giam so luong phan tu di 1 }while( m>1); // chay vong lap cho den khi m = 1 *last = *first; // gan phan tu con lai cuoi cung cho con //tro **first } Nguyên tắc trung gian : Sử dụng đối tượng trung gian, chuyển tiếp. Trong nhiều chương trình máy tính, người ta có thể viết những biểu thức tính toán phức tạp trên cùng một hàng. Điều này tuy chẳng ảnh hưởng đến kết quả tính toán cuối cùng nhưng sẽ làm cho việc đọc biểu thức trở lên khó khăn hơn. Trong trường hợp đó ta dùng biến trung gian để làm cho chương trình dễ hiểu hơn. Ở đây ta thấy hàm print_ds() sử dụng phần tử node trung gian là tmp để duyệt danh sách và in ra các phần tử. void print_ds(struct node **first) { struct node *tmp; // su dung node trung gian tmp de duyet tmp = first; // gan tmp tai vi tri phan tu dau tien printf(“Cac gia tri cua danh sach: ”); while( tmp != NULL) // duyet danh sach va in ra cac phan tu cho { // den khi het danh sach printf(“%d”, tmp ->element); // in ra so thu tu cac tmp = tmp -> next; // phan tu } } Nguyên tắc chứa trong : Một đối tượng được đặt bên trong một đối tượng khác và bản thân nó lại chứa trong một đối tượng thứ ba…. Một đối tượng chuyển động xuyên suốt bên trong một đối tượng khác. - Trong tin học, một chương trình chứa nhiều chương trình con. Trong chương trình con lại chứa nhiều chương trình con khác. - Ở đây ta thấy danh sách node chẳng qua là một con trỏ (node *next) chạy suốt trỏ đến một mảng các phần tử (element_type), hay có thể nói next là một đối tượng chuyển động xuyên suốt bên trong danh sách node. ­ Code bài toán Josephus hoàn chỉnh : #include typedef int element_type; struct node { element_type element; struct node *next; }; void khoi_tao_ds(struct node **first, struct node ** last) { *first = *last = NULL; } void insert(element_type e, struct node **first, struct node **last) { struct node *tmp; tmp = (struct node*) malloc(sizeof(struct node)); tmp -> element = e; tmp -> next = NULL; if(*first == NULL) *first = *last = tmp; else { (*last) -> = tmp; (*last) = (*last) -> next; } } void xoa_ds(struct node **first, struct node **last) { struct node *tmp; tmp = *first; while( tmp != NULL) { tmp = (*first) -> next; free(*first); *first = tmp; } *first = *last = NULL; } void tao_ds( struct node **first, struct node **last, int n) { element_type e; for ( e=0; e<n; e++) insert(e, first, last); } void print_ds(struct node **first) { struct node *tmp; tmp = first; printf(“Cac gia tri cua danh sach: ”); while( tmp != NULL) { printf(“%d”, tmp ->element); tmp = tmp -> next; } } void Josephus( struct node **first, struct node **last, int n, int m, int k) { struct node *tmp, *b; int i; tmp = *first; for( i = 0; i<k; i++) tmp = tmp -> next; do{ for(i = 0; i<n-2; i++) if( tmp -> next != NULL) tmp = tmp -> next; else tmp = *first; if( tmp ->next == NULL) { tmp = (*first) -> next; free(first); *first = tmp; } else { b = tmp -> next; if( tmp -> next -> next != NULL) { tmp -> next = tmp -> next -> next; tmp = tmp -> next; } else { tmp -> next = NULL; tmp = *first; } free(b); } m--; }while( m>1); *last = *first; } void main() { struct node *first; int n,m,k; khoi_tao_ds(&first, &last); printf(“\nCho biet so luong binh si: ”); scanf(“%d“, &m); tao_ds(&first, &last, m); print_ds(first); printf(“\nCho biet so thu tu binh si duoc chon: ”); scanf(“%d”, &k); printf(“\nCho biet gia tri dem: ”); scanf(“%d”, &n); Josephus(&first, &last, m, n, k); printf(“\nNguoi duoc chon co thu tu la : %d”, first -> element); xoa_ds(&first, &last); getch(); }