Đệ Quy Trong Toán Và Lập Trình

By QLamXmaster , Leave a Comment

Cơ bản về thuật toán đệ quy


1. Đệ quy là gì ?
Một đối tượng được gọi là đệ quy nếu nó được mô tả thông qua định nghĩa của chính nó. Nghĩa là, các đối tượng này được định nghĩa một cách quy nạp từ những khái niệm đơn giản nhất cùng dạng với nó. Trong toán học và tin học có rất nhiều đối tượng như thế.

VD :
- Số tự nhiên được định nghĩa như sau :
  • 0 là một số tự nhiên
  • Nếu k là một số tự nhiên thì k+1 cũng là một số tự nhiên
Theo đó, ta sẽ có : 1=0+1 là số tự nhiên, 2=1+1 cũng là một số tự nhiên,….Cứ như vậy ta sẽ định nghĩa được các số tự nhiên khác lớn hơn. Do đó, số tự nhiên là khái niệm mang bản chất đệ quy.
- Định nghĩa giai thừa của n (n!) :
  • Khi n=0, ta có 0!=1
  • Khi n>0, ta có n!=(n-1)! x n
Như vậy, ta suy ra : 1! = 0! x 1, 2! = 1! x 2,… –> giai thừa cũng là một khái niệm mang tính đệ quy.
2. Bài toán đệ quy
Đó là những bài toán mang bản chất đệ quy. Nghĩa là những bài toán này có thể được phân rã thành các bài toán nhỏ hơn, đơn giản hơn nhưng có cùng dạng với bài toán ban đầu. Những bài toán nhỏ lại được phân rã thành các bài toán nhỏ hơn. Cứ như vậy, việc phân rã chỉ dừng lại khi bài toán con đơn giản đến mức có thể suy ra ngay kết quả mà không cần phải phân rã nữa. Ta phải giải tất cả các bài toán con rồi kết hợp các kết quả đó lại để có được lời giải cho bài toán lớn ban đầu. Cách phân rã bài toán như vậy gọi là “chia để trị” (devide and conquer), là một dạng của đệ quy.
3. Đệ quy trong lập trình
Một hàm được gọi là đệ quy nếu bên trong thân nó có một lời gọi đến chính nó. Nghe có vẻ vô lý nhỉ ? Một hàm làm sao có thể gọi nó mãi được, vì nếu như vậy sẽ sinh ra một vòng lặp vô tận. Nhưng trong thực tế, một hàm đệ quy luôn có điều kiện đừng được gọi là “điểm neo”. Khi đạt tới điểm neo, hàm sẽ không gọi chính nó nữa.
Khi được gọi, hàm đệ quy thường được truyền cho một tham số, thường là kích thước của bài toán lớn ban đầu. Sau mỗi lời gọi đệ quy, tham số sẽ nhỏ dần, nhằm phản ánh bài toán đã nhỏ hơn và đơn giản hơn. Khi tham số đạt tới một giá trị cực tiểu (tại điểm neo), hàm sẽ chấm dứt.
Trong lập trình, một bài toán muốn giải quyết bằng đệ quy thì bản thân nó phải là một bài toán đệ quy. Tức là bài toán đó có thể được đưa về bài toán cùng dạng nhưng đơn giản hơn.
4. Một số bài toán đệ quy kinh điển
a. Bài toán tính giai thừa
Cho n là một số tự nhiên (n>=0). Hãy tính giai thừa của n (n!) biết rằng 0!=1 và n!=(n-1)! x n.
Phân tích :
- Theo giả thiết, ta có : n! = (n-1)! x n. Như vậy :
  • Để tính n! ta cần phải tính (n-1)!
  • Để tính (n-1)! ta phải tính (n-2)!
  • …
- Cứ như vậy, cho tới khi gặp trường hợp 0!. Khi đó ta lập tức có được kết quả là 1, không cần phải tính thông qua một kết quả trung gian khác.
Cài đặt trên C# :
Code
  1. public static long GiaiThua(int n)
  2. {
  3.     if (n == 0) return 1;   //điểm neo
  4.     return n * GiaiThua(n – 1);     //gọi đệ quy
  5. }
