K54A3 - Students of A3
December 2016
MonTueWedThuFriSatSun
   1234
567891011
12131415161718
19202122232425
262728293031 

Calendar Calendar


Lap trinh C_Cac buoc lam 1 bai toan_1

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down

Lap trinh C_Cac buoc lam 1 bai toan_1

Bài gửi by nguyendnhat on Wed 07 Apr 2010, 11:42 pm

cách làm 1 bài toán khi đã có đề có những bước cơ bản sau đây
Bước 1 Chúng ta tất nhiên là phải đọc kĩ đề xem nó nói cái gì và cái quan trọng nhất chúng ta phải giải quyết là gì chúng ta không nên nóng vội mà làm luôn làm như thế sẽ không ra kết quả nếu bài này mà làm được còn những bài sau bài khó hơn thì sao mình cứa cắm đầu vào viết đề làm gì chúng ta phải hiểu đề và tất nhiên chúng ta phải có thuật toán ở bài ấy nữa (Bước này chỉ nghĩ sơ sơ thôi không phải nghĩ vội) khi chúng ta đã hiểu đề thì bước tiếp theo của chúng ta là
Bước 2: (Không 1 bài toán nào mà tớ không làm bước này cả không tội gì mà các bạn phải nhớ các thuật toán cả nếu không có bước này tớ sẽ không làm được bài nào cả) debug là chúng ta cho 1 Input nào đấy rồi làm theo thuật toán mình nghĩ ra ở trên kia (Bước 1 ấy) làm theo thứ tự các bước (Làm như trong bài kiểm tra lần trước ấy chúng ta có bài 1 ấy chúng ta phải ghi ra từng bước làm) ghi ra rồi thì xem kết quả như thế nào nếu đúng thì chúng ta xem như thuật toán là Ok chuyển sang bước 3 nếu không đúng thì chúng ta phải xem sai chổ nào và cần sữa như thế nào đề cho nó đúng nếu chúng ta thấy chúng ta sai hoàn toàn không sữa được thì chúng ta cần phải ghi ra thuật toán khác của mình khi này phải suy nghĩ cẩn thận và dựa vào cái debug của mình để 1 phần nghĩ ra thuật toán nếu không làm ok bước này thì đừng viết tiếp nữa kiểu gì cũng sai
Bước 3: Viết mã giả 1 công việc quan trọng không kém việc viết chương trình viết mã giả chúng ta dọc các bước như thế nào thì chúng ta sẽ phải viết như thế ấy
Bươc 4: tối ưu bài toán (Cái này mình sẽ nói vào lần sau vậy)
Bước 5: Bỏ qua bước 4 chúng ta viết thẳng vào chương trình nhờ cái mã giả của mình
Bươc 6: Tối ưu bài toán
Bước 7: Vỗ tay khen mình giỏi quá
Mình sẽ ví dụ luôn nha

Đề bài cho bài tìm giá trị lớn nhất của dãy số (Nhập từ bàn phím)
Bước 1 hiểu đề
chúng ta phải hiểu giá trị lớn nhất là như thế nào
nhìn sơ qua thì tìm giá trị lớn nhất là tìm ra số nào lớn nhất trong dãy đó là ok
Bước 2 Debug
cho 1 Input bất kì
3 4 5 7 6 7 5 8
Dãy này gồn có 8 số đươc đánh từ 0 đến 7
cách tìm
đặt a[0]=3 là max
so sánh max với 4 thấy 4 lớn hơn thì 4 là max
so sánh 5 với max thấy 5>4 đặt 5 là max
so sánh tương tự
ta thấy 8 là max ok debug đúng => thuật toán 0k (Nên nhớ rằng 1 bài toán có nhiều trương hợp khác nhau nên nói thuật toán đúng là không chính xác lắm nhưng bài này dễ chúng ta có thê viêt là đúng luôn)
Bước 3
viết mã giả
chúng ta đã được làm quen mã giả rồi chúng ta không cần phải nhớ công thức là mà giả là như thế nào chúng ta chỉ cần viết sao cho mình hiểu là 0k rồi

đầu tiên là phải nhâp mảng (cái này sơ đẳng mà cô cho rồi các bạn tự viết nhé :D)
khi đã có mảng rồi thì chúng ta tìm max
đầu tiên là max=vị trí đầu tiên trong mảng
cho i=1 (vì chúng ta so sánh a[0]với a[1]mà)
khi mà i<n thì chúng ta làm
nếu mà a[i]>max
thì chúng ta thay max=a[i]
tăng i lên 1 đơn vị
quay lại vòng lặp


