• Vui lòng đọc nội qui diễn đàn để tránh bị xóa bài viết
  • Tìm kiếm trước khi đặt câu hỏi

FVS học thuật toán qua các bài tập

Đây là nơi để các bạn trao đổi về cấu trúc dữ liệu và giải thuật

Điều hành viên: Điều hành

Hình đại diện của người dùng
FVS
Thành viên tích cực
Thành viên tích cực
Bài viết: 178
Ngày tham gia: T.Ba 13/05/2008 10:38 am

FVS học thuật toán qua các bài tập

Gửi bàigửi bởi FVS » CN 21/12/2008 7:55 am

Tên bài viết: FVS học thuật toán qua các bài tập
Tác giả: FVS">FVS
Cấp độ bài viết: Chưa đánh giá
Tóm tắt: Cũng có thể coi là cuốn nhật ký làm bài của FVS (vì tính ngẫu nhiên của bài tập).
Mỗi bài toán được đưa ra sẽ đều có lời giải chi tiết với đầy đủ mã nguồn (mạn phép được minh họa bằng Turbo Pascal) và tư tưởng thuật.
Chắc chắn sẽ giúp ích cho nhiều bạn trong forum!


*Lưu ý: Tất cả source trong topic này đều được Code bởi FVS Mong các bạn tôn trọng bản quyền tác giả khi sao chép.
Sửa lần cuối bởi FVS vào ngày CN 04/01/2009 8:50 am với 4 lần sửa.


Nhật kí giải thuật - FVS:

Http://GiaiThuat.WordPress.Com

Hình đại diện của người dùng
FVS
Thành viên tích cực
Thành viên tích cực
Bài viết: 178
Ngày tham gia: T.Ba 13/05/2008 10:38 am

Thuật toán Dijkstra

Gửi bàigửi bởi FVS » CN 21/12/2008 8:22 am

Nội dung thuật toán: Thuật toán tìm đường đi ngắn nhất trong đồ thị có trọng số cho bởi ma trận kề.
Mô tả:Ta quản lý một tập hợp động S. Ban đầu S={s}.

Với mỗi đỉnh v, chúng ta quản lý một nhãn d[v] là độ dài bé nhất trong các đường đi từ nguồn s đến một đỉnh u nào đó thuộc S, rồi đi theo cạnh nối u-v.

Trong các đỉnh ngoài S, chúng ta chọn đỉnh u có nhãn d[u] bé nhất, bổ sung vào tập S. Tập S được mở rộng thêm một đỉnh, khi đó chúng ta cần cập nhật lại các nhãn d cho phù hợp với định nghĩa.

Thuật toán kết thúc khi toàn bộ các đỉnh đã nằm trong tập S, hoặc nếu chỉ cần tìm đường đi ngắn nhất đến một đỉnh đích t, thì chúng ta dừng lại khi đỉnh t được bổ sung vào tập S.
Cài đặt:
Lúc cài đặt mình vướng mắc nhất chỗ lấy phần tử ở cuối mảng. Cách làm đơn sơ có thể nghĩ ra là dồn các phần tử ở trên xuống --> tuy nhiên làm vậy rùa. Về sau nghĩ ra hai giải pháp:
+, Xài hai mảng luôn phiên (lát nữa sẽ cài đặt theo cách này).
+, Thì mình cứ lấy ở cuối đi, không dồn lại, lúc sau đặt chồng lên nhưng lưu ý thiết kế một biến lưu vị trí phần tử đầu. Vì do số phần tử max=số cạnh của đồ thị nên cách này là khả thi và ưu hơn cách trên cả về thời gian và mem. Đơn giản nên để các bạn tự cài đặt

