Ung Dung Kieu Xau De Giai Cac Bai Toan So - Tài Liệu Text - 123doc

Tải bản đầy đủ (.docx) (37 trang)

1. Trang chủ
>>
2. Công Nghệ Thông Tin
>>
3. Kỹ thuật lập trình

ung dung kieu xau de giai cac bai toan so

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (160.3 KB, 37 trang )

TÓM TẮT NỘI DUNG SÁNG KIẾNĐặt vấn đề: Môn Tin học đã được đưa vào giảng dạy chính thức trongchương trình bậc học trung học phổ thông. Lập trình là một chủ đề khó trongchương trình Tin học ở bậc phổ thông. Lượng thời gian 1.5 tiết/tuần chỉ giúp họcsinh biết sử dụng ngôn ngữ lập trình Pascal để viết chương trình giải bài toántrên máy tính. Để giải một bài toán trên máy tính ngoài việc nắm vững ngôn ngữlập trình, tư duy toán học đòi hỏi học sinh phải có sự sáng tạo để giải đượcnhững bài toán phức tạp. Cái khó ở đây không phải là ngôn ngữ mà là thuật toán.Thế nhưng có thuật toán rồi việc cài đặt thuật toán đó như thế nào là cả một vấnđề. Trong các kì thi học sinh giỏi Tỉnh thì Môn Tin học là thi lập trình giải cácbài toán trên máy tính. Trong đó tập trung là dạng bài toán số. Có những bài toánsố nếu ta biết kết hợp sử dụng kiểu dữ liệu xâu để giải thì việc tìm ra Output đơngiản hơn nhiều. Trong quá trình giảng dạy cho học sinh lớp 11 Toán, 11 Hóa, 11Tin và bồi dưỡng học sinh giỏi, học hỏi đồng nghiệp và nghiên cứu một số sáchtham khảo tôi đã tìm ra một cách tiếp cận để giải được các bài toán số học nhờsử dụng kiểu dữ liệu xâu. Việc sử dụng kiểu dữ liệu xâu giúp cho một số bài toánđược lập trình giải trên máy tính trở nên đơn giản, thuận lợi hơn nhiều. Thôngqua một số bài tập số học nhờ sử dụng kiểu dữ liệu xâu học sinh mới thấy đượclợi ích và cái hay của kiểu dữ liệu xâu.Ví dụ : Viết chương trình nhập vào số tự nhiên n(00 dobegint≔t+n mod 10;n≔n div 10;end;writeln(t);End.Đánh giá:-Với cách viết trên ta phải sử dụng n lần hai phép toán chia nguyên và chialấy phần dư. Như vậy sẽ mất nhiều thời gian thực hiện chương trình.-Tối đa n mới nhận được 2.10 9, còn lớn hơn trong Free Pascal thì tối đađược n mới được 2.1018 . Mà đề bài cho 0=a[i+1]) and (i370->30->0Thuật toán:8Bước 1: Việc đầu tiên ta phải tạo ra số nguyên n1 từ n bằng cách sử dụngvòng lặp for duyệt từ i=1 đến n . Với mỗi giá trị của i ta đổi sang xâu và dùngphép ghép xâu để ghép lại với nhau ta được một xâu s chính là n1.Bước 2: Ta tiến hành xóa ở các vị trí chẵn trước nên khởi tạo i=2; sau khixóa lần thứ nhất một kí tự thì các kí tự ở phía sau vị trí xóa sẽ dịch chuyển sangbên trái 1 vị trí do vậy i chỉ cần tăng thêm 1 đơn vị. Quá trình xóa lại tiếp tục cứnhư vậy cho đến khi kết thúc nếu i>length(n1);Bước 3: Tiếp theo tiến hành xóa ở các vị trí lẻ. Khởi tạo i=1, sau khi xóalần thứ nhất một kí tự thì các kí tự ở phía sau vị trí xóa sẽ dịch chuyển sang bêntrái 1 vị trí do vậy i chỉ cần tăng thêm 1 đơn vị. Quá trình xóa lại tiếp tục cứ nhưvậy cho đến khi kết thúc nếu i>length(n1);Quá trình xóa vị trí chẵn rồi lại lẻ cứ như vậy cho đến khi n1 chỉ còn mộtchữ số. Do vậy bước 2 và bước 3 sẽ lặp đi lặp lại cho đến khi độ dài của n1 bằng1 thì dừng lại.Đoạn mã chương trình đầy đủ:program bt1;var n,i:longint;n1,s:string;Beginreadln(n);n1:='';for i:=1 to n dobeginstr(i,s);n1:=n1+s;end;repeat9i:=2;while length(n1)>1 dobegindelete(n1,i,1);inc(i);if i >length(n1) then break;end;i:=1;while length(n1)>1 dobegindelete(n1,i,1);inc(i);if i >length(n1) then break;end;untillength(s)=1;write(s);readln;End.Bài tập 2.Viết liên tiếp các số nguyên từ 1 đến n thành một dãy các kí tự (n56 nên 90 ghép trước để tạo thành 9056>5690.Nhưng khi ghép 90 với 123 nếu so sánh 90’123’ do vậy ‘90’ ghép trước. Quy tắc sosánh 2 xâu là kí tự đầu tiên khác nhau giữa chúng kể từ trái sang có mã lớn hơnsẽ lớn hơn.Thuật toán: Sắp xếp dãy số nguyên a 1, a2, …an thành dãy số mà thỏa mãnai đứng trước ai+1 nếu xâu ai > xâu ai+1. Như vậy trước khi so sánh xâu ta phảiđổi hai số nguyên ai, ai+1 sang xâu sau đó mới so sánh. Việc đầu tiên ta viết mộthàm kiểm tra xem tại hai vị trí i, j mà xâu a[i] có nhỏ hơn xâu a[j] không hàm trảvề giá trị True nếu có, giá trị False nếu không.Sau đó lần lượt kiểm tra cứ hai vị trí mà behon(i,j) thì phải đổi chỗ a[i] vớia[j] cho nhau. Sau khi sắp xếp xong ta in dãy a viết liền sẽ được một số ghép cógiá trị lớn nhất.Đoạn mã chương trình đầy đủprogram bt6;consttfi='join.inp';tfo='join.out';var n: longint;a: array[0..51] of longint;function behon(i,j: longint): boolean;var si, sj: string;18beginstr(a[i],si);str(a[j],sj);if si0 do24beginr:=n mod b;kq:=mau[r+1]+kq;n := n div b;end;exit(kq);beginassign(input,tfi);reset(input);assign(output,tfo);rewrite(output);readln(n,b);s≔doiso(n,b));for i:=1 to length(s) doif (s[i]>=’0’ )and (s[i]=’A’ and (s[i]