chương trình trên C thì các bạn tự làm nha có gì cư hỏi nếu không làm được chúng ta mới làm quen với C nên bây giờ mà bắt mà viết được code luôn thì là một điều rất khó các bạn phải cố gắng thực hành không có cánh nào khác ngoài việc luyện tập kĩ năng đâu chỉ còn mấy tháng nữa là thi cuối kì rồi chúng ta phải chăm code ngay từ bấy giờ nếu không thì chúng ta phải học lại cho chắc thôi A3 cố lên
Bài tiếp theo của mình là phân tách bài toán nếu các bạn làm 3 bước đầu Ok rồi thì phân tách bài toán là 1 điều khá quan trọng khi chúng ta đã học được cách phân tách rồi thì chúng ta viết code đơn giản hơn vì nó phân ra thành những bài toán con mà mình có thể giải được
Và 1 điều cuối cùng là Môn C rất quan trọng các bạn phải chú ý mà học không thì hối hận sau này đó
Bibi

nguyendnhat

Tổng số bài gửi : 70
thanks : 0
Join date : 31/03/2010
Age : 25
Đến từ : Nghệ An

Xem lý lịch thành viên

Về Đầu Trang Go down

Re: Lap trinh C_Cac buoc lam 1 bai toan_1

Bài gửi by nguyendnhat on Thu 02 Sep 2010, 2:33 pm

Chào các bạn vì mình thời gian không cho phép mà kinh nghiệm và kĩ năng kiến thức mình chưa nhiều nên mình viết chắc các bạn khó hiêu (Không hiểu thì đúng hơn) nên mình mạo muội đưa bài viết kĩ năng lập trình của thầy Minh (Vũ Đức Minh) và Anh Nghị(Đông Nghị) Vào đây để các bạn hiểu và code rõ ràng hơn

Đây là bài viết của thầy có gì không hiểu thì sau này sẽ hiểu các bạn chú ý vào from của 1 bài làm
và cách bố trí từng câu lệnh


Trang này sẽ chú trọng vào hướng dẫn các em gõ code ngắn gọn, chính xác, ít lỗi:

Bố cục của trang như sau:
+) Ban đầu là hướng dẫn trình bày code sao cho dễ đọc, sáng sủa.
+) Sau đó là một vài hướng dẫn về ngôn ngữ C, giúp code gọn hơn, chính xác hơn.
+) Cuối cùng là một bài hướng dẫn chi tiết từ phân tích, tới gõ code, nâng cấp và cuối cùng là chỉnh sửa để nộp bài Online.

Cũng giống nhiều môn học khác, trong lời giải các bài toán tin cũng có form trình bày riêng. Trong mục này mình sẽ trình bày các thành phần cơ bản giúp cho các bạn viết được "chuyên nghiệp" hơn. Điều này sẽ giúp các bạn "tìm và diệt" những lỗi không đáng có. Hi vọng bài viết sẽ giúp ích nhiều cho các bạn.

Trong phần này tôi dùng ngôn ngữ C để trình bày. Hi vọng trong bài viết tới sẽ là C++ ^___^

Phần I: khai báo tiền xử lý:

Các thư viện thường dùng là:
+) stdio.h
+) conio.h (dùng cho lệnh getch() )
+) process.h (dùng cho lệnh exit() )
+) stdlib.h
+) math.h
+) string.h
Vì vậy khi vào một chương trình bạn nên include những file này.

Phần II: khai báo hằng:

Trong các bài toán tin, thường cho giới hạn dữ liệu đầu vào. Ví dụ: cho dãy n phần tử với n <= 100, ma trận n x m với n <= 1000 và m <= 100, tìm số các số nguyên tố nhỏ hơn n với n <= 10^9,.... Khi đó, nhằm tránh trường hợp bạn khai báo khắp chương trình sẽ rất mất thời gian hoặc dễ sai nếu bạn khai báo mảng như sau:

int a[100];
hay:
int a[1000][100];

