Học tin học cơ bản

Thuật toán FF (First Fit): đây là thuật toán tô mầu các đỉnh theo thứ tự đơn giản nhất. Tư tưởng của thuật toán này là phương pháp tham: lần lượt tô mầu cho các đỉnh theo thứ tự của đỉnh, với mỗi đỉnh x, ta tô cho x mầu có số thứ tự nhỏ nhất còn hợp lý (chưa tô cho đỉnh nào kề x). Chương trình: #include <stdio.h> #include <conio.h> #include <stdlib.h> int *doc_tep(int *a,int *n); void in_matran(int *a,int n); int ktra_mau(int *a,int *b,int *c,int n,int x); void ToMau(int *a,int n); int main() { int n,*a; a=doc_tep(a,&n); in_matran(a,n); [...]

Thuật toán SDO (Saturation Degree Ordering) : do Brèlaz đề xuất năm 1979 [12]. Đây cũng là một thuật toán tô mầu tuần tự các đỉnh. SDO cải tiến FF ở chỗ các đỉnh được tô mầu không theo số thứ tự của đỉnh, mà theo thứ tự bậc SD từ lớn tới bé. Trong đó bậc SD của đỉnh x được tính bằng số mầu khác nhau đã dùng để tô cho các đỉnh kề với x. Chương trình: #include <stdio.h> #include <conio.h> #include <stdlib.h> int *doc_tep(int *a,int *n); void in_matran(int *a,int n); int *bac_dinh(int *a,int n); int max(int [...]

Thuật toán LDO (Largest Degree Ordering): do De Werra đề xuất năm 1990 [13]. Tương tự như SDO, LDO là một cải tiến của FF, trong đó các đỉnh được tô mầu theo thứ tự bậc của đỉnh từ lớn tới bé. Chương trình: #include <stdio.h> #include <conio.h> #include <stdlib.h> int *doc_tep(int *a,int *n); void in_matran(int *a,int n); void in(int *b,int n); int dem(int *b,int n); int max(int *b,int n); void up_date(int *a,int *SD,int *ToMau,int n); int ktra_mau(int *a,int *b,int *c,int n,int d,int x); void ToMau_SDO(int *a,int n); int main() { int n,*a; a=doc_tep(a,&n); in_matran(a,n); ToMau_SDO(a,n); getch(); return 0; } [...]

Thuật toán của ta dựa trên ý tưởng: nếu n >1 không chia hết cho số nguyên nào trong tất cả các số từ 2 đến thì n là số nguyên tố. Do đó ta sẽ kiểm tra tất cả các số nguyên từ 2 đến có round(sqrt(n)), nếu n không chia hết cho số nào trong đó thì n là số nguyên tố. Nếu thấy biểu thức round(sqrt(n)) khó viết thì ta có thể kiểm tra từ 2 đến n div 2. Hàm kiểm tra nguyên tố nhận vào một số nguyên n và trả lại kết quả là [...]

Ý tưởng của thuật toán Euclide là UCLN của 2 số a,b cũng là UCLN của 2 số b và a mod b, vậy ta sẽ đổi a là b, b là a mod b cho đến khi b bằng 0. Khi đó UCLN là a. Chương trình: Hàm UCLN nhận vào 2 số nguyên a,b và trả lại kết quả là UCLN của 2 số đó. function UCLN(a,b: integer): integer; var r : integer; begin while b<>0 do begin r := a mod b; a := b; b := r; end; UCLN := a; end; Theo laptrinhvn Bạn đang [...]

Để tính tổng các ước số của số n, ta cho i chạy từ 1 đến n div 2, nếu n chia hết cho số nào thì ta cộng số đó vào tổng. (Chú ý cách tính này chưa xét n cũng là ước số của n). Chương trình: function tongus(n : integer): integer; var i,s : integer; begin s := 0; for i := 1 to n div 2 do if n mod i = 0 then s := s + i; tongus := s; end; Theo laptrinhvn Bạn đang muốn nâng cao kỹ năng lập trình của mình [...]