Giáo trình Turbo C nâng cao và C++ (Phần 1)

/ticks),string,10); 
 outtext(string); 
 } 
 setusercharsize(2,3,2,2); 
 settextstyle(font,VERT_DIR,0); 
 for (i=0;i<n;i++) 
 { 
 setfillstyle(SOLID_FILL,i); 
 bar3d(left+shft+i*di,bot-data[i]*ppd,left+shft+i*di+bwidth,bot,depth,topflag); 
 moveto(left+i*di+bwidth-1,bot+5); 
 outtext(month[i]); 
 } 
 75
 getch(); 
 closegraph(); 
 } 
 Đ5. Ví dụ kết thúc 
Ch−ơng trình 6-19 : Lập ch−ơng trình vẽ một mặt Mallbrot 
#include 
#include 
#include 
#define ymax 400 
#define xmax 400 
#define maxcount 16 
void main() 
 { 
 int gd,gm; 
 int x,y,count; 
 float xscale,yscale; 
 float left,top,xside,yside,zx,zy,cx,cy,tempx; 
 clrscr(); 
 gd=DETECT; 
 initgraph(&gd,&gm,"c:\\bc\\bgi"); 
 left=-2.0; 
 top=1.25; 
 xside=2.5; 
 yside=-2.5; 
 xscale=xside/xmax; 
 yscale=yside/ymax; 
 rectangle(0,0,xmax+1,ymax+1); 
 for (y=1;y<=ymax;y++) 
 { 
 for (x=1;x<=xmax;x++) 
 { 
 cx=x*xscale+left; 
 cy=y*yscale+top; 
 zx=zy=0; 
 count=0; 
 while((zx*zx+zy*zy<4) && (count<maxcount)) 
 { 
 tempx=zx*zx-zy*zy+cx; 
 zy=2*zx*zy+cy; 
 zx=tempx; 
 count++; 
 } 
 putpixel(x,y,count); 
 if (kbhit()) 
 exit(0); 
 } 
 76
 } 
 getch(); 
 closegraph(); 
} 
 77
 Ch−ơng 7 : một số vấn đề về đa thức và hàm số 
 Đ1. Một số khái niệm chung 
1. Khái niệm về ph−ơng pháp tính : Ph−ơng pháp tính là môn học về những lí luận cơ bản 
và các ph−ơng pháp giải gần đúng,cho ra kết quả bằng số của các bài toán th−ờng gặp trong 
toán học cũng nh− trong kĩ thuật. 
 Chúng ta thấy rằng hầu hết các bài toán trong toán học nh− giải các ph−ơng trình đại 
số hay siêu việt,các hệ ph−ơng trình tuyến tính hay phi tuyến,các ph−ơng trình vi phân 
th−ờng hay đạo hàm riêng,tính các tích phân,... th−ờng khó giải đúng đ−ợc,nghĩa là khó tìm 
kết quả d−ới dạng các biểu thức. 
 Một số bài toán có thể giải đúng đ−ợc nh−ng biểu thức kết quả lại cồng kềnh,phức 
tạp khối l−ợng tính toán rất lớn.Vì những lí do trên,viẹc giải gần đúng các bài toán là vô 
cùng cần thiết. 
 Các bài toán trong kĩ thuật th−ờng dựa trên số liệu thực nghiệm và các giả thiết gần 
đúng.Do vậy việc tìm ra kết quả gần đúng với sai số cho phép là hoàn toàn có ý nghĩa thực 
tế. 
 Từ lâu ng−ời ta đã nghiên cứu ph−ơng pháp tính và đạt nhiều kết quả đáng kể. Tuy 
nhiên để lời giải đạt đ−ợc độ chính xác cao,khối l−ợng tính toán th−ờng rất lớn.Với các 
ph−ơng tiện tính toán thô sơ,nhiều ph−ơng pháp tính đã đ−ợc đề xuất không thể thực hiện 
đ−ợc vì khối l−ợng tính toán quá lớn.Khó khăn trên đã làm ph−ơng pháp tính không phát 
triển đ−ợc. 
 Ngày nay nhờ máy tính điện tử ng−ời ta đã giải rất nhanh các bài toán khổng lồ,phức 