Tại sao lại không nên làm như vậy: Lý do là trong khi gỡ lỗi chương trình bạn thường không khai báo kích thước tối đa của mảng (ví dụ 1000) mà chỉ khai báo 10 hoặc 20,... Khi đó, nếu giải xong bạn phải thay đổi lại toàn bộ những khai báo kích thước mảng (thật kinh hoàng *__*). Một lý do khác là bạn muốn thử thời gian chạy của thuật toán nên sẽ nới rộng kích thước mảng.

Một cách làm hay là bạn có thể khai báo hằng số. Ví dụ:

#define Nmax 100
hay
#define Mmax 1000

Khi đó, ta có thể khai báo mảng như sau:

int a[Nmax];

Nếu bạn muốn thay đổi kích thước của mảng thì chỉ cần thay đổi trong phần Nmax là đủ. Trình biên dịch sẽ làm tất cả phần còn lại thay bạn.

Kết thúc hai phần ta có form sau:

#include <stdio.h>
#include <conio.h>
#include <process.h>
#include <string.h> //Nếu phải dùng các hàm liên quan đến xâu
#include <math.h> //Nếu phải dùng các hàm toán học
//Nên có khoảng trắng cho dễ nhìn
#define Nmax 100
#define Mmax 1000

#define fi "file_input.inp" //Phần này nói sau. Liên quan đến làm việc với file

Phần III: Làm việc với file

Lý do tại sao lại làm việc với file cũng là dễ hiểu, bởi trong một bài toán tin bạn gần như không thể là được đúng ngay mà thường phải test một vài ví dụ. Ví dụ bài của bạn làm trên một dãy 10 phần tử chẳng hạn thì mỗi lần test lại chương trình, bạn lại phải nhập 10 phần tử, thật nhàm chán (và kinh hoàng khi là ma trận 5x5 chẳng hạn *__*).

Một cách hay là bạn tạo trước một file dữ liệu rồi đọc dữ liệu từ đó ra. Để xem cách khai báo tên file bạn có thể tham khảo bài trước của mình. Ở đây mình tập trung vào viết các hàm xử lý.

Form thường như sau:

FILE *f1, *f2;

int openf(void ){
f1 = fopen(fin,"rt");
f2 = fopen(fout,"wt");
if (f1 == NULL || f2 == NULL) {
printf("Loi khong mo duoc file");
exit(1);
}
return 0;
}

int closef(void ){
fclose(f1);
fclose(f2);
return 0;
}

int main(void) {
openf();

//Nơi bạn sẽ chèn những hàm xử lý (viết sau).

closef();
}

Phần IV: Modul hóa chương trình thành các hàm riêng biệt

Việc modul hóa là việc bạn tách chương trình thành các đơn vị nhỏ, được gọi là các hàm (các bạn nếu ai chưa thạo về hàm thì có thể tham khảo thêm trong cách sách dạy lập trình - và đừng có lo lắng quá ^__^ ). Việc tách này nhằm giúp các bạn gỡ lỗi chương trình và cũng góp phần tăng tốc gõ code nữa.

Nguyên tắc tách modul là: bạn phải phân tích thuật toán thành các thao tác nhỏ, từ đó sẽ có từng hàm (hoặc nhiều hàm) phụ trách từng thao tác đó. Tất nhiên hợp các thao tác nhỏ đó sẽ giải quyết xong bài toán đặt ra.

Nguyên tắc đặt tên hàm: Phải gợi nhớ và phù hợp với thao tác nó thực hiện. Tất nhiên cũng không được trùng với tên hàm chuẩn đã có. Việc đặt tên dài hay ngắn là phụ thuộc vào tốc độ gõ của bạn, không liên quan đến thời gian chạy của thuật toán cũng như bộ nhớ.

Sau đây là một vài lời khuyên của tôi khi đặt tên hàm:
1. Không nên viết hoa tên hàm. Vì trong C/C++ phần biệt hoa - thường và việc bạn quản lý nhiều hàm sẽ dẫn tới những nhầm lẫn nếu viết hoa tên hàm.

2. Không nên đặt tên hai hàm na ná như nhau, sẽ rất dễ nhầm lẫn khi gọi hàm.

3. Đặt tên gợi nhớ, tốt nhất là đúng với chức năng của hàm. Ví dụ:
sort_arr, find_element,...

4. Không nên đặt tham số là mảng. Liên quan đến tốc độ chạy của chương trình. Nếu buộc phải truyền tham số là mảng thì tốt nhất dùng con trỏ để thay thế (xem ví dụ dưới).