- Ở đây, điểm neo chính là n=0. Sau mỗi lời gọi đệ quy, n sẽ giảm xuống 1 cho đến khi gặp điểm neo.
b. Dãy Fibonaci
Dãy Fibonaci là dãy vô hạn các số tự nhiên. Số Fibonaci thứ n, ký hiệu F(n), được định nghĩa như sau :
  • F(n) = 1, nếu n=1 hoặc n=2
  • F(n) = F(n-1) + F(n-2), nếu n>=3
c. Bài toán “Tháp Hà Nội” (Tower of Ha Noi)
Đây là một bài toán rất nổi tiếng và kinh điển, rất thích hợp để minh họa cho thuật toán đệ quy. Sau đây là nội dung bài toán :
Có 3 chiếc cọc được đánh dấu lần lượt là A, B, C và n chiếc đĩa. Các đĩa này có kích thước khác nhau và mỗi đĩa đều có một lỗ ở giữa để cắm vào cọc. Ban đầu, các đĩa đều nằm ở cọc A, trong đó, đĩa nhỏ luôn nằm trên đĩa lớn hơn.

Yêu cầu : chuyển n đĩa từ cọc A sang cọc đích C với các điều kiện sau :
+ Mỗi lần chỉ chuyển được 1 đĩa
+ Trong quá trình chuyển, đĩa nhỏ phải luôn nằm trên đĩa lớn hơn.
+ Cho phép sử dụng cọc B làm cọc trung gian
Phân tích : ta sẽ xét các trường hợp của n
- Trường hợp đơn giản nhất, n=1, ta chỉ cần chuyển 1 đĩa từ cọc A sang cọc C.
- Nhiều hơn một chút, n=2, ta chuyển đĩa nhỏ nhất sang cọc B, chuyển đĩa còn lại sang cọc C, và cuối cùng chuyển đĩa nhỏ ở cọc B sang cọc C.
- Bây giờ ta xét n đĩa (n>2). Giả sử ta đã có cách chuyển n-1 đĩa từ một cọc sang một cọc khác. Như vậy, để chuyển n đĩa từ cọc nguồn sang cọc đích, ta cần chuyển n-1 đĩa từ cọc nguồn sang cọc trung gian. Sau đó chuyển đĩa lớn nhất từ cọc nguồn sang cọc đích. Cuối cùng, chuyển n-1 từ cọc trung gian về cọc đích.
Cài đặt bằng C# :
Code
  1. public static void ThapHaNoi(int n, char nguon, char dich, char tgian)
  2. {
  3.     //điểm neo
  4.     if (n == 1) Console.WriteLine(“Chuyen 1 dia tu {0} sang {1}”, nguon, dich);
  5.     else
  6.     {
  7.         //chuyển n-1 đĩa từ cọc nguồn sang cọc trung gian,
  8.         //lấy cọc đích làm cọc phụ
  9.         ThapHaNoi(n – 1, nguon, tgian, dich);
  10.         //chuyển còn lại từ cọc nguồn sang cọc đích
  11.         Console.WriteLine(“Chuyen 1 dia tu {0} sang {1}”, nguon, dich);
  12.         //chuyễn n-1 từ cọc trung gian về cọc đích,
  13.         //lấy cọc nguồn làm cọc trung gian
  14.         ThapHaNoi(n – 1, tgian, dich, nguon);
  15.     }
  16. }
Hàm trên có nhiệm vụ chuyển n đĩa từ cột nguon sang cọc dich, sử dụng cọc tgian làm cọc phụ. Ở đây ta ký hiệu các cột là A, B, C nên ta sẽ dùng kiểu char.
Như vậy, ta đã tìm hiểu xong những điểm cơ bản về đệ quy. Trên đây chỉ là những bài toán đệ quy đơn giản. Còn rất nhiều bài toán và kỹ thuật khác sử dụng phương pháp đệ quy.
Nguồn Internet
Xem Tiếp

Mẫu Thiệp 3D (thiệp nổi) Chúc mừng ngày nhà giáo VN 20/11

