Tìm hiểu ngôn ngữ bằng các ví dụ thực hành

Chia sẻ: Nhung Nhung | Ngày: | Loại File: PDF | Số trang:8

Thêm vào BST

Báo xấu

61
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Các hàm, các dãy số và các phép bao hàm Bài toán đầu tiên của Dự án Euler mà bạn sẽ giải quyết là Bài toán 6 (xem phần Tài nguyên), trong đó yêu cầu bạn tính toán tổng các bình phương của các số tự nhiên đầu tiên, bình phương của tổng các số đó và sau đó đưa ra hiệu của chúng. Với bài toán này, bạn sẽ sử dụng Vòng lặpĐọc-Tính toán-In ra (REPL - Read-Evaluate-Print-Loop) của CoffeeScript. Liệt kê 1 hiển thị mã và kết quả đầu ra tương ứng từ phiên làm việc của REPL....

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Tìm hiểu ngôn ngữ bằng các ví dụ thực hành

Tìm hiểu ngôn ngữ bằng các ví dụ thực hành Các hàm, các dãy số và các phép bao hàm Bài toán đầu tiên của Dự án Euler mà bạn sẽ giải quyết là Bài toán 6 (xem phần Tài nguyên), trong đó yêu cầu bạn tính toán tổng các bình phương của các số tự nhiên đầu tiên, bình phương của tổng các số đó và sau đó đưa ra hiệu của chúng. Với bài toán này, bạn sẽ sử dụng Vòng lặp- Đọc-Tính toán-In ra (REPL - Read-Evaluate-Print-Loop) của CoffeeScript. Liệt kê 1 hiển thị mã và kết quả đầu ra tương ứng từ phiên làm việc của REPL. Liệt kê 1. Bài toán 6 từ REPL coffee> square = (x) -> x*x [Function] coffee> sum = (nums) -> nums.reduce (a,b) -> a+b [Function] coffee> diff = (nums) -> (square sum nums) - (sum nums.map square) [Function] coffee> diff [1..100] 25164150 Giải thích chi tiết: 1. Trong REPL, ta định nghĩa một hàm. (Như đã đề cập trong Phần 1, CoffeeScript đề cao bản chất lập trình hàm của JavaScript, loại bỏ nhiều cú pháp giống C của JavaScript đã làm cho cú pháp CoffeeScript trở nên dễ nhìn và dễ lập trơ hơn). Ví dụ trong Liệt kê 1 định nghĩa một hàm tên là square (bình phương) và nói rằng nó nhận một tham số duy nhất và trả về tích của phép nhân tham số đó với chính nó (bình phương nó lên). Rồi REPL cho bạn biết rằng bạn đã định nghĩa một hàm. 2. Định nghĩa một hàm khác tên là sum (tổng số) nhận một tham số duy nhất: một mảng. Sau đó hàm Sum gọi phương thức reduce (thu gọn) trên mảng đó. Phương thức reduce là hàm có sẵn của JavaScript (được thêm vào trong JavaScript 1.8). Phương thức reduce tương tự như hàm reduce trong Python hoặc hàm fold (gấp) trong Haskell hoặc Scala. Nó lấy một hàm và di chuyển từ trái sang phải trên mảng đó, áp dụng hàm cho giá trị được trả về trong lần tính trước đó và giá trị tiếp theo trong mảng. Cú pháp hàm cô đọng của CoffeeScript làm cho phương thức reduce dễ sử dụng. Trong trường hợp này, hàm được chuyển sang hàm reduce được quy định là (a,b) -> a + b. Đây là một hàm nhận hai giá trị và cộng chúng với nhau, do đó làm cho tất cả các phần tử của mảng được cộng với nhau.
3. Tạo một hàm tên là diff (hiệu), nó lấy một mảng các số, tính toán hai biểu thức con, rồi trừ chúng cho nhau. Biểu thức con đầu tiên chuyển mảng tới hàm sum, rồi lấy kết quả và chuyển nó tới hàm square. CoffeeScript cho phép bạn bỏ qua các dấu ngoặc đơn trong nhiều trường hợp vì thế không có sai sót nào. Ví dụ, square sum nums tương đương với square(sum(nums)). Biểu thức con thứ hai gọi phương thức map (ánh xạ) của mảng, đó là một phương thức JavaScript 1.8 khác nhận một hàm khác làm đầu vào của nó. Sau đó nó áp dụng hàm đó cho từng thành viên của mảng, tạo ra một mảng mới từ các kết quả. Ví dụ trong Liệt kê 1 sử dụng hàm bình phương làm tham số đầu vào cho hàm map, cung cấp cho bạn một mảng có các phần tử của mảng là các số bình phương của mảng đầu vào. Sau đó, bạn chỉ cần chuyển mảng này tới hàm sum để nhận được tổng của các số bình phương. 4. Chuyển mảng các số thích hợp vào hàm diff để giải Bài toán 6, khi sử dụng một dãy số [1..100]. Dãy số này tương đương với một mảng của tất cả các số từ 1 đến 100, bao gồm cả số 100. Nếu bạn đã muốn dải số này không bao gồm cả số 100 bạn phải viết [1...100], tức là dùng ba dấu chấm thay vì chỉ có hai. Việc chuyển mảng này vào hàm diff cung cấp cho bạn lời giải cho Bài toán 6. Hãy quay trở lại một chút và xem xét Bài toán 1 của Dự án Euler (xem phần Tài nguyên), trong đó yêu cầu bạn tính tổng tất cả các số nguyên nhỏ hơn 1000 có thể chia hết cho 3 hoặc 5. Bạn có thể nghĩ rằng đây sẽ là bài toán đơn giản nhất trong số các bài toán của Dự án Euler. Bạn có thể dễ dàng giải nó chỉ bằng cách sử dụng các hàm và các dãy số, như trong Bài toán 6. Tuy nhiên, với tính năng phép bao hàm của CoffeeScript, bạn có thể đưa ra lời giải ngắn gọn trong Liệt kê 2. Liệt kê 2. Giải Bài toán 1 bằng cách sử dụng các phép bao hàm (comprehensions) coffee> (n for n in [1..999] when n % 3 == 0 or n % 5 == 0).reduce (x,y) -> x+y 233168 Thật dễ chịu khi có thể giải một bài toán chỉ bằng một dòng mã duy nhất và cú pháp cô đọng của CoffeeScript cho phép nó trở thành ngôn ngữ một dòng lệnh. Lời giải trong Liệt kê 2 sẽ tạo một danh sách tất cả các số nguyên là bội số của 3 hoặc 5 bằng cách sử dụng một phép bao hàm. Danh sách được tạo ra bằng cách bắt đầu với dãy số [1..999] nhưng chỉ sử dụng các giá trị chia hết cho 3 hoặc 5. Sau đó sử dụng một hàm reduce khác để tính tổng các giá trị đó. REPL tính toán một dòng mã này và in ra lời giải cho bài toán đó. Phần tiếp theo, chúng ta sẽ giải các bài toán phức tạp hơn một chút và tiếp tục khám phá CoffeeScript. Về đầu trang
Các câu lệnh khối, các mảng và các tệp Bài toán 4 của Dự án Euler (xem phần Tài nguyên) yêu cầu bạn tìm ra số lớn nhất có các chữ số có thể đọc xuôi hay đọc ngược đều được (số palindrome), số này phải là tích của hai số có ba chữ số. Có rất nhiều cách để giải quyết vấn đề này; Liệt kê 3 hiển thị một cách giải. Liệt kê 3. Thử nghiệm với các palindrome isPal = (n) -> digits = [] while n > 0 digits.push(n % 10) n = Math.floor(n / 10) len = digits.length comps = [0..len/2].map (i) -> digits[i] == digits[len-i-1] comps.reduce (a,b)-> a && b vals = [] vals.push(x*y) for x in [100..999] for y in [100..999] pals = vals.filter (n) -> isPal(n) biggest = pals.reduce (a,b) -> Math.max(a,b) console.log biggest 1. Định nghĩa một hàm tên là isPal, mà nó sẽ kiểm tra xem một số có là một palindrome hay không. Hàm này phức tạp hơn một chút so với những hàm trước đây. Nó có bảy dòng mã trong phần thân của mình. Bạn có thể nhận thấy rằng CoffeeScript không sử dụng dấu ngoặc nhọn ({ }) hoặc bất kỳ cơ chế tường minh nào khác để biểu thị điểm bắt đầu và kết thúc của hàm. Nó sử dụng khoảng trống (thụt đầu dòng), giống như Python và bắt đầu với cùng một ký pháp để biểu thị một hàm: danh sách tham số, tiếp sau bằng mũi tên lớn hơn (->). Sau đó, bạn tạo ra một mảng rỗng cho các chữ số của các số và bắt đầu một vòng lặp while. Vòng lặp này tương tự như vòng lặp while của JavaScript (hoặc C, Java và v.v). Điều kiện n > 0 không đòi hỏi các dấu ngoặc đơn xung quanh nó. Phần thân của vòng lặp được thụt vào sâu hơn nữa để cho biết nó là một phần của vòng lặp. Bên trong vòng lặp, bạn cắt rời chữ số cuối của số đó, đẩy nó lên phía trước của mảng, rồi chia số đó cho 10, loại bỏ phần dư của phép chia. Việc này dẫn đến một mảng các chữ số của số ban đầu. Bạn cũng có thể thay thế vòng lặp đơn giản bằng digits = new String n, biến đổi n thành một chuỗi. Phần còn lại của mã này hoạt động như nó vốn có. 2. Sau khi bạn có mảng các chữ số, hãy tạo ra một mảng bằng một nửa chiều dài của mảng này. Sử dụng hàm map để lần lượt chuyển từng phần tử của mảng này thành một giá trị Boolean tương ứng để xem các chữ số cách điểm bắt đầu và kết thúc của mảng có bằng nhau không.
Nếu tất cả các giá trị Boolean đều là đúng, thì bạn có một palindrome. Để kiểm tra điều này, chỉ cần sử dụng một hàm reduce khác, lần này hàm thực hiện phép toán logic AND các giá trị Boolean với nhau. 3. Bây giờ bạn đã định nghĩa hàm isPal, hãy sử dụng nó để kiểm tra các palindrome. Hãy kiểm tra tất cả các số là tích của hai số có ba chữ số. a. Tạo hai phép bao hàm, mỗi phép bao hàm trải rộng từ số có ba chữ số nhỏ nhất (100) đến số có ba chữ số lớn nhất (999). b. Đối với mỗi phép bao hàm, lấy tích số và đặt nó vào trong một mảng. c. Sử dụng một hàm reduce khác để tìm phần tử lớn nhất trong mảng. Cuối cùng, phần tử này được in ra bằng cách sử dụng console.log. d. Lưu phần tử này vào một tệp. Liệt kê 4 Liệt kê 4 cho thấy cách thực hiện và tính thời gian giải. Liệt kê 4. Thực hiện lời giải cho Bài toán 4 $ time coffee p4.coffee 906609 real 0m2.132s user 0m2.106s sys 0m0.022s Kịch bản lệnh trong Liệt kê 4 phải mất hơn hai giây để thực hiện trên một máy tính chạy nhanh, phần lớn là do phép bao hàm ghép để tạo ra 899*899 = 808.201 giá trị để kiểm tra (nhiều giá trị trong đó bị lặp lại). Bạn hãy thử tối ưu hóa mã trong Liệt kê 3. (Gợi ý: Chuyển đổi số thành một chuỗi ký tự thực sự nhanh hơn nhiều). Bài toán 22 của Dự án Euler (xem phần Tài nguyên) yêu cầu bạn phải thực hiện một phép tính phức tạp trên một danh sách các chuỗi ký tự. Bạn sẽ đọc danh sách từ một tệp, phân tích cú pháp các nội dung trong một danh sách, sắp xếp nó và chuyển đổi mỗi chuỗi ký tự thành một số, rồi tính tổng các tích của mỗi số nhân với vị trí của nó trong danh sách. Bài toán 22 cho phép bạn xem các tệp làm việc ra sao trong CoffeeScript. Ngoài ra còn có một số thao tác chuỗi và nhiều thủ thuật mảng hơn nữa. Liệt kê 5 hiển thị lời giải. Liệt kê 5. Làm việc với các tệp trong CoffeeScript path = "/path/on/your/computer/names.txt" fs = require "fs" contents = fs.readFileSync path, "utf8" strs = contents.split(",") names = strs.map (str) -> str[1 .. str.length - 2] names = names.sort() vals = names.map (name) -> name.split("")
vals = vals.map (list) -> list.map (ch) -> 1 + ch.charCodeAt(0) - 'A'.charCodeAt(0) vals = vals.map (list) -> list.reduce (a,b) -> a+b vals = ((i+1)*vals[i] for i in [0...vals.length]) total = vals.reduce (a,b) -> a+b console.log total 1. Lưu tệp này. Có một liên kết trong phần mô tả bài toán hoặc bạn có thể sử dụng mã nguồn kèm theo bài viết này. Hãy thay đổi giá trị của biến đường dẫn thành đường dẫn tới tệp trên máy tính của bạn. CoffeeScript không kèm theo bất kỳ thư viện đặc biệt nào để làm việc với các tệp. Thay vào đó, nó dùng node.js và mô đun fs của mình. Nạp mô đun fs bằng cách sử dụng hàm require. 2. Đọc các nội dung của tệp này bằng cách sử dụng fs.readFileSync. Tệp này trông giống như "MARY", "PATRICIA" và v.v. Nó khởi đầu một chuỗi duy nhất, vì thế hãy sử dụng phương thức split để phân chia nó thành từng phần theo các dấu phẩy. Mỗi chuỗi ký tự vẫn còn có dấu nháy kép (") ở đầu và cuối của chuỗi. Để loại bỏ chúng, hãy sử dụng hàm map và thay thế mỗi chuỗi bằng một chuỗi nhỏ hơn. Nếu str là một chuỗi, thì str[1 .. str.length -2] là một chuỗi con bắt đầu bằng ký tự thứ hai và kết thúc bằng ký tự tiếp theo đến ký tự cuối cùng. Mã này sẽ loại bỏ chính xác các ký tự đầu và cuối—chính là các dấu nháy kép khó chịu đó. Việc cắt các chuỗi ra thành các chuỗi nhỏ hơn có thể rất thuận tiện. 3. Sau khi bạn có một danh sách các chuỗi không có dấu nháy kép, bạn đã sẵn sàng sắp xếp. Hãy sử dụng phương thức sort (sắp xếp) của mảng. Bạn cần chuyển đổi các chuỗi ký tự thành một số ở đây mỗi ký tự sẽ phù hợp với vị trí của nó trong bảng chữ cái (A -> 1, B - > 2, C -> 3 và v.v). a. Chuyển từng chuỗi thành một mảng các ký tự bằng cách sử dụng lại phương thức split. b. Ánh xạ mỗi ký tự tới một giá trị số bằng cách sử dụng phương thức charCodeAt. c. Tính tổng các giá trị số này bằng cách sử dụng một phép toán reduce. Danh sách các chuỗi ký tự được chuyển đổi thành một danh sách các số. 4. Nhân mỗi số với vị trí của nó trong danh sách và cộng chúng lại với nhau bằng cách sử dụng phép bao hàm khác. Tạo một mảng mới trong đó mỗi phần tử được tạo ra bằng cách nhân một phần tử của mảng trước đó với vị trí của nó. Tính tổng các phần tử của mảng này bằng cách sử dụng thêm một phép toán reduce nữa và in ra tổng số. Một lần nữa, bạn có thể lưu công việc này vào một tệp rồi thực hiện và tính thời gian chạy nó, như thể hiện trong Liệt kê 6:
Liệt kê 6. Tính thời gian thực hiện Bài toán 22 $ time coffee p22.coffee 871198282 real 0m0.133s user 0m0.115s sys 0m0.013s Cần chưa đến 0,2 giây để thực hiện lời giải cho Bài toán 22. Hầu như số dòng tiếng Anh để mô tả cần tính toán những gì cũng bằng số các dòng mã để thực hiện tính toán. Đây là một ví dụ tuyệt vời về cú pháp cô đọng của CoffeeScript. Bạn có thể hình dung nếu sử dụng ngôn ngữ lập trình khác cho ví dụ này thì sẽ phải dùng nhiều dòng mã hơn. Trong phần này, bạn đã giải được các bài toán khó hơn bằng cách sử dụng một số tính năng quan trọng của CoffeeScript. Phần tiếp theo sẽ xem xét một tính năng quan trọng trong CoffeeScript: đó là lập trình hướng đối tượng. Về đầu trang CoffeeScript hướng đối tượng Như đã đề cập trong Phần 1, một điểm yếu chính của JavaScript là phong cách "bất thường" về lập trình hướng đối tượng (OOP). Nó bất thường chỉ vì thường thì lập trình hướng đối tượng là dựa trên lớp. CoffeeScript thực hiện lập trình hướng đối tượng dựa trên lớp. Thử thách kế tiếp của bạn là sử dụng lập trình hướng đối tượng của CoffeeScript để giải Bài toán 35 của Dự án Euler (xem phần Tài nguyên). Trong Bài toán 35, người ta nói với bạn rằng một số nguyên tố vòng tròn là một loại số nguyên tố đặc biệt có đặc tính là bạn có thể thực hiện bất kỳ sự xoay vòng nào của các chữ số của nó và vẫn còn có một số nguyên tố. Mã trong Liệt kê 7 sử dụng lập trình hướng đối tượng để tính toán số lượng các số nguyên tố vòng tròn nhỏ hơn 1.000.000. Liệt kê 7. Đếm các số nguyên tố vòng tròn class PrimeSieve constructor: (@max) -> @nums = [2..@max] for p in @nums d = 2*p while p != 0 and d @nums[n-2] != 0 thePrimes: -> @nums.filter (n) -> n != 0
class CircularPrimeGenerator extends PrimeSieve genPerms = (num) -> s = new String num x = (for i in [0 ... s.length] s[i+1 ... s.length].concat s[0..i]) x.map (a) -> parseInt(a) isCircularPrime : (n) -> perms = genPerms(n) len = perms.length primePerms = perms.filter (p) => @isPrime(p) len == primePerms.length theCircularPrimes: -> (p for p in @thePrimes() when @isCircularPrime(p)) max = process.argv[2] generator = new CircularPrimeGenerator max console.log "Number of circular primes less than #{max} is #{generator.theCircularPrimes().length}" 1. Tạo một lớp tên là PrimeSieve, thực hiện thuật toán Sàng lọc Erasthones (Sieve of Erasthones) cổ điển để tính toán tất cả các số nguyên tố nhỏ hơn một giá trị cụ thể. Ký hiệu @ biểu thị một đặc tính của một lớp và cũng là ký hiệu tắt cho 'this.'. Vì vậy, @nums = [2..@max] tương đương với this.nums = [2 .. this.max]. Các phương thức lớp được chỉ rõ bằng tên của chúng tiếp sau là một dấu chấm phẩy và định nghĩa hàm. Phương thức đầu tiên, được gọi là constructor, là một hàm tạo cho lớp. Ví dụ, lệnh PrimeSieve(100) mới sẽ gọi hàm tạo và chuyển 100 làm giá trị max và được gán cho this.max. Hàm tạo của chúng ta xây dựng cái sàng và lưu trữ các số nguyên tố trong biến thành viên @nums. Sau đó nó khai báo hai phương thức: isPrime và thePrimes. Phương thức thePrimes sử dụng một bộ lọc mảng để loại bỏ các số đa hợp khỏi @nums. 2. Khai báo một lớp con của PrimeSieve, tên là CircularPrimeGenerator. CoffeeScript sử dụng cú pháp class ... extends, giống như nhiều ngôn ngữ lập trình hướng đối tượng phổ biến. Lớp này sẽ kế thừa hàm tạo, các biến thành viên và các phương thức của lớp PrimeSieve. Nó có: o Phương thức genPerms để tạo ra tất cả các hoán vị của một số đã cho bằng cách xoay vòng các chữ số của số đó. o Phương thức isCircularPrime tạo ra tất cả các hoán vị của một số đã cho và loại bỏ bất kỳ số nào trong danh sách các hoán vị mà không phải là một số nguyên tố. Nếu danh sách sau khi đã lọc có chứa tất cả các phần tử giống như danh sách chưa được lọc, thì số đó phải là một số nguyên tố vòng tròn. o Phương thức theCircularPrimes tạo ra một danh sách tất cả các số nguyên tố vòng tròn bằng cách sử dụng một phép bao hàm.
Lưu ý cách bạn có thể sử dụng phương thức @thePrimes đã định nghĩa trong siêu lớp và sau đó chỉ cần lọc ra các số nguyên tố không phải là số nguyên tố vòng tròn. Sau khi bạn có hai lớp được định nghĩa, bạn đã sẵn sàng sử dụng chúng để giải bài toán đó. 3. Liệt kê 7 đã được viết để lấy một đối số dòng lệnh, đó là giá trị tối đa (max) được sử dụng để tính toán các số nguyên tố và các số nguyên tố vòng tròn. Có thể truy cập tất cả các đối số dòng lệnh bằng cách sử dụng process.argv. Hai giá trị đầu tiên trong mảng này là lệnh và kịch bản lệnh, vì thế, chính process.argv[2] chứa tham số đầu tiên được kịch bản lệnh sử dụng. Tạo một cá thể của CircularPrimeGenerator bằng cách sử dụng giá trị max được chuyển vào kịch bản lệnh. In ra số lượng các số nguyên tố vòng tròn đã được tìm thấy bằng cách sử dụng console.log. Trong ví dụ này, bạn đã sử dụng một tính năng thuận tiện khác của CoffeeScript: phép nội suy- chuỗi để tạo ra chuỗi được chuyển tới console.log.