tạp,đã kiểm nghiệm đ−ợc các ph−ơng pháp tính cũ và đề ra các ph−ơng pháp tính mới. 
Ph−ơng pháp tính nhờ đó phát triển rất mạnh mẽ.Nó là cầu nối giữa toán học và thực tiễn.Nó 
là môn học không thể thiếu đối với các kĩ s−. 
 Ngoài nhiệmvụ chính của ph−ơng pháp tính là tìm các ph−ơng pháp giải gần đúng 
các bài toán,nó còn có nhiệm vụ khác nh− nghiên cứu tính chất nghiệm,nghiên cứu bài toán 
cực trị,xấp xỉ hàm v.v. Trong phần này chúng ta sẽ nghiên cứu một loạt bài toán th−ờng 
gặp trong thực té và đ−a ra ch−ơng trình giải chúng. 
2. Các đặc điểm của ph−ơng pháp tính : Đặc điểm về ph−ơng pháp coả môn học này là hữu 
hạn hoá và rời rạc hoá. 
 Ph−ơng pháp tính th−ờng biến cái vô hạn thành cái hữu hạn,cái liên tục thành cái rời 
rạc và sau cùng lại trở về với cái vô hạn,cái liên tục.Nh−ng cần chú ý rằng quá trình trở lại 
cái vô hạn,cái liên tục phải trả giá đắt vì khối l−ợng tính toán tăng lên rất nhiều.Cho nên 
trong thực tế ng−ời ta dừng lại khi nghiệm gần đúg sát với nghiệm đúng ở một mức độ nào 
đó. 
 Đặc diểm thứ hai của môn học là sự tiến đến kết quả bằng quá trình liên tiếp.Đó là 
quá trình chia ngày càng nhỏ hơn,càng dày đặc hơn hoặc quá trình tính toán b−ớc sau dựa 
vào các kết quả của các b−ớc tr−ớc.Công việc tính toán lặp đi lặp lại này rất thích hợp với 
máy điện toán. 
 Khi nghiên cứu ph−ơng pháp tính ng−ời ta th−ờng triệt để lợi dụng các kết quả đạt 
đ−ợc trong toán học.Cùng một bài toán có thể có nhiều ph−ơng pháp tính khác nhau.Một 
ph−ơng pháp tính đ−ợc coi là tốt nếu nó đạt các yêu cầu sau : 
 - ph−ơng pháp tính đ−ợc biểu diễn bằng một dãy hữu hạn các b−ớc tính cụ thể.Các 
b−ớc tính toán cụ thể này của ph−ơng pháp tính đ−ợc gọi là thuật toán. Thuật toán càng đơn 
giản càng tốt. 
 - đánh giá đ−ợc sai số và sai số càng nhỏ càng tốt. 
 - thuật toán thực hiện đ−ợc trên máy điện toán và thời gian chạy máy ít nhất 
 78
3. Các loại sai số : Trong việc thiếtlập và giải các bài toán thực tế ta th−ờng gặp các loại sai 
số. 
 Giả sử ta xét bài toán A nào đó.Nghiên cứu các quy luật liên hệ giữa các đại l−ợng 
trong bài toán đẫn đến ph−ơng trình có dạng tổng quát : 
 y = Bx 
Trong đó : x - đại l−ợng đã biết 
 y - đại l−ợng ch−a biết 
 B - quy luật bién đổi từ x sang y 
 Bài toán thực tế th−ờng rất phức tạp.Để đơn giản và có thể diễn đạt nó bằng toán 
học,ng−ời ta đ−a ra một số giả thiết không hoàn toàn chính xác để nhận đ−ợc ph−ơng trình 
trên. 
 Vì vậy nếu gọi y1 là giá trị đúng của y thì khi đó y ≠ y1. Giá trị | y - y1| đ−ợc gọi là sai 
số giả thiết của bài toán. 
 Do x là số liệu ban đầu của bài toán,thu đ−ợc từ đo l−ờng,thí nghiệm nên nó chỉ là giá 