Mã: Chọn hết

  1. uses crt;
  2. const inp='dijtra.inp';
  3. var a: array[1..50, 1..50] of integer;
  4.     b,c: array[1..50] of byte;
  5.     n,cds,s,f :integer;
  6.     ds:array[1..50] of integer;
  7. procedure readdt;
  8. var Fs:text;
  9.     I,j: integer;
  10. begin
  11.  assign(fs,inp); reset(fs);
  12.  read(fs,n,s,f);
  13.  for i:=1 to n do
  14.   begin
  15.    for j:=1 to n do read(fs,a[i,j]);
  16.    readln(fs);
  17.   end;
  18. close(fs);
  19. end;
  20. procedure Xuat(v:byte);
  21. begin
  22.  if c[v]<>0 then xuat(c[v]);
  23.  write('---->',v);
  24. end;
  25. procedure proc;
  26. var i,j,ht:integer;
  27. begin
  28.  cds:=1;
  29.  fillchar(b[1], sizeof(b), 0);
  30.  b[s]:=1;
  31.  ds[1]:=s;
  32.  c[s]:=0;
  33.  while cds>0 do
  34.   begin
  35.    ht:=ds[cds];
  36.    dec(cds);
  37.    for i:=1 to n do if a[ht, i]<>0 then
  38.     begin
  39.      if b[i]=0 then begin
  40.                      b[i]:=b[ht]+a[ht,i];
  41.                      c[i]:=ht;
  42.                      inc(cds);
  43.                      ds[cds]:=i;
  44.                     end
  45.                else if b[i]>b[ht]+a[ht,i] then begin
  46.                                                 b[i]:=b[ht]+a[ht,i];
  47.                                                 c[i]:=ht;
  48.                                                end;
  49.     end;
  50.   end;
  51. end;
  52. begin
  53.  clrscr;
  54.  readdt;
  55.  proc;writeln;
  56.  writeln(b[f]-1);
  57.  xuat(v);
  58.  readln;
  59. end.
  60.  
Nhật kí giải thuật - FVS:

Http://GiaiThuat.WordPress.Com

Hình đại diện của người dùng
FVS
Thành viên tích cực
Thành viên tích cực
Bài viết: 178
Ngày tham gia: T.Ba 13/05/2008 10:38 am

Cộng số lớn

Gửi bàigửi bởi FVS » CN 21/12/2008 8:34 am

Thiết kế một mảng longint.
Phân tích các số hạng ra dạng: a1*10^3n+a2*10^3(n-1)+...+an*1
Đưa a1, a2, a3,.., an vô mảng.
Cộng hai mảng lại.
Khác với một vài cách tiếp cận là đổi số ra string rồi tiến hành cộng từng chữ số một ---> giảm hiệu suất bộ nhớ (1 byte chỉ lưu được 1 chữ số :)) ) , tính toán rất chậm.
Cách làm này mới thực sự mở rộng phạm vi số nguyên, khoa học :D

Mã: Chọn hết

  1. uses crt;
  2. var s1,s2,tg: string;
  3.     a,b,ab:array[1..100] of longint;
  4.     ca,cb,i,j,cc,nho:longint;
  5.     k,err:integer;
  6. begin
  7.  clrscr;
  8.  write('nhap a, b:');readln(s1);readln(s2);
  9.  ca:=0;cb:=0;
  10.  while length(s1)>0 do
  11.   begin
  12.    if length(s1)<=4 then begin tg:=s1; s1:='' end
  13.                    else begin
  14.                          tg:=copy(s1,length(s1)-3,4);
  15.                          delete(s1, length(s1)-3,4);
  16.                          end;
  17.    inc(ca);val(tg,k,err);a[ca]:=k;
  18.   end;
  19. {-------------}
  20.  cb:=0;
  21.  while length(s2)>0 do
  22.   begin
  23.    if length(s2)<4 then begin tg:=s2; s2:='' end
  24.                    else begin
  25.                          tg:=copy(s2,length(s2)-3,4);
  26.                          delete(s2, length(s2)-3,4);
  27.                          end;
  28.    inc(cb);val(tg,k,err);b[cb]:=k;
  29.   end;
  30.  clrscr;
  31.  for i:=ca downto 1 do write(a[i]);
  32.  writeln;
  33.  writeln('+');
  34.  for i:=cb downto 1 do write(b[i]);writeln;
  35.  writeln('---------------------------------------------------------');
  36.  if ca<=cb then cc:=ca else cc:=cb;
  37.  nho:=0;
  38.  for i:=1 to cc do
  39.   begin
  40.    k:=a[i]+b[i]+nho;
  41.    ab[i]:=k mod 10000;
  42.    nho:=k div 10000;
  43.   end;
  44.  for i:=cc downto 1 do write(ab[i]);
  45.  readln;
  46. end.
Nhật kí giải thuật - FVS:

Http://GiaiThuat.WordPress.Com

Hình đại diện của người dùng
FVS
Thành viên tích cực
Thành viên tích cực
Bài viết: 178
Ngày tham gia: T.Ba 13/05/2008 10:38 am

Re: FVS học thuật toán qua các bài tập

Gửi bàigửi bởi FVS » CN 28/12/2008 6:21 am

Dạo này bận quá, chưa viết tiếp được + mất điện triền miên
Tối đi thi chuyên đề về kiểu gì nếu có điện cũng phải thêm vào bài :)
Nhật kí giải thuật - FVS:

Http://GiaiThuat.WordPress.Com

Hình đại diện của người dùng
tiger86love102
Thành viên danh dự
Thành viên danh dự
Bài viết: 610
Ngày tham gia: CN 19/10/2008 1:10 am
Đến từ: http://ready.vn
Has thanked: 4 time
Been thanked: 21 time
Liên hệ:

Re: FVS học thuật toán qua các bài tập

Gửi bàigửi bởi tiger86love102 » CN 28/12/2008 8:15 am

FVS tiếp tục nhé, có nhiều thuật toán lắm, FVS tiếp hết đc ko? Cố lên nào =D>
Kiếm thêm vài bài tập liên quan cho mọi người tự code để cùng học với chứ :-S
Đội bóng Ready
facebook.com/tiger86love102

Hình đại diện của người dùng
FVS
Thành viên tích cực
Thành viên tích cực
Bài viết: 178
Ngày tham gia: T.Ba 13/05/2008 10:38 am

Dãy quân bài

Gửi bàigửi bởi FVS » T.Hai 29/12/2008 2:36 pm

>>Đề bài: Cho N (2-->10000) quân bài, mỗi quân bài i được đánh số Ai (0-->1000). Quân joker là quân đánh số 0. Quân Joker có thể thay thế bất kì một quân bài nào trong khoảng từ 0-->1000. Hãy chọn ra tập lớn nhất các quân bài lập thành cấp số cộng công sai d=1.
Data trong file Joker.inp: -Dòng đầu là N - số quân bài.
-Dòng tiếp theo gồm n sô Ai-->An (ngăn bởi dấu cách)
Xuất ra file Joker.Out: M S F tương ứng với độ dài max, giá trị đầu, giá trị cuối (trong cách viết xắp xếp từ nhỏ đến lớn của tập cần tìm)
Thuật toán: -Gọi N0 là số quân Joker
-Ta chỉ load mảng A là các quân bài có giá trị khác 0
-Xắp xếp mảng A theo thứ tự tăng dần
Code quy hoạch động:

Mã: Chọn hết

  1. if i=j then fx[i,j]:=0 else fx[i,j]:= fx[i,j-1]+a[j]-a[j-1]-1;
  2.     if fx[i,j]>n0 then break;
  3.     if (a[j]-a[i]+1-fx[i,j]+n0)>max then begin
  4.      max:=(a[j]-a[i]+1-fx[i,j]+n0); s:=i; f:=j;  

Trong đó F[i,j] là max của bài toán con độ dài dữ liệu I-->J
Code:

Mã: Chọn hết

  1. uses crt;
  2. const inp='joker.inp';
  3.       out='joker.out';
  4. var A: array[1..50] of longint;
  5.     Fx: array[1..50, 1..50] of byte;
  6.     i, n, n0, max, s, f: longint;
  7. procedure Qs(l,r: integer);
  8. var k, mid:longint;
  9.     i, j: integer;
  10. begin
  11.  mid:=a[(l+r) div 2];
  12.  i:=l; J:=r;
  13.  repeat
  14.   while a[i]< mid do inc(i);
  15.   while a[j]> mid do dec(j);
  16.   if i<=j then begin
  17.                 k:=a[i];
  18.                 a[i]:=a[j];
  19.                 a[j]:=k;
  20.                 inc(i);
  21.                 dec(j);
  22.                end;
  23.  until i>j;
  24.  if I<r then qs(i, r);
  25.  If L<J Then Qs(L, J);
  26. end;
  27. procedure loaddata;
  28. var f: text;
  29.     i, k, j: integer;
  30. begin
  31.  n0:=0;j:=0;
  32.  assign(f, inp); reset(f);
  33.  readln(f,n);
  34.  for i:=1 to n do
  35.   begin
  36.    read(f,k);
  37.    if k=0 then inc(n0) else begin
  38.                              inc(j);
  39.                              a[j]:=k;
  40.                             end;
  41.   end;
  42.  n:=j;
  43.  close(f);
  44. end;
  45. procedure procdata;
  46. var i,j: integer;
  47. begin
  48.  Qs(1, n); max:=0;
  49.  for i:=1 to n do
  50.   for j:=1 to n do
  51.    begin
  52.     if i=j then fx[i,j]:=0 else fx[i,j]:= fx[i,j-1]+a[j]-a[j-1]-1;
  53.     if fx[i,j]>n0 then break;
  54.     if (a[j]-a[i]+1-fx[i,j]+n0)>max then begin
  55.      max:=(a[j]-a[i]+1-fx[i,j]+n0); s:=i; f:=j;
  56.     end;
  57.    end;
  58. end;
  59. begin
  60.  clrscr;
  61.  loaddata;
  62.  procdata;
  63.  write(max, ' ',a[s],' ',a[f], ' ', fx[s,f]);
  64.  readln;
  65. end.
Nhật kí giải thuật - FVS:

Http://GiaiThuat.WordPress.Com

boy1234
Guru
Guru
Bài viết: 448
Ngày tham gia: T.Hai 13/10/2008 3:12 pm
Đến từ: Dĩ An - Bình Dương
Been thanked: 32 time

Re: FVS học thuật toán qua các bài tập

Gửi bàigửi bởi boy1234 » T.Hai 29/12/2008 2:43 pm

Cái này hay quá lâu lâu nhìn lại Pascal thấy mờ cả mắt. Tks!
Dạo này nghiện honda SS50

Hình đại diện của người dùng
FVS
Thành viên tích cực
Thành viên tích cực
Bài viết: 178
Ngày tham gia: T.Ba 13/05/2008 10:38 am

Xâu palindrom con

Gửi bàigửi bởi FVS » T.Hai 29/12/2008 2:53 pm