5. Không nên đặt quá nhiều tham số. Liên quan đến bộ nhớ và tốc độ chạy của chương trình (tất nhiên bộ nhớ của hầu hết các trình biên dịch bây giờ là... vô biên nhưng luôn có ý thức tiết kiệm vẫn là một phong cách lập trình tốt). Cũng thể hiện sự "chuyên nghiệp" nữa ^__^ Một good suggest là 1 hoặc 2 tham số là đủ, tối đa là 4 - 5 tham số.

Ví dụ:

int input(void ){
...
return 0;
}

int find_element(int *arr, int value){//Dùng con trỏ thay cho dùng mảng.
...
return 0;
}

/* Có thể dùng từ khóa: const nếu không muốn thay đổi giá trị phần tử:
int find_element(const int *arr, int value){
...
return 0;
}
*/

int sort_arr(int left, int right) {
...
return 0;
}

int writeresult(void ){
...
return 0;
}

int main(void ) {
openf();
input();
sort_arr(1, n);
find_element(arr, x);//Tìm sự xuất hiện phần tử có giá trị x trong mảng arr đã sắp xếp.
write_result();
closef();
getch();
return 0;
}

Lưu ý: bạn nên sắp xếp làm sao cho trong hàm main chỉ gồm các lời gọi hàm. Không viết code trong hàm main nếu ko cần thiết.

Hết phần IV.

Trên đây là bài viết sơ lược về form trình bày một bài toán tin. Tất nhiên một số bạn sẽ hỏi: form này dùng ở đâu? Lợi ích và sự khác biệt khi sử dụng. Câu trả lời như sau:
Dùng ở: tại một số kì thi tin học như thi hết kì, thi OLP, hoặc khi bạn test chương trình tại nhà thì bạn nên sử dụng form này.
Lợi ích và khác biệt: nhiều (code sáng sủa, dễ sửa và xem lại code, có thể sử dụng lại một vài module,....).

K44:
Cac em nam 1 can hoc xu ly vao ra voi file ngay tu dau.
Chi can biet cach doc va ghi du lieu doi voi file text thoi. No cung
tuong tu nhu lenh scanf, va printf.
Mot site tham khao ve cac lenh co ban + vi du ve C va C++ rat co ich :
[You must be registered and logged in to see this link.]
[You must be registered and logged in to see this link.] - phan xu
ly file : cac lenh nam o cot ben trai. Cac em chi viec copy code vi du
vao DevC va chay. Doc duoc tieng Anh thi rat tot, neu khong co them 1
quyen sach TV de tham khao.
------------------------------------------


1. typedef dùng để định nghĩa kiểu, khi khai báo các mảng hoặc cấu trúc dùng nó rất tiện

[You must be registered and logged in to see this link.]

ví dụ

#define MAX 10001

typedef int mang1chieu[MAX];
typedef int mang2chieu[MAX][MAX];

mang1chieu a;
mang2chieu b,c;

2. sizeof trả về kích thước tính theo byte của mảng, biến,cấu trúc

Ví dụ

sizeof(int) trả về 2 vì int là 2 byte

int a[MAX];
sizeof(a) trả về MAX*sizeof(int) = 20002

nhưng chú ý :

void test(int a[])
{
...
sizeof(a) -> không trả về 20002 nữa mà chỉ trả về 2, là kích thước con trỏ kiểu int.
}

Nghĩa là lệnh sizeof(x) trả về đúng kích thước mong muốn khi và chỉ khi x không bị che.

3. memset dùng để gán mảng, ví dụ gán toàn bộ mảng bằng 0. Nằm trong string.h

void * memset ( void * ptr, int value, size_t num );
<cstring>
Gán num bytes đầu tiên của khối trỏ bới ptr một giá trị cụ thể là value, được hiểu một số unsigned char.
Tham số

ptr
Trỏ tới khối được gán
value
Giá trị để gán, tham số truyền vào là int nhưng sẽ chuyển thành unsigned char , cho nên chỉ khởi tạo giá trị từ 0..255
num
Số byte dùng để gán.
Ví dụ :

/* memset example */
#include <stdio.h>
#include <string.h>

int main ()
{
char str[] = "almost every programmer should know memset!";
memset (str,'-',6);
puts (str);
return 0;
}
Output:
------ every programmer should know memset!
Rất hay kết hợp sử dụng memset + sizeof để khởi tạo mảng:
Khởi tạo mảng toàn 0
int a[MAX];
int main()
{
memset(a,0,sizeof(a)); //ok
}
nhưng chú ý khi truyền vào chương trình con thì phải lấy kích thước tường minh

