ĐỀ TÀI TÌM HIỂU VỀ BÀI TOÁN THÁP HÀ NỘI - Tài Liệu Text - 123doc

Có thể bạn quan tâm

Tải bản đầy đủ (.doc) (14 trang)

Trang chủ

Luận Văn - Báo Cáo

Khoa học tự nhiên

ĐỀ TÀI TÌM HIỂU VỀ BÀI TOÁN THÁP HÀ NỘI

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 (206.97 KB, 14 trang )

K8 TIN Đại Học Hùng VươngTRƯỜNG ĐẠI HỌC HÙNG VƯƠNGKHOA TOÁN – CÔNG NGHỆ******o0o******Báo cáo bài tiểu luậnMÔN: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬTĐề tài:TÌM HIỂU VỀ BÀI TOÁN THÁP HÀ NỘIGiảng viên hướng dẫn: Nguyễn Thị Hảo Nhóm sinh viên thực hiện:1. Trương Thị Thúy Hương2. Nguyễn Hoàng Phong3. Lã Thị Ánh Tuyết4. Nguyễn Thị Châm5. Nguyễn Thị Thanh Huyền6. Nguyễn Quang Trung- 1 -K8 TIN Đại Học Hùng VươngMỤC LỤCTrangLời nói đầu 3Chương 1. MỞ ĐẦU VỀ BÀI TOÁN 41.1. Tìm hiểu bài toán 41.2. Phân tích & đánh giá ban đầu 5Chương 2. GIẢI THUẬT ĐỆ QUYTHUẬT TOÁN & CÀI ĐẶT CHƯƠNG TRÌNH 62.1. Sơ lược về giải thuật đệ quy 62.1.1. Khái niệm đệ quy 62.1.2. Giải thuật đệ quy 62.1.3.Thiết kế giải thuật đệ quy 62.2. Thuật toán 72.3. Cài đặt chương trình 11 2.4. Độ phức tạp của thuật toán…………………………………… 12 Chương 3. Ý NGHĨA CỦA BÀI TOÁN 123.1. Về khoa học 123.2. Trong lĩnh vực toán – tin 123.3. Trong lĩnh vực giải trí 123.4. Về lịch sử 133.5. Thành tựu 13 Tài liệu tham khảo 14- 2 -K8 TIN Đại Học Hùng VươngLỜI NÓI ĐẦUCác bạn thân mến!Có lẽ nhắc đến bài toán tháp Hà Nội, một bài toán cổ xưa mang đậm chất tính toán, song cũng như một trò chơi tri thức được lưu truyền tới nay với nhiều ứng dụng trong thực tế. Hẳn không ai là sinh viên IT chúng ta không biết tới. Nó như một lời thách thức, hay một bước khởi đầu cho những ai muốn chinh phục tầm hiểu biết trong môn tính toán.Trong khoa học tính toán ngày nay, phép truy hồi là thuật toán cơ bản để lập trình. Ưu điểm của phương pháp truy hồi là ở chỗ nó dùng một công thức nhất định để diễn tả những phép tính lặp đi lặp lại bất chấp số lần lặp lại là bao nhiêu. Nếu số lần lặp lại lên đến con số hàng triệu hàng tỷ thì con người không đủ sức và thời gian để làm, nhưng máy tính thì có thể giải quyết trong chớp mắt. Điểm mạnh của computer là ở chỗ nó không hề biết e ngại và mệt mỏi trước những công việc lặp đi lặp lại lên đến hàng triệu hàng tỷ lần. Và vì thế, việc cộng tác giữa computer với con người là mô hình lý tưởng của lao động trí óc trong cuộc sống hiện đại. Bài toán Tháp Hà Nội không chỉ thú vị ở chỗ nó mang tên Hà Nội, thủ đô của Việt Nam, mà nó hấp dẫn các nhà Toán-Tin học, bởi nó liên quan đến nhiều vấn đề như giải thuật đệ qui, hệ đếm, tam giác Pascal, thảm Sierpinski, lý thuyết đồ thị và chu trình Hamilton, ôtômát hữu hạn, độ phức tạp tính toán,v.v Bài toán Tháp Hà Nội gợi ý cho nhiều nghiên cứu trong khoa học máy tính và toán học. Chính vì thế nhóm Sv k8 Tin chọn đề tài này để cùng các bạn khám phá những gì còn bí ẩn sau bài toán THÁP HÀ NỘI.- 3 -K8 TIN Đại Học Hùng VươngChương 1.MỞ ĐẦU VỀ BÀI TOÁN1.1. Tìm hiểu bài toánCó thể còn ít người Việt Nam biết Tháp Hà Nội, nhưng rất nhiều thanh niên sinh viên trên toàn thế giới lại biết đến nó. Đó là vì, Tháp Hà Nội là tên một bài toán rất nổi tiếng trong Chương trình khoa học tính toán (Computing Science) dành cho sinh viên những năm đầu tại các trường đại học ở nhiều nơi trên thế giới.Bài toán hay trò chơi tháp Hà Nội được nhắc tới trong rất nhiều tài liệu. Tương truyền rằng: Ngày xửa ngày xưa, lâu lắm rồi, ở một vùng xa xôi viễn đông, thành phố Hà Nội của Việt Nam, vị quân sư của Hoàng đế vừa qua đời, Hoàng đế cần một vị quân sư mới thay thế. Bản thân Hoàng đế cũng là một nhà thông thái, nên ngài đặt ra một bài toán đố, tuyên bố ai giải được sẽ được phong làm quân sư. Bài toán của Hoàng đế là: cho n cái đĩa (ngài không nói chính xác là bao nhiêu) và ba cái trục: A là trục nguồn, B là trục đích, và C là trục trung chuyển. Những cái đĩa có kích cỡ khác nhau và có lỗ ở giữa để có thể lồng vào trục, theo quy định "nhỏ trên lớn dưới". Đầu tiên, những cái đĩa này được xếp tại trục A. Vậy làm thế nào để chuyển toàn bộ các đĩa sang trục B, với điều kiện chuyển từng cái một và luôn phải đảm bảo quy định "nhỏ trên lớn dưới", biết rằng trục C được phép sử dụng làm trục trung chuyển?Vì địa vị quân sư được coi là vinh hiển nên có rất nhiều người dự thi. Từ vị học giả đến bác nông phu, họ đua nhau trình lên Hoàng đế lời giải của mình. Nhiều lời giải dài tới hàng nghìn bước, và nhiều lời giải có chữ "chuyển sang bước tiếp theo" (go to). Nhưng hoàng đế thấy mệt mỏi vì những lời giải đó, nên cuối cùng hạ chiếu: "Ta không hiểu những lời giải này. Phải có một cách giải nào khác dễ hiểu và nhanh chóng hơn". May mắn thay, cuối cùng đã có một cách giải như thế.- 4 -K8 TIN Đại Học Hùng VươngThật vậy, ngay sau khi chiếu vua ban ra, một vị cao tăng trông bề ngoài giống như một kỳ nhân hạ sơn tới xin yết kiến hoàng đế. Vị cao tăng nói: "Thưa Bệ hạ, bài toán đố đó dễ quá, hầu như nó tự giải cho nó". Quan trùm cấm vệ đứng hầu ngay bên cạnh vua quắc mắt nhìn gã kỳ nhân, muốn quẳng gã ra ngoài, nhưng Hoàng đế vẫn kiên nhẫn tiếp tục lắng nghe. "Nếu chỉ có 1 đĩa, thì ; nếu có nhiều hơn 1 đĩa (n>1), thì ", cứ thế vị cao tăng bình tĩnh giảng giải. Im lặng được một lát, cuối cùng Hoàng đế sốt ruột gắt: "Được, thế cao tăng có nói rõ cho ta lời giải hay không cơ chứ?". Thay vì giải thích tiếp, gã kỳ nhân mỉm cười thâm thúy rồi biến mất, bởi vì hoàng đế tuy giỏi giang nhưng rõ ràng là chưa hiểu ý nghĩa của phép truy hồi (recursion). Nhưng các bạn sinh viên ngày nay thì có thể thấy cách giải của vị cao tăng là hoàn toàn đúngTừ việc tìm hiểu lịch sử bài toán ta thấy rõ được yêu cầu bài toán như sau:• Mỗi lần chỉ được chuyển một đĩa• Một đĩa có thể được chuyển từ một cọc này sang cọc khác bất kỳ• Không thể để đĩa lớn bên trên đĩa nhỏ 1.2. Phân tích & đánh giá ban đầuBài toán Tháp Hà Nội là một bài toán rất thú vị. Bạn có thể bắt đầu bằng bài toán 3 đĩa, rồi nâng lên 4 đĩa. Với 4 đĩa chắc bạn bắt đầu thấy rắc rối. Nâng tiếp lên 5 và cao hơn nữa, chẳng hạn n = 1 triệu, bài toán sẽ rắc rối đến mức không ai đủ kiên trì và đủ thì giờ để thử từng đĩa một. Vậy mà vị cao tăng nêu trên lại nói là dễ quá! Vì vị đó đã sử dụng phép truy hồi, một quy tắc toán học cho phép xác định số hạng thứ n từ số hạng đứng trước nó, tức số hạng thứ n-1. Cái giỏi của vị cao tăng là ông tìm ra một quy tắc chung, tức một thuật toán chung cho tất cả các bước chuyển đĩa.Thay vì mô tả toàn bộ quá trình chuyển đĩa từng cái một, người ta đã mô tả một quy tắc chung. Cứ làm theo quy tắc đó, lặp đi lặp lại chẳng cần suy nghĩ gì, rồi cuối cùng tự nhiên sẽ tới đích. Vì thế vị cao tăng nói rằng bài toán này "tự nó giải nó".Và vì vậy, một hướng tối ưu để giải quyết bài toán này là bằng cách sử dụng phép truy hồi, hay còn được gọi là phép đệ quy.- 5 -K8 TIN Đại Học Hùng VươngChương 2.GIẢI THUẬT ĐỆ QUYTHUẬT TOÁN & CÀI ĐẶT CHƯƠNG TRÌNH2.1. Sơ lược về giải thuật đệ quy2.1.1. Khái niệm đệ quyTa nói một đối tượng là đệ quy (recursive algorithm) nếu nó bao gồm chính nó như một bộ phận hoặc nó được định nghĩa dưới dạng của chính nó.Ví dụ: 1. Số tự nhiêna) 1 là một số tự nhiênb) x là số tự nhiên nếu x-1 là số tự nhiên2. Hàm n giai thừa: n!a) 0! = 1b) Nếu n > 0 thì n! = n(n-1)!2.2.2. Giải thuật đệ quyNếu lời giải của bài toán T được thực hiện bằng lời giải của một bài toán T’, có dạng giống T, thì đó là một lời giải đệ quy. Giải thuật tương tự với lời giải như vậy gọi là giải thuật đệ quy.Thoạt nghe thì có vẻ hơi lạ, nhưng điểm mấu chốt cần lưu ý đó là: T’ tuy có dạng giống như T, nhưng theo một nghĩa nào đó, nó phải “nhỏ” hơn T.2.2.3. Thiết kế giải thuật đệ quyKhi bài toán đang xét hoặc dữ liệu được định nghĩa dưới dạng đệ quy thì việc thiết kế các giải thuật tỏ ra rất thuận lợi. Hầu như nó phản ánh rất sát nội dung của định nghĩa đó.*** Trên cơ sở thừa kế tinh thần của các mục trên, dưới đây sẽ trình bày thuật toán đệ quy áp dụng vào việc giải quyết bài toán Tháp Hà Nội đã được nêu ở chương 1.- 6 -K8 TIN Đại Học Hùng Vương2.2. Thuật toánTrước tiên ta đánh số thứ tự cho 3 cọc, giả sử là c1, c2, c3. Và cũng giả sử rằng có n đĩa với đường kính giảm dần được đánh số thứ tự từ trên xuống dưới, xếp vào cọc c1 như hình vẽ:Bài toán với một khối dữ liệu lớn được đưa vào để tính toán. Để giải quyết vấn đề trên, ta phải tìm cách để chia nhỏ được khối dữ liệu đó. Với bộ dữ liệu đưa vào là n đĩa, ta sẽ chia bộ dữ liệu này thành 2 bộ dữ liệu con là n-1 đĩa trên, từ đĩa thứ nhất tới đĩa thứ n-1, và 1 đĩa lớn nhất ở dưới cùng, tức là đĩa thứ n. Việc chia như vậy phải có tính đệ quy, tức là chia nhỏ cho tới khi giải quyết được bằng cách đơn giản nhất.Trước hết, ta xét vài trường hợp đơn giản:• Trường hợp n=1 đĩa:- Chuyển đĩa từ c1 sang c2• Trường hợp n=2 đĩa:- Chuyển đĩa 1 từ c1 sang c3- Chuyển đĩa 2 từ c1 sang c2- Chuyển đĩa 1 từ c3 sang c2• Trường hợp n > 2, nếu coi (n-1) đĩa ở trên, đóng vai trò như đĩa thứ nhất thì có thể xử lý giống như trường hợp 2 đĩa được, nghĩa là: - Chuyển (n-1) đĩa trên từ c1 sang c3- Chuyển đĩa thứ n từ c1 sang c2- Chuyển (n-1) đĩa từ c3 sang c2Một cách tổng quát, khi không còn là một đĩa, toàn bộ quá trình thực hiện di chuyển được chia làm 3 giai đoạn:Giai đoạn 1: chuyển n-1 đĩa trên từ cọc gốc đến cọc trung gianGiai đoạn 2: chuyển một đĩa (đĩa thứ n) từ cọc gốc đến cọc đíchGiai đoạn 3: chuyển n-1 đĩa từ cọc trung gian đến cọc đích- 7 -K8 TIN Đại Học Hùng VươngCó thể hình dung việc thể hiện 3 giai đoạn này theo mô hình: - 8 -K8 TIN Đại Học Hùng VươngĐể giải quyết các giai đoạn trên, ta đưa ra một chương trình con “dich_chuyen” với cấu trúc như sau:dich_chuyen(n_dia, tu_coc, toi_coc, coc_trung_gian);procedure dich_chuyen(n, c1, c2, c3:integer);beginif n=1 then writeln(c1, ‘ -> ‘,c2) elsebegindich_chuyen(n-1, c1, c3, c2);dich_chuyen( 1, c1, c2, c3);dich_chuyen(n-1, c3, c2, c1);end;end;Trong đoạn chương trình con trên, tại sao ta phải có lời gọi đệ quy của chính nó tới 3 lần? Bởi vì mỗi một lần gọi như vậy thể hiện một giai đoạn vừa kể trên. Ban đầu, ta muốn di chuyển toàn bộ n đĩa từ cọc gốc (c1) sang cọc đích (c2). Muốn làm được công việc đó, trước hết phải kiểm tra xem số đĩa cần chuyển có phải là một đĩa không. n=1 là điều kiện đóng hay trường hợp suy biến của bài toán, nếu điều này đúng thì sau khi thực hiện công việc dịch chuyển xong, thủ tục sẽ kết thúc. Còn nếu không phải là một đĩa thì qua các lời gọi, các lớp chương trình sẽ tiếp tục được đưa ra để thực hiện công việc đến khi điều kiện n=1 đúng thì thôi.Xét một ví dụ với n=3. Quá trình thực hiện của trình biên dịch như sau:Mức chương trình đầu tiên được gọi tới:{muc 1} dich_chuyen(3, c1, c2, c3);Ở đây n<> 1 cho nên điều kiện n=1 không thỏa mãn. Mức chương trình tiếp theo sẽ được gọi tới như sau:{muc 2} dich_chuyen(2, c1, c3, c2); dich_chuyen(1, c1, c2, c3);dich_chuyen(2, c3, c2, c1);Chuyển sang mức chương trình thứ hai (n - 1 = 2):{procedure} dich_chuyen(2, c1, c3, c2);Trong thủ tục này thì n=2, vẫn khác 1, chưa thể kết thúc được, lại tiếp tục gọi tới lớp chương trình tiếp theo:{muc 3} dich_chuyen(1, c1, c3, c2);dich_chuyen(1, c1, c2, c3);dich_chuyen(1, c3, c2, c1);- 9 -K8 TIN Đại Học Hùng VươngLúc này, điều kiện n=1 được thỏa mãn nên không còn lời gọi mức chương trình tiếp theo. Công việc được thực hiện ở mức này đó là:- Chuyển 1 đĩa từ cọc (c1) đến cọc (c3).Mức 3 hoàn thành ở câu lệnh thứ nhất của mức 2, mức 2 tiếp tục thực hiện công việc tiếp theo của nó:- Chuyển 1 đĩa từ cọc (c1) đến cọc (c2).- Chuyển 1 đĩa từ cọc (c3) đến cọc (c1).Vậy mức 2 đã hoàn thành ở câu lệnh thứ nhất của mức 1. Mức 1 thực hiện tiếp các lệnh tiếp theo:- Chuyển 1 đĩa từ cọc (c1) sang cọc (c2).- Chuyển n-1 đĩa từ cọc (c3) sang cọc (c2).Đến đây, toàn bộ quá trình đệ quy trên lại được lặp lại. Bắt đầu mức 2 của câu lệnh thứ 3. Và cứ như vậy, bài toán dịch chuyển 3 đĩa đã được hoàn thành.Mô tả lại toàn bộ quá trình như sau:{muc 1} dich_chuyen(3, c1, c2, c3);{muc 2} dich_chuyen(2, c1, c3, c2);{muc 3} dich_chuyen(1, c1, c2, c3);dich_chuyen(1, c1, c3, c2);dich_chuyen(1, c2, c3, c1);dich_chuyen(1, c1, c2, c3);dich_chuyen(2, c3, c2, c1);{muc 2} dich_chuyen(1, c3, c1, c2);dich_chuyen(1, c3, c2, c1);dich_chuyen(1, c1, c2, c3);Như vậy, bài toán Tháp Hà Nội tổng quát với n đĩa được dẫn đến bài toán tương tự với kích thước nhỏ hơn. Và ta đã có lời giải cho bài toán tháp Hà Nội rất nổi tiếng.Việc áp dụng thuật toán đệ quy vào việc giải quyết bài toán này là một trong những giải pháp tối ưu nhất, dễ nghiên cứu, dễ hiểu.- 10 -K8 TIN Đại Học Hùng Vương2.3. Cài đặt chương trìnhProgram thaphanoi;uses crt;varn: integer;procedure dich_chuyen(n, c1, c2, c3:integer);beginif n=1 then writeln(c1, ‘  ‘,c2) elsebegindich_chuyen(n-1, c1, c3, c2);dich_chuyen( 1, c1, c2, c3);dich_chuyen(n-1, c3, c2, c1);end;end;BeginClrscr;Writeln(‘***************************************’);Writeln(‘* BAI TOAN THAP HA NOI *’);Writeln(‘***************************************’);write(‘Nhap so dia can chuyen: ‘);readln (n);writeln(‘Cac buoc chuyen dia nhu sau: ‘);dich_chuyen (n,1, 2, 3);readln ;end.*** Lưu ý rằng ở đây, khi thay đổi các mức đệ quy thì vai trò cũng như trật tự của các cọc đã được tự động hoán đổi cho nhau. - 11 -K8 TIN Đại Học Hùng Vương2.4 Độ phức tạp của bài toán:Nhận xét:• Kích thước của dữ liệu là n• Khi n=1 thì thời gian thực hiện la O(1)• Với n>1 cần thực hiện lệnh dich_chuyen, số lần dich chuyển tới 2n-1 lần.  Ta có quan hệ đệ quy như sau :T(1)=O(1)T(n) = O(1)+T(n-1)Từ đó ta tính được độ phức tạp của bài toán là:O(n)=T(n)=2n Chương 3.Ý NGHĨA CỦA BÀI TOÁN3.1. Về khoa họcTháp Hà Nội còn sử dụng trong nghiên cứu giáo dục về giải quyết vấn đề, trong chuẩn đoán và điều trị thần kinh sinh lí đối với các chức năng thực hành3.2. Trong lĩnh vực nghiên cứu toán-tinĐó là giải thuật đệ quy, hệ đếm, tam giác Pascal, thảm Sierpinski, lý thuyết đồ thị và chu trình Hamilton, ôtômát hữu hạn, độ phức tạp tính toán, 3.3.Trong lĩnh vực giải trí Tháp Hà Nội là một trò chơi trí tuệ rất vui, bổ ích, dễ học, dễ chơi, rèn luyện tính kiên nhẫn.- 12 -K8 TIN Đại Học Hùng Vương4.4. Về mặt lịch sử Tháp Hà Nội được E. Lucas phát hiện từ năm 1883, nhưng mãi đến gần đây người ta mới nhận ra ý nghĩa hiện đại của nó. Hiện vẫn chưa rõ vì sao Lucas lại gọi chồng đĩa trong bài toán là Tháp Hà Nội, mà không gọi là Tháp Bắc Kinh, hay Tháp Tokyo.4.5. Thành tựuTháp Hà Nội đã mở tung cánh cửa cho tương lai khi nhiều nghiên cứu lấy Tháp Hà Nội làm điểm xuất phát đã đạt được thành tựu mới:(1) Nâng câu hỏi của Tháp Hà Nội lên một mức cao hơn, sao cho số lần chuyển đĩa là nhỏ nhất. Các nhà toán học đã phát hiện ra rằng Tháp Hà Nội có cùng bản chất với bài toán tìm Đường Hamilton (Hamilton Path) trên một hình giả phương cấp n (n-Hypercube), một bài toán cũng rất nổi tiếng.(2) Nhà toán học D.G. Poole đã sáng tạo ra Lược Đồ Hà Nội - một tam giác có các đỉnh tương ứng với các cách sắp xếp đĩa trong Tháp Hà Nội, từ đó tìm ra những liên hệ lý thú giữa Tam giác Pascal với Lược đồ Hà Nội. Liên hệ này đã được công bố trong một công trình mang một cái tên đầy liên tưởng: Pascal biết Hà Nội (Pascal knows Hanoi). Hiện nay, tại một số đại học ở Australia, uy tín của sinh viên Việt Nam trong lĩnh vực lập trình được đánh giá ngang với sinh viên Ấn Độ - một cường quốc lập trình của thế giới, làm cho Tháp Hà Nội vốn đã nổi tiếng lại càng nổi tiếng hơn.***************o0o***************- 13 -K8 TIN Đại Học Hùng VươngTài liệu tham khảo1. Cấu trúc dữ liệu và giải thuật - Đỗ Xuân Lôi.2. Ngôn ngữ lập trình Pascal - Quách Tuấn Ngọc.4. Trò chơi tháp Hà Nội ( website: www.kienthuc.net)5. Tháp Hà Nội (website: www.vi.wikipedia.org) {Phân công công việc: }1. Tìm hiểu tài liệu: + Lịch sử bài toán & yêu cầu đề bài: Tuyết + Châm+ Cơ sở lý thuyết: Huyền+ Cách giải bài toán: Trung + Hương2. Thực hiện tiểu luận:+ Thuật toán & độ phức tạp bài toán:Tuyết + Cài đặt chương trình & Ứng dụng: Phong + Hương.+ Trình bày trên Word: Huyền + Châm + Trung+ Trình bày trên Powerpoint: Tuyết + Hương+ Thuyết Trình: Phong.- 14 -

