Giáo trình Lập trình căn bản - Lập trình máy tính

Thuật toán là một bảng liệt kê các chỉ dẫn (hay quy tắc) cần thực hiện theo từng bước xác định nhằm giải một bài toán đã cho.

Thuật ngữ “Algorithm” (thuật toán) là xuất phát từ tên nhà toán học Ả Rập Al-KhowarizmA. Ban đầu, từ algorism được dùng để chỉ các quy tắc thực hiện các phép tính số học trên các số thập phân. Sau đó, algorism chuyển thành algorithm vào thế kỷ 19. Với sự quan tâm ngày càng tăng đối với các máy tính, khái niệm thuật toán đã được cho một ý nghĩa chung hơn, bao hàm cả các thủ tục xác định để giải các bài toán, chứ không phải chỉ là thủ tục để thực hiện các phép tính số học.

Có nhiều cách trình bày thuật toán: dùng ngôn ngữ tự nhiên, ngôn ngữ lưu đồ (sơ đồ khối), ngôn ngữ lập trình. Tuy nhiên, một khi dùng ngôn ngữ lập trình thì chỉ những lệnh được phép trong ngôn ngữ đó mới có thể dùng được và điều này thường làm cho sự mô tả các thuật toán trở nên rối rắm và khó hiểu. Hơn nữa, vì nhiều ngôn ngữ lập trình đều được dùng rộng rãi, nên chọn một ngôn ngữ đặc biệt nào đó là điều người ta không muốn. Vì vậy ở đây các thuật toán ngoài việc được trình bày bằng ngôn ngữ tự nhiên cùng với những ký hiệu toán học quen thuộc còn dùng một dạng giả mã để mô tả thuật toán. Giả mã tạo ra bước trung gian giữa sự mô tả một thuật toán bằng ngôn ngữ thông thường và sự thực hiện thuật toán đó trong ngôn ngữ lập trình. Các bước của thuật toán được chỉ rõ bằng cách dùng các lệnh giống như trong các ngôn ngữ lập trình.

Thí dụ 1: Mô tả thuật toán tìm phần tử lớn nhất trong một dãy hữu hạn các số nguyên.

a) Dùng ngôn ngữ tự nhiên để mô tả các bước cần phải thực hiện:

1. Đặt giá trị cực đại tạm thời bằng số nguyên đầu tiên trong dãy. (Cực đại tạm thời sẽ là số nguyên lớn nhất đã được kiểm tra ở một giai đoạn nào đó của thủ tục.)

2. So sánh số nguyên tiếp sau với giá trị cực đại tạm thời, nếu nó lớn hơn giá trị cực đại tạm thời thì đặt cực đại tạm thời bằng số nguyên đó.

3. Lặp lại bước trước nếu còn các số nguyên trong dãy.

4. Dừng khi không còn số nguyên nào nữa trong dãy. Cực đại tạm thời ở điểm này chính là số nguyên lớn nhất của dãy.

b) Dùng đoạn giả mã:

procedure max (a¬1, a2, ., an: integers)

max:= a1

for i:= 2 to n

 if max

{max là phần tử lớn nhất}

Thuật toán này trước hết gán số hạng đầu tiên a1 của dãy cho biến max. Vòng lặp “for” được dùng để kiểm tra lần lượt các số hạng của dãy. Nếu một số hạng lớn hơn giá trị hiện thời của max thì nó được gán làm giá trị mới của max.

 

Giáo trình Lập trình căn bản - Lập trình máy tính trang 1

Trang 1

Giáo trình Lập trình căn bản - Lập trình máy tính trang 2

Trang 2

Giáo trình Lập trình căn bản - Lập trình máy tính trang 3

Trang 3

Giáo trình Lập trình căn bản - Lập trình máy tính trang 4

Trang 4

Giáo trình Lập trình căn bản - Lập trình máy tính trang 5

Trang 5

Giáo trình Lập trình căn bản - Lập trình máy tính trang 6

Trang 6

Giáo trình Lập trình căn bản - Lập trình máy tính trang 7

Trang 7

Giáo trình Lập trình căn bản - Lập trình máy tính trang 8

Trang 8

Giáo trình Lập trình căn bản - Lập trình máy tính trang 9

Trang 9

Giáo trình Lập trình căn bản - Lập trình máy tính trang 10

Trang 10

Tải về để xem bản đầy đủ

doc 116 trang duykhanh 9800
Bạn đang xem 10 trang mẫu của tài liệu "Giáo trình Lập trình căn bản - Lập trình máy tính", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

