thì tui nói !!! đọc tham khảo chứ nói mấy người copy hết vô đâu
chán chít mẹ.........!!!!!!!!! không đọc rõ cứ ghi lun tung.........

Phân tích thiết kế và đánh giá thuật toán

[You must be registered and logged in to see this link.] Đề bài
Câu 1.
a) Thế nào là bài toán tìm kiếm. Trình bày các bước, đánh giá độ phức tạp và viết sơ đồ thuật toán tìm kiếm tuyến tính.
b) Cài đặt thuật toán sắp xếp nổi bọt tăng dần trên mảng cấu trúc công nhân.
Câu 2.
a) Thuật toán sinh xâu số từ các số 1,2,3 với độ dài n nhập từ bàn phím.
b) Sắp xếp trộn áp dụng trên mảng số nguyên: 3 8 10 9 82 4 78 28 9 10 13 11.
Câu 3.
a) Bài toán nhân dãy các ma trận áp dụng với dãy các ma trận: 5x50; 50x10; 10x20; 20x15.
b) Bài toán tìm dãy con gồm các phần tử liên tiếp có tổng lớn nhất áp dụng với dãy số nguyên:
-9 8 -3 18 4 -2 8 -13 20 -4 8 9 3

Trẻ sơ sinh là sau?
chung ta là sinh viên.
vậy =>> diễn đàn có tôn trọng thàh viên không.
nếu muốn đánh giá thành viên dùng thang điểm hay j đó.

Anh em quên đề thi này của thầy cho hôm học môn LTDT thầy cho à.
Tính độ phưc tạp của thuật toán Dịkstra?
Tính độ phưc tạp của thuật toán Ford_bellman?
Cho bết sự khác biệt về độ phức tạp của 2 thuật toán đó?
(viết trên 1 trang giấy)

tkhking đã viết:

10. Vì sao Pascal bỏ dòng lệnh tăng i lên
Vì vòng lập For trong Pascal thì nó truy cập dựa trên cơ sở đúng trong đó có thể tăng hoặc giảm mổi lần 1 đơn vị khi vòng lập được thực thi. Vì thế nó ít linh hoạt hơn so với các ngôn ngữ khác( vì không thể xác định được số lần tăng hoặc giảm khác 1)

nói rõ hơn ý này nha:

là do vòng lặp for của pascal ý nghĩa rất rõ ràng : cho i chạy từ 1 đến n;

còn for của C gồm 3 biểu thức : for ( bt1; bt2 ; bt3) { khối lệnh }
1 trong 3 biểu thưc này có thể khuyết ;

ở dạng đầy đủ, bt1 là biểu thức khởi gán của for ; vd : i =1 tưc là gán
gia trị i = 1 ; là giá trị đầu tiên của vòng lặp để vòng lặp thực hiện.

bt2 là biểu thức quan trọng nhất, là biểu thưc điều kiện tiwwps tục lặp,
VD i<n ;bt này trả về trị hoặc true hoặc false; nếu true thì tiếp
tục thực hiện khối lệnh, và sau khi thực hiện khối lệnh rồi; phải tăng i lên để lặp, do đó mới có câu lệnh i++ ; i++ mang ý nghĩa là cập nhật lại i để lặp tiếp; còn nếu bt2 nhận giá trị false thì sẽ dừng vòng lặp.

Nếu xet về mặt ý nghĩa, vòng for của pascal tường minh hơn ; có nghĩa
nếu bạn viết for i := 1 to n do .... thì bạn sẽ biết chắc đc nó sẽ lặp n
lần;

còn trong vòng lặp for của C nếu bạn viết for ( i=0 ; i<n; bt3 )
thì bạn chưa biết chắc nó sẽ lặp bao nhiêu lần ; vì số lần lặp này còn
phụ thuộc vào biểu thức thứ 3 : VD nếu là i ++ thì sau 1 vòng lặp, giá
trị của i tăng 1; vì vậy sẽ lặp n lần; nhưng nếu i = i+2 thì mọi chuyện
sẽ khác.

nói vậy có nghĩa : pascal là bạn lặp từ 1 đến n, còn C là : đầu tiên bạn
cho i là gia trị nào đó, kiểm tra xem i có thỏa mãn đk hay ko ( i<n )
; nếu đúng thì thực hiện khối lệnh rồi tăng i lên 1 đơn vị, rồi lại
kiểm tra xem i có thỏa mãn đk hay ko, rồi tiếp tục công việc như trên .