trị gần đúng.Sai số này đ−ợc gọi là sai số của các số liệu ban đầu. 
 Để giải gần đúng ph−ơng trình trên ta th−ờng thay B bằng C hay x bằng t để ph−ơng 
trình đơn giản hơn và có thể giải đ−ợc.Bằng cách đó ta tìm đ−ợc y2 gần đúng với y.Giá trị | 
y2 - y| đ−ợc gọi là sai số ph−ơng pháp của bài toán. 
 Cuối cùng khi thực hiện các phép tính ta th−ờng thu gọn các kết quả trung gian hay 
kết quả cuối cùng nên đáp số của bài toán là y3.Giá trị | y3 - y | là sai số tính toán. 
 Trong phần này chúng ta quan tâm tới sai số ph−ơng pháp. 
4. Xấp xỉ và hội tụ : Xét bài toán 
 y = Bx 
 Giả sử y là nghiệm đúng của bài toán mà ta ch−a biết.Bằng ph−ơng pháp nào đó ta 
lấy y1 thay cho y và khi đó y1 gọi là xấp xỉ thứ nhất của nghiệm và viết : 
 y1 ≈ y 
Cũng bằng ph−ơng pháp t−ơng tự,ta xây dựng đ−ợc một dãy các xấp xỉ y1,y2,y3,..yn.Nếu ta 
có : 
 =
 limyyn
 n→∞
thì ta nói dãy xấp xỉ hội tụ tới nghiệm y. 
 Đ2. Tính giá trị của đa thức theo sơ đồ Horner 
1. Sơ đồ Horner : Giả sử chúng ta cần tìm giá trị của một đa thức tổng quát dạng : 
 n n - 1 n - 2
 P(x) = a0x + a1x + a2x +....+ an (1) 
tại một trị số x nào đó. Trong (1) các hệ số ai là các số thực đã cho. Chúng ta viết lại (1) theo 
thuật toán Horner d−ới dạng : 
 P(xo) = (...((a0x + a1)x+ a2x)+...+ an -1 )x + an (2) 
 Từ (2) ta nhận thấy : 
 P0 = a0 
 P1 = P0x + a1 
 P2 = P1x + a2 
 P3 = P2x + a3 
 .................. 
 P(x) = Pn = Pn-1x + an 
 Tổng quát ta có : 
 Pk = Pk-1x + ak với k =1,2...n ; P0 = a0 
 79
 Do chúng ta chỉ quan tâm đến trị số của Pn nên trong các công thức truy hồi về sau 
chúng ta sẽ bỏ qua chỉ số k của P và viết gọn P := Px + ak với k = 0...n.Khi ta tính tới k = n 
thì P chính là giá trị cần tìm của đa thức khi đã cho x. Chúng ta thử các b−ớc tính nh− sau : 
 Ban đầu P = 0 
 B−ớc 0 k = 0 P = ao 
 B−ớc 1 k = 1 P = aox + a1 
 B−ớc 2 k = 2 P = (aox + a1)x + a2 
 ................................. 
 B−ớc n-1 k = n - 1 P = P(xo) = (...((aox + a1)x+a2x)+...+an-1)x 
 B−ớc n k = n P = P(xo) = (...((aox + a1)x+a2x)+...+an-1)x + an 
Sau đây là ch−ơng trình thực hiên thuật toán trên 
Ch−ơng trình 7-1 
#include 
#include 
#define m 10 
void main(void) 
 { 
 int k,n; 
 float p,x; 
 float a[m]; 
 clrscr(); 
 printf("\nCho bac cua da thuc n = "); 
 scanf("\%d",&n); 
 printf("Vao cac he so a:\n"); 
 for (k=1;k<=n+1;k++) 
 { 
 printf("a[%d] = ",k-1); 
 scanf("%f",&a[k]); 
 }; 
 printf("Cho gia tri x = "); 
 scanf("%f",&x); 
 p=0.0; 
 for (k=1;k<=n+1;k++) 
 p=p*x+a[k]; 
 printf("Tri so cua da thuc P tai x =%.2f la :%.5f",x,p); 
 getch(); 
 } 
