Chủ đề này có 13 trả lời

[m&i_star]

các bác cho tui hỏi chút nha:
_thứ nhất : có ai có đề thi tin học quốc gia (cả bảng A và B) 2 năm gần đây ko?gửi cho tui nha.cám ơn rất rất nhiều.
_thứ hai: các bác thấy đệ quy trong pascal có khó xơi ko?

[duylong01]

đề quốc gia thì mình không có,bạn thử lên trang web sau www.thnt.com.vn mà tìm.
Còn về đệ qui mình thấy không khó xơi )

[Magus]

các bác cho tui hỏi chút nha:
_thứ nhất : có ai có đề thi tin học quốc gia (cả bảng A và B) 2 năm gần đây ko?gửi cho tui nha.cám ơn rất rất nhiều.
_thứ hai: các bác thấy đệ quy trong pascal có khó xơi ko?

Có đây:

http://www.lamdong.g...ng/dethi/11.HTM


Còn đề quốc gia thì đây:
http://www.lamdong.g...thi/11/DTQG.HTM

[kaka'sfan]

bọn mình chưa học hệ đệ qui nên không bít nó có khó không!
u đc học rồi hả?thấy có khó không?mà các bạn có tài liệu tin học nào về pascal không ?chỉ cho mình với

[vuviet]

đệ quy cũng ko khó lắm cứ chịu khó mà cày

[toanhoc]

Đệ quy không phụ thuộc ngôn ngữ lập trình. Nó xuất phát từ các giải thuật đệ quy (recursive algorithms) ví dụ tính n! hay dãy Fibonacci. Bạn có thể cài đặt không dùng đệ quy của Pascal mà dùng cấu trúc dữ liệu Stack. Cái này hình như các giáo trình tiếng Việt gọi là khử đệ quy. Đệ quy thực ra rất cồng kềnh, chỉ được cái là code ngắn. Bạn tìm hiểu sâu thêm sẽ có cái nhìn toàn diện.
Books: Algorithms-Robert Sedgewick (Cẩm nang thuật toán-bản dịch)
Data structures and algorithms (Aho-Hoftcroft-Ullman) (kinh điển)

[TheIncredibleMachine]

Đệ quy không phụ thuộc ngôn ngữ lập trình. Nó xuất phát từ các giải thuật đệ quy (recursive algorithms) ví dụ tính n! hay dãy Fibonacci. Bạn có thể cài đặt không dùng đệ quy của Pascal mà dùng cấu trúc dữ liệu Stack. Cái này hình như các giáo trình tiếng Việt gọi là khử đệ quy. Đệ quy thực ra rất cồng kềnh, chỉ được cái là code ngắn. Bạn tìm hiểu sâu thêm sẽ có cái nhìn toàn diện.

Mình thấy không đúng lắm, cách dựa vào Stack để khử đệ quy chỉ là một trong những phương pháp khử đệ quy mà thôi. Hơn nữa, bài toán n! được người ta tính bằng phương pháp Quy hoạch động, chỉ đơn giản dùng 3 biến lưu trữ.
Đệ quy rất không khả thi trong nhiều bài toán vì bộ nhớ cần cho đệ quy khá nhiều, chương trình đệ quy khó kiểm soát, nhưng cái bất lợi lớn nhất là rất nhiều trường hợp, đệ quy phải tính lại một giá trị đã tính ở các bước truớc đó rồi.
Mặc dù vậy, một số bài toán tin kinh điển như các bài NP-complete, bài toán người du lịch, các bài toán áp dụng phương pháp sinh hoặc các bài toán quay lui,... thì đệ quy kết hợp đặt cận là phương pháp cực kỳ hữu hiệu.
Mọi người hay quan niệm là đệ quy thường duyệt, code ngắn nhưng chương trình tốn nhiều bộ nhớ, chạy lâu, kỳ thực không phải như vậy. Đệ quy là một kỹ thuật được áp dụng cho nhiều thuật toán chứ không hoàn toàn là một thuật toán đơn lẻ. Những điều bất lợi cho đệ quy đem lại là do thuật toán mà chúng ta dùng đệ quy để thực thi, chứ không phải do đệ quy. Một trong 10 thuật toán hay nhất thế kỷ là QuickSort chẳng phải được cài đặt bằng đệ quy hay sao? Rất hiệu quả mà mạnh mẽ.

[Magus]

Khử đệ quy thực chất là chúng ta phải làm công việc của một trình biên dịch đối với một thủ tục, đó là: Đặt tất cả các giá trị của các biến cục bộ và địa chỉ của chỉ thị kế tiếp vào ngăn xếp (Stack), quy định các giá trị tham số cho thủ tục và chuyển tới vị trí bắt đầu thủ tục, thực hiện lần lượt từng câu lệnh. Sau khi thủ tục hoàn tất thì nó phải lấy ra khỏi ngăn xếp địa chỉ trả về và các giá trị của các biến cục bộ, khôi phục các biến và chuyển tới địa chỉ trả về.Vậy anh nói rõ ra nếu ko dựa vào Stack thì còn cách nào khả quan hơn nữa?

Đệ quy là một kỹ thuật được áp dụng cho nhiều thuật toán chứ không hoàn toàn là một thuật toán đơn lẻ. Những điều bất lợi cho đệ quy đem lại là do thuật toán mà chúng ta dùng đệ quy để thực thi, chứ không phải do đệ quy. Một trong 10 thuật toán hay nhất thế kỷ là QuickSort chẳng phải được cài đặt bằng đệ quy hay sao? Rất hiệu quả mà mạnh mẽ.

Người ta vẫn chú trọng Đệ quy vì Đệ quy là quả tim trong các nghiên cứu lý thuyết cũng như thực hành tính toán

[toanhoc]

Tóm lại, đệ quy chỉ là kỹ thuật cài đặt dành cho recursive algorithms, không có gì hơn. Nếu thuật toán mà không phải là recursive thì không dùng được. Thực tế có một số ngôn ngữ không hỗ trợ đệ quy. Recursive có lẽ được dịch là quay lui. Đừng gom tất cả NP complete vào đây. Phổ các bài toán này rất rộng, traveling salesman person chỉ là một trong số đó. NP complete là khái niệm cơ bản cho millenium problem "P vs NP". Cái mà người ta thường cài bằng đệ quy là các approximation algorithms.
Magus mô tả cách trình biên dịch thực thi đệ quy. Ý tôi là không làm thế trình biên dịch. Bạn chạy vòng lặp với cấu trúc stack i.e. không lưu toàn bộ variables, cũng không cần dùng lệnh go to, chỉ lưu cái biến giữ giá trị cơ bản của thuật toán. Một trong các bài tập hay là cài đặt reversed Polish notation (qua đây ta cũng biết cách máy tình thực hiện các phép toán-không hề có dấu ngoặc) và Quick sort bằng 2 cách đệ quy+không đệ quy.
Just for fun. Gửi các bạn bài của Edsger W. Dijkstra về câu lệnh go to
http://www.acm.org/classics/oct95/
Đây có lẽ là bài đầu tiên mà cũng là bài nổi tiếng nhất thuộc thể loại "considered harmful".

[Magus]

Nếu thuật toán mà không phải là recursive thì không dùng được

recursive có phải là Recursive Maximum Likehood Estimation of Autoregressive Process của ông
Steven M. Key không anh? nếu có tài liệu ebook về thuật toán này thì anh send em cái

[TheIncredibleMachine]

Khử đệ quy thực chất là chúng ta phải làm công việc của một trình biên dịch đối với một thủ tục, đó là: Đặt tất cả các giá trị của các biến cục bộ và địa chỉ của chỉ thị kế tiếp vào ngăn xếp (Stack), quy định các giá trị tham số cho thủ tục và chuyển tới vị trí bắt đầu thủ tục, thực hiện lần lượt từng câu lệnh. Sau khi thủ tục hoàn tất thì nó phải lấy ra khỏi ngăn xếp địa chỉ trả về và các giá trị của các biến cục bộ, khôi phục các biến và chuyển tới địa chỉ trả về.Vậy anh nói rõ ra nếu ko dựa vào Stack thì còn cách nào khả quan hơn nữa?

Stack là mô phỏng đệ quy!!!! Chứ không phải là chuyển bài toán đệ quy sang dạng khác để khử đệ quy!!! Bài toán dẫy Fibonaccy chẳng hạn, bây giờ ai người ta dùng đệ quy để giải, chỉ đưa ra đệ quy để hiểu nguyên lý thôi, còn người ta dùng quy hoạch động. Rất nhiều cấu trúc dữ liệu như Interval Tree cũng được cài đặt bằng đệ quy, chẳng ai dại gì mà đi khử đệ quy bằng Stack, hiệu quả không bằng mà tốn công cài đặt.

[nhantt2]

Có ai có bài giải mấy bài này không?help me
Bài 1: Cho hai dãy số a, b độ dài bằng nhau. Gọi chi phí chọn cho một cặp số a[i], b[j] là |a[i] + b[j]|. Tìm các cặp số a[i], b[j] trong 2 dãy sao cho tổng chi phí chọn là nhỏ nhất.
Giới hạn: nhiều nhất có 1000 số mỗi dãy.

Bài 2: Cho một dãy các ô, mỗi ô ghi một số nguyên dương. (a[i] là số ghi ở ô thứ i). Giữa các ô có các đường nối độ dài 1 với quy tắc: nếu tồn tại 3 số i, j, k sao cho a[k] = a[i] + a[j] thì nối i đến k, j đến k (đường một chiều). Tìm đường đi dài nhất qua các ô này (đi qua các đường nối - tất nhiên).
Giới hạn: nhiều nhất có 10000 ô.

Bài 3: Cho một miếng sôcôla hình vuông, cạnh 2^k.
Ta bắt đầu cắt song song với các cạnh, đầu tiên cắt song song với cạnh ngang chia thành 2 phần bằng nhau, rồi gấp phần dưới chồng lên phần trên => thành 1 chồng.(kiểu gấp sách). Sau đó cắt song song với cạnh dọc chia thành 2 phần bằng nhau, rồi gấp phần bên phải lên chồng bên trái => thành 1 chồng.
Lặp lại cho đến khi chồng sôcôla có độ dài cạnh là 1 (các miếng hình vuông).
Vấn đề: cho trước hai ô (p, q), (u, v), hỏi sau khi cắt như trên thì 2 ô này nằm ở vị trí thứ mấy?
Giới hạn: k <= 40.

[haominh]

Có ai có bài giải mấy bài này không?help me
Bài 1: Cho hai dãy số a, b độ dài bằng nhau. Gọi chi phí chọn cho một cặp số a[i], b[j] là |a[i] + b[j]|. Tìm các cặp số a[i], b[j] trong 2 dãy sao cho tổng chi phí chọn là nhỏ nhất.
Giới hạn: nhiều nhất có 1000 số mỗi dãy.

Bài 2: Cho một dãy các ô, mỗi ô ghi một số nguyên dương. (a[i] là số ghi ở ô thứ i). Giữa các ô có các đường nối độ dài 1 với quy tắc: nếu tồn tại 3 số i, j, k sao cho a[k] = a[i] + a[j] thì nối i đến k, j đến k (đường một chiều). Tìm đường đi dài nhất qua các ô này (đi qua các đường nối - tất nhiên).
Giới hạn: nhiều nhất có 10000 ô.

Bài 3: Cho một miếng sôcôla hình vuông, cạnh 2^k.
Ta bắt đầu cắt song song với các cạnh, đầu tiên cắt song song với cạnh ngang chia thành 2 phần bằng nhau, rồi gấp phần dưới chồng lên phần trên => thành 1 chồng.(kiểu gấp sách). Sau đó cắt song song với cạnh dọc chia thành 2 phần bằng nhau, rồi gấp phần bên phải lên chồng bên trái => thành 1 chồng.
Lặp lại cho đến khi chồng sôcôla có độ dài cạnh là 1 (các miếng hình vuông).
Vấn đề: cho trước hai ô (p, q), (u, v), hỏi sau khi cắt như trên thì 2 ô này nằm ở vị trí thứ mấy?
Giới hạn: k <= 40.

Nè bạn, đây là đề và bài giải mấy bài toán bạn nói đến đó, cũng dễ hiểu lắm
 De_bai_va_loi_giai_thi_quoc_gia_tin_hoc_2008.pdf   143.09K   33 Số lần tải

[DinhCuongTk14]

Có bạn hay anh chị nào có tài liệu tin luyện thi QG ko?có đứa em đang cần để năm sau thi ?? tài liệu TA hay tiếng việt gì cũng được mình cảm ơn nhé!