Ờ, lấy pascal làm mình họa cho nhanh mà :D
Đề bài: Tìm xâu plalidrom(đối xứng) con của xâu S cho trước.
Ví dụ: S=lmevxeyzl --> Kết qủa: level
Code:
Lưu ý: code này chạy trên FP
bài này làm trên SPOJ, hôm nay lên down về, paste qua cái list của nó sang đây--> lỗi ngắt dòng tùm lum. Mọi ng thông cảm :((

Mã: Chọn hết

  1. var s,s2: ansistring;
  2. Fx: array[1..2000,1..2000] of integer;    
  3. max,dmax,cmax,i,j,k,d,n:integer;
  4. begin
  5. readln(s);
  6. fillchar(fx[1,1], sizeof(fx),0);
  7. max:=0;n:=length(s);
  8. for k:=1 to n do  for i:=1 to n-k+1 do   begin    j:=i+k-1;
  9. while s[i]<>s[j] do dec(j);    
  10. if i=j then fx[i,j]:=1 else    
  11. for d:=i+1 to j-1 do    
  12.  if (fx[d,j-1]+2)>fx[i,j] then fx[i,j]:=fx[d,j-1]+2;      
  13.  if fx[i,j]>max then begin                            
  14. max:=fx[i,j];                            
  15. dmax:=i;                            
  16. cmax:=j;                          
  17. end;
  18.    end;
  19.  s2:='';
  20.  while max>0 do
  21.   begin
  22.    while
  23.  fx[dmax,cmax]<>max do inc(dmax);
  24.    s2:=s2+s[cmax];
  25. if max>1 then write(s[cmax]);
  26.    if dmax=cmax then dec(max) else dec(max,2);
  27.    dec(cmax);
  28. inc(dmax);
  29.  end;
  30.  for i:=length(s2) downto 1 do write(s2[i]);
  31. end.
Nhật kí giải thuật - FVS:

Http://GiaiThuat.WordPress.Com

Hình đại diện của người dùng
FVS
Thành viên tích cực
Thành viên tích cực
Bài viết: 178
Ngày tham gia: T.Ba 13/05/2008 10:38 am

Khám phá hang động:

Gửi bàigửi bởi FVS » CN 04/01/2009 7:55 am

Tuy bận nhưng mỗi tuần sẽ post ít nhất một bài
Đề bài: Với một hang động chưa biết đường đi, nhiệm vụ của các nhà thám hiểm là vẽ sơ đồ đường đi cho hang động đó. Để làm được điều đó, họ nhờ sự trợ giúp của MTĐT:
Sau mỗi đơn vị khoảng cách máy tính sẽ ghi lại hướng đi của đoàn thám hiểm ( đơn vị khoảng cách được trọn sao cho trong một đơn khoảng cách hướng đi không thay đổi) là một trong các kí tự: D,T,N,B (tương ứng: Đông ,Tây, Nam, Bắc). Công việc đầu tiên mà máy tính cần xử lý khi các nhà thám hiểm đã ở cuối đường hầm (không thể đi tiếp theo một trong các hướng trên) là tìm đường đi ngắn nhất để đưa họ trở về cửa hang theo chuỗi dữ liệu đã có.
Dữ liệu vào: từ bàn phím chuỗi kí tự đã ghi nhận của máy tính (gồm các kí tự D,T,N,B viết hoa)
Dữ liệu ra: màn hình, đường đi cần tìm
Ví dụ
Nhập: DTNB ----------------> Xuất: TD
Nhập: DDTTB ----------------> XuấtTDN
[Code:]

Mã: Chọn hết

  1. {Coded by FVS}
  2. {day ki tu nhap vaof phai laf chu hoa. vi du: DTNB
  3. khong duoc nhap: dtnb}
  4. uses crt;
  5. var s,r:string;
  6.     i,j,d:integer;
  7.     f:array[1..255] of record x,y:byte; end;
  8. begin
  9.  clrscr;readln(s);
  10.  i:=0;j:=0;
  11.  for d:=1 to length(s) do
  12.   case upcase(s[d]) of
  13.    'D':begin inc(i); f[d].x:=i;f[d].y:=j; end;
  14.    'T':begin dec(i); f[d].x:=i;f[d].y:=j; end;
  15.    'N':begin inc(j); f[d].x:=i;f[d].y:=j; end;
  16.    'B':begin dec(j); f[d].x:=i;f[d].y:=j; end;
  17.   end;
  18.  d:=length(s);r:='';
  19.  while d>=1 do
  20.   begin
  21.    for i:=1 to d do
  22.     if (f[i].y=f[d].y)and(f[i].x=f[d].x) then begin
  23.                                                r:=r+s[i];
  24.                                                break
  25.                                               end;
  26.    d:=i-1;
  27.   end;
  28.  for d:=length(r) downto 1 do
  29.   case r[d] of
  30.    'D':write('T');
  31.    'T':write('D');
  32.    'N':write('B');
  33.    'B':write('N');
  34.   end;
  35.  readln;
  36. end.
Nhật kí giải thuật - FVS:

Http://GiaiThuat.WordPress.Com

Hình đại diện của người dùng
VANQUYEN2112
Thành viên chính thức
Thành viên chính thức
Bài viết: 17
Ngày tham gia: T.Tư 16/04/2008 4:59 pm
Đến từ: Đăk Lăk
Has thanked: 4 time
Been thanked: 2 time
Liên hệ:

Re: FVS học thuật toán qua các bài tập

Gửi bàigửi bởi VANQUYEN2112 » T.Bảy 25/04/2009 8:34 pm

Cảm ơn FSV về các thuật toán nhiều nhé !
Hãy tự tạo cho mình một niềm tin và đừng để người khác lấy mất niềm tin của mình.

vandinh89
Bài viết: 1
Ngày tham gia: CN 23/05/2010 12:54 am

Re: FVS học thuật toán qua các bài tập

Gửi bàigửi bởi vandinh89 » CN 23/05/2010 11:17 am

Bác chỉ cho em bài này với.em đang cần tìm giải thuật sinh số nguyên lớn cỡ 1024 bit trong VB6 để thực hiện mã hóa file với RSA nhưng chưa bít gì.Bác giúp em với nhé.Thanks bác!


Quay về “Cấu trúc dữ liệu và giải thuật”

Đang trực tuyến

Đang xem chuyên mục này: Không có thành viên nào trực tuyến.1 khách