Blog Tin Học | Đại Học Tin Khóa 5 | Thành Đô University: tháng 8 2015

Câu 1:

Xây dựng và cài đặt thuật toán vẽ đoạn thẳng đi qua hai điểm

và

Quy ước vẽ từ

đến

Đáp án:

Ta phân biệt các trường hợp:

Đường ngang và

hoặc

Đường dọc và

hoặc

Trị tuyệt đối hệ số góc

và

hoặc

Trị tuyệt đối hệ số góc

và

hoặc

Ta có phương trình đường thẳng đi qua 2 điểm

và

là

. hay

, đặt

và

. Vậy ta có phương trình

int Round(double a)

{

return (int)(a+0.5);

}

void Line(HDC hdc, int x1, int y1, int x2, int y2)

{

int x, y;

double m, b;

COLORREF Color = RGB(255,0,0);

// Duong ngang

if (y1 == y2)

if (x1 <= x2)

for (x=x1; x<=x2; x++)

SetPoint(hdc,x,y1,Color);

else

for (x=x1; x>=x2; x--)

SetPoint(hdc,x,y1,Color);

// Duong doc

else if (x1 == x2)

if (y1 <= y2)

for (y=y1; y<=y2; y++)

SetPoint(hdc,x1,y,Color);

else

for (y=y1; y>=y2; y--)

SetPoint(hdc,x1,y,Color);

else {

m = 1.0*(y2-y1)/(x2-x1);

b = -m*x1 + y1;

if (fabs(m) <= 1)

if (x1 <= x2)

for (x=x1; x<=x2; x++) {

y = Round(m*x+b);

SetPoint(hdc,x,y,Color);

}

else

for (x=x1; x>=x2; x--) {

y = Round(m*x+b);

SetPoint(hdc,x,y,Color);

}

else {

m = 1.0*(x2-x1)/(y2-y1);

b = -m*y1 + x1;

if (y1 <= y2)

for (y=y1; y<=y2; y++) {

x = Round(m*y+b);

SetPoint(hdc,x,y,Color);

}

else

for (y=y1; y>=y2; y--) {

x = Round(m*y+b);

SetPoint(hdc,x,y,Color);

}

return;

}

Câu 2:

Xây dựng và cài đặt thuật toán vẽ đường tròn có phương trình là

ra chính giữa màn hình.

Đáp án:

Ta có phương trình đường tròn là

Do tính đối xứng của đường tròn, nên ta chỉ cần vẽ cung I, các cung còn lại đều suy ra từ cung I.

Quan sát trên hình vẽ, ta thấy ở cung I, x tăng nhanh hơn y, nên ta dùng phương trình

, hay

, tức là khi lập trình ta cho x chạy rồi tính y.

int Round(double a)

{

return (int)(a+0.5);

}

void Circle(HWND hWnd)

{

HDC hdc;

RECT rt;

int xc, yc;

hdc = GetDC(hWnd);

GetClientRect(hWnd,&rt);

xc = rt.right/2;

yc = rt.bottom/2;

int x, y, r = 100;

x = 0;

y = r;

SetPixel(hdc,xc+x,yc-y,RGB(255,0,0));

SetPixel(hdc,xc+y,yc-x,RGB(255,0,0));

SetPixel(hdc,xc+y,yc+x,RGB(255,0,0));

SetPixel(hdc,xc+x,yc+y,RGB(255,0,0));

SetPixel(hdc,xc-x,yc+y,RGB(255,0,0));

SetPixel(hdc,xc-y,yc+x,RGB(255,0,0));

SetPixel(hdc,xc-y,yc-x,RGB(255,0,0));

SetPixel(hdc,xc-x,yc-y,RGB(255,0,0));

while (x < y) {

x++;

y = Round(sqrt(1.0*r*r-x*x));

SetPixel(hdc,xc+x,yc-y,RGB(255,0,0));

SetPixel(hdc,xc+y,yc-x,RGB(255,0,0));

SetPixel(hdc,xc+y,yc+x,RGB(255,0,0));

SetPixel(hdc,xc+x,yc+y,RGB(255,0,0));

SetPixel(hdc,xc-x,yc+y,RGB(255,0,0));

SetPixel(hdc,xc-y,yc+x,RGB(255,0,0));

SetPixel(hdc,xc-y,yc-x,RGB(255,0,0));

SetPixel(hdc,xc-x,yc-y,RGB(255,0,0));

}

ReleaseDC(hWnd,hdc);

return;

}

Câu 3: Xây dựng và cài đặt thuật toán vẽ ellipse có phương trình là

ra chính giữa màn hình.

Đáp án:

Ta có phương trình của ellipse là

sát trên đồ thị, ta thấy:

Cung I có x tăng nhanh hơn y, nên ta dùng phương trình

, tức là khi lập trình ta cho x chạy rồi tính y.

Cung II có y tăng nhanh hơn x, nên ta dùng phương trình

, tức là khi lập trình ta cho y chạy rồi tính x.

Để xác định được điểm chuyển tiếp A(

, ta cho đạo hàm cấp một của phương trình

bằng -1.

Như vậy ta chỉ cần vẽ cung I và II, các cung còn lại lấy đối xứng là được.

int Round(double a)

{

return (int)(a+0.5);

}

void Ellipse(HWND hWnd)

{

HDC hdc;

RECT rt;

int xc, yc;

hdc = GetDC(hWnd);

int x, y;

GetClientRect(hWnd,&rt);

xc = rt.right/2;

yc = rt.bottom/2;

int a = 300, b = 200;

int xa = Round(a*a/sqrt(1.0*a*a+b*b));

x=0; y=b;

SetPixel(hdc,xc+x,yc-y,RGB(255,0,0));

SetPixel(hdc,xc+x,yc+y,RGB(255,0,0));

SetPixel(hdc,xc-x,yc+y,RGB(255,0,0));

SetPixel(hdc,xc-x,yc-y,RGB(255,0,0));

while (x<xa) {

x++;

y = Round(1.0*b/a*sqrt(1.0*a*a-x*x));

SetPixel(hdc,xc+x,yc-y,RGB(255,0,0));

SetPixel(hdc,xc+x,yc+y,RGB(255,0,0));

SetPixel(hdc,xc-x,yc+y,RGB(255,0,0));

SetPixel(hdc,xc-x,yc-y,RGB(255,0,0));

}

while (y>0) {

y--;

x = Round(1.0*a/b*sqrt(1.0*b*b-y*y));

SetPixel(hdc,xc+x,yc-y,RGB(255,0,0));

SetPixel(hdc,xc+x,yc+y,RGB(255,0,0));

SetPixel(hdc,xc-x,yc+y,RGB(255,0,0));

SetPixel(hdc,xc-x,yc-y,RGB(255,0,0));

}

ReleaseDC(hWnd,hdc);

return;

}

Câu 4: Xây dựng và cài đặt thuật toán vẽ parabola

có a dương ra chính giữa màn hình.

Đáp án:

Quan sát trên đồ thị, ta thấy

Cung I có x tăng nhanh hơn y nên ta dùng phương trình

, tức là khi lập trình ta cho x chạy rồi tính y.

Cung II có y tăng nhanh hơn x nên ta dùng phương trình

, tức là khi lập trình ta cho y chạy rồi tính x.

Để xác định được điểm chuyển tiếp A(

, ta cho đạo hàm cấp một của phương trình

bằng 1.

hay

Như vậy ta chỉ cần vẽ cung I và II, nhánh còn lại của parabola lấy đối xứng là được.

void Parabola(HWND hWnd)

{

HDC hdc;

RECT rt;

int xc, yc;

hdc = GetDC(hWnd);

int x, y;

int a = 100;

int xa = Round(1.0*a/2);

GetClientRect(hWnd,&rt);

xc = rt.right/2;

yc = rt.bottom/2;

x=0;

y=0;

SetPixel(hdc,xc+x,yc-y,RGB(0,0,0));

while (x < xa) {

x++;

y = Round(1.0*x*x/a);

SetPixel(hdc,xc+x,yc-y,RGB(0,0,0));

SetPixel(hdc,xc-x,yc-y,RGB(0,0,0));

}

while (y < 250) {

y++;

x = Round(sqrt(1.0*a*y));

SetPixel(hdc,xc+x,yc-y,RGB(0,0,0));

SetPixel(hdc,xc-x,yc-y,RGB(0,0,0));

}

ReleaseDC(hWnd,hdc);

return;

}

Câu 5: Xây dựng và cài đặt thuật toán vẽ đường

trong một chu kỳ ra chính giữa màn hình.

Đáp án:

Ta phải chuẩn hóa phương trình

để có thể vẽ ra màn hình, chẳng hạn ta chuẩn hóa như sau:

với x = 0..N

Quan sát trên đồ thị, ta nhận thấy:

Cung I có x tăng hơn y nên ta dùng phương trình

, tức là khi lập trình ta cho x chạy rồi tính y.

Cung II có y tăng hơn x nên ta dùng phương trình

, tức là khi lập trình ta cho y chạy rồi tính x.

Để xác định được điểm chuyển tiếp A(

, ta cho đạo hàm cấp một của phương trình

bằng 1.

Như vậy ta chỉ cần vẽ cung I và II, các cung còn lại lấy đối xứng là được.

int Round(double a)

{

return (int)(a+0.5);

}

void Sin(HWND hWnd)

{

HDC hdc;

RECT rt;

double pi = 4.0*atan(1.0);

int xc, yc;

int x, y;

int A = 200, N = 400;

int xa = Round(N/(2*pi)*acos(N/(2*pi*A)));

hdc = GetDC(hWnd);

GetClientRect(hWnd,&rt);

xc = rt.right/2;

yc = rt.bottom/2;

x = N/4; y = A;

SetPixel(hdc,x,yc-y,RGB(0,0,0));

SetPixel(hdc,N/2-x,yc-y,RGB(0,0,0));

SetPixel(hdc,N/2+x,yc+y,RGB(0,0,0));

SetPixel(hdc,N-x,yc+y,RGB(0,0,0));

while (x>xa) {

x--;

y = Round(A*sin(2*pi*x/N));

SetPixel(hdc,x,yc-y,RGB(0,0,0));

SetPixel(hdc,N/2-x,yc-y,RGB(0,0,0));

SetPixel(hdc,N/2+x,yc+y,RGB(0,0,0));

SetPixel(hdc,N-x,yc+y,RGB(0,0,0));

}

while (y>0) {

y--;

x = Round(N/(2*pi)*asin(1.0*y/A));

SetPixel(hdc,x,yc-y,RGB(0,0,0));

SetPixel(hdc,N/2-x,yc-y,RGB(0,0,0));

SetPixel(hdc,N/2+x,yc+y,RGB(0,0,0));

SetPixel(hdc,N-x,yc+y,RGB(0,0,0));

}

ReleaseDC(hWnd,hdc);

return;

}

Câu 5: Xây dựng và cài đặt thuật toán DDA (Digital Differential Analyzer)

vẽ đoạn thẳng đi qua hai điểm

và

. Giới hạn chỉ xét hệ số góc

và

Đáp án:

Ta có phương trình đường thẳng đi qua 2 điểm

và

là

. Do giới hạn hệ số góc

, tức là x tăng nhanh hơn y nên ta dùng phương trình

, hay

, đặt

và

. Vậy ta có phương trình

Ở bước k ta có

Ở bước k+1 ta có

Do x tăng nhanh hơn y nên

Suy ra

Hay

So sánh phương trình

với phương trình

, ta thấy bớt đi một phép nhân.

Đại lượng

được gọi là vi phân số (sai phân), do

nên thuật toán có tên là bộ phân tích sai phân.

int Round(double a)

{

return (int)(a+0.5);

}

void DDALine(HWND hWnd, int x1, int y1, int x2, int y2)

{

HDC hdc;

hdc = GetDC(hWnd);

double x,y,m;

x = x1;

y = y1;

SetPixel(hdc,Round(x),Round(y),RGB(255,0,0));

if (x1 == x2)

if (y1<y2)

while (y<y2) {

y++;

Sleep(20);

SetPixel(hdc,Round(x),Round(y),RGB(255,0,0));

}

else

while (y>y2) {

y--;

Sleep(20);

SetPixel(hdc,Round(x),Round(y),RGB(255,0,0));

}

else if (y1 == y2)

if (x1<x2)

while (x<x2) {

x++;

Sleep(20);

SetPixel(hdc,Round(x),Round(y),RGB(255,0,0));

}

else

while (x>x2) {

x--;

Sleep(20);

SetPixel(hdc,Round(x),Round(y),RGB(255,0,0));

}

else {

m = 1.0*(y2-y1)/(x2-x1);

if (fabs(m)<=1)

if (x1<x2)

while (x<x2) {

x++;

y = y+m;

Sleep(20);

SetPixel(hdc,Round(x),Round(y),RGB(255,0,0));

}

else

while (x>x2) {

x--;

y = y-m;

Sleep(20);

SetPixel(hdc,Round(x),Round(y),RGB(255,0,0));

}

else

if (y1<y2)

while (y<y2) {

y++;

x = x+1/m;

Sleep(20);

SetPixel(hdc,Round(x),Round(y),RGB(255,0,0));

}

else

while (y>y2) {

y--;

x = x-1/m;

Sleep(20);

SetPixel(hdc,Round(x),Round(y),RGB(255,0,0));

}

ReleaseDC(hWnd,hdc);

return;

}

Câu 6:

Xây dựng và cài đặt thuật toán Bresenham vẽ đoạn thẳng đi qua hai điểm

và

. Giới hạn chỉ xét hệ số góc

và

Đáp án:

Ta có phương trình đường thẳng đi qua 2 điểm

và

là

. Do giới hạn hệ số góc

, tức là x tăng nhanh hơn y nên ta dùng phương trình

, hay

, đặt

và

. Vậy ta có phương trình

Do giới hạn hệ số góc

và

, nên ở:

Bước k ta có

Bước

ta có

, trong đó

hoặc

Mục đích của thuật toán Bresenham là dùng toàn số nguyên để tính toán cho nhanh.

Thuật toán gồm 3 bước:

Bước 1: Tính

và

nên

và

dương.

Gọi

Nhận xét: nếu

thì

Ta có:

Ta nhận thấy d có đại lượng

là số thực, nên d là số thực do đó ta phải chuyển thành số nguyên, nếu không chuyển được thành số nguyên thì ta dùng phương pháp bình thường để vẽ đường.

Đặt

và

Nhân 2 vế của d cho dx để tạo ra

nguyên.

Do giới hạn

nên

dương, nên nhận xét về

cũng như nhận xét về d, tức là nếu

thì

Bước 2: Đệ qui

Nhắc lại

Suy ra

, nên

hay

Nếu

thì

, hay

Nếu

thì

, hay

Bước 3: Tính p ban đầu

Dùng phương trình

Tại điểm ban đầu thì

nên

void BresenhamLine(HWND hWnd)

{

HDC hdc;

hdc = GetDC(hWnd);

int x1,y1,x2,y2;

x1 = 100; y1 = 100; x2 = 400; y2 = 300;

int dx = x2-x1, dy = y2-y1;

int p = 2*dy - dx;

int x, y;

x = x1;

y = y1;

SetPixel(hdc,x,y,RGB(255,0,0));

while (x<x2) {

if (p<0)

p = p + 2*dy;

else {

p = p + 2*dy - 2*dx;

y++;

}

x++;

Sleep(20);

SetPixel(hdc,x,y,RGB(255,0,0));

}

ReleaseDC(hWnd,hdc);

return;

}

Câu 7: Xây dựng và cài đặt thuật toán vẽ đường tròn có phương trình là

ra chính giữa màn hình bằng thuật toán Bresenham.

Đáp án:

Do tính đối xứng của đường tròn, nên ta chỉ cần vẽ cung

, các cung còn lại lấy đối xứng là được. Cung cần vẽ có x tăng nhanh hơn y, nên ta dùng phương trình

, hay

, tức là khi lập trình ta cho x chạy rồi tính y.

Bước k ta có

Bước

ta có

, trong đó

hoặc

Mục đích của thuật toán Bresenham là dùng toàn số nguyên để tính toán cho nhanh.

Thuật toán gồm 3 bước:

Bước 1: Tính

và

nên

và

dương.

Gọi

Nhận xét: nếu

thì

Ta có

Ta nhận thấy d có đại lượng

là số thực, nên d là số thực do đó ta phải chuyển thành số nguyên, nếu không chuyển được thành số nguyên thì ta dùng phương pháp bình thường để vẽ đường tròn.

Đặt

Gọi

Nhận xét: nếu

thì

Ta thấy

nguyên.

Ta có

Bước 2: Đệ qui

Nhắc lại

Suy ra

Ta có

, nên

Hay

Nếu

thì

, hay

Nếu

thì

, hay

Bước 3: Tính p ban đầu

Dùng phương trình

Tại điểm ban đầu thì

Nên

void BresenhamCircle(HWND hWnd)

{

HDC hdc;

RECT rt;

int xc, yc;

hdc = GetDC(hWnd);

int x, y, p;

GetClientRect(hWnd,&rt);

xc = rt.right/2;

yc = rt.bottom/2;

int r = 200;

x=0; y=r;

SetPixel(hdc,xc+x,yc-y,RGB(255,0,0));

SetPixel(hdc,xc+y,yc-x,RGB(255,0,0));

SetPixel(hdc,xc+y,yc+x,RGB(255,0,0));

SetPixel(hdc,xc+x,yc+y,RGB(255,0,0));

SetPixel(hdc,xc-x,yc+y,RGB(255,0,0));

SetPixel(hdc,xc-y,yc+x,RGB(255,0,0));

SetPixel(hdc,xc-y,yc-x,RGB(255,0,0));

SetPixel(hdc,xc-x,yc-y,RGB(255,0,0));

p = 2*r-3;

while (x<y) {

if (p<0) {

p = p - 4*x + 4*y - 10;

y--;

}

else

p = p - 4*x - 6;

x++;

SetPixel(hdc,xc+x,yc-y,RGB(255,0,0));

SetPixel(hdc,xc+y,yc-x,RGB(255,0,0));

SetPixel(hdc,xc+y,yc+x,RGB(255,0,0));

SetPixel(hdc,xc+x,yc+y,RGB(255,0,0));

SetPixel(hdc,xc-x,yc+y,RGB(255,0,0));

SetPixel(hdc,xc-y,yc+x,RGB(255,0,0));

SetPixel(hdc,xc-y,yc-x,RGB(255,0,0));

SetPixel(hdc,xc-x,yc-y,RGB(255,0,0));

}

ReleaseDC(hWnd, hdc);

return;

}

Câu 8: Xây dựng và cài đặt thuật toán vẽ ellipse có phương trình là

ra chính giữa màn hình bằng thuật toán Bresenham.

Đáp án:

Quan sát trên đồ thị, ta thấy:

Cung I có x tăng nhanh hơn y, nên ta dùng phương trình

, tức là khi lập trình ta cho x chạy rồi tính y.

Cung II có y tăng nhanh hơn x, nên ta dùng phương trình

, tức là khi lập trình ta cho y chạy rồi tính x.

Để xác định được điểm chuyển tiếp A(

, ta cho đạo hàm cấp một của phương trình

bằng -1.

Như vậy ta chỉ cần vẽ cung I và II, các cung còn lại lấy đối xứng là được.

Thuật toán Bresenham gồm 3 bước:

Xét cung I:

Bước k ta có

Bước

ta có

, trong đó

hoặc

Mục đích của thuật toán Bresenham là dùng toàn số nguyên để tính toán cho nhanh.

Bước 1: Tính

và

nên

và

dương.

Gọi

Nhận xét: nếu

thì

Ta có

Ta nhận thấy d có đại lượng

là số thực, nên d là số thực do đó ta phải chuyển thành số nguyên, nếu không chuyển được thành số nguyên thì ta dùng phương pháp bình thường để vẽ ellipse.

Đặt

nên

và

dương.

Gọi

Nhận xét cũng tương tự như trên:

Nếu

thì

Ta có

Bước 2: Đệ qui

Nhắc lại

Suy ra

Nếu

thì

Nếu

thì

Bước 3: Tính p ban đầu

Dùng phương trình

Tại điểm ban đầu thì

Nên

Thực hiện tương tự cho cung II

void BresenhamEllipse(HWND hWnd)

{

HDC hdc;

RECT rt;

int xc, yc;

hdc = GetDC(hWnd);

int x, y;

GetClientRect(hWnd,&rt);

xc = rt.right/2;

yc = rt.bottom/2;

int a = 200, b = 250;

int xa = Round(a*a/sqrt(1.0*a*a+b*b));

int p = 2*a*a*b - a*a - 2*b*b ;

x=0; y=b;

SetPixel(hdc,xc+x,yc-y,RGB(0,0,0));

SetPixel(hdc,xc+x,yc+y,RGB(0,0,0));

SetPixel(hdc,xc-x,yc+y,RGB(0,0,0));

SetPixel(hdc,xc-x,yc-y,RGB(0,0,0));

// Cung I

while (x<xa) {

if (p<0) {

p = p - 4*b*b*x+4*a*a*y-4*a*a-6*b*b;

y--;

}

else

p = p -4*b*b*x - 6*b*b;

x++;

SetPixel(hdc,xc+x,yc-y,RGB(0,0,0));

SetPixel(hdc,xc+x,yc+y,RGB(0,0,0));

SetPixel(hdc,xc-x,yc+y,RGB(0,0,0));

SetPixel(hdc,xc-x,yc-y,RGB(0,0,0));

}

// Cung II

p = -2*a*a*y*y-4*a*a*y-2*b*b*x*x+2*b*b*x+2*a*a*b*b-2*a*a-b*b;

while (y>0) {

if (p<0) {

p = p - 4*a*a*y+4*b*b*x-4*b*b-6*a*a;

x++;

}

else

p = p -4*a*a*y - 6*a*a;

y--;

SetPixel(hdc,xc+x,yc-y,RGB(0,0,0));

SetPixel(hdc,xc+x,yc+y,RGB(0,0,0));

SetPixel(hdc,xc-x,yc+y,RGB(0,0,0));

SetPixel(hdc,xc-x,yc-y,RGB(0,0,0));

}

ReleaseDC(hWnd,hdc);

return;

}

Câu 9: Xây dựng và cài đặt thuật toán vẽ parabola

với a nguyên dương ra chính giữa màn hình dùng thuật toán Bresenham.

Đáp án:

Quan sát trên đồ thị, ta thấy

Cung I có x tăng nhanh hơn y nên ta dùng phương trình

, tức là khi lập trình ta cho x chạy rồi tính y.

Cung II có y tăng nhanh hơn x nên ta dùng phương trình

, tức là khi lập trình ta cho y chạy rồi tính x.

Để xác định được điểm chuyển tiếp A(

, ta cho đạo hàm cấp một của phương trình

bằng 1.

hay

Như vậy ta chỉ cần vẽ cung I và II, nhánh còn lại của parabola lấy đối xứng là được.

Mục đích của thuật toán Bresenham là dùng toàn số nguyên để tính toán cho nhanh.

Xét cung I:

Ta có x tăng nhanh hơn y.

Bước k ta có

Bước

ta có

, trong đó

hoặc

Thuật toán Bresenham gồm 3 bước:

Bước 1: Tính

và

nên

và

dương.

Gọi

Nhận xét: nếu

thì

Ta có

với

nên d là số thực do đó ta phải chuyển thành số nguyên, nếu không chuyển được thành số nguyên thì ta dùng phương pháp bình thường để vẽ.

Nhân 2 vế của d cho a.

Đặt

Nhận xét của d và

giống nhau vì a dương, do a nguyên nên

nguyên.

Nhận xét: nếu

thì

Bước 2: Đệ qui

Nhắc lại

Suy ra

Nếu

thì

nên

Nếu

thì

nên

Bước 3: Tính p ban đầu

Dùng phương trình

Tại điểm ban đầu thì

Nên

Xét cung II:

Ta có y tăng nhanh hơn x.

Bước k ta có

Bước

ta có

, trong đó

hoặc

Thuật toán Bresenham gồm 3 bước:

Bước 1: Tính

và

nên

và

dương.

Gọi

Nhận xét: nếu

thì

Ta có

với

nên d là số thực do đó ta phải chuyển thành số nguyên, nếu không chuyển được thành số nguyên thì ta dùng phương pháp bình thường để vẽ.

Đặt

Nhận xét của d và

cũng giống nhau.

Nếu

thì

Bước 2: Đệ qui

Nhắc lại

Suy ra

với

Suy ra

Nếu

thì

, hay

thì

, hay

Bước 3: Tính p ban đầu

Dùng phương trình

void BresenhamParabola(HWND hWnd)

{

HDC hdc;

RECT rt;

int xc, yc;

hdc = GetDC(hWnd);

int x, y;

int a = 200;

int xa = Round(1.0*a/2);

int p = -a+2;

GetClientRect(hWnd,&rt);

xc = rt.right/2;

yc = rt.bottom/2;

x=0;

y=0;

SetPixel(hdc,xc+x,yc-y,RGB(0,0,0));

while (x < xa) {

if (p<0)

p = p + 4*x+6;

else {

p = p + 4*x+6-2*a;

y++;

}

x++;

SetPixel(hdc,xc+x,yc-y,RGB(0,0,0));

SetPixel(hdc,xc-x,yc-y,RGB(0,0,0));

}

p = 2*x*x+2*x-2*a*y-2*a+1;

while (y < 250) {

if (p<0) {

p = p + 4*x+4-2*a;

x++;

}

else

p = p - 2*a;

y++;

SetPixel(hdc,xc+x,yc-y,RGB(0,0,0));

SetPixel(hdc,xc-x,yc-y,RGB(0,0,0));

}

ReleaseDC(hWnd,hdc);

return;

}

Câu 10:

Xây dựng và cài đặt thuật toán MidPoint vẽ đoạn thẳng đi qua hai điểm

và

. Giới hạn chỉ xét hệ số góc

và

. Quy ước vẽ từ

đến

Đáp án:

Do giới hạn hệ số góc

và

, nên ở:

Bước k ta có

Bước

ta có

, trong đó

hoặc

Ta dùng phương trình tổng quát của đường thẳng

Ta có phương trình đường thẳng đi qua 2 điểm

và

là

Suy ra

Đặt

và

Ta được phương trình

Ta chọn phương trình đơn giản nhất để dễ nêu nhận xét, chẳng hạn chọn

và

, khi đó ta được phương trình

Nhận xét:

thì điểm

nằm phía trên đường thẳng.

thì điểm

nằm trùng hay nằm phía dưới đường thẳng.

Thuật toán MidPoint gồm 3 bước:

Bước 1: Tính

với

Mục đích của thuật toán MidPoint là dùng số nguyên để tính cho nhanh. Ta thấy

có đại lượng

nên

là số thực. Ta phải chuyển

thành số nguyên nhưng nhận xét cũng giống như nhận xét về

Đặt

Rõ ràng

nguyên (A, B, C nguyên)

Nhận xét: Nếu

thì điểm M nằm phía trên đường thẳng, hay

Nếu

thì điểm M nằm trùng hay nằm phía dưới đường thẳng, hay

Bước 2: Đệ qui

Nhắc lại

Suy ra

, nên

Suy ra

Nếu

thì

, hay

Nếu

thì

, hay

Bước 3: Tính p ban đầu

Dùng

Tại điểm ban đầu thì

Ta có

, nên

void MidPointLine(HWND hWnd)

{

HDC hdc;

hdc = GetDC(hWnd);

int x1,y1,x2,y2;

x1=100; y1=100;

x2=400; y2=300;

int A = y2-y1;

int B = -(x2-x1);

int p = 2*A+B;

int x, y;

x=x1; y=y1;

SetPixel(hdc,x,y,RGB(255,0,0));

while (x<x2) {

if (p<0)

p = p + 2*A;

else {

p = p + 2*A + 2*B;

y++;

}

x++;

Sleep(20);

SetPixel(hdc,x,y,RGB(255,0,0));

}

ReleaseDC(hWnd,hdc);

return;

}

Câu 11:

Xây dựng và cài đặt thuật toán MidPoint vẽ đoạn thẳng đi qua hai điểm

và

. Giới hạn chỉ xét hệ số góc

và

. Quy ước vẽ từ

đến

Đáp án:

Do giới hạn hệ số góc

và

, nên ở:

Bước k ta có

Bước

ta có

, trong đó

hoặc

Ta dùng phương trình tổng quát của đường thẳng

Ta có phương trình đường thẳng đi qua 2 điểm

và

là

Suy ra

Đặt

và

Ta được phương trình

Ta chọn trường hợp đơn giản để dễ nêu nhận xét, chẳng hạn chọn

và

, khi đó ta được phương trình

Nhận xét: nếu

thì điểm

nằm phía dưới đường thẳng.

nếu

thì điểm

nằm trùng hoặc nằm phía trên đường thẳng

Thuật toán MidPoint gồm 3 bước:

Bước 1: Tính

với

Mục đích của thuật toán MidPoint là dùng số nguyên để tính cho nhanh. Ta thấy

có đại lượng

nên

là số thực. Ta phải chuyển

thành số nguyên nhưng nhận xét cũng giống như nhận xét về

Đặt

Rõ ràng

nguyên (A, B, C nguyên)

Nhận xét: Nếu

thì điểm M nằm phía dưới đường thẳng, hay

Nếu

thì điểm M nằm trùng hay nằm phía trên đường thẳng, hay

Bước 2: Đệ qui

Nhắc lại

Suy ra

, nên

Suy ra

Nếu

thì

, hay

Nếu

thì

, hay

Bước 3: Tính p ban đầu

Dùng

Tại điểm ban đầu thì

Ta có

, nên

void MidPointLine(HWND hWnd)

{

HDC hdc;

hdc = GetDC(hWnd);

int x1,y1,x2,y2;

x1=400; y1=300;

x2=100; y2=100;

int A = y2-y1;

int B = -(x2-x1);

int p = -2*A-B;

int x, y;

x=x1; y=y1;

SetPixel(hdc,x,y,RGB(255,0,0));

while (x>x2) {

if (p<0)

p = p - 2*A;

else {

p = p - 2*A - 2*B;

y--;

}

x--;

Sleep(20);

SetPixel(hdc,x,y,RGB(255,0,0));

}

ReleaseDC(hWnd,hdc);

return;

}

Câu 12:

Xây dựng và cài đặt thuật toán MidPoint vẽ đoạn thẳng đi qua hai điểm

và

. Giới hạn chỉ xét hệ số góc

và

. Quy ước vẽ từ

đến

Đáp án:

Do giới hạn hệ số góc

và

, nên ở:

Bước k ta có

Bước

ta có

, trong đó

hoặc

Ta dùng phương trình tổng quát của đường thẳng

Ta có phương trình đường thẳng đi qua 2 điểm

và

là

Suy ra

Đặt

và

Ta được phương trình

Ta chọn phương trình đơn giản nhất để dễ nêu nhận xét, chẳng hạn chọn

và

, khi đó ta được phương trình

Nhận xét:

thì điểm

nằm bên trái đường thẳng.

thì điểm

nằm trùng hay nằm bên phải đường thẳng.

Thuật toán MidPoint gồm 3 bước:

Bước 1: Tính

với

Mục đích của thuật toán MidPoint là dùng số nguyên để tính cho nhanh. Ta thấy

có đại lượng

nên

là số thực. Ta phải chuyển

thành số nguyên nhưng nhận xét cũng giống như nhận xét về

Đặt

Rõ ràng

nguyên (A, B, C nguyên)

Nhận xét: Nếu

thì điểm M nằm bên trái đường thẳng, hay

Nếu

thì điểm M nằm trùng hay nằm bên phải đường thẳng, hay

Bước 2: Đệ qui

Nhắc lại

Suy ra

, nên

Suy ra

Nếu

thì

, hay

Nếu

thì

, hay

Bước 3: Tính p ban đầu

Dùng

Tại điểm ban đầu thì

Ta có

, nên

void MidPointLine(HWND hWnd)

{

HDC hdc;

hdc = GetDC(hWnd);

int x1,y1,x2,y2;

x1=0; y1=0;

x2=100; y2=300;

int A = y2-y1;

int B = -(x2-x1);

int p = A+2*B;

int x, y;

x=x1; y=y1;

SetPixel(hdc,x,y,RGB(255,0,0));

while (y<y2) {

if (p<0){

p = p + 2*A + 2*B;

x++;

}

else

p = p + 2*B;

y++;

Sleep(20);

SetPixel(hdc,x,y,RGB(255,0,0));

}

ReleaseDC(hWnd,hdc);

return;

}

Câu 13:

Xây dựng và cài đặt thuật toán MidPoint vẽ đoạn thẳng đi qua hai điểm

và

. Giới hạn chỉ xét hệ số góc

và

. Quy ước vẽ từ

đến

Đáp án:

Do giới hạn hệ số góc

và

, nên ở:

Bước k ta có

Bước

ta có

, trong đó

hoặc

Ta dùng phương trình tổng quát của đường thẳng

Ta có phương trình đường thẳng đi qua 2 điểm

và

là

Suy ra

Đặt

và

Ta được phương trình

Ta chọn trường hợp đơn giản để dễ nêu nhận xét, chẳng hạn chọn

và

, khi đó ta được phương trình

Nhận xét: nếu

thì điểm

nằm bên phải đường thẳng.

nếu

thì điểm

nằm trùng hoặc nằm bên trái đường thẳng

Thuật toán MidPoint gồm 3 bước:

Bước 1: Tính

với

Mục đích của thuật toán MidPoint là dùng số nguyên để tính cho nhanh. Ta thấy

có đại lượng

nên

là số thực. Ta phải chuyển

thành số nguyên nhưng nhận xét cũng giống như nhận xét về

Đặt

Rõ ràng

nguyên (A, B, C nguyên)

Nhận xét: Nếu

thì điểm M nằm bên phải đường thẳng, hay

Nếu

thì điểm M nằm trùng hay nằm bên trái đường thẳng, hay

Bước 2: Đệ qui

Nhắc lại

Suy ra

, nên

Suy ra

Nếu

thì

, hay

Nếu

thì

, hay

Bước 3: Tính p ban đầu

Dùng

Tại điểm ban đầu thì

Ta có

, nên

void MidPointLine (HWND hWnd)

{

HDC hdc;

hdc = GetDC(hWnd);

int x1,y1,x2,y2;

x1=300; y1=300;

x2=200; y2=0;

int A = y2-y1;

int B = -(x2-x1);

int p = -A-2*B;

int x, y;

x=x1; y=y1;

SetPixel(hdc,x,y,RGB(255,0,0));

while (y>y2) {

if (p<0) {

p = p - 2*A - 2*B;

x--;

}

else

p = p - 2*B;

y--;

Sleep(20);

SetPixel(hdc,x,y,RGB(255,0,0));

}

ReleaseDC(hWnd,hdc);

return;

}

Câu 14: Xây dựng và cài đặt thuật toán vẽ đường tròn có phương trình là

ra chính giữa màn hình bằng thuật toán MidPoint.

Đáp án:

Do tính đối xứng của đường tròn, nên ta chỉ cần vẽ cung

, các cung còn lại lấy đối xứng là được. Cung cần vẽ có x tăng nhanh hơn y, nên ở

Bước k ta có

Bước

ta có

, trong đó

hoặc

Ta dùng phương trình tổng quát của đường tròn

Ta chọn trường hợp đơn giản để dễ nêu nhận xét, chẳng hạn chọn

Nhận xét: nếu

thì điểm

nằm bên trong đường tròn.

nếu

thì điểm

nằm trùng hay nằm bên ngoài đường tròn.

Thuật toán MidPoint gồm 3 bước:

Bước 1: Tính

với

Mục đích của thuật toán MidPoint là dùng số nguyên để tính cho nhanh. Ta thấy

có đại lượng

nên

là số thực. Ta phải chuyển

thành số nguyên nhưng nhận xét cũng giống như nhận xét về

Đặt

Rõ ràng

nguyên (r nguyên)

Nhận xét: Nếu

thì điểm M nằm bên trong đường tròn, hay

Nếu

thì điểm M nằm trùng hay nằm bên ngoài đường tròn, hay

Bước 2: Đệ qui

Nhắc lại

Suy ra

Ta có

Nên

Suy ra

Nếu

thì

, hay

Nếu

thì

, hay

Bước 3: Tính p ban đầu

Dùng

Tại điểm ban đầu thì

nên

void MidPointCircle(HWND hWnd)

{

HDC hdc;

hdc = GetDC(hWnd);

RECT rt;

int xc, yc;

GetClientRect(hWnd,&rt);

xc = rt.right/2;

yc = rt.bottom/2;

int r = 200;

int p = 5-4*r;

int x, y;

x = 0; y = r;

SetPixel(hdc,xc+x,yc-y,RGB(255,0,0));

SetPixel(hdc,xc+y,yc-x,RGB(255,0,0));

SetPixel(hdc,xc+y,yc+x,RGB(255,0,0));

SetPixel(hdc,xc+x,yc+y,RGB(255,0,0));

SetPixel(hdc,xc-x,yc+y,RGB(255,0,0));

SetPixel(hdc,xc-y,yc+x,RGB(255,0,0));

SetPixel(hdc,xc-y,yc-x,RGB(255,0,0));

SetPixel(hdc,xc-x,yc-y,RGB(255,0,0));

while (x<y) {

if (p<0)

p = p + 8*x + 12;

else {

p = p + 8*x - 8*y + 20;

y--;

}

x++;

Sleep(20);

SetPixel(hdc,xc+x,yc-y,RGB(255,0,0));

SetPixel(hdc,xc+y,yc-x,RGB(255,0,0));

SetPixel(hdc,xc+y,yc+x,RGB(255,0,0));

SetPixel(hdc,xc+x,yc+y,RGB(255,0,0));

SetPixel(hdc,xc-x,yc+y,RGB(255,0,0));

SetPixel(hdc,xc-y,yc+x,RGB(255,0,0));

SetPixel(hdc,xc-y,yc-x,RGB(255,0,0));

SetPixel(hdc,xc-x,yc-y,RGB(255,0,0));

}

ReleaseDC(hWnd,hdc);

return;

}

Câu 15: Xây dựng và cài đặt thuật toán vẽ ellipse có phương trình là

ra chính giữa màn hình bằng thuật toán MidPoint.

Đáp án:

Quan sát trên đồ thị, ta thấy:

Cung I có x tăng nhanh hơn y còn cung II có y tăng nhanh hơn x nên để xác định được điểm chuyển tiếp A(

, ta cho đạo hàm cấp một của phương trình

bằng -1.

Như vậy ta chỉ cần vẽ cung I và II, các cung còn lại lấy đối xứng là được.

Xét cung I:

Bước k ta có

Bước

ta có

, trong đó

hoặc

Ta dùng phương trình tổng quát của đường tròn

Ta chọn trường hợp đơn giản để dễ nêu nhận xét, chẳng hạn chọn

và

, khi đó ta được phương trình

Nhận xét: nếu

thì điểm

nằm bên trong ellipse.

nếu

thì điểm

nằm trùng hay nằm bên ngoài ellipse.

Thuật toán MidPoint gồm 3 bước:

Bước 1: Tính

với

Mục đích của thuật toán MidPoint là dùng số nguyên để tính cho nhanh. Ta thấy

có đại lượng

nên

là số thực. Ta phải chuyển

thành số nguyên nhưng nhận xét cũng giống như nhận xét về

Đặt

Rõ ràng

nguyên (a, b nguyên)

Nhận xét: Nếu

thì điểm M nằm bên trong ellipse, hay

Nếu

thì điểm M nằm trùng hay nằm bên ngoài ellipse, hay

Bước 2: Đệ qui

Nhắc lại

Suy ra

Ta có

Nên

Suy ra

Nếu

thì

, hay

Nếu

thì

, hay

Bước 3: Tính p ban đầu

Dùng

Tại điểm ban đầu thì

nên

Thực hiện tương tự cho cung II

void MidPointEllipse(HWND hWnd)

{

HDC hdc;

RECT rt;

int xc,yc;

hdc = GetDC(hWnd);

GetClientRect(hWnd,&rt);

xc = rt.right/2;

yc = rt.bottom/2;

int a = 300, b = 200;

int xa = Round(1.0*a*a/sqrt(1.0*a*a+b*b));

int p = -4*a*a*b + a*a + 4*b*b;

int x, y;

x=0; y=b;

SetPixel(hdc,xc+x,yc-y,RGB(255,0,0));

SetPixel(hdc,xc+x,yc+y,RGB(255,0,0));

SetPixel(hdc,xc-x,yc+y,RGB(255,0,0));

SetPixel(hdc,xc-x,yc-y,RGB(255,0,0));

while (x<xa) {

if (p<0)

p = p + 8*b*b*x + 12*b*b;

else {

p = p + 8*b*b*x - 8*a*a*y + 8*a*a + 12*b*b;

y--;

}

x++;

Sleep(10);

SetPixel(hdc,xc+x,yc+y,RGB(255,0,0));

SetPixel(hdc,xc+x,yc-y,RGB(255,0,0));

SetPixel(hdc,xc-x,yc+y,RGB(255,0,0));

SetPixel(hdc,xc-x,yc-y,RGB(255,0,0));

}

p = 4*b*b*x*x+4*b*b*x+4*a*a*y*y-8*a*a*y+4*a*a+b*b-4*a*a*b*b;

while (y>0) {

if (p<0) {

p = p + 8*b*b*x - 8*a*a*y + + 12*a*a + 8*b*b;

x++;

}

else

p = p - 8*a*a*y + 12*a*a;

y--;

Sleep(10);

SetPixel(hdc,xc+x,yc-y,RGB(255,0,0));

SetPixel(hdc,xc+x,yc+y,RGB(255,0,0));

SetPixel(hdc,xc-x,yc+y,RGB(255,0,0));

SetPixel(hdc,xc-x,yc-y,RGB(255,0,0));

}

ReleaseDC(hWnd,hdc);

return;

}

Câu 16: Xây dựng và cài đặt thuật toán vẽ parabola

với a nguyên dương ra chính giữa màn hình dùng thuật toán MidPoint.

Đáp án:

Quan sát trên đồ thị, ta thấy

Cung I có x tăng nhanh hơn y, còn cung II có y tăng nhanh hơn x nên để xác định được điểm chuyển tiếp A(

, ta cho đạo hàm cấp một của phương trình

bằng 1.

hay

Ta chỉ cần vẽ cung I và II, nhánh còn lại của parabola lấy đối xứng là được.

Xét cung I:

Bước k ta có

Bước

ta có

, trong đó

hoặc

Ta dùng phương trình tổng quát của parabola

Nhận xét: nếu

thì điểm

nằm bên trong parabola.

nếu

thì điểm

nằm trùng hay nằm bên ngoài parabola.

Thuật toán MidPoint gồm 3 bước:

Bước 1: Tính

với

Mục đích của thuật toán MidPoint là dùng số nguyên để tính cho nhanh. Ta thấy

có đại lượng

nên

là số thực. Ta phải chuyển

thành số nguyên nhưng nhận xét cũng giống như nhận xét về

Đặt

Rõ ràng

nguyên (a nguyên)

Nhận xét: Nếu

thì điểm M nằm bên trong parabola, hay

Nếu

thì điểm M nằm trùng hay nằm bên ngoài parabola, hay

Bước 2: Đệ qui

Nhắc lại

Suy ra

Ta có

Nên

Suy ra

Nếu

thì

, hay

Nếu

thì

, hay

Bước 3: Tính p ban đầu

Dùng

Tại điểm ban đầu thì

nên

Xét cung II:

Ta có y tăng nhanh hơn x.

Bước k ta có

Bước

ta có

, trong đó

hoặc

Ta dùng phương trình tổng quát của parabola

Nhận xét: nếu

thì điểm

nằm bên trong parabola.

nếu

thì điểm

nằm trùng hay nằm bên ngoài parabola.

Thuật toán MidPoint gồm 3 bước:

Bước 1: Tính

với

Mục đích của thuật toán MidPoint là dùng số nguyên để tính cho nhanh. Ta thấy

có đại lượng

nên

là số thực. Ta phải chuyển

thành số nguyên nhưng nhận xét cũng giống như nhận xét về

Đặt

Rõ ràng

nguyên (a nguyên)

Nhận xét: Nếu

thì điểm M nằm bên trong parabola, hay

Nếu

thì điểm M nằm trùng hay nằm bên ngoài parabola, hay

Bước 2: Đệ qui

Nhắc lại

Suy ra

Ta có

Nên

Suy ra

Nếu

thì

, hay

Nếu

thì

, hay

Bước 3: Tính p ban đầu

Dùng

void MidPointParabol(HWND hWnd)

{

HDC hdc;

RECT rt;

int xc,yc;

hdc = GetDC(hWnd);

GetClientRect(hWnd,&rt);

xc = rt.right/2;

yc = rt.bottom/2;

int a = 100;

int xa = Round(1.0*a/2);

int p = 2-a;

int x, y;

x=0; y=0;

SetPixel(hdc,xc+x,yc-y,RGB(255,0,0));

SetPixel(hdc,xc-x,yc-y,RGB(255,0,0));

while (x<xa) {

if (p<0)

p = p + 4*x + 6;

else {

p = p + 4*x - 2*a + 6;

y++;

}

x++;

Sleep(10);

SetPixel(hdc,xc+x,yc-y,RGB(255,0,0));

SetPixel(hdc,xc-x,yc-y,RGB(255,0,0));

}

p = 4*x*x + 4*x - 4*a*y - 4*a + 1 ;

while (y<300) {

if (p<0) {

p = p + 8*x - 4*a + 8;

x++;

}

else

p = p - 4*a;

y++;

Sleep(10);

SetPixel(hdc,xc+x,yc-y,RGB(0,0,255));

SetPixel(hdc,xc-x,yc-y,RGB(0,0,255));

}

ReleaseDC(hWnd,hdc);

return;

}

Blog Tin Học | Đại Học Tin Khóa 5 | Thành Đô University

Thứ Bảy, 29 tháng 8, 2015

Bài viết

Chia sẻ để thành công