TAILIEUCHUNG - Sáng tạo trong thuật toán và lập trình với ngôn ngữ Pascal và C# Tập 3 - Chương 4

Các phép lật và chuyển vị Lật xâu Cho xâu kí tự s. Hãy lật xâu s, tức là sắp các kí tự của xâu s theo trật tự ngược lại. Thí dụ, với s = "abcd", thì sau khi đảo ta thu được s = "dcba". Thuật toán Để lật một đoạn s[dc] trong dãy s bất kì ta thực hiện liên tiếp các phép đổi chỗ hai phần tử cách đều đầu và cuối tính dần từ ngoài vào giữa dãy. Độ phức tạp Nếu đoạn cần lật có chiều dài n, mỗi lần đổi chố hai phần. | Chương 4 Các phép lật và chuyển vị Lật xâu Cho xâu kí tự s. Hãy lật xâu s tức là sắp các kí tự của xâu s theo trật tự ngược lại. Thí dụ với s abcd thì sau khi đảo ta thu được s dcba . Thuật toán Để lật một đoạn s trong dãy s bất kì ta thực hiện liên tiếp các phép đổi chỗ hai phần tử cách đều đầu và cuối tính dần từ ngoài vào giữa dãy. Độ phức tạp Nếu đoạn cần lật có chiều dài n mỗi lần đổi chố hai phần tử ta cần 3 phép gán. Tổng cộng có n 2 cặp phần tử do đó số phép gán sẽ là 3n 2. Chương trình Hàm Rev trong các chương trình sau đây nhận vào một xâu s và hai chỉ số đầu d và cuối c sau đó thực hiện phép đảo đoạn s rồi cho ra chính xâu s đó. uses crt const nl 13 10 var s string function Rev var s string d c integer string var ch char begin while d c do begin ch s d s d s c s c ch inc d dec c end Rev s end BEGIN s I have a dream write nl Given s Rev s 1 length s writeln s writeln nl Now the source string is Rev s 1 length s readln END. DevC include fstream include iostream using namespace std P R O T O T Y P E S int main char Rev char s int d int c I M P L E M E N T A T I O N int main char s strdup I have a dream cout endl Given s cout Rev s 0 strlen s -1 cout endl Now the source string is Rev s 0 strlen s -1 cout endl system PAUSE return EXIT_SUCCESS char Rev char s int d int c char ch while d c ch s d s d s c s c ch d --c return s Giải thích Hàm s strdup I have a dream cấp phát miền nhớ cho xâu s và khởi trị xâu này bằng dãy kí tự I have a dream . Lật số nguyên Viết hàm Rev x cho ra số nguyên dạng lật của số nguyên x. Thí dụ Rev -1234 - 4321. Thuật toán Gọi y là kết quả. Ta khởi trị y 0 sau đó lấy lần lượt các chữ số đầu phải của x ghép vào bên phải số y. Độ phức tạp Nếu số đã cho có n chữ số mỗi lần chuyển một chữ số ta cần thực hiện một phép chia dư và hai phép nhân. Nếu ta coi thời gian thực hiện phép nhân chia và chia dư là xấp xỉ bằng nhau thì thuật toán lật số nguyên cần thời gian 3n. Mỗi số nguyên x có lg x 1 chữ số .

• Kỹ thuật lập trình
• ngôn ngữ Pascal
• lập trình C#
• giải bài toán tin
• giáo trình lập trình
• thuật toán máy tính
• Ngôn ngữ lập trình Pascal
• Bài giảng Ngôn ngữ lập trình Pascal
• Thực hành Turbo Pascal
• Turbo Pascal Version 5
• Turbo Pascal Version 7
• Cách khởi động Turbo Pascal
• kinh nghiệm sử dụng
• lập trình căn bản
• ngôn ngữ lập trình
• kỹ thuật pascal
• tài liệu về pascal
• lập trình pascal
• giáo trình pascal căn bản
• kỹ thuật phần mềm
• giải bài toán pascal
• tài liêu bài toán pascal
• bài tập tin học
• Pascal
• tài liệu ngôn ngữ pascal
• giáo trình pascal
• bài giảng ngôn ngữ pascal
• Lý thuyết và bài tập Pascal
• Thành phần ngôn ngữ Pascal
• Ngôn ngữ lập trình cấp cao
• Ký hiệu của Pascal
• Ký tự trong Pascal
• Giáo trình Ngôn ngữ lập trình Pascal
• Giới thiệu chương trình Pascal
• Cấu trúc chương trình Pascal
• Ký tự sử dụng trong Pascal
• Bài tập Pascal cơ bản
• Các dạng bài tập Pascal
• Một số mẫu bài tập Pascal
• Bài tập Pascal
• Ôn tập Pascal
• Bài giảng môn Lập trình Pascal
• Môn lập trình Pascal
• Môi trường làm việc của Turbo Pascal
• Kỹ thuật Lập trình Pascal
• ứng dụng Pascal
• giáo trình
• Giáo trình bài tập Pascal
• Bài tập ngôn ngữ lập trình Pascal
• Bài giảng Lập trình Pascal
• Lệnh cơ bản trong Pascal
• Cấu trúc một chương trình Pascal
• Thuật toán lập trình
• Các khái niệm trong Pascal
• Kiểu dữ liệu đơn giản
• Các câu lệnh điều khiển
• giáo án tin học
• Giáo trình Tin học
• Cách sử dụng ngôn ngữ Pascal
• Câu hỏi Pascal
• Thành phần Pascal
• Ôn tập thi liên thông ngành tin học
• Thành phần của ngôn ngữ lập trình pascal
• Ôn tập Pascal cơ bản
• toán Pascal
• bài tập toán Pascal
• tài liệu toán Pascal
• lý thuyết toán Pascal
• Tự học lập trình Pascal
• Bài tập lập trình Pascal
• Kỹ thuật lập trình
• Học lập trình Pascal