Tóm tắt nội dung tài liệu: Giáo trình Lập trình căn bản - Lập trình máy tính

Giáo trình Lập trình căn bản - Lập trình máy tính
 vì độ dài của nó là không xác định và vì vậy chúng ta phải dùng đến toán tử chuyển kiểu dữ liệu hay phép gán để chuyển con trỏ không kiểu thành một con trỏ trỏ tới một loại dữ liệu cụ thể. 
Một trong những tiện ích của nó là cho phép truyền tham số cho hàm mà không cần chỉ rõ kiểu 
// integer increaser
#include 
void increase (void* data, int type)
{
 switch (type)
 {
 case sizeof(char) : (*((char*)data))++; break;
 case sizeof(short): (*((short*)data))++; break;
 case sizeof(long) : (*((long*)data))++; break;
 }
}
int main ()
{
 char a = 5;
 short b = 9;
 long c = 12;
 increase (&a,sizeof(a));
 increase (&b,sizeof(b));
 increase (&c,sizeof(c));
 cout << (int) a << ", " << b << ", " << c;
 return 0;
}
sizeof là một toán tử của ngôn ngữ C++, nó trả về một giá trị hằng là kích thước tính bằng byte của tham số truyền cho nó, ví dụ sizeof(char) bằng 1 vì kích thước của char là 1 byte. 
11. Con trỏ hàm
C++ cho phép thao tác với các con trỏ hàm. Tiện ích tuyệt vời này cho phép truyền một hàm như là một tham số đến một hàm khác. Để có thể khai báo một con trỏ trỏ tới một hàm chúng ta phải khai báo nó như là khai báo mẫu của một hàm nhưng phải bao trong một cặp ngoặc đơn () tên của hàm và chèn dấu sao (*) đằng trước.  
// pointer to functions
#include 
int addition (int a, int b)
{ return (a+b); }
int subtraction (int a, int b)
{ return (a-b); }
int (*minus)(int,int) = subtraction;
int operation (int x, int y, int (*functocall)(int,int))
{
 int g;
 g = (*functocall)(x,y);
 return (g);
}
int main ()
{
 int m,n;
 m = operation (7, 5, &addition);
 n = operation (20, m, minus);
 cout <<n;
 system(“pause”);
 return 0;
}
Trong ví dụ này, minus là một con trỏ toàn cục trỏ tới một hàm có hai tham số kiểu int, con trỏ này được gám để trỏ tới hàm subtraction, tất cả đều trên một dòng: 
int (* minus)(int,int) = subtraction;
Kết luận
Một sự mô hình tốt đối với bộ nhớ máy tính chính là một phố trong một thành phố. Trên một phố tất cả các ngôi nhà đều được đánh số tuần tự với một cái tên duy nhất nên nếu chúng ta nói đến số 27 phố Trần Hưng Đạo thì chúng ta có thể tìm được nơi đó mà không lầm lẫn vì chỉ có một ngôi nhà với số như vậy.
Cũng với cách tổ chức tương tự như việc đánh số các ngôi nhà, hệ điều hành tổ chức bộ nhớ thành những số đơn nhất, tuần tự, nên nếu chúng ta nói đến vị trí 1776 trong bộ nhớ chúng ta biết chính xác ô nhớ đó vì chỉ có một vị trí với địa chỉ như vậy. 
CHƯƠNG 8
CẤU TRÚC (STRUCTURE)
Mã chương: MH05_CH08
Mục tiêu:
- Khai báo được cấu trúc.
- Biết cách truy cập đến các thành phần của cấu trúc.
- Sử dụng được kiểu cấu trúc trong lập trình.
- Nghiêm túc trong học tập
Nội dung chính:
CHƯƠNG 8: CẤU TRÚC (STRUCTURE)
Để lưu trữ các giá trị gồm nhiều thành phần dữ liệu giống nhau ta có kiểu biến mảng. Thực tế rất nhiều dữ liệu là tập các kiểu dữ liệu khác nhau tập hợp lại, để quản lý dữ liệu kiểu này C++ đưa ra kiểu dữ liệu cấu trúc. Một ví dụ của dữ liệu kiểu cấu trúc là một bảng lý lịch trong đó mỗi nhân sự được lưu trong một bảng gồm nhiều kiểu dữ liệu khác nhau như họ tên, tuổi, giới tính, mức lương 
1. Khái niệm cấu trúc
Một cấu trúc dữ liệu là một tập hợp của những kiểu dữ liệu khác nhau được gộp lại với một cái tên duy nhất.
2. Khai báo cấu trúc
2.1. Sử dụng struct
Dạng thức của nó như sau: 
struct model_name {
 type1 element1;
 type2 element2;
 type3 element3;
 .
 .
} object_name;
trong đó model_name là tên của mẫu kiểu dữ liệu và tham số tùy chọn object_name một tên hợp lệ cho đối tượng. Bên trong cặp ngoặc nhọn là tên các phần tử của cấu trúc và kiểu của chúng. 
Nếu định nghĩa của cấu trúc bao gồm tham số model_name (tuỳ chọn), tham số này trở thành một tên kiểu hợp lệ tương đương với cấu trúc. Ví dụ: 
struct products {
 char name [30];
 float price;
} ;
products apple;
products orange, melon;
Chúng ta đã định nghĩa cấu trúc products với hai trường: name và price, mỗi trường có một kiểu khác nhau. Chúng ta cũng đã sử dụng tên của kiểu cấu trúc (products) để khai báo ba đối tượng có kiểu đó : apple, orange và melon. 
Sau khi được khai báo, products trở thành một tên kiểu hợp lệ giống các kiểu cơ bản như int, char hay short.
Trường tuỳ chọn object_name có thể nằm ở cuối của phần khai báo cấu trúc dùng để khai báo trực tiếp đối tượng có kiểu cấu trúc. Ví dụ, để khai báo các đối tượng apple, orange và melon như đã làm ở phần trước chúng ta cũng có thể làm theo cách sau:
struct products {
 char name [30];
 float price;
} apple, orange, melon;
Hơn nữa, trong trường hợp này tham số model_name trở thành tuỳ chọn. Mặc dù nếu model_name không được sử dụng thì chúng ta sẽ không thể khai báo thêm các đối tượng có kiểu mẫu này. 
Một điều quan trọng là cần phân biệt rõ ràng đâu là kiểu mẫu cấu trúc, đâu là đối tượng cấu trúc. Nếu dùng các thuật ngữ chúng ta đã sử dụng với các biến, kiểu mẫu là tên kiểu dữ liệu còn đối tượng là các biến.
2.2 Định nghĩa cấu trúc với từ khoá typedef
Để tránh phải dùng từ khoá struct mỗi khi khai báo biến cấu trúc, ta có thể dùng từ khóa typedef
khi định nghĩa cấu trúc:
typedef struct {
 ;
 ;
 ;
} ;
Trong đó:
• Tên kiểu dữ liệu cấu trúc: là tên kiểu dữ liệu của cấu trúc vừa định nghĩa. Tên này sẽ được dùng như một kiểu dữ liệu thông thường khi khai báo biến cấu trúc. Ví dụ, muốn có kiểu dữ liệu có cấu trúc nhân viên, có tên là Employee, ta dùng từ khoá typedef để định nghĩa cấu trúc như sau:
typedef struct {
char name[20]; // Tên nhân viên
int age; // Tuổi nhân viên
char role[20]; // Chức vụ của nhân viên
float salary; // Lương của nhân viên
} Employee;
Khi đó, muốn có hai biến là myEmployee1 và myEmployee2 có kiểu cấu trúc Employee, ta chỉ cần khai báo như sau mà không cần từ khoá struct:
Employee myEmployee1, myEmployee2;
Trong ví dụ khai báo lồng cấu trúc Employee, dùng từ khoá typedef cho kiểu Date:
typedef struct {
int day;
int month;
int year;
} Date;
cấu trúc Employee trở thành:
typedef struct {
char name[20]; // Tên nhân viên
Date birthDay; // Ngày sinh của nhân viên
char role[20]; // Chức vụ của nhân viên
float salary; // Lương của nhân viên
} Employee;
Lưu ý:
• Khi không dùng từ khoá typedef, tên cấu trúc (nằm sau từ khoá struct) được dùng để khai báo biến. Trong khi đó, khi có từ khoá typedef, tên kiểu dữ liệu cấu trúc (dòng cuối cùng trong định nghĩa) mới được dùng để khai báo biến.
• Khi dùng từ khoá typedef thì không thể khai báo biến đồng thời với định nghĩa cấu trúc.
3. Truy nhập đến các thành phần của cấu trúc
3.1. Truy nhập đến thành phần
Sau khi đã khai báo ba đối tượng có kiểu là một mẫu cấu trúc xác định (apple, orange and melon) chúng ta có thể thao tác với các trường tạo nên chúng. Để làm việc này chúng ta sử dụng một dấu chấm (.) chèn ở giữa tên đối tượng và tên trường. Ví dụ, chúng ta có thể thao tác với bất kì phần tử nào của cấu trúc như là đối với các biến chuẩn : 
apple.name
apple.price
orange.name
orange.price
melon.name
melon.price
mỗi trường có kiểu dữ liệu tương ứng: apple.name, orange.name và melon.name có kiểu char[30], và apple.price, orange.price và melon.price có kiểu float. 
Chúng ta tạm biệt apples, oranges và melons để đến với một ví dụ về các bộ phim: 
// example about structures
#include 
#include 
#include 
struct movies_t {
 char title [50];
 int year;
} mine, yours;
void printmovie (movies_t movie);
int main ()
{
 char buffer [50];
 strcpy (mine.title, "2001 A Space Odyssey");
 mine.year = 1968;
 cout << "Enter title: ";
 cin.getline (yours.title,50);
 cout << "Enter year: ";
 cin.getline (buffer,50);
 yours.year = atoi (buffer);
 cout << "My favourite movie is:\n ";
 printmovie (mine);
 cout << "And yours:\n ";
 printmovie (yours);
 return 0;
}
void printmovie (movies_t movie)
{
 cout << movie.title;
 cout << " (" << movie.year << ")\n";
}
Ví dụ này cho chúng ta thấy cách sử dụng các phần tử của một cấu trúc và bản thân cấu trúc như là các biến thông thường. Ví dụ, yours.year là một biến hợp lệ có kiểu int cũng như mine.title là một mảng hợp lệ với 50 phần tử kiểu chars. 
Chú ý rằng cả mine and yours đều được coi là các biến hợp lệ kiểu movie_t khi được truyền cho hàm printmovie().Hơn nữa một lợi thế quan trọng của cấu trúc là chúng ta có thể xét các phần tử của chúng một cách riêng biệt hoặc toàn bộ cấu trúc như là một khốA. 
3.2. Cấu trúc với mảng
Các cấu trúc được sử dụng rất nhiều để xây dựng cơ sở dữ liệu đặc biệt nếu chúng ta xét đến khả năng xây dựng các mảng của chúng. 
// array of structures
#include 
#include 
#define N_MOVIES 5
struct movies_t {
 char title [50];
 int year;
} films [N_MOVIES];
void printmovie (movies_t movie);
int main ()
{
 char buffer [50];
 int n;
 for (n=0; n<N_MOVIES; n++)
 {
 cout << "Enter title: ";
 cin.getline (films[n].title,50);
 cout << "Enter year: ";
 cin.getline (buffer,50);
 films[n].year = atoi (buffer);
 }
 cout << "\nYou have entered these movies:\n";
 for (n=0; n<N_MOVIES; n++)
 printmovie (films[n]);
 return 0;
}
void printmovie (movies_t movie)
{
 cout << movie.title;
 cout << " (" << movie.year << ")\n";
}
3.3. Con trỏ đến cấu trúc
Như bất kì các kiểu dữ liệu nào khác, các cấu trúc có thể được trỏ đến bởi con trỏ. Quy tắc hoàn toàn giống như đối với bất kì kiểu dữ liệu cơ bản nào: 
struct movies_t {
 char title [50];
 int year;
};
movies_t amovie;
movies_t * pmovie;
Ở đây amovie là một đối tượng có kiểu movies_t và pmovie là một con trỏ trỏ tới đối tượng movies_t. Bây giờ chúng ta sẽ đến với một ví dụ khác, nó sẽ giới thiệu một toán tử mới: 
// pointers to structures
#include 
#include 
struct movies_t {
 char title [50];
 int year;
};
int main ()
{
 char buffer[50];
 movies_t amovie;
 movies_t * pmovie;
 pmovie = & amovie;
 cout << "Enter title: ";
fflush(stdin);
 cin.getline (pmovie->title,50);
 cout << "Enter year: ";
 cin.getline (buffer,50);
 pmovie->year = atoi (buffer);
 cout << "\nYou have entered:\n";
 cout title;
 cout year << ")\n";
 return 0;
}
Đoạn mã trên giới thiệu một điều quan trọng: toán tử ->. Đây là một toán tử tham chiếu chỉ dùng để trỏ tới các cấu trúc và các lớp (class). Nó cho phép chúng ta không phải dùng ngoặc mỗi khi tham chiếu đến một phần tử của cấu trúc. Trong ví dụ này chúng ta sử dụng: 
movies->title
nó có thể được dịch thành: 
(*movies).title
cả hai biểu thức movies->title và (*movies).title đều hợp lệ và chúng đều dùng để tham chiếu đến phần tử title của cấu trúc được trỏ bởi movies. Bạn cần phân biệt rõ ràng với: 
*movies.title
nó tương đương với 
*(movies.title)
lệnh này dùng để tính toán giá trị được trỏ bởi phần tử title của cấu trúc movies, trong trường hợp này (title không phải là một con trỏ) nó không có ý nghĩa gì nhiều. 
3.4. Cấu trúc lồng nhau
Các cấu trúc có thể được đặt lồng nhau vì vậy một phần tử hợp lệ của một cấu trúc có thể là một cấu trúc khác. 
struct movies_t {
 char title [50];
 int year;
}
struct friends_t {
 char name [50];
 char email [50];
 movies_t favourite_movie;
 } charlie, maria;