Tài liệu liên quan

Đề tài tìm hiểu về hệ truyền động điện servox
- 71
- 775
- 1
Tài liệu Đề tài “Tìm hiểu về hệ thống phanh tay” docx
- 16
- 825
- 3
Tài liệu Đề tài :"Tìm hiểu về trọng tài quốc tế và sự khác biệt giữa trọng tài quốc tế và tòa án" pdf
- 13
- 710
- 0
Tài liệu Đề tài : "Tìm hiểu về thực trạng giải quyết tranh chấp trong lĩnh vực chứng khoán và đưa ra ý kiến pháp lý để hạn chế và giải quyết tốt các tranh chấp" pptx
- 17
- 953
- 0
Đề Tài: Tìm hiểu về thuế thu nhập doanh nghiệp docx
- 10
- 720
- 0
ĐỀ TÀI :Tìm hiểu về sự phát triển của Ngân hàng Nhân dân Trung Quốc và những tác động của nó đối với các nước trên thế giới potx
- 82
- 803
- 1
Đề tài: Tìm hiểu về quá trình hoạt động tín dụng của Ngân hàng taị điạ phương qua 3 năm 2005-2006-2007. ppt
- 44
- 676
- 0
Tiểu luận khoa học - Đề tài: "Tìm hiểu về tranzito khuếch đại công suất" doc
- 16
- 1
- 0
Đề tài: Tìm Hiểu Về Biến Tần S1 Của DELTA docx
- 32
- 940
- 0
Đề tài: Tìm hiểu về WLANS, WPANS và xu hướng phát triển thông tin di động 4G pptx
- 102
- 617
- 0