2. Sơ đồ Horner tổng quát : Giả sử chúng ta có đa thức : 
 n n - 1 n - 2
Pn(x) = a0x + a1x + a2x +....+ an (1) 
Khai triển Taylor của đa thức tại x = xo có dạng : 
 P′(x ) P′′(x ) P (n) (x )
 P (x) = P (x ) + 0 (x − x ) + 0 (x − x )2 + ⋅⋅⋅ + 0 (x − x )n (2) 
 n n 0 1! 0 2! 0 2! 0
Mặt khác chúng ta có thể biến đổi đa thức về dạng : 
 Pn(x) = (x - xo)Pn-1(x) + Pn(xo) (3) 
 80
Trong đó Pn-1(x) là đa thức bậc n-1 và có dạng : 
 n-1 n - 2 n - 3
 Pn-1 (x) = box + bo-1x + b2x +....+ bn-1 (4) 
Thuật toán để tìm các hệ số nhận đ−ợc bằng cách so sánh (1) và (3) : 
 bo = ao 
 bi = ai + bi-1xo 
 bn = Pn(xo) 
So sánh (2) và (3) ta có : 
 P′(x0 ) P′′(x0 ) 2
 (x − x0 )Pn−1(x0 ) + Pn (x0 ) = Pn (x0 ) + (x − x0 ) + (x − x0 )
 1! 2! 
 P (n) (x )
 + ⋅⋅⋅ + 0 (x − x )n
 2! 0
hay : 
 P′(x ) P′′(x ) P (n) (x )
 (x − x )P (x) = 0 (x − x ) + 0 (x − x )2 + ⋅⋅⋅ + 0 (x − x )n 
 0 n−1 1! 0 2! 0 2! 0
và khi chia hai vế cho (x - x0) ta nhận đ−ợc : 
 P′(x ) P′′(x ) P (n) (x )
 P (x) = 0 + 0 (x − x ) + ⋅⋅⋅ + 0 (x − x )n−1 (5) 
 n−1 1! 2! 0 2! 0
So sánh (4) và (5) ta nhận đ−ợc kết quả : 
 P′(x )
 P (x ) = 0 
 n−1 0 1!
 Trong đó Pn-1(x) lại có thể phân tích giống nh− Pn(x) dạng (3) để tìm ra Pn-1(xo).Quá 
trình này đ−ợc tiếp tục cho đến khi ta tìm hết các hệ số của chuỗi Taylor của Pn(x) 
Tổng quát thuật toán thể hiện ở bảng sau : 
 Pn(x) ao a1 a2 a3 ... an-1 an 
 x = xo 0 boxo b1xo b2xo bn-2xo bn-1xo 
 Pn-1(x) bo b1 b2 b3 ... bn-1 bn = Pn(xo) 
Để hiểu rõ hơn chúng ta lấy một ví dụ cụ thể sau : Khai triển đa thức sau tại x0= 2 
 P(x) = x5 - 2x4 + x3 -5x + 4 
Ta lập bảng tính sau : 
 1 -2 1 0 -5 4 
 2 0 2 0 2 4 2 
 1 0 1 2 -1 2 = P(2)/0! 
 2 0 2 4 10 24 
 1 2 5 12 23 = P'(2)/1! 
 2 0 2 8 26 
 1 4 13 38 = P"(2)/2! 
 2 0 2 12 
 1 6 25 = P"'(2)/3! 
 2 0 2 
 1 8 = P""(2)/4! 
 81
 2 0 
 1 = P""'(2)/4! 
 Nh− vậy : 
 5 4 3 2
 Pn(x) = (x-2) + 8(x-2) +25(x-2) + 38(x-2) + 23(x-2) + 2 
 Ch−ơng trình sau dùng để xác định các hệ số của chuỗi Taylor của đa thức P(x) tại x0 