By QLamXmaster , Leave a Comment
1.
làm thiệp hoa dễ thương cho ngày nhà giáo 20/11 20
làm thiệp hoa dễ thương cho ngày nhà giáo 20/11 21
làm thiệp hoa dễ thương cho ngày nhà giáo 20/11 22



2.




3.


4.




5.


6.






Xem Tiếp

Khảo sát hàm số - giải tích 1

By QLamXmaster , Leave a Comment
1. Phương trình tham số của đường cong:
Cho hai hàm số: \left \{ \begin{array}{c} {x = x(t) \qquad (1)} \\{y = y(t) \qquad (2)} \end{array} \right.
Khi t thay đổi, điểm \text{M(x(t), y(t))} vẽ nên đường cong (C) trong mặt phẳng tọa độ (Oxy).
Nếu từ (1) ta giải được t theo x ( t = t(x)) rồi thế vào (2) thì ta sẽ có phương trình của đường cong (C) : y = f(x).
Các hàm số {(1), (2)} được gọi là phương trình tham số của đường cong (C).
Ví dụ 1: Xét hyperbol (H): { \dfrac{x^2}{a^2} - \dfrac{y^2}{b^2} =1}
Vì hiệu bình phương của { \dfrac{x}{a}} , { \dfrac{y}{b}} bằng 1, nên có thể coi chúng là cht và sht:
\dfrac{x}{a} = cht , \dfrac{y}{b} = sht , t \in \mathbb R
Vậy ta có phương trình tham số của Hyperbol là:
\fbox {x = a.cht ; y = b.sht}
Ví dụ 2: Xicloit là quỹ đạo của một điểm M nằm trên một đường tròn bán kính a khi vòng tròn đó lăn không trượt trên một đường thẳng.
Giả sử vòng tròn lăn về phía hướng dương của trục Ox (và lăn trên trục hoành) , vị trí ban đầu của M trùng với gốc tọa độ O.
cycloidanim04.gif
Khi đó, ta dễ dàng xác định được phương trình tham số của quỹ đạo điểm M là:
\fbox {x = a.(t \!- sint) \qquad; \qquad y = a.(1 \!- cost)}
2. Khảo sát đường cong cho bằng tham số:
Việc khảo sát và vẽ đồ thị của đường cong tham số tiến hành tương tự như đã làm đối với đường cong có phương trình y = f(x) . Gồm các bước sau đây:
  1. Tìm miền xác định, tính chẵn lẻ, tuần hoàn.
  2. Khảo sát và lập bảng biến thiên:
    • Tính đạo hàm { \dfrac{{dy}}{{dx}} = \dfrac{{{y'}_t}}{{{x'}_t}} = \dfrac{\dot{y}}{\dot{x}} } \qquad (3)
    • Tìm các giá trị của tham số t sao cho tại đó ít nhất một trong các đạo hàm \dot{x} = x_{t}^{'} hay \dot{y} = y_{t}^{'} triệt tiêu. (nếu tồn tại t_0 sao cho \dot{x}(t_{0}) = x_{t}^{'}(t_0) = 0 , \dot{y}(t_{0}) = y_{t}^{'}(t_0) = 0 thì điểm M(x_0 , y_0) là điểm kỳ dị, với x_0 = x(t_0) , y_0 = y(t_0) ).
    • Mỗi khoảng (t_k , t_{k+1}) tương ứng với khoảng (x_k , x_{k+1}) sẽ xác định dấu của y'(x).
    • Tính đạo hàm cấp 2:
    { \dfrac{d^{2}y}{dx^2}} = { \dfrac{y''(t).x'(t) - x''(t).y'(t)}{{[x'(t)]}^3}} = { \dfrac{{\ddot{y}}.{\dot{x}} - {\ddot{x}}.{\dot{y}}}{{\dot{x}}^3} } \qquad (4)
  3. Từ (4) ta tìm các giá trị để đạo hàm cấp 2 triệt tiêu, từ đó xác định khoảng lồi, lõm của đường cong.
  4. Tìm tiệm cận của đường cong:
  • Nếu lim_{t \to t_0} x(t) = a , \lim_{t \to t_0} y(t) = \infty thì x = a là tiệm cận đứng.
  • Nếu lim_{t \to t_0} x(t) = \infty , \lim_{t \to t_0} y(t) = b thì y = b là tiệm cận ngang.
  • Nếu khi t \to t_0 , x \to \infty , y \to \infty và:
lim_{t \to t_0} \frac{y(t)}{x(t)} = a , lim_{t \to t_0} [y(t) \! - ax(t) ] = b
thì y = ax + b là tiệm cận xiên.
3. Các ví dụ minh họa:
Ví dụ 1: Khảo sát và vẽ đường cong cho bởi phương trình:
\left \{ \begin{array}{c} {x = acos^{3}t} \\{y = asin^{3}t} \end{array} \right.
Các hàm số x(t), y(t) xác định với mọi t.
Nhưng vì các hàm số acos^{3}t, asin^{3}t là các hàm số tuần hoàn với chu kỳ 2\pi nên ta chỉ cần khảo sát với t nằm trong đoạn [0;2\pi ].
Do đó, khoảng biến thiên của x là đoạn [-a; a] và khoảng biến thiên của y là đoạn [-a; a].
Vậy đường cong được khảo sát không có tiệm cận.
Xét khoảng biến thiên. Ta có:
x_t^{'} = -3acos^{2}tsint = 0 khi t=0, { \frac{ \pi}{2} }, \pi , { \frac{3 \pi}{2} } ,2\pi
y_t^{'} = 3asin^{2}tcost khi t=0, { \frac{ \pi}{2} }, \pi , { \frac{3 \pi}{2} } ,2\pi
y_{x}^{'} = -tg t = 0 khi t = 0, \pi , 2\pi y_{x}^{'} = \infty tại { \dfrac{\pi}{2}} , { \dfrac{3\pi}{2}}
Ta có bảng biến thiên sau:
\begin{array}{c| c c c c c c c c c} \hline t & 0 & \quad & {\pi}/2 & \quad & {\pi} & \quad & 3{\pi}/2 & \quad & 2{pi} \\ \hline x't & 0 & - & 0 & - & 0 & + & 0 &+ & 0 \\ \hline x & a & \searrow & 0 & \searrow & -a & \nearrow & 0 & \nearrow & a \\ \hline y't & 0 & + & 0 & - & 0 & - & 0 & + & 0 \\ \hline y & 0 & \nearrow & a & \searrow & 0 & \searrow & -a & \nearrow & 0 \\ \hline \ y'x & 0 & - & || & + & 0 & - & || & + & 0 \\ \hline \end{array}
Tính đạo hàm cấp hai ta có:
\ddot{y} = 6a.cost.sin^{2}t - 3a.cos^{3}t
\ddot{x} = 6a.sint.cos^{2}t - 3a.sin^{3}t
Do đó:
{ \dfrac{d^{2}y}{dx^2}} = { \dfrac{{\ddot{y}}.{\dot{x}} - {\ddot{x}}.{\dot{y}}}{{\dot{x}}^3} } = { \dfrac{1}{3a.cos^{4}t.sint}}
Nhận thấy:
Khi 0 < t < \pi : thì đường cong lõm
Khi \pi < t < 2{\pi} : thì đường cong lồi
Lại có:
Khi 0 \le t \le {\pi}/2 : thì x \ge 0 , y \ge 0 nên đường cong nằm trong góc phần tư thứ nhất
Khi {\pi}/2 \le t \le {\pi} : thì x \le 0 , y \ge 0 nên đường cong nằm trong góc phần tư thứ hai.
Khi {\pi} \le t \le 3.{\pi}/2 : thì x \le 0 , y \le 0 nên đường cong nằm trong góc phần tư thứ ba.
Khi 3{\pi}/2 \le t \le 2.{\pi} : thì x \ge 0 , y \le 0 nên đường cong nằm trong góc phần tư thứ tư.
Từ những dữ liệu trên ta sẽ có đường cong (C) trong mặt phằng là đường màu đỏ trong hình sau:
astroid01.gif

Phương trình đường cong (C) có được bằng cách lăn đường tròn nhỏ, bán kính a/4 bên tròn đường tròn lớn, bán kính a theo hướng ngược chiều kim đồng hồ, bắt đầu từ điểm (1;0)
Xem Tiếp