int test(int a[])
{
memset(a,0,sizeof(int)*MAX);
}


hoặc một cách khác:

Chú ý ví dụ sau:
[You must be registered and logged in to see this link.]

Để khởi tạo cả mảng toàn 0, chỉ cần khởi tạo phần tử đầu tiên là 0.
float p1[1000]; // No intitialization.
float p2[1000] = {0.0}; // All 1000 values initialized to zero.

Ứng dụng:

1. Sizeof --> làm chương trình của bạn "mềm dẻo" hơn theo nghĩa: chạy tốt trên nhiều hệ thống.
Điều này đặc biệt quan trọng khi bạn làm việc trên một môi trường nhưng lại chạy trên một môi trường khác, ví dụ: nộp bài chấm Online chẳng hạn. Ví dụ:
Kích thước biến kiểu int trong Linux/window ---> 4bytes
Kích thước biến kiểu int trong Dos ---> 2bytes
Do đó, trong chương trình nếu các em khai báo cấp phát động (hoặc bất cứ cái gì liên quan đến kích thước biến - nén theo bit chẳng hạn) thì thay vì viết chính xác 4 hay 2 bytes thì nên viết là sizeof(int). Như vậy có thể chạy trên cả hai hệ thống.
2. Memset ---> khởi tạo mảng/ xâu.
Lệnh này gọn và giúp ta gỡ lỗi chương trình nhanh chóng. Tuy nhiên chạy chậm. Khi nộp bài Online các em cố gắng hạn chế dùng lệnh này hoặc bất cứ vòng lặp khởi tạo nào (chỉ khuyến khích dùng tại nhà thôi).
Lý do:
+) Mặc định các biến đều có giá trị 0 (trừ biến cục bộ). ????
+) Không nên làm chậm chương trình bằng các vòng lặp, dù có thể rất ít.

---------------------
Cach doc/ghi du lieu doi voi file text :
Doc du lieu tu 1 file text:

freopen("test.inp","rt",stdin); //doc du lieu o trong file test.inp thay vi doc tu ban phim
scanf("%d",&n); //doc du lieu nhu binh thuong, khong can phai fopen, fscanf ... gi ca.
...

Ghi du lieu ra file text:
freopen("test.out","wt",stdout); //ghi du lieu ra file test.out thay cho viec ghi ra man hinh
scanf("%d",&n); //ghi du lieu nhu binh thuong, khong can phai fprintf gi ca
..

Khi nao muon doc du lieu tu ban phim hay ghi ra man hinh, comment cai dong chua freopen la xong
------------------------------------

Sắp xếp là một việc hay làm (sắp xếp tăng, giảm) và quicksort là một thuật toán sắp xếp quan trọng vì nó nhanh với dữ liệu lớn (ví dụ >100 phần tử). Độ phức tập là O(nlogn), còn sắp xếp bình thường độ phức tạp O(n^2); với n>=1000 thì toi rồi.

Về chi tiết có thể đọc sách thuật toán, hoặc tham khảo tại:


[You must be registered and logged in to see this link.]
[You must be registered and logged in to see this link.]
[You must be registered and logged in to see this link.] --> Code

Ở đây , ta sử dụng hàm quicksort có sẵn trong thư viện stdlib.h, vì đi thi nhớ code nó hơi khó, dễ nhầm ...

[You must be registered and logged in to see this link.]
void qsort ( void * base, size_t num, size_t size, int ( * comparator ) ( const void *, const void * ) );
base: con trỏ tới mảng cần sắp xếp.
num: số phần tử
size : kích thước mỗi phần tử, dùng sizeof để tiện
comparator : con trỏ hàm để so sánh -> rất thuận tiện, có thể sắp xếp tăng dần, giảm dần , theo chỉ số ...
Và đây là ví dụ :

/* qsort example */
#include <stdio.h>
#include <stdlib.h>

int values[] = { 40, 10, 100, 90, 20, 25 };

int compare (const void * a, const void * b)
//cai nay dung de so sanh phan tu mang, neu xep tang thi nhan voi -1 hoac doi
// *(int*)b- *(int*)a
{
return ( *(int*)a - *(int*)b );
}