= 2. 
Ch−ơng trình 7-2 
#include 
#include 
#define m 10 
void main(void) 
 { 
 float a[m],b[m],c[m]; 
 int n,i,j,k; 
 float x; 
 clrscr(); 
 printf("Cho bac cua da thuc n = "); 
 scanf("%d",&n); 
 printf("Cho gia tri x = "); 
 scanf("%f",&x); 
 printf("Vao cac he so a\n"); 
 for (k=n;k>=0;k--) 
 { 
 printf("a[%d] = ",n-k); 
 scanf("%f",&a[k]); 
 } 
 printf("\n"); 
 b[n] = a[n]; 
 c[n] = a[n]; 
 for (k=0;k<=n-1;k++) 
 { 
 for (i=n-1;i>=k;i--) 
 b[i] = b[i+1]*x + a[i]; 
 c[k] = b[k]; 
 for (j=n;j>=k+1;j--) 
 a[j] = b[j]; 
 } 
 printf("\nSo do Horner tong quat"); 
 printf("\nKhai trien tai x = %.4f\n",x); 
 for (k=n;k>=0;k--) 
 printf("%10.4f\t",c[k]); 
 getch(); 
 } 
 82
 Đ3. Các phép tính trên đa thức 
1. Phép cộng hai đa thức : Giả sử chúng ta có hai đa thức A(x) bậc n và B(x) bậc m với 
n>m. Khi cộng hai đa thức này,chúng ta cộng lần l−ợt các hệ số cùng bậc của chúng với 
nhau.Ta có ch−ơng trình sau : 
Ch−ơng trình 7-3 
#include 
#include 
#define t 10 
void main(void) 
 { 
 int k,n,m; 
 float a[t],b[t],c[t]; 
 clrscr(); 
 printf("Cho bac cua da thuc A n = "); 
 scanf("%d",&n); 
 printf("Vao cac he so a\n"); 
 for (k=1;k<=n+1;k++) 
 { 
 printf("a[%d] = ",k-1); 
 scanf("%f",&a[k]); 
 } 
 printf("Cho bac cua da thuc B m = "); 
 scanf("%d",&m); 
 printf("Vao cac he so b\n"); 
 for (k=1;k<=m+1;k++) 
 { 
 printf("b[%d] = ",k-1); 
 scanf("%f",&b[k]); 
 } 
 printf("\n"); 
 for (k=1;k<=n+1;k++) 
 if (k<=n-m) 
 c[k] = a[k]; 
 else 
 c[k] = a[k] + b[k-n+m]; 
 printf("Cac he so cua da thuc tong C la :\n"); 
 for (k=1;k<=n+1;k++) 
 printf("%.4f\t",c[k]); 
 getch(); 
 } 
2. Phép nhân hai đa thức : Để thấy rõ thuật toán xác định các hệ số của đa thức C(x) là kết 
quả của phép nhân hai đa thức A(x) và B(x) ta cho một ví dụ cụ thể : 
 83
 5 4 3 2
 A(x) = aox + a1x + a2x + a3x + a4x + a5 
 3 2 
 B(x) = box + b1x + b2x + b3 
 C(x) = A(x).B(x) 
 8 7 6 5
 = aobo x + (aob1 + a1bo)x +( aob2 + a1b1 + a2bo)x + (aob3 + a1b2 + a2b1+ a3bo )x 
 4 3 2
+ (a1b3 + a2b2 + a3b1 + a4bo)x + (a2b3 + a3b2 + a4b1 + a5bo)x + ( a3b3 + a4b2 + a5b1)x 
+ a5b2x + a5b3 
Các hệ số của đa thức kết quả là : 
 Co = aobo 
 C1 = aob1 + a1bo 
 C2 = aob2 + a1b1 + a2bo 
 C3 = aob3 + a1b2 + a2b1+ a3bo 
 C4 = a1b3 + a2b2 + a3b1 + a4bo 
 C5 = a2b3 + a3b2 + a4b1 + a5bo 
 C6 = a3b3 + a4b2 + a5b1 
 C7 = a5b2 
 C8 = a5b3 
 Ta nhận thấy là hệ số Ck của C(x) là tổng các tích các hệ số của đơn thức bậc i của A(x) và 
bậc (k-i) của B(x). Chỉ số i = 0 khi k m+1.Chỉ số j 
 = k khi k n + 1. Ch−ơng trình tính tích hai đa thức : 
Ch−ơng trình 7-4 
#include 
#include 
#define t 10 
void main() 
 { 
 int k,n,m,l,i,j,p; 
 float a[t],b[t],c[2*t]; 
 clrscr(); 
 printf("Cho bac cua da thuc A n = "); 
 scanf("%d",&n); 
 printf("Vao cac he so a\n"); 
 for (k=1;k<=n+1;k++) 
 { 
 printf("a[%d] = ",k-1); 
 scanf("%f",&a[k]); 
 } 
 printf("Cho bac cua da thuc B m = "); 
 scanf("%d",&m); 
 printf("Vao cac he so b\n"); 
 for (k=1;k<=m+1;k++) 
 { 
 printf("b[%d] = ",k-1); 
 scanf("%f",&b[k]); 
 } 
 printf("\n"); 
 l=n+m; 
 84
 for (k=1;k<=l+1;k++) 
 { 
 if (k<=(n+1)) 
 j=k; 
 else 
 j=n+1; 
 if (k<=(m+1)) 
 p=1; 
 else 
 p= k-m; 
 c[k]=0; 
 for (i=p;i<=j;i++) 
 c[k] = c[k] + a[i]*b[k-i+1]; 
 } 
 printf("Cac he so cua da thuc tich C voi bac %d la :\n",l); 
 for (k=1;k<=l+1;k++) 
 printf("%.4f\t",c[k]); 
 getch(); 
 } 
3. Chia hai đa thức : Giả sử ta có hai đa thức là An(x) và Bm(x) với n ≥ m.Th−ơng hai đa 
thức này là : 
 A n (x) R m−1 (x)
 = Q n−m (x) + 
 B m (x) B m (x)
Ch−ơng trình sau thực hiện việc chia 2 đa thức : 
 Ch−ơng trình 7-5 
#include 
#include 
#include 
#define t 10 
void main() 
 { 
 int k,n,m,l,i,j,jp; 
 float a[t],b[t],q[t],r[t],epsi; 
 clrscr(); 
 printf("Cho bac cua da thuc A n = "); 
 scanf("%d",&n); 
 printf("Vao cac he so a\n"); 
 for (k=1;k<=n+1;k++) 
 { 
 printf("a[%d] = ",k-1); 
 scanf("%f",&a[k]); 
 } 
 printf("\n"); 
 printf("Cho bac cua da thuc B m = "); 
 scanf("%d",&m); 
 85
 printf("Vao cac he so b\n"); 
for (k=1;k<=m+1;k++) 
 { 
 printf("b[%d] = ",k-1); 
 scanf("%f",&b[k]); 
 } 
printf("\n"); 
 printf("Cho gia tri sai so epsilon epsi = "); 
scanf("%f",&epsi); 
if ((m+1)>1) 
 { 
 l=n-m+1; 
 for (i=0;i<=t;i++) 
 r[i]=a[i]; 
 j=n; 
 for (k=1;k<=l;k++) 
 { 
 q[k]=r[1]/b[1]; 
 for (i=1;i<=j;i++) 
 if ((i<m+1)) 
 r[i]=r[i+1]-q[k]*b[i+1]; 
 else 
 r[i]=r[i+1]; 
 j=j-1; 
 } 
 while ((abs(r[i])0)) 
 { 
 for (i=1;i<=j;i++) 
 r[i]=r[i+1]; 
 j=j-1; 
 } 
 if (abs(r[1])<epsi) 
 r[1]=0.0; 
 jp=j+1; 
 } 
 else 
 { 
 l=n+1; 
 for (k=1;k<=l;k++) 
 q[k]=a[k]/b[1]; 
 jp=1; 
 r[1]=0.0; 
 } 
printf("\n"); 
 printf("Cac he so cua thuong Q(x) bac %d la : ",l); 
for (k=1;k<=l;k++) 
 printf("%.3f\t",q[k]); 
printf("\n"); 
 printf("Cac he so cua phan du R(x) bac %d la : ",jp-1); 
for (k=1;k<=jp;k++) 
 86
 printf("%.3f",r[k]); 
getch(); 
 } 
 87