không có EDIT được nên tui post bổ sung thêm ý này

Trong Pascal nếu muốn có bước nhảy chỉ có cách dùng While..Do hoặc Repeat..Until
Vì Pascal có cấu trúc mạnh, chặt chẽ, ko tự do như 1 số ngôn ngữ khác (C/C++, VB...)
Trong Pascal vòng biến điều khiển vòng for tăng lần lượt từ chỉ số đầu
đến chỉ sô cuối, bước nhảy là 1 đơn vị. Nếu trong vòng for có lệnh làm
thay đổi giá trị biến điều kiển thì sẽ phá vỡ tính cấu trúc,đặc biệt lưu
ý không được thay đổi giá trị của biến điều khiển vòng for.

mình thấy mấy pạn giải mấy câu đó vậy là ổn rồi có ai giải được câu 13 ko? cho mình hỏi cái lệnh gọi đệ qui trong hàm đó vậy tính big O sao?

Code:

Void DFS(int
s)  [b][/b]


{


                [b][color=red]1[/color][/b] Int u;                                                                                                 


                [b][color=red]2[/color][/b] daxet[s]=1;


                [b][color=red]3[/color][/b] for(u=1;u<=n;u++)


                {


                                [b][color=red]4[/color][/b] If(a[s][u]
&&!daxet[u])


                                {


                                                [b][color=red]5[/color][/b] Truoc[u]=s;


                                                [b][color=red]6[/color][/b] If(u==t) // khi đã đến được đỉnh T



                                                                [b][color=red]7[/color][/b] Xuat();//hàm
xuất đường đi 


                                                [b][color=red]8 [/color][/b]Else


                                                                [b][color=red]9[/color][/b] DFS(u);


}


}


}

Các lệnh 1,2,7
có độ phúc tạp là O(1)


Vòng for ở
hàng 3 có độ phức tạp là O(n+1)


Hàng 4 có độ phức tạp là O(n)


Hàng 5,6,8,9 có độ phức tạp là O(m) do không xác định
được sẽ có bao nhiêu đỉnh thỏa điều kiện ở hàng 4


èT(n)=3x1+n+1+n+4xm=4+2n+4m,
áp dụng luật tổng ta suy ra độ phức tạp của DFS là O(n+m)

Void DFS(int
s)


{


1 Int u;


2 daxet[s]=1;


3 for(u=1;u<=n;u++)


{


4 If(a[s][u]
&&!daxet[u])


{


5 Truoc[u]=s;


6 If(u==t) // khi đã đến được đỉnh T



7 Xuat();//hàm
xuất đường đi


8 Else


9 DFS(u);


}


}


}





Các lệnh 1,2,7
có độ phúc tạp là O(1)


Vòng for ở
hàng 3 có độ phức tạp là O(n+1)


Hàng 4 có độ phức tạp là O(n)


Hàng 5,6,8,9 có độ phức tạp là O(m) do không xác định
được sẽ có bao nhiêu đỉnh thỏa điều kiện ở hàng 4


èT(n)=3x1+n+1+n+4xm=4+2n+4m,
áp dụng luật tổng ta suy ra độ phức tạp của DFS là O(n+m)

hotboy đã viết:

Void DFS(int
s)


{


1 Int u;


2 daxet[s]=1;


3 for(u=1;u<=n;u++)


{


4 If(a[s][u]
&&!daxet[u])


{


5 Truoc[u]=s;


6 If(u==t) // khi đã đến được đỉnh T



7 Xuat();//hàm
xuất đường đi


8 Else


9 DFS(u);


}


}


}





Các lệnh 1,2,7
có độ phúc tạp là O(1)


Vòng for ở
hàng 3 có độ phức tạp là O(n+1)


Hàng 4 có độ phức tạp là O(n)


Hàng 5,6,8,9 có độ phức tạp là O(m) do không xác định
được sẽ có bao nhiêu đỉnh thỏa điều kiện ở hàng 4


èT(n)=3x1+n+1+n+4xm=4+2n+4m,
áp dụng luật tổng ta suy ra độ phức tạp của DFS là O(n+m)

theo tui nghĩ thì kết quả là đúng nhưng mà cách làm thì sai đó để tui nghiên cứu tí nếu được thì post lên anh em tham khảo nha..ai tìm được thì post lên cho anh em luôn nha

binhduong đã viết:

DFS

Để đánh giá độ phức tạp tính toán của thủ tục, trước hết nhận thấy rằng số phép toán cần thực hiện trong hai chu trình của thuật toán (hai vòng for ở chương trình chính) là cỡ n. Thủ tục DFS phải thực hiện không quá n lần. Tổng số phép toán cần phaỉ thực hiện trong các thủ tục này là O(n+m), do trong các thủ tục này ta phải xét qua tất cả các cạnh và các đỉnh của đồ thị. Vậy độ phức tạp tính toán của thuật toán là O(n+m).

pài ở trên mình thấy như vậy là tạm ổn rồi=> vì đề thầy kêu là phân tích độ phức tạp(tức ta phải mổ xẽ vấn đề ra ->đi đến kết luận 1 cách cụ thể) chứ ko phải là đánh giá như pạn làm.ai có cách làm hay hơn xin post cho anh em nhe.

4. Hệ thức truy hồi tuyến tính thuần nhất bậc một với hệ số hằng. cho vd
Hệ thức truy hồi tuyến tính bậc 1 có dạng: an=c.an-1 với c#0
Ví dụ: Đếm số lần chuyển đĩa của bài toán tháp Hanoi.

5. Hệ thức truy hồi tuyến tính không thuần nhất bậc k. cho vd

Trích dẫn :

Hệ thức truy hồi tuyến tính không thuần nhất bậc k là hệ thức truy hồi có dạng :
an = c1an-1 +… + ckan-k + fn
Trong đó c1, c2, …,ck là những số thực và c*k ≠ 0
Ví dụ Hệ thức truy hồi an= 2an-2 + 2n là hệt thức truy hồi tuyến tính không thuần nhất bậc 2 với hệ số hằng

Câu 6 thì tôi po hand rồi có anh em nào biết không sposst lên nha

Chứng minh bằng phương pháp quy nạp
Bước cơ sở: 1  21 (hiển nhiên đúng)

n  2n
2n  2n .2
n+1  2n  2n+1
n+1  2n+1

tkhking đã viết:

Chứng minh bằng phương pháp quy nạp
Bước cơ sở: 1  21 (hiển nhiên đúng)

n  2n
2n  2n .2
n+1  2n  2n+1
n+1  2n+1

sao cái bài này post lên bị lỗi thế này diển đàn bị sao zậy mong admin sửa dùm nha...

Mấy câu kia thì pó tay rồi sao không có ai thức hổ trợ hết vậy trời...(
mai không biết mình sẽ ra sao nữa

Code:

DFS:
Procedure DFS(v);
1Begin
2   Thamdinh(v);
3            Chuaxet[v]:=false;
 4                For u thuoc ke(v) do
 5                         If chuaxet[u] then DFS(u);
6End;
Có chương trình DFS thì thực hiện không quá n lần
 2 3 có độ phức tạp là O(1)
4  có độ phức tạp là O(n)
5 theo định lý cộng thì dòng if và đệ quy có độ phức tạp là max(O(1, m)) => O(m)
=> Theo định lý cộng xét cho nguyên thuật toán DFS có độ phức tạp là O(n+m)

Code:

BFS
produce BFS(v)
1 begin 2   Queue:=rổng; 3 Queue<= v; 4 chuaxet[v]:=false; 5 while Queue #rổng do 6 begin 7   p<=Queue; 8 thamdinh(p); 9 for u thuoc ke[p] do 10 if chuaxet then 11 begin 12   Queue<= u; 13 chuaxet[u]:=false; 14 end; 15 end; 16 end;   
2,3,4,7,8,13,14 có độ phức tạp là O(1)
5 dòng lặp While có độ phức tạp là O(n)
10,11 vì chỉ chạy không quá số đỉnh nên O(m)
=>Thuật toán BFS có độ phức tạp là O(m+n)

đã hoàn thành nhiệm vụ đã hứa với anh em chỉ còn việc ngày mai lên thi nữa là ok ah

Dẹp hết đi, thảo luận cho đã, cuối cùng được gì nào? 70k à? kakak! tốt nhất là nên đi cúng để các môn sau không gặp ổng thì tốt hơn! hehe!
Ikariam nào anh em!
[You must be registered and logged in to see this link.]

thế là được 70k rồi.hehe