int main ()
{
int n;
qsort (values, 6, sizeof(int), compare); //1 dong duy nhat + viet cai compare mat 2 dòng :D
for (n=0; n<6; n++)
printf ("%d ",values[n]);
return 0;
}
Trong bài hướng dẫn này tôi sẽ đưa ra từng khâu để giải một bài toán tin, bao gồm:
+) Phân tích đề bài
+) Soạn lời giải trên giấy
+) Trình bày code
+) Debug lỗi, chạy trên máy
+) Sửa và nộp bài Online.

Để thuận tiện cho việc trình bày tôi sẽ đưa ra một bài toán làm ví dụ. Vậy nhiệm vụ của các bạn là gì? Đọc thật kĩ đầu bài, từng bước tự mình phân tích đề bài đó, đọc phân tích của tôi xem có thêm hay thiếu gì so với phân tích của mình không, tự mình gõ code, so sánh với những kĩ thuật tôi dùng,.... Giờ chúng ta bắt đầu.

Đề bài:
Cho một số nguyên dương n (n <= 1000) và một dãy số nguyên a có n phần tử (-10^9 <= a[i] <= 10^9). Người ta gọi khoảng cách giữa hai phần tử trong dãy là trị tuyệt đối của hiệu hai phần tử đó. Yêu cầu hãy tìm số hiệu hai phần tử trong dãy ban đầu có khoảng cách nhỏ nhất.
Input:
+) Dòng đầu là số n.
+) Dòng sau là n số nguyên.
Output:
In ra 2 số tự nhiên là số hiệu hai phần tử có khoảng cách nhỏ nhất.
Ví dụ 1:
10
-4 -3 -2 -1 0 1 2 3 4 5
---> In ra: 1 2
Ví dụ 2:
10
5 -2 0 -3 -1 1 3 -4 4 2
---> In ra: 1 9

1. Phân tích đề bài:
Điều đầu tiên ta để ý là n <= 1000, do đó, trong code ta sẽ khai báo:

#define Nmax 1000

là kích thước tối đa của dữ liệu đầu vào.
Tiếp theo, ta để ý -10^9 <= a[i] <= 10^9, do đó, tổng của hai phần tử bất kì sẽ quá lắm là 2*10^9. Và như vậy miền giá trị không vượt quá 2 tỉ. Ta có thể lưu trong biến kiểu longint là đủ.
Ta lưu ý rằng khoảng cách giữa hai phân tử là trị tuyệt đối của hiệu hai phần tử, như vậy để tìm được min của khoảng cách, ta chỉ cần duyệt từng cặp 2 phần tử là đủ. Để giới hạn thêm ta có nhận xét: với hai số a[i], a[j], ta chỉ xét |a[i] - a[j]| với i < j <= n.
Cuối cùng, đầu bài yêu cầu tìm số hiệu hai phần tử trong dãy, tức nếu min đạt tại a[i] và a[j] thì ta phải in ra i, j. Điều này tuy đơn giản nhưng đôi lúc sẽ gây một số hiểu nhầm nho nhỏ.

2. Miêu tả thuật toán trên giấy:
Trong phần phân tích trên ta đã hình dung ra một cách xử lý đơn giản, gần giống hàm sắp xếp mà các em hay sử dụng:
(Soạn trên nháp):
+) Xét phần tử thứ i, i có giá trị từ 1 --> n.
+) Tại mỗi phần tử i, ta xét phần tử j, j có giá trị từ i + 1 ---> n. Khi đó rõ ràng j > i.
Xét m = abs( a[i] - a[j]):
-) Nếu m < min (min là biến lưu giá trị min hiện tại tìm được) thì cập nhật lại min và i, j.
-) Ngược lại, ta không làm gì cả.

Đến bước này các em nên tự chứng minh hoặc "cảm nhận" thuật toán trên là đúng đắn.

Ước lượng độ phức tạp:
Với mỗi i xét từ 1 ---> n, ta có n trường hợp. Tương ứng với mỗi trường hợp của i, ta có (n - i) trường hợp của j. Ta có thể hình dung:
i = 1. j = 2 ---> n. Có (n - 1) khả năng chọn j.
i = 2. j = 3 ---> n. Có (n - 2) khả năng chọn j.
....
i = k. j = k + 1 ---> n. Có (n - k) khả năng chọn j.
Tổng quát, có: (n - 1) + (n - 2) + ... + (n - k) +...+ (n - (n -1)) = 1 + 2 + ... + k + ... (n - 1) = (n - 1)*n/2 (CT Gauss)
Nếu viết gọn lại, ta có tổng trên là: O(n^2) (là một hàm bình phương của n).