friends_t * pfriends = &charlie;
Vì vậy, sau phần khai báo trên chúng ta có thể sử dụng các biểu thức sau: 
charlie.name
maria.favourite_movie.title
charlie.favourite_movie.year
pfriends->favourite_movie.year
(trong đó hai biểu thức cuối cùng là tương đương). 
4. Ví dụ cấu trúc
Dưới đây chúng ta đưa ra một vài ví dụ minh hoạ cho việc sử dụng kiểu cấu trúc.
Ví dụ 8.1: Cộng, trừ, nhân chia hai phân số được cho dưới dạng cấu trúc
#include 
#include 
struct Phanso { 
int tu ; 
int mau ; 
} a, b, c ; 
int main() 
{ 
cout << "Nhập phân số a:" << endl ; // nhập a 
cout > a.tu; 
cout > a.mau; 
cout << "Nhập phân số b:" << endl ; // nhập b 
cout > b.tu; 
cout > b.mau; 
c.tu = a.tu*b.mau + a.mau*b.tu; // tính và in a+b 
c.mau = a.mau*b.mau; 
cout << "a + b = " << c.tu << "/" << c.mau; 
c.tu = a.tu*b.mau - a.mau*b.tu; // tính và in a-b 
c.mau = a.mau*b.mau; 
cout << "a - b = " << c.tu << "/" << c.mau; 
c.tu = a.tu*b.tu; // tính và in axb 
c.mau = a.mau*b.mau; 
cout << "a + b = " << c.tu << "/" << c.mau; 
c.tu = a.tu*b.mau; // tính và in a/b 
c.mau = a.mau*b.tu; 
cout << "a + b = " << c.tu << "/" << c.mau; 
getch(); 
return 0;
} 
Ví dụ 8.2: Nhập mảng K41T. Tính tuổi trung bình của sinh viên nam, nữ. Hiện danh sách của sinh viên có điểm thi cao nhất. 
#include 
#include 
int main() 
{ 
struct Sinhvien { 
char hoten[25] ; 
Ngaythang ns; 
int gt; 
float diem ; 
} x, K41T[60]; 
int i, n; 
// nhập dữ liệu 
cout > n; 
for (i=1, i<=n, i++) 
{ 
cout << "Nhap sinh vien thu " << i); 
cout << "Ho ten: " ;
fflush(stdin);
 cin.getline(x.hoten); 
cout > x.ns.ng >> x.ns.th >>x.ns.nam ; 
cout << "Giới tính: " ;
fflush(stdin);
cin >> x.gt ; 
cout > x.diem ; 
cin.ignore(); 
K41T[i] = x ; 
} 
} 
// Tính điểm trung bình 
float tbnam = 0, tbnu = 0; 
int sonam = 0, sonu = 0 ; 
for (i=1; i<=n; i++) 
if (K41T[i].gt == 1) 
{ 
sonam++ ; tbnam += K41T[1].diem ; 
} 
else 
{
 sonu++ ; tbnu += K41T[1].diem ; 
} 
cout << "Điểm trung bình của sinh viên nam là " << tbnam/sonam ; 
cout << "Điểm trung bình của sinh viên nữ là " << tbnu/sonu ; 
// In danh sách sinh viên có điểm cao nhất 
float diemmax = 0; 
for (i=1; i<=n; i++) // Tìm điểm cao nhất 
if (diemmax < K41T[i].diem) diemmax = K41T[i].diem ; 
for (i=1; i<=n; i++) // In danh sách 
{ 
if (K41T[i].diem < diemmax) continue ; 
x = K41T[1] ; 
cout << x.hoten << '\t' ; 
cout << x.ns.ng << "/" << x.ns.th << "/" << x.ns.nam << '\t' ; 
cout << (x.gt == 1) ? "Nam": "Nữ" << '\t' ; 
cout << x.diem << endl; 
}
system(“pause”); 
return 0;
}

File đính kèm:

  • docgiao_trinh_lap_trinh_can_ban_lap_trinh_may_tinh.doc