tek4

[Lập trình C từ 0 đến 1]Bài 17. Đệ quy

by - September. 21, 2021
Kiến thức
<p style="text-align: justify;">B&agrave;i viết &ldquo;[Lập tr&igrave;nh C từ 0 đến 1] B&agrave;i 7. Biến trong C v&agrave; c&aacute;c vấn đề li&ecirc;n quan&rdquo; l&agrave; b&agrave;i viết tiếp theo nằm trong series hướng dẫn học lập tr&igrave;nh C của&nbsp;<a href="../../../" target="_blank" rel="noopener">tek4.vn</a>.</p> <p style="text-align: justify;">Độc giả c&oacute; thể tham khảo c&aacute;c b&agrave;i viết kh&aacute;c trong series b&agrave;i viết n&agrave;y&nbsp;<a href="../../../lap-trinh-c-co-ban-den-nang-cao/" target="_blank" rel="noopener">tại đ&acirc;y</a></p> <p style="text-align: justify;">B&agrave;i viết n&agrave;y sẽ cung cấp đến độc giả về đệ quy. Đệ quy được sử dụng như thế n&agrave;o trong C. Trong loạt b&agrave;i hướng dẫn [Lập tr&igrave;nh C từ 0 đến 1], IDE được sử dụng l&agrave; Code::Blocks</p> <h2 id="ftoc-heading-2" class="cap1 ftwp-heading">1. KH&Aacute;I NIỆM CHUNG VỀ &ETH;Ệ QUY</h2> <h3>1.1. Kh&aacute;i niệm</h3> <p style="text-align: justify;" align="justify">C&aacute;c chương tr&igrave;nh m&agrave; ch&uacute;ng ta đ&atilde; xem x&eacute;t đều c&oacute; chung cấu tr&uacute;c dạng h&agrave;m v&agrave; việc gọi c&aacute;c h&agrave;m sẽ dưới dạng m&ocirc; h&igrave;nh ph&acirc;n cấp. Tuy nhi&ecirc;n đối với một số b&agrave;i to&aacute;n, việc d&ugrave;ng h&agrave;m gọi ngay ch&iacute;nh n&oacute; rất hữu dụng. C&oacute; thể định nghĩa h&agrave;m đệ quy l&agrave; h&agrave;m sẽ gọi đến ch&iacute;nh n&oacute; trực tiếp hay gi&aacute;n tiếp th&ocirc;ng qua c&aacute;c h&agrave;m kh&aacute;c. Vấn đề đệ quy l&agrave; một vấn đề rất phức tạp, l&agrave; chủ đề của nhiều kho&aacute; học n&acirc;ng cao trong tin học, v&igrave; vậy trong phần n&agrave;y chỉ giới thiệu những kh&iacute;a cạnh c&ugrave;ng với những v&iacute; dụ đơn giản nhất của vấn đề đệ quy.</p> <p style="text-align: justify;" align="justify">Trước ti&ecirc;n ta xem x&eacute;t kh&aacute;i niệm đệ quy, sau đ&oacute; kiểm tra tr&ecirc;n một v&agrave;i chương tr&igrave;nh c&oacute; chứa c&aacute;c h&agrave;m đệ quy . C&aacute;ch tiến h&agrave;nh giải một b&agrave;i to&aacute;n đệ quy nh&igrave;n chung c&oacute; những điểm chung sau.</p> <p style="text-align: justify;" align="justify">Trước ti&ecirc;n gọi h&agrave;m đệ quy để giải b&agrave;i to&aacute;n, h&agrave;m đệ quy thực ra chỉ biết c&aacute;ch giải b&agrave;i to&aacute;n trong trường hợp đơn giản nhất (hay c&ograve;n gọi l&agrave; trường hợp cơ sở). Nếu h&agrave;m đệ quy được gọi trong trường hợp cơ sở, h&agrave;m chỉ cần đơn giản trả lại kết quả. Nếu h&agrave;m được gọi trong c&aacute;c trường hợp phức tạp hơn, h&agrave;m đệ quy sẽ chia c&ocirc;ng việc cần giải quyết th&agrave;nh hai phần. Một phần h&agrave;m biết c&aacute;ch giải quyết như thế n&agrave;o, c&ograve;n phần kia vẫn kh&ocirc;ng biết c&aacute;ch giải quyết như thế n&agrave;o tuy nhi&ecirc;n để được gọi l&agrave; c&oacute; khả năng đệ quy, phần sau phải giống với b&agrave;i to&aacute;n ban đầu nhưng đơn giản hơn hay nhỏ hơn b&agrave;i to&aacute;n ban đầu. Bởi v&igrave; b&agrave;i to&aacute;n mới giống với b&agrave;i to&aacute;n ban đầu n&ecirc;n h&agrave;m sẽ thực hiện gọi ch&iacute;nh n&oacute; để giải quyết c&ocirc;ng việc đơn giản hơn n&agrave;y &ndash; đ&acirc;y ch&iacute;nh l&agrave; lời gọi đệ quy hay c&ograve;n gọi l&agrave; một bước đệ quy. &ETH;ể đảm bảo việc đệ quy c&oacute; kết th&uacute;c, mỗi một lần gọi đệ quy th&igrave; b&agrave;i to&aacute;n phải đảm bảo đơn giản hơn v&agrave; c&aacute;c bước đệ quy n&agrave;y c&ograve;n thực hiện tiếp cho dến khi n&agrave;o b&agrave;i to&aacute;n đơn giản dần, đơn giản tới mức trở th&agrave;nh trường hợp cơ sở. C&oacute; thể nhận thấy h&agrave;m đệ quy xử l&yacute; trường hợp cơ sở để trả lại kết quả t&iacute;nh được cho c&aacute;c h&agrave;m mức phức tạp hơn, rồi đến lượt c&aacute;c h&agrave;m n&agrave;y lại t&iacute;nh trả lại kết quả cho c&aacute;c h&agrave;m phức tạp hơn nữa &hellip; cứ như vậy cho đến lời gọi h&agrave;m ban đầu.</p> <h3 id="ftoc-heading-4" class="cap2 ftwp-heading">1.2. V&iacute; dụ minh họa</h3> <p align="justify">Mới nghe c&oacute; vẻ lạ l&ugrave;ng khi so s&aacute;nh với c&aacute;ch giải quyết c&aacute;c b&agrave;i to&aacute;n th&ocirc;ng thường. Nhưng trước khi nhận x&eacute;t tiếp ta xem x&eacute;t v&iacute; dụ t&iacute;nh n giai thừa ( n! ).</p> <p>Theo định nghĩa n! bằng t&iacute;ch của tất cả c&aacute;c số tự nhi&ecirc;n từ 1 đến n: n! = n * (n-1) &hellip; 2 * 1</p> <p>v&iacute; dụ 5! = 5 * 4 * 3 * 2 * 1 = 120, 0! được định nghĩa bằng 1.</p> <p>&ETH;ể t&iacute;nh n! c&oacute; thể d&ugrave;ng v&ograve;ng lặp như sau :</p> <pre class="language-c"><code>factorial = 1; for (i = n; i &gt;= 1; i&ndash;) factorial *= i;</code></pre> <p>Tuy nhi&ecirc;n cũng c&oacute; thể định nghĩa đệ quy h&agrave;m giai thừa như sau :</p> <pre class="language-c"><code>if n&gt;0 n! = n * (n-1)! else if n=0 n! = 0! = 1</code></pre> <p align="justify">Khi đ&oacute; để t&iacute;nh 3! qu&aacute; tr&igrave;nh t&iacute;nh phải lần ngược trở về t&iacute;nh 0!, sau đ&oacute; lấy kết quả để t&iacute;nh 1!, lại lấy kết quả để t&iacute;nh 2! v&agrave; cuối c&ugrave;ng mới t&iacute;nh được 3! :</p> <pre class="language-c"><code>3! = 3*(2!) = 3*(2*(1!)) = 3*(2*(1*(0!))) 3! = 3*(2*(1*1))) = 3*(2*1) = 3*2 = 6</code></pre> <pre class="language-c"><code>/* T&iacute;nh giai thừa theo phương ph&aacute;p đệ qui */ #include &amp;lt;stdio.h&amp;gt; long factorial( long ); /* H&agrave;m nguy&ecirc;n mẫu */ void main() { int i; for ( i=0; i&amp;lt;=10; i=i+2) printf("%2d! = %ld\n", i, factorial(i)); } /* &ETH;ịnh nghĩa đệ qui h&agrave;m factorial */ long factorial( long number) { if ( number = 0 ) return 1; else return (number*factorial(number-1)); }</code></pre> <p>Kết quả</p> <pre class="language-c"><code>0! = 1 2! = 2 4! = 24 6! = 720 8! = 40320 10! = 3628800</code></pre> <p style="text-align: justify;">Chương tr&igrave;nh tr&ecirc;n : T&iacute;nh giai thừa theo phương ph&aacute;p đệ quy</p> <h4 id="ftoc-heading-5" class="ftwp-heading" style="text-align: justify;">Một v&iacute; dụ thứ hai d&ugrave;ng đệ quy l&agrave; t&iacute;nh d&atilde;y số Fibonaci</h4> <p style="text-align: justify;">D&atilde;y số Fibonaci gồm những số 0, 1, 1, 2, 3, 5, 8, 13, 21 &hellip; bắt đầu từ hai số 0 v&agrave; 1, tiếp sau đ&oacute; c&aacute;c số Fibonaci sau bằng tổng của 2 số Fibonaci trước n&oacute;.</p> <p style="text-align: justify;" align="justify">Dẫy Fibonaci gặp rất nhiều trong thực tế, đặc biệt khi m&ocirc; tả c&aacute;c m&ocirc; h&igrave;nh xoắn ốc. Tỉ số giữa 2 số Fibonaci li&ecirc;n tiếp khoảng 1,618&hellip; Số n&agrave;y gặp rất nhiều trong thực tế v&agrave; được gọi l&agrave; tỉ số v&agrave;ng. C&aacute;c kiến tr&uacute;c sư thường thiết kế k&iacute;ch thước cửa sổ, ph&ograve;ng, nh&agrave; ở c&oacute; tỉ lệ giữa chiều d&agrave;i v&agrave; chiều rộng bằng tỉ số v&agrave;ng. C&aacute;c bưu thiếp cũng thường c&oacute; tỉ lệ giữa chiều d&agrave;i v&agrave; chiều rộng bằng tỉ số v&agrave;ng.</p> <p style="text-align: justify;">Dẫy Fibonaci c&oacute; thể định nghĩa đệ quy như sau:</p> <pre class="language-c"><code>fibonaci(0) = 0; fibonaci(1) = 1; fibonaci(n) = fibonaci(n-1) + fibonaci(n-2) //(n&gt;1)</code></pre> <p style="text-align: justify;" align="justify">Chương tr&igrave;nh trong h&igrave;nh dưới đ&acirc;y t&iacute;nh đệ quy số Fibonaci thứ i bằng c&aacute;ch d&ugrave;ng h&agrave;m fibonaci. Ch&uacute; &yacute; rằng d&atilde;y số Fibonaci tăng rất nhanh, v&igrave; vậy ch&uacute;ng ta chọn kiểu long cho tham số v&agrave; gi&aacute; trị trả về của h&agrave;m fibonaci.</p> <pre class="language-c"><code>/* T&iacute;nh d&atilde;y số Fibonaci phương ph&aacute;p đệ qui */ #include &amp;lt;stdio.h&amp;gt; long fibonaci( long ); /* H&agrave;m nguy&ecirc;n mẫu */ void main() { long result, number; printf("H&atilde;y nhập v&agrave;o một số nguy&ecirc;n : "); scanf("%ld", &amp;amp;number); result = fibonaci(number); printf("Fibonaci thứ %ld l&agrave; : %ld\n", number, result); return 0; } /* &ETH;ịnh nghĩa đệ qui h&agrave;m fibonaci */ long fibonaci( long n) { if ( n = 0 || n = 1 ) return n; else return fibonaci(n-1) + fibonaci(n-2); }</code></pre> <p>Kết quả</p> <pre class="language-c"><code>H&atilde;y nhập v&agrave;o một số nguy&ecirc;n : 0 Fibonaci thứ 0 l&agrave; : 0 H&atilde;y nhập v&agrave;o một số nguy&ecirc;n : 1 Fibonaci thứ 1 l&agrave; : 1 H&atilde;y nhập v&agrave;o một số nguy&ecirc;n : 2 Fibonaci thứ 2 l&agrave; : 1 H&atilde;y nhập v&agrave;o một số nguy&ecirc;n : 3 Fibonaci thứ 3 l&agrave; : 2 H&atilde;y nhập v&agrave;o một số nguy&ecirc;n : 4 Fibonaci thứ 4 l&agrave; : 3 H&atilde;y nhập v&agrave;o một số nguy&ecirc;n : 5 Fibonaci thứ 5 l&agrave; : 5 H&atilde;y nhập v&agrave;o một số nguy&ecirc;n : 6 Fibonaci thứ 8 l&agrave; : 8 H&atilde;y nhập v&agrave;o một số nguy&ecirc;n : 10 Fibonaci thứ 10 l&agrave; : 55 H&atilde;y nhập v&agrave;o một số nguy&ecirc;n : 20 Fibonaci thứ 20 l&agrave; : 6765 H&atilde;y nhập v&agrave;o một số nguy&ecirc;n : 35 Fibonaci thứ 35 l&agrave; : 9227465</code></pre> <p>Chương tr&igrave;nh tr&ecirc;n:Tạo ra c&aacute;c số Fibonaci bằng đệ quy.</p> <p style="text-align: justify;" align="justify">Mỗi một lần h&agrave;m fibonaci được gọi, n&oacute; kiểm tra ngay lập tức xem liệu đ&acirc;y c&oacute; phải l&agrave; trường hợp cơ sở, n bằng 0 hay 1 hay kh&ocirc;ng. Nếu đ&uacute;ng n được trả lại, bằng kh&ocirc;ng, tức l&agrave; khi n&gt;1, n&oacute; sẽ tạo ra hai lời gọi đệ quy đơn giản hơn lời gọi đến h&agrave;m fibonaci ban đầu.</p> <h3 id="ftoc-heading-6" class="cap2 ftwp-heading">1.3. So s&aacute;nh đệ quy v&agrave; lặp</h3> <p style="text-align: justify;" align="justify">Ta đ&atilde; xem x&eacute;t c&aacute;ch t&iacute;nh giai thừa của một số, c&oacute; thể t&iacute;nh theo phương ph&aacute;p lặp (phi đệ quy) hoặc phương ph&aacute;p đệ quy. Trong phần n&agrave;y ta sẽ so s&aacute;nh hai phương ph&aacute;p n&agrave;y v&agrave; t&igrave;m hiểu tại sao trong thực tế thường chọn phương ph&aacute;p lặp hơn.</p> <p style="text-align: justify;" align="justify">Lập tr&igrave;nh đệ quy sử dụng cấu tr&uacute;c lựa chọn, c&ograve;n lặp sử dụng cấu tr&uacute;c lặp. Cả hai phương ph&aacute;p đều li&ecirc;n quan đến qu&aacute; tr&igrave;nh lặp, tuy nhi&ecirc;n phương ph&aacute;p lặp sử dụng v&ograve;ng lặp tường minh, c&ograve;n phương ph&aacute;p đệ quy c&oacute; được qu&aacute; tr&igrave;nh lặp bằng c&aacute;c sử dụng li&ecirc;n tục c&aacute;c lời gọi h&agrave;m. Cả hai phương ph&aacute;p đều phải kiểm tra khi n&agrave;o th&igrave; kết th&uacute;c. Phương ph&aacute;p lặp kết th&uacute;c khi điều kiện để tiếp tục v&ograve;ng lặp sai, c&ograve;n phương ph&aacute;p đệ quy kết th&uacute;c khi đến trường hợp cơ sở, lặp thay đổi biến đếm trong v&ograve;ng lặp cho đến khi n&oacute; l&agrave;m cho điều kiện lặp sai c&ograve;n đệ quy l&agrave;m cho c&aacute;c lời gọi h&agrave;m đơn giản dần cho đến khi đơn giản tới trường hợp cơ sở. Cả hai phương ph&aacute;p đều c&oacute; thể dẫn đến trường hợp chạy v&ocirc; hạn m&atilde;i, lặp sẽ kh&ocirc;ng tho&aacute;t ra được khi điều kiện lặp kh&ocirc;ng bao giờ sai c&ograve;n đệ quy kh&ocirc;ng tho&aacute;t ra được khi c&aacute;c bước đệ quy kh&ocirc;ng l&agrave;m cho b&agrave;i to&aacute;n đơn giản hơn v&agrave; cuối c&ugrave;ng hội tụ về trường hợp cơ sở.</p> <p style="text-align: justify;" align="justify">Tuy nhi&ecirc;n đệ quy tồi hơn, n&oacute; li&ecirc;n tục đưa ra c&aacute;c lời gọi h&agrave;m l&agrave;m tốn thời gian xử l&yacute; của bộ vi xử l&yacute; v&agrave; kh&ocirc;ng gian nhớ. Mỗi lần gọi h&agrave;m, lại cần th&ecirc;m một bản sao của h&agrave;m, tốn th&ecirc;m bộ nhớ (lưu c&aacute;c biến của h&agrave;m, địa chỉ trở về của h&agrave;m &hellip;). V&igrave; vậy phương ph&aacute;p lặp được chuộng hơn. Tuy nhi&ecirc;n tồn tại nhiều b&agrave;i to&aacute;n chỉ c&oacute; thể giải bằng đệ quy.</p> <h2 id="ftoc-heading-7" class="cap1 ftwp-heading">2. C&Aacute;CH D&Ugrave;NG &ETH;Ệ QUY</h2> <h3 id="ftoc-heading-8" class="cap2 ftwp-heading">2.1. C&aacute;c b&agrave;i to&aacute;n c&oacute; thể d&ugrave;ng &ETH;ệ Quy</h3> <p style="text-align: justify;" align="justify">Thường &aacute;p dụng cho c&aacute;c b&agrave;i to&aacute;n phụ thuộc tham số c&oacute; hai đặc điểm sau:</p> <p style="text-align: justify;" align="justify">B&agrave;i to&aacute;n dễ d&agrave;ng giải quyết trong một số trường hợp ri&ecirc;ng ứng với c&aacute;c gi&aacute; trị đặc biệt của tham số. Ta gọi đ&acirc;y l&agrave; trường hợp suy biến.</p> <p style="text-align: justify;" align="justify">Trong trường hợp tổng qu&aacute;t, b&agrave;i to&aacute;n c&oacute; thể quy về một b&agrave;i to&aacute;n c&ugrave;ng dạng nhưng gi&aacute; trị tham số th&igrave; bị thay đổi. V&agrave; sau một số hữu hạn bước biến đổi &ETH;ệ Quy sẽ dẫn đến trường hợp suy biến.</p> <p style="text-align: justify;"><strong>Nhận x&eacute;t:</strong>&nbsp;B&agrave;i to&aacute;n t&iacute;nh n! ở tr&ecirc;n thể hiện rất r&otilde; c&aacute;c đặc điểm n&agrave;y.</p> <h3 id="ftoc-heading-9" class="cap2 ftwp-heading">2.2. C&aacute;ch x&acirc;y dựng h&agrave;m &ETH;ệ Quy</h3> <p class="cap2 ftwp-heading">H&agrave;m &ETH;ệ Quy thường được viết theo thuật to&aacute;n sau:</p> <pre class="language-c"><code>if ( trường hợp suy biến) { tr&igrave;nh bầy c&aacute;ch giải b&agrave;i to&aacute;n (giả định đ&atilde; c&oacute; c&aacute;ch giải) } else /* trường hợp tổng qu&aacute;t*/ { gọi đệ quy tới h&agrave;m (đang lập) với gi&aacute; trị kh&aacute;c của tham số }</code></pre> <h2 id="ftoc-heading-10" class="cap1 ftwp-heading">3. MỘT V&Agrave;I ỨNG DỤNG CỦA &ETH;Ệ QUY</h2> <h3 id="ftoc-heading-11" class="cap2 ftwp-heading">3.1. B&agrave;i to&aacute;n ước số chung lớn nhất của hai số nguy&ecirc;n dương x v&agrave; y</h3> <p class="cap2 ftwp-heading">Trường hợp suy biến l&agrave; trường hợp x=y. Khi đ&oacute; usc(x,y)=x.</p> <p class="cap2 ftwp-heading">Trường hợp chung x kh&aacute;c y c&oacute; thể đệ quy như sau:</p> <pre class="language-c"><code>usc(x,y)=usc(x-y,y) nếu x&gt;y usc(x,y)=usc(x,y-x) nếu x&lt;y</code></pre> <p>H&agrave;m t&igrave;m ước số chung lớn nhất c&oacute; thể viết như sau:</p> <pre class="language-c"><code>int usc(int x, int y) { if (x==y) return x; else if (x&gt;y) return usc(x-y,y); else return usc(x,y-x); }</code></pre> <h3 id="ftoc-heading-12" class="cap2 ftwp-heading">3.2. B&agrave;i to&aacute;n th&aacute;p H&agrave; nội</h3> <p class="cap2 ftwp-heading" style="text-align: justify;">B&agrave;i to&aacute;n th&aacute;p H&agrave; nội được dặt ra như sau: C&oacute; một th&aacute;p m tầng đang dặt tại vị tr&iacute; (x1,y1), cần chuyển đến vị trị mới (x2,y2). Khi chuyển cho ph&eacute;p d&ugrave;ng vị tr&iacute; trung gian (x3,y3).</p> <p>Quy ước như sau:</p> <p style="text-align: justify;">- Số tầng m lớn hơn hoặc bằng 1.</p> <p style="text-align: justify;">- Số thứ tự tầng đ&aacute;nh từ 1 đến m từ đỉnh xuống đ&aacute;y.</p> <p style="text-align: justify;">- Mỗi tầng được biểu diễn bằng một h&igrave;nh chữ nhật c&oacute; chiều cao l&agrave; một đơn vị k&yacute; tự m&agrave;n h&igrave;nh, v&agrave; chiều rộng l&agrave; một số lẻ đơn vị k&yacute; tự. Tầng dưới rộng hơn tầng tr&ecirc;n.</p> <p style="text-align: justify;">- Tọa độ hiểu l&agrave; tọa độ m&agrave;n h&igrave;nh h&igrave;nh ở chế độ văn bản.</p> <p style="text-align: justify;">- T&acirc;m th&aacute;p l&agrave; t&acirc;m của tầng cuối. Như vậy (x1,y1) l&agrave; t&acirc;m th&aacute;p ban đầu.</p> <p style="text-align: justify;">Y&ecirc;u cầu x&acirc;y dựng quy tr&igrave;nh chuyển th&aacute;p theo nhiều bước. Mỗi bước chuyển một tầng từ vị tr&iacute; n&agrave;y đến vị tr&iacute; kh&aacute;c. Ngo&agrave;i ra kh&ocirc;ng được đặt tầng lớn đ&egrave; l&ecirc;n tầng nhỏ.</p> <p>Thuật to&aacute;n c&oacute; thể diễn đạt như sau:</p> <ul> <li>Trường hợp suy biến:&nbsp; m=1, khi đ&oacute; chỉ cần chuyển tầng 1 từ (x1,y1) đến (x2,y2).</li> <li>Trường hợp tổng qu&aacute;t m&gt;1 c&oacute; thể giải quyết đệ quy như sau: <ul> <li>Chuyển th&aacute;p m-1 tầng từ (x1,y1-1) đến (x3,y3), d&ugrave;ng (x2,y2) l&agrave;m vị tr&iacute; trung gian.</li> <li>Chuyển tầng m từ (x1,y1) đến (x2,y2).</li> <li>Chuyển th&aacute;p m-1 tầng từ (x3,y3) đến (x2,y2-1), d&ugrave;ng (x1,y1) l&agrave;m vị tr&iacute; trung gian.</li> </ul> </li> </ul> <p style="text-align: justify;">Theo thuật to&aacute;n n&agrave;y c&oacute; thể lập h&agrave;m chuyển th&aacute;p v&agrave; chương tr&igrave;nh như sau. Chương tr&igrave;nh sẽ in ra quy tr&igrave;nh vận chuyển.</p> <pre class="language-c"><code>/* Th&aacute;p H&agrave; nội*/ #include&amp;lt;stdio.h&amp;gt; #include&amp;lt;conio.h&amp;gt; void cthap(int m, int x1, int y1, int x2, int y2, int x3, int y3) { if (m&amp;lt;1) return; else if (m==1) printf("\n chuyen tang1 tu (%d,%d) den (%d,%d)",x1,y1,x2,y2); else { cthap(m-1,x1,y1-1,x3,y3,x2,y2); printf("\n chuyen tang %d tu (%d, %d) den (%d,%d)",m,x1,y1,x2,y2); cthap(m-1,x3,y3,x2,y2-1,x1,y1); } } void main() { int m; printf("\n so tang:"); scanf("%d",&amp;amp;m); cthap(m,10,24,30,24,50,24); }</code></pre> <h3 class="cap2">3.3. C&aacute;c v&ograve;ng for lồng nhau v&agrave; b&agrave;i to&aacute;n tổ hợp</h3> <p class="cap2" style="text-align: justify;">B&agrave;i to&aacute;n tổ chức m chu tr&igrave;nh lồng nhau c&oacute; đặc trưng đệ quy. Tại chu tr&igrave;nh k&lt;m sẽ gọi tới chu tr&igrave;nh k+1. Tại chu tr&igrave;nh m (trường hợp suy biến) sẽ thực hiện một c&ocirc;ng việc t&ugrave;y theo y&ecirc;u cầu của mỗi b&agrave;i to&aacute;n. X&eacute;t h&agrave;m tạo một v&ograve;ng lặp.</p> <p>H&agrave;m n&agrave;y c&oacute; 3 đối l&agrave;:</p> <ul> <li>Số hiệu v&ograve;ng lặp k;</li> <li>Cận dưới của biến điều khiển d;</li> <li>Cận tr&ecirc;n của biến điều khiển t.</li> </ul> <p>H&agrave;m c&oacute; thể x&acirc;y dựng theo lược đồ:</p> <div id="urvanov-syntax-highlighter-61109f0dca41e296120304" class="urvanov-syntax-highlighter-syntax crayon-theme-classic urvanov-syntax-highlighter-font-monaco urvanov-syntax-highlighter-os-pc print-yes notranslate" data-settings=" minimize scroll-mouseover"> <div class="urvanov-syntax-highlighter-main"> <pre class="language-c"><code>void chu_trinh(int k, int d, int t) { int i; /* Biến điều khiển*/ for(i=d;i&amp;lt;=t;i++) if (k==m) { /*l&agrave; c&ocirc;ng vi&ecirc;c t&ugrave;y thuộc v&agrave;o y&ecirc;u cầu b&agrave;i to&aacute;n*/ } else { /*Gọi đệ qui, ch&uacute; &yacute; d(i) v&agrave; t(i) phụ thuộc v&agrave;o i*/ chu_trinh(k+1,d(i),t(i)); } }</code></pre> </div> </div> <p>X&eacute;t b&agrave;i to&aacute;n liệt k&ecirc; tổ hợp chập m của n số : 1,2,.,n. Một tổ hợp i1,i2, ., im cần thỏa m&atilde;n điều kiện:</p> <pre class="language-c"><code>1&lt;= i1&lt;i2&lt;i3&lt; &hellip;.&lt;im &lt;= n</code></pre> <p>Ta d&ugrave;ng mảng ngo&agrave;i cs[20] để chứa tổ hợp theo c&aacute;ch:</p> <ul> <li>cs[1] chứa phần tử thứ nhất i<sub>1.</sub></li> <li>cs[2] chứa phần tử thứ hai i<sub>2.</sub></li> </ul> <p style="text-align: justify;">Khi m=3 th&igrave; b&agrave;i to&aacute;n được giải quyết bằng 3 v&ograve;ng for lồng nhau như sau:</p> <div id="urvanov-syntax-highlighter-61109f0dca425793649905" class="urvanov-syntax-highlighter-syntax crayon-theme-classic urvanov-syntax-highlighter-font-monaco urvanov-syntax-highlighter-os-pc print-yes notranslate" data-settings=" minimize scroll-mouseover"> <div class="urvanov-syntax-highlighter-main"> <pre class="language-c"><code>k=1; for( i1=1;i1&amp;lt;=n-2; i1++) { ck[k]= i1; ++k; for(i2=i1+1; i2&amp;lt;=n-1; i2++) { cs[k]=i2; ++k; for(i3=i2+1;i3&amp;lt;=n; i3++) { cs[k]=i3; /* Do k=3; in cs[1], .,cs[k]*/ } } }</code></pre> </div> </div> <p style="text-align: justify;">Trong trường hợp tổ hợp chập m, ta phải tổ chức m chu tr&igrave;nh lồng nhau. Muốn vậy phải d&ugrave;ng h&agrave;m:</p> <pre class="language-c"><code>void chu_trinh(int k, int d, int t)</code></pre> <p>Với b&agrave;i to&aacute;n tổ hợp th&igrave;:</p> <pre class="language-c"><code>Khi k=1, cận dưới d=1;</code></pre> <p>Tại v&ograve;ng lặp k cận tr&ecirc;n bằng n-m+k, v&igrave; vậy c&oacute; thể bỏ đối t.</p> <pre class="language-c"><code>d(i) =i+1.</code></pre> <p style="text-align: justify;">Từ tr&ecirc;n, c&oacute; thể viết h&agrave;m chu_trinh cho b&agrave;i to&aacute;n tổ hợp:</p> <pre class="language-c"><code>#include&amp;lt;stdio.h&amp;gt; int m,n,cs[20]; void chu_trinh(int k, int d) { int i; /*Bien dieu khien*/ for (i=d; i&amp;lt;=n-m+k;++i) { cs[k]=i; if (k==m) { /*In mot to hop*/ int j; printf("\n"); for(j=1;j&amp;lt;=k;++j) printf("%d",cs[j]); } else chu_trinh(k+1,i+1); } }</code></pre> <p>H&agrave;m chu_trinh sẽ được &aacute;p dụng trong main như sau:</p> <pre class="language-c"><code>/*Liet ke to hop*/ #include&amp;lt;conio.h&amp;gt; #include&amp;lt;stdio.h&amp;gt; void main() { clrscr(); printf("\n Vao m va n (m&amp;lt;=n)"); scanf("%d%d",&amp;amp;m,&amp;amp;n); chu_trinh(1,1); getch(); }</code></pre> <h3 class="cap2">3.4. Một b&agrave;i to&aacute;n ứng dụng tổ hợp</h3> <p class="cap2" style="text-align: justify;">Cho d&atilde;y n số thực h&atilde;y t&igrave;m m số c&oacute; t&iacute;ch lớn nhất. Một bộ m số ch&iacute;nh l&agrave; tổ hợp chập m của n số, v&igrave; vậy đ&acirc;y ch&iacute;nh l&agrave; b&agrave;i to&aacute;n duyệt c&aacute;c tổ hợp. Khi nhận được một tổ hợp ta cần t&iacute;nh t&iacute;ch của ch&uacute;ng v&agrave; so s&aacute;nh với c&aacute;c gi&aacute; trị trước đ&oacute; để chọn t&iacute;ch lớn nhất. Ta đưa c&aacute;c biến, mảng ngo&agrave;i như sau:</p> <ul> <li class="cap2" style="text-align: justify;">Mảng thực x[20] chứa dẫy số thực</li> <li style="text-align: justify;">Mảng nguy&ecirc;n cs[20] chứa c&aacute;c tổ hợp được duyệt,</li> <li style="text-align: justify;">Mảng nguy&ecirc;n csmax[20] chứa tổ hợp cần t&igrave;m (c&oacute; t&iacute;ch lớn nhất),</li> <li style="text-align: justify;">Biến thực max chứa t&iacute;ch lớn nhất.</li> <li style="text-align: justify;">H&agrave;m chu_trinh được sửa đ&ocirc;i ch&uacute;t: khi k=m (tức l&agrave; nhận được một tổ hợp) th&igrave; t&iacute;nh t&iacute;ch của ch&uacute;ng v&agrave; so s&aacute;nh với phương &aacute;n cũ để t&igrave;m t&iacute;ch lớn hơn.</li> <li style="text-align: justify;">Phương &aacute;n ban đầu ch&iacute;nh l&agrave; tổ hợp gồm c&aacute;c chỉ số từ 1 đến m được x&acirc;y dựng trong h&agrave;m main.</li> </ul> <p style="text-align: justify;">Dưới đ&acirc;y l&agrave; chương tr&igrave;nh t&igrave;m bộ m phần tử (trong dẫy n số ) c&oacute; t&iacute;ch lớn nhất.</p> <pre class="language-c"><code>/* tim bo m phan tu (trong n so) co tich lon nhat*/ #include&amp;lt;stdio.h&amp;gt; #include&amp;lt;conio.h&amp;gt; int m,n,cs[20], csmax[20]; float max, x[20]; void chu_trinh(int k, int d) { int i; for(i=d;i&amp;lt;=n-m+k;++i) { cs[k]=i; if(k==m) { int j; float s=1.0; for(j=1;j&amp;lt;=k;++j) s*=x[cs[j]]; if (s&amp;gt;max) { max=s; for(j=1;j&amp;lt;=k;++j) csmax[j]=cs[j]; } } else chu_trinh(k+1,i+1); } } void main() { int j; clrscr(); printf("\n vao m va n(m&amp;lt;=n)"); scanf("%d%d",&amp;amp;m,&amp;amp;n); for(j=1;j&amp;lt;=n;++j) { printf("\n x[%d]=",j); scanf("%f",&amp;amp;x[j]); } max=1; for(j=1; j&amp;lt;=m;++j) { csmax[j]=j; max*=x[j]; } chu_trinh(1,1); for(j=1;j&amp;lt;=m;++j) { printf("\n x[%d]=%f", csmax[j],x[csmax[j]]); } printf("\n Tich=%f",max); }</code></pre> <h3 class="cap2">3.5. Duyệt tr&ecirc;n c&acirc;y v&agrave; b&agrave;i to&aacute;n biểu diễn tổng</h3> <p class="cap2">B&agrave;i to&aacute;n duyệt tr&ecirc;n c&acirc;y c&oacute; thể giải theo đệ quy như sau:</p> <p>Xuất ph&aacute;t từ một đỉnh n&agrave;o đ&oacute; ta thực hiện hai động t&aacute;c:</p> <ul> <li>X&eacute;t đỉnh n&agrave;y</li> <li>&ETH;i đến c&aacute;c đỉnh kề n&oacute; bằng ph&eacute;p đệ quy</li> </ul> <p style="text-align: justify;">Bằng thủ tục n&oacute;i tr&ecirc;n c&oacute; thể đi qua tất cả c&aacute;c đỉnh của một c&acirc;y. Ta minh họa điều n&agrave;y bằng c&aacute;ch x&eacute;t b&agrave;i to&aacute;n ph&acirc;n t&iacute;ch số n nguy&ecirc;n dương th&agrave;nh tổng c&aacute;c số nguy&ecirc;n dương nhỏ hơn n. &ETH;ỉnh xuất ph&aacute;t l&agrave; n. Từ đỉnh n&agrave;y c&oacute; thể đi đến c&aacute;c đỉnh gồm một cặp hai số c&oacute; tổng bằng n, c&aacute;c đỉnh đ&oacute; l&agrave;:</p> <p style="text-align: justify;">(i,n-i), với i=1,&hellip;,n/2.</p> <p>Tại mỗi đỉnh hai số lại c&oacute; thể đi đến c&aacute;c đỉnh 3 số. Một c&aacute;ch tổng qu&aacute;t từ đỉnh k số:</p> <pre class="language-c"><code>(a1,&hellip;, ak-1, ak)</code></pre> <p>c&oacute; thể đi đến đỉnh k+1 số sau:</p> <pre class="language-c"><code>(a1,&hellip;, ak-1, i, ak-i), với i=ak-1,&hellip;, ak/2</code></pre> <p>Nhận x&eacute;t: Mỗi d&atilde;y số tại đỉnh l&agrave; đơn điệu tăng.</p> <p>C&oacute; thể chứng minh mọi tổng đều ứng với một đỉnh n&agrave;o đ&oacute; thực vậy x&eacute;t tổng (k+1) số:</p> <pre class="language-c"><code>n=t1+t2+. + tk+tk+1</code></pre> <p>(D&atilde;y ti kh&ocirc;ng giảm). R&otilde; r&agrave;ng tổng n&agrave;y c&oacute; thể suy ra từ đỉnh gồm k số:</p> <pre class="language-c"><code>(t1,&hellip;,tk-1, tk+tk+1)</code></pre> <p>Như vậy mỗi tổng (k+1) số đều c&oacute; thể suy ra từ đỉnh k số. Do tập c&aacute;c tổng một số l&agrave; đầy đủ chỉ gồm n, n&ecirc;n c&aacute;c tập k số cũng đầy đủ với mọi k &gt;1. &ETH;&oacute; l&agrave; điều cần chứng minh.</p> <p>Ta d&ugrave;ng mảng ngo&agrave;i a[100] để chứa bộ số của đỉnh. Với đỉnh xuất ph&aacute;t th&igrave;:</p> <p>k=1 v&agrave; a[1] =n</p> <p>V&igrave; cần d&ugrave;ng đến a[k-1], n&ecirc;n đưa th&ecirc;m a[0]=1. Ta x&acirc;y dựng h&agrave;m duyệt đỉnh k với nội dung sau:</p> <p>1. X&eacute;t đỉnh k&gt;1 in c&aacute;c số a[1],&hellip;, a[k] dưới dạng tổng.</p> <pre class="language-c"><code>a[1] +a[2]+&hellip;+ a[k]</code></pre> <p>(kh&ocirc;ng x&eacute;t đỉnh với k=1)</p> <p>2. &ETH;i đến c&aacute;c đỉnh (k+1) số :</p> <pre class="language-c"><code>(a1,&hellip;,ak-1,i,ak-i), với i=ak-1,&hellip;,ak/2</code></pre> <p>H&agrave;m void duyet_dinh(int k);</p> <p>chương tr&igrave;nh dưới đ&acirc;y sẽ lập theo thuật to&aacute;n n&agrave;y:</p> <pre class="language-c"><code>/* Ph&acirc;n t&iacute;ch n v&agrave; tổng c&aacute;c số nhỏ hơn n duyệt c&aacute;c đỉnh của c&acirc;y bằng thủ tục đệ qui*/ #include&amp;lt;stdio.h&amp;gt; #include&amp;lt;conio.h&amp;gt; int a[100]; /*Da biet a[0],..., a[k] */ void duyet_dinh(int k) { int x,i; /*xet dinh k&amp;gt;1*/ if(k&amp;gt;1) for(i=1;i&amp;lt;=k;++i) printf("%c%d",i&amp;gt;1?+:\n,a[i]); /*đi đến c&aacute;c đỉnh (k +1) số*/ x=a[k]; for (i=a[k-1];i&amp;lt;=x/2;++i) { a[k]=i; a[k+1]=x-i; duyet_dinh(k+1); } } void main() { int n; clrscr(); printf("\nn="); scanf("%d",&amp;amp;n); a[0]=1; a[1]=n; duyet_dinh(1); getch(); }</code></pre> <p style="text-align: justify;">Ch&uacute;ng ta sẽ kết th&uacute;c &ldquo;[Lập tr&igrave;nh C từ 0 đến 1] B&agrave;i 17. Đệ quy&rdquo; trong series [Lập tr&igrave;nh C từ 0 đến 1] ở đ&acirc;y. H&atilde;y c&ugrave;ng đ&oacute;n xem &ldquo;B&agrave;i 18. Phạm vi của biến trong chương tr&igrave;nh&rdquo;.</p> <p style="text-align: justify;">H&atilde;y để lại b&igrave;nh luận v&agrave; theo d&otilde;i series b&agrave;i viết: &ldquo;<a href="../../../tu-khoa/lap-trinh-c-tu-0-den-1/">Lập tr&igrave;nh C từ 0 đến 1</a>&rdquo; để tiếp tục cập nhật những th&ocirc;ng tin mới nhất.</p>