3. Trình bày code:
Từ miêu tả trên, ta có thể viết code tương ứng như sau:

min = abs(a[1] - a[2]);
i_min = 1;
j_min = 2;
for (i = 1;i < n; i++)
for (j = i + 1;j <= n; j++)
if (abs(a[i] - a[j]) < min) {
min = abs(a[i] - a[j]);
i_min = i;
j_min = j;
}

---> in ra i_min và j_min.
(còn tiếp)
--------------------------
Ước lượng độ phức tạp giải thuật dựa vào input: Nói chung với time-limit là 1s/1 test CPU trên vn.spoj.pl (Pen 3) xử lý khoảng 1MB-5MB phép toán (tùy loại, *,/ lâu, +,- nhanh ...)

Dưới đây ước lượng độ phức tạp tối đa để có thể AC, có thể có thuật toán tốt hơn nhưng ko thể tồi hơn mà AC được.

- N ~ 100,200: O(N^3).

- N ~ 1000, 2000: O(N^2).

- N ~ 10000,2000, ... 100000: O(NlogN) hoặc O(N).

- N ~ 10^6, 10^7 : O(N) hoac O(NloglogN) : vi dụ thuật toán sàng số nguyên tố.

- N ~ 10^9 : O(sqrt(N)).
--------------------------


Đừng ai nói với Thầy nhé hi

nguyendnhat

Tổng số bài gửi : 70
thanks : 0
Join date : 31/03/2010
Age : 25
Đến từ : Nghệ An

Xem lý lịch thành viên

Về Đầu Trang Go down

Re: Lap trinh C_Cac buoc lam 1 bai toan_1

Bài gửi by buithiphuong on Wed 08 Sep 2010, 6:25 pm

Sao mà cậu có thể chịu khó như thế vậy?

buithiphuong

Tổng số bài gửi : 30
thanks : 0
Join date : 19/04/2010

Xem lý lịch thành viên

Về Đầu Trang Go down

Re: Lap trinh C_Cac buoc lam 1 bai toan_1

Bài gửi by nguyendnhat on Wed 08 Sep 2010, 6:35 pm

Không hiểu SAO VẬY
Có Ý KIẾN gì à???

nguyendnhat

Tổng số bài gửi : 70
thanks : 0
Join date : 31/03/2010
Age : 25
Đến từ : Nghệ An

Xem lý lịch thành viên

Về Đầu Trang Go down

Re: Lap trinh C_Cac buoc lam 1 bai toan_1

Bài gửi by toankid1412 on Wed 08 Sep 2010, 7:47 pm

Chắc các bạn lây bệnh ngại đọc của Nhật rồi!! Tóm tắt đi Nhật!!

_________________________


Đố Ai Định Nghĩa Được Chữ Cười
Cười Là Vui Sướng Lệ Không Rơi
Ai Cười Người Ấy Thường Đau Khổ
Cười Để Quên Đi Hết CHuyện Đời!


toankid1412
Super Moderator
Super Moderator

Tổng số bài gửi : 329
thanks : 4
Join date : 27/03/2010
Age : 25
Đến từ : vô ja kư

Xem lý lịch thành viên

Về Đầu Trang Go down

Re: Lap trinh C_Cac buoc lam 1 bai toan_1

Bài gửi by buithiphuong on Thu 09 Sep 2010, 1:43 am

Tớ mắc bệnh lười đọc bẩm sinh nên bị " mẫn cảm đối với các thể loại nhiều từ ngữ ".Mặc dù bài của Nhật rất hữu ích nhưng tớ có Ý KIẾN như đồng chí Kid là Tóm Tắt thui

buithiphuong

Tổng số bài gửi : 30
thanks : 0
Join date : 19/04/2010

Xem lý lịch thành viên

Về Đầu Trang Go down

Re: Lap trinh C_Cac buoc lam 1 bai toan_1

Bài gửi by Sponsored content Today at 6:29 pm


Sponsored content


Về Đầu Trang Go down

Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang

- Similar topics

 
Permissions in this forum:
Bạn không có quyền trả lời bài viết