Hàm friend của hai lớp

#include <iostream.h>
#include <stdio.h>
#include <conio.h>
#include <iomanip.h>
class DIEM;
class SINHVIEN
{ char hoten[25];
 int tuoi;
 public:
        int masv;
        char *gethoten(){return hoten;}
 friend void  nhapdiem(SINHVIEN s, DIEM &d);
 friend void  xemdiem(SINHVIEN s, DIEM &d);
 void nhap(void)
  {
  cout <<"\n nhap ho ten "; gets(hoten);
  cout <<"\n nhap ma sv "; cin>>masv;
  cout <<"\n nhap tuoi "; cin>>tuoi; cin.clear();
  }
 void xem(void)
  {
  cout <<"\n ho ten sinh vien: "<<hoten;
  cout <<"\n tuoi la: "<< tuoi << endl;
  }
};
//
class DIEM
{ float diem;
      public:
  float getdiem() {return diem;}
  void  putdiem(float d1) {diem=d1;}
 friend void  nhapdiem(SINHVIEN s, DIEM &d);
 friend  void  xemdiem(SINHVIEN s, DIEM &d);
};
//
void nhapdiem(SINHVIEN s, DIEM &d)
{
 float d2;
 cout <<"\n nhap diem cho sinh vien " <<s.masv <<": ";
 cin >> d2;
 d.putdiem(d2);
}
//
void xemdiem(SINHVIEN s, DIEM &d)
{
 cout <<"\n thong tin sinh vien: " ;
     cout<<"\nma sv: " <<s.masv;
     cout<<"\nho ten: " << s.gethoten();
     cout<<"\ndiem: "<<d.getdiem()<<endl;
}
//
const maxn=50;
void main () {
clrscr();
SINHVIEN s[maxn];
DIEM d[maxn];
int n, i;
cout<<"\nSo sinh vien: "; cin>>n; cin.clear();
for(i=1; i<=n; i++) s[i].nhap();
cout<<"\nThong tin vua nhap la: \n";
for(i=1; i<=n; i++) s[i].xem();
cout<<"\nNhap diem cho tung sinh vien: \n";
for(i=1; i<=n; i++) nhapdiem(s[i],d[i]);
for(i=1; i<=n; i++) xemdiem(s[i],d[i]);
getch();
}

Một số bài tập luyên tập

Đây chỉ là bài tập mang tính tham khảo, sẽ còn được bổ sung hay cập nhật.

1. Xây dựng hàm tìm giá trị lớn nhất trong mảng số nguyên.
 2. Xây dựng hàm tìm phần tử dương đầu tiên trong mảng
 3. Xây dựng hàm tìm phần tử âm đầu tiên trong mảng
 4. Xây dựng hàm tìm phần tử chẵn đầu tiên trong mảng
 5. Xây dựng hàm tìm phần tử lẻ đầu tiên trong mảng.
 6. Xây dựng hàm tìm phần tử chẵn cuối cùng trong mảng
 7. Xây dựng hàm tìm phần tử lẽ cuối cùng trong mảng
 8. Xây dựng hàm tìm vị trí chẵn cuối cùng trong mảng.
 9. Xây dựng hàm tìm vị trí dương đầu tiên trong mảng
 10. Xây dựng hàm tìm vị trí âm đầu tiên trong mảng
 11. Xây dựng hàm tìm vị trí chẵn đầu tiên trong mảng
 12. Xây dựng hàm tìm vị trí lẻ đầu tiên trong mảng. 13. Xây dựng hàm tìm vị trí chẵn cuối cùng trong mảng
 14. Xây dựng hàm tìm vị trí lẽ cuối cùng trong mảng
 15. Xây dựng hàm tìm vị trí chẵn cuối cùng trong mảng.
 16. Xây dựng hàm tìm vị trí số hoàn thiện cuối cùng trong mảng.
 17. Xây dựng hàm tìm số nguyên tố đầu tiên trong mảng.
 18. Xây dựng hàm tìm vị trí đầu tiên của số nguyên tố trong mảng.
 19. Xây dựng hàm tìm số nguyên tố lớn nhất trong mảng.
 20. Xây dựng hàm tìm vị trí số nguyên tố lớn nhất trong mảng.
 21. Xây dựng hàm tìm vị trí số hoàn thiện đầu tiên trong mảng.
 IV. tính tổng và trung bình
1. Xây dựng hàm tính tổng các phần tử của mảng.
 2. Xây dựng hàm tính tổng các phần tử có chỉ số lẽ
 3. Xây dựng hàm tính tổng các phần tử chẵn.
int sum_array_3(int a[MAX], int n);
4. Xây dựng hàm tính tổng các phần tử lẽ.
int sum_array_4(int a[MAX], int n);
5. Xây dựng hàm tính tổng các phần tử có chỉ số chẵn.
int sum_array_5(int a[MAX], int n);
6. Xây dựng hàm tính tổng các phần tử chia hết cho 3
int sum_array_6(int a[MAX], int n);
7. Xây dựng hàm tính tổng các phần tử có chỉ số chia hết cho 3.
int sum_array_7(int a[MAX], int n);
8. Xây dựng hàm tính tổng các phần tử mảng là số nguyên tố.
int sum_array_8(int a[MAX], int n);
9. Xây dựng hàm tính tổng các phần tử vừa chia hết cho 5 và chia hết cho 10
int sum_array_9(int a[MAX], int n);
10. Xây dựng hàm tính tổng các phần tử mảng lớn hơn X.
int sum_array_10(int a[MAX], int n);
11. Xây dựng hàm tính tổng các phân tử mảng nhỏ hơn X.
int sum_array_11(int a[MAX], int n);
12. Xây dựng hàm tính tổng các phần tử chia hết cho X
int sum_array_12(int a[MAX], int n);
13. Xây dựng hàm tính tổng các phần tử không chia hết cho X
int sum_array_13(int a[MAX], int n);
14. Xây dựng hàm tính tổng các phần tử chính phương của mảng.
int sum_array_14(int a[MAX], int n);
15. Xây dựng hàm tính tổng các phần tử chính phương của mảng.
int sum_array_15(int a[MAX], int n);
16. Xây dựng hàm tính trung bình các phần tử mảng.
float average_array_1(int a[MAX], int n);
17. Xây dựng hàm tính trung bình các phần tử có chỉ số lẽ
float average_array_2(int a[MAX], int n);
18. Xây dựng hàm tính trung bình các phần tử chẵn.
float average_array_3(int a[MAX], int n);
19. Xây dựng hàm tính trung bình các phần tử lẽ.
float average_array_4(int a[MAX], int n);
20. Xây dựng hàm tính trung bình các phần tử có chỉ số chẵn.
float average_array_5(int a[MAX], int n);
21. Xây dựng hàm tính trung bình các phần tử chia hết cho 3
float average_array_6(int a[MAX], int n);
22. Xây dựng hàm tính trung bình các phần tử có chỉ số chia hết cho 3.
float average_array_7(int a[MAX], int n);
23. Xây dựng hàm tính trung bình các phần tử mảng là số nguyên tố.
float average_array_8(int a[MAX], int n);
24. Xây dựng hàm tính trung bình các phần tử vừa chia hết cho 5 và chia hết cho 10
float average_array_9(int a[MAX], int n);
25. Xây dựng hàm tính trung bình các phần tử mảng lớn hơn X.
float average_array_10(int a[MAX], int n, int X);
26. Xây dựng hàm tính trung bình các phân tử mảng nhỏ hơn X.
float average_array_11(int a[MAX], int n, int X);
27. Xây dựng hàm tính trung bình các phần tử chia hết cho X
float average_array_12(int a[MAX], int n, int X);
28. Xây dựng hàm tính trung bình các phần tử không chia hết cho X
float average_array_13(int a[MAX], int n, int X);
V. Các kỹ thuật đếm
1. Xây dựng hàm đếm các phần tử chẵn
int count_array_1(int a[MAX], int n);
2. Xây dựng hàm đếm các phần tử lẽ.
int count_array_2(int a[MAX], int n);
3. Xây dựng hàm điếm các phần tử chẵn.
int count_array_3(int a[MAX], int n);
4. Xây dựng hàm đếm các phần tử lẽ
int count_array_4(int a[MAX], int n);
5. Xây dựng hàm đếm các phần tử chia hết cho 3
int count_array_5(int a[MAX], int n);
6. Xây dựng hàm đếm các phần tử chia hết cho 3 hoặc chia hết cho 5.
int count_array_6(int a[MAX], int n);
7. Xây dựng hàm đếm các phần tử dương chia hết cho 3
int count_array_7(int a[MAX], int n);
8. Xây dựng hàm đểm các phần tử âm chia hết cho 2
int count_array_8(int a[MAX], int n, int X);
9. Xây dựng hàm đếm số lần xuất hiện của phần tử X.
int count_array_9(int a[MAX], int n);
10. Xây dựng hàm đểm trong mảng xem có bao nhiêu số nguyên tố.
int count_array_10(int a[MAX], int n);
11. Xây dựng hàm đếm trong mảng có bao nhiêu số hoàn thiện.
int count_array_11(int a[MAX], int n);
VI. Các thao tác thêm phần tử vào mảng
1. Xây dựng hàm thêm một phần tử(K) vào đầu mảng.
int add_array_1(int a[MAX], int n, int K);
2. Xây dựng hàm thêm một phần tử(K) vào cuối mảng.
int add_array_2(int a[MAX], int n, int K);
3. Xây dựng hàm thêm một phần tử(K) vào sau phần tử X.
int add_array_3(int a[MAX], int n, int K, int X);
4. Xây dựng hàm thêm một phần tử(K) vào vị trí sau M
int add_array_4(int a[MAX], int n, int K, int M);
5. Xây dựng hàm thêm một phần tử(K) vào mảng đã sắp xếp sao cho mảng không đổi thứ tự sắp xếp.
int add_array_5(int a[MAX], int n, int K);VII. Các thao tác xóa một phần tử mảng
1. Xây dựng hàm xóa phần tử cuối cùng của mảng
int del_array_1(int a[MAX], int n);
2. Xây dựng hàm xóa phần tử đầu tiên của mảng.
int del_array_2(int a[MAX], int n);
3. Xây dựng hàm xóa phần tử sau phần tử X
int del_array_3(int a[MAX], int n, int X);
4. Xây dựng hàm xóa phần tử sau vị trị M
int del_array_4(int a[MAX], int n, int M);
5. Xây dựng hàm xóa các phần tử có giá trị trong mảng trùng nhau.
int del_array_5(int a[MAX], int n);
6. Xây dựng hàm xóa các phần tử mảng chia hết cho 3.
int del_array_6(int a[MAX], int n);
7. Xây dựng hàm xóa các phần tử mảng có giá trị âm.
int del_array_7(int a[MAX], int n);
8. Xây dựng hàm xóa các phần tử có giá trị dương.
int del_array_8(int a[MAX], int n);
9. Xây dựng hàm xóa các phần tử không phải là số nguyên tố.
int del_array_9(int a[MAX], int n);
10. Xây dựng hàm xóa các phần tử là số nguyên tố.
int del_array_10(int a[MAX], int n);VIII. Các thao tác sao chép mảng(5 bài)
1. Xây dựng hàm sao chép giá các phần tử của mảng a vào mảng b.
type_array copy_array_1(int a[MAX], int n);
2. Xây dựng hàm sao chép các phân tử có giá trị chẵn vào mảng khác.
type_array copy_array_2(int a[MAX], int n);
3. Xây dựng hàm sao chép các phần tử có giá trị lẽ vào mảng khác.
type_array copy_array_3(int a[MAX], int n);
4. Xây dựng hàm sao chép các phần tử có giá trị chia hết cho 2 và cho 3 vào mảng khác.
type_array copy_array_2(int a[MAX], int n);
5. Xây dựng hàm sao chép các phần tử của mảng có chỉ số chia hết cho 3 vào mảng khác.
type_array copy_array_2(int a[MAX], int n);
IX. Các thao tác ghép mảng(7 bài)
1. Xây dựng hàm ghép hai mảng a và b thành một mảng c.
type_array merge_array(int a[MAX], int n, int b[MAX], int m);
2. Xây dựng hàm ghép mảng b vào mảng a.
type_array merge_array(int a[MAX], int n, int b[MAX], int m);
3. Xây dựng hàm ghép mảng b vào mảng a mà các phần tử mảng a vẫn được sắp xếp theo thứ tự tăng dần(mảng a là mảng được sắp xếp tăng).
type_array merge_array(int a[MAX], int n, int b[MAX], int m);
4. Xây dựng hàm ghép mảng b vào mảng a mà các phần tử mảng a vẫn được sắp xếp theo thứ tự giảm dần(mảng a là mảng được sắp xếp giảm).
type_array merge_array(int a[MAX], int n, int b[MAX], int m);
5. Xây dựng hàm ghép hai mảng a và b sao cho các phần tử sau khi ghép được sắp xếp theo thứ tự tăng.
type_array merge_array(int a[MAX], int n, int b[MAX], int m);
6. Xây dựng hàm ghép hai mảng a và b sao cho các phần tử sau khi ghép được sắp xếp giảm dần.
type_array merge_array(int a[MAX], int n, int b[MAX], int m);
7. Xây dựng hàm ghép hai mảng a và b sao cho các phần tử của mảng a và mảng b được sắp xếp đan xen nhau(Chú ý: Nếu hai mảng có số phần tử khác nhau thì các phần tử còn lại của mảng có nhiều phần tử hơn được đưa vào sau).
type_array merge_array(int a[MAX], int n, int b[MAX], int m);
MỘT SỐ BÀI TẬP VỀ DANH SÁCH LIÊN KẾT

Bài 1: Hãy tạo danh sách liên kết, mỗi phần tử của danh sách lưu trữ một số nguyên
1. Xây dựng hàm tạo phần tử và tạo danh sách liên kết đơn.
2. Xây dựng hàm tạo danh sách liên kết đơn bằng cách tự động nhập random
3. Xây dựng hàm xóa các phần tử trùng trên dslk đơn
4. Xây dựng hàm thêm 1 phần tử vào cuối danh sách liên kết đơn
5. Xây dựng hàm thêm 1 phần tử vào đầu danh sách liên kết đơn
6. Xây dựng hàm thêm phần tử y vào trước phần tử x trên danh sách liên kết đơn
7. Xây dựng hàm thêm phần tử y sau phần tử x trên danh sách liên kết đơn
8. Xây dựng hàm xóa phần tử trước phần tử X và xóa sau phần tử X
9. Xây dựng hàm xóa phần tử có giá trị x trên danh sách liên kết đơn
10. Xây dựng hàm xóa đầu, xóa cuối trên danh sách liên kết đơn
11. Xây dựng hàm tìm phần tử lớn nhất (max) trên danh sách liên kết
12. Xây dựng hàm viết hàm tìm phần tử X trong danh sach lien ket
13. Xây dựng hàm nối 2 danh sách liên kết đơn
14. Xây dựng hàm tách danh sách liên kết đơn
15. Xây dựng hàm cộng liên tiếp 2 phần tử trên danh sách liên kết đơn
16. Xây dựng hàm tìm phần tử chẵn lớn nhất, lớn hơn phần tử lẽ lớn nhất trên dslk đơn
17. Xây dựng hàm đảo ngược danh sách liên kết đơn
18. Xây dựng hàm xóa phần tử nhỏ nhất trên dslk đơn
19. Xây dựng hàm tìm phần tử lẽ cuối cùng và thêm 1 phần tử X trước phần tử đó trên dslk đơn
20. Xây dựng hàm tìm phần tử chẵn đầu tiên và thêm 1 phần tử X trước phần tử đó trên dslk đơn
21. Xây dựng hàm kiểm tra, đếm và in các số nguyên tố ra màn hình
22. Xây dựng hàm tính tổng các phần tử trên dslk đơn
23. Xây dựng hàm liệt kê tất cả các số âm trên dslk đơn
24. Xây dựng hàm sao chép các phần tử trên danh sách liên kết đơn
25. Xây dựng hàm xóa toàn bộ các phần tử trên dslk đơn
Bài 2: Hãy tạo danh sách liên kết, mỗi phần tử của danh sách lưu trữ thông tin của sinh viên(Họ tên, điểm)
1. Xây dựng hàm tạo danh sách sinh viên.
2. Xây dựng hàm tạo danh sách liên kết không có 2 sinh viên trùng tên
3. Xây dựng hàm thêm 1 sinh viên vào cuối danh sách liên kết đơn
4. Xây dựng hàm thêm 1 sinh viên vào đầu danh sách liên kết đơn
5. Xây dựng hàm thêm 1 sinh viên vào trước sinh viên x trên danh sách liên kết đơn
6. Xây dựng hàm thêm 1 sinh viên vào sau sinh viên x trên danh sách liên kết đơn
7. Xây dựng hàm xóa 1 sinh viên trước sinh viên X và xóa sau sinh viên X
8. Xây dựng hàm xóa 1 sinh viên có tên x trên danh sách liên kết đơn
9. Xây dựng hàm xóa 1 sinh viên đầu, xóa cuối trên danh sách liên kết đơn
10. Xây dựng hàm tìm sinh viên có điểm cao nhất trên danh sách liên kết.
11. Xây dựng hàm sắp xếp các sinh viên trong danh sách liên kết theo tên sinh viên.
12. Xây dựng hàm in ra sinh viên có điểm lớn nhất.
13. Xây dựng hàm in ra danh sách các sinh viên có điểm lớn hơn 5.

DFS

//Bai toan: Cho do thi G(V, E).
// 1. Cho biet do thi co lien thong khong
// 2. Neu do thi lien thong: Tim duong di dai nhat tu u0 den v0
//
//Algorithm: Deapth First Search
//Data structure: Ma tran ke
//Input: Text file
//Output: Text file
//
#include <iostream.h>
#include <fstream.h>
#include <conio.h>
#include <iomanip.h>
//
#define    MAX    100
#define FINPUT    "DFS2.INP"
#define FOUTPUT    "DFS2.OUT"
//
int n,u0,v0;
int a[MAX][MAX];
//
void nhapdulieu(){
  int i,j,x;
  for(i=1;i<=n;i++)
  for(j=1;j<=n;j++) a[i][j]=0;
  i=1;
  ifstream fin(FINPUT);
  fin>>n>>u0>>v0;
  while (!fin.eof()){
    fin>>j;
    if (j==0) i++;
    else {a[i][j]=1; a[j][i]=1;}
  }
  fin.close();
  cout<<n<<", "<<u0<<", "<<v0<<endl;
  for(i=1;i<=n;i++) {
    cout<<i<<": ";
    for(j=1;j<=n;j++)
    if(a[i][j]>0) cout<<j<<",";
    cout<<endl;
  }
}
//
int pred[MAX];
//
void DFS(int u){
 int v;
 for(v=1;v<=n;v++)
 if(a[u][v]==1 && pred[v]==0)
 { pred[v]=u;
   DFS(v);
 }
}
//
int path[MAX];
int lt,m;
//
void xuli(){
 int u;
 lt=1;
 for(u=1;u<=n;u++) pred[u]=0;
 pred[u0]=-1;
 DFS(u0);
 for(u=1;u<=n;u++)
 if (pred[u]==0) lt=0;
 if (lt) {
   m=0;
   u=v0;
   do{
     path[++m]=u;
     u=pred[u];
   }while (u!=-1);
 }
}
//
void xuatketqua(){
 ofstream fo(FOUTPUT);
 if(!lt) fo<<"Do thi khong lien thong";
 else{ fo<<"Duong di dai nhat can tim co do dai "<<m<<endl;
       for(int i=m;i>0;i--)
      fo<<path[i]<<"->";
     }
 fo.close();
}
//
int main(){
 clrscr();
 nhapdulieu();
 xuli();
 xuatketqua();
 cout<<"done!"; getch();
 return 0;
}
=====================
9 1 8
2 0
3 9 0
5 7 8 0
5 7 0
6 8 0
7 0
9 0
9 0

code for BFS

#include <iostream.h>
#include <fstream.h>
#include <conio.h>
#include <iomanip.h>

#define    MAX    100
#define FINPUT    "BFS2.INP"
#define FOUTPUT    "BFS2.OUT"

typedef struct    {
        int      front, rear;
        int    nodes[MAX];
} queue;

void    init(queue *Q) {
        Q->front = -1;
        Q->rear = -1;
}
int    empty(queue *Q) {
        return (Q->front==Q->rear);
}

int     full(queue *Q){
        return (Q->rear+1 == Q->front);
}

void      push(queue *Q, int x) {
        if (full(Q)) {
            cout<<"\n stack full";
            return;
        }
        Q->rear++;
        Q->nodes[Q->rear] = x;
}

int     pop(queue *Q){
        int x;
        if(empty(Q)){
        cout<< "\n Stack rong";
        return NULL;
        }
        Q->front++;
        x = Q->nodes[Q->front];
        return (x);
  }

 queue *Q;
 int n,u0,v0;
 int a[MAX][MAX];

void nhapdulieu(){
  int i,j,x;
  for(i=1;i<=n;i++)
  for(j=1;j<=n;j++) a[i][j]=0;
  i=1;
  ifstream fin(FINPUT);
  fin>>n>>u0>>v0;
  while (!fin.eof()){
    fin>>j;
    if (j==0) i++;
    else a[i][j]=1;
  }
  fin.close();
  cout<<n<<" "<<u0<<" "<<v0<<endl;
  for(i=1;i<=n;i++) {
    cout<<i<<": ";
    for(j=1;j<=n;j++)
    if(a[i][j]>0) cout<<j<<",";
    cout<<endl;
  }
}

int pred[MAX];
int found;

void BFS(int u0,int v0){
 int u,v;
 for(u=1;u<=n;u++) pred[u]=0;
 pred[u0]=-1;
 found=0;
 push(Q,u0);
 while (!empty(Q) && !found){
  /*step 1*/ u=pop(Q);
  /*step 2*/ if(u==v0) found=1;
  /*step 3*/ else
         for(v=1;v<=n;v++)
          if(a[u][v]==1 && pred[v]==0){
          /* 3.1 */ pred[v]=u;
          /* 3.2 */ push(Q,v);
          }
 } //while
}

void xuatketqua(){
 int v,m;
 int path[MAX];
 ofstream fo(FOUTPUT);
 if(!found) fo<<"No Solution";
 else{ v=v0; m=0;
    do {
      path[++m]=v;
      v=pred[v];
    }while(v!=-1);
    fo<<"Length of shorted path = "<<m<<endl;
    cout<<"Length of shorted path = "<<m<<endl;
    for(v=m;v>0;v--){
      fo<<path[v]<<"->";
      cout<<path[v]<<"->";
    }
     }
 fo.close();
}

int main(){
 clrscr();
 nhapdulieu();
 BFS(u0,v0);
 xuatketqua();
 cout<<"done!"; getch();
 return 0;
}

======================
6 1 6
2 3 0
3 5 0
5 0
5 0
6 0
4 0

danh sách đề tài môn Lập trình nâng cao

STT	Đề tài thảo luận
1	Xây dựng hệ thống quản lý bán hàng bằng phương pháp phân tích - lập trình HĐT.
2	Xây dựng hệ thống quản lý tín dụng trong ngân hàng bằng phương pháp phân tích - lập trình HĐT.
3	Tìm hiểu về khuôn hình trong C++ và xây dựng một chương trình nhỏ ứng dụng khuôn hình trong C++.
4	Tìm hiểu về lập trình MFC (C++) và xây dựng một ứng dụng sử dụng MFC.

mô tả ảnh củađề tài 2

Đề tài thảo luận môn CTDL và GT

1. Đề tài về sắp xếp, tìm kiếm

Bài toán: Xếp lịch hội thảo

Có n cuộc hội thảo đánh số thứ tự từ 1 đến n,  cùng đăng kí sử dụng một phòng hội trường trong khoảng thời gian từ ngày 1 đến ngày 30 cùng tháng. Cuộc hội thảo thứ i diễn ra từ ngày a_i đến ngày b_i. Biết rằng tại một thời điểm, phòng hội trường chỉ có thể cho phép bố trí được một cuộc hội thảo. Hãy tìm cách xếp lịch sao cho có nhiều cuộc hội thảo được tổ chức nhất.

Dữ liệu vào cho trong một file văn bản có tên là XEPLICH.INP: Dòng thứ nhất ghi số n. Trong n dòng tiếp theo, dòng thứ i ghi hai số a_i và b_i , i = 1, 2, ..., n.

Dữ liệu ra ghi vào một file văn bản khác có tên là XEPLICH.OUT: Dòng thứ nhất ghi số m, là số (lớn nhất) các cuộc hội thảo được bố trí tổ chức. Trong m dòng tiếp theo, ghi danh sách các cuộc hội thảo được tổ chức, dòng thứ i ghi số thứ tự của một cuộc họp.

Ví dụ

XEPLICH.INP	XEPLICH.OUT
6 4  7 11 13 8  9 3  5 1  3 6  11	4 1  3 4  7 8  9 11  12

Bài toán: Vận chuyển hàng tối ưu

Một nhà vận chuyển (bên B) nhận hợp đồng chuyên chở hàng hóa từ các kho của một tổng công ty (bên A) đến các  địa điểm giao hàng. Hợp đồng ghi rõ một số điều khoản như sau:

1) Công việc vận chuyển được tiến hành từ ngày đầu tiên của một tháng nào đó do bên B quyết định. Xem như mỗi tháng có 30 ngày.

2) Phải vận chuyển N loại hàng khác nhau, kí hiệu từ 1 đến N.

3) Trong cùng một ngày tổng công ty chỉ xuất kho một loại hàng. Khi đã xuất hết một loại hàng thì tổng công ty mới cho xuất loại hàng khác.

4) Thời gian vận chuyển trễ một loại hàng được coi là số ngày tính từ ngày đầu tiên đến ngày bắt đầu vận chuyển loại hàng đó. Cứ mỗi ngày vận chuyển trễ loại hàng i thì bên B bị trừ một lượng tiền là C_i nghìn đồng (gọi là tiền phạt).

5) Bên B được quyền quyết định trình tự trước sau các loại hàng cần vận chuyển.

Từ bảng thông tin về các loại hàng cần vận chuyển, nhà vận chuyển đã tính toán thấy rằng loại hàng thứ i muốn chuyển hết về các nơi giao phải mất T_i ngày.

Hãy giúp nhà vận chuyển sắp xếp một trình tự từng loại hàng cần chuyên chở sao cho tổng số tiền phạt là ít nhất.

Dữ liệu vào cho trong một file văn bản có tên là TRANS.INP, trong đó dòng thứ nhất ghi số nguyên dương N (N ≤ 200). Với 1 ≤ i ≤ N, dòng thứ i + 1 ghi hai số nguyên T_i và C_i.

Dữ liệu ra ghi vào một file văn bản với một tên khác là TRANS.OUT. Dòng thứ nhất ghi tổng số tiền bị phạt. Từ dòng thứ hai, mỗi dòng ghi một bộ ba số: số thứ nhất là số hiệu loại hàng cần vận chuyển, số thứ hai là ngày bắt đầu vận chuyển, số thứ ba là số tiền phạt. Trình tự từ trên xuống dưới là trình tự các loại hàng lần lượt  được vận chuyển.

Ví dụ

TRANS.INP	TRANS.OUT
5 2 10 15 4 10 5 20 2 25 15	1660 4  1  0 2  21  80 3  26  175 5   46  675 1   71  700

2. Đề tài về cấu trúc dữ liệu ngăn xếp và hàng đợi

Bài toán: Kho sửa tầu

Xét mạng đường sắt sau đây:

Các toa tàu ở đường ray A bên phải (được đánh số 1, 2, ..., n) cần phải hoán vị chuyển sang đường ray B bên trái. B được xem như đầu ra của các toa tầu, còn A được xem là đầu vào. Như hình vẽ đã chỉ ra, một toa có thể chuyển thẳng sang đường ray bên trái, hay nó có thể rẽ xuống đường ray bên cạnh (để sửa chữa) để sau này sẽ đi ra đường ray bên trái. Các toa tàu không được phép đi được ngược chiều các mũi tên đã chỉ dẫn.

Cho trước một hoán vị toa tầu ở đầu ra B. Hãy cho biết liệu hoán vị đó có xảy ra hay không.

Ví dụ: ở đầu vào, có 4 toa tầu, ở đầu ra các toa tầu theo thứ tự là 3, 1, 4, 2. Hoán vị này không thể xảy ra. Vì toa đầu tiên là toa 3, điều này chứng tỏ nó đi thẳng ra đầu ra B, còn các toa 1 và 2 được chuyển vào kho. Khi ra khỏi kho thì toa 2 phải ra trước nghĩa là phải có thứ tự 2 trước 1. Điều này mâu thuẫn với thứ tự 2 sau 1 trong hoán vị 3, 1, 4, 2.

Dữ liệu vào cho trong một file văn bản có tên là TRAINS.INP.

- Dòng một ghi số n biểu thị số toa tầu ở đường ray vào A, theo thứ tự các toa được đánh số liên tục 1, 2, ..., n từ trái sang phải.

- Từ dòng 2 trở đi, mỗi dòng ghi một hoán vị toa tầu ở đường ra ra B.

- Dòng cuối cùng của file dữ liệu vào ghi một số 0.

Dữ liệu ra ghi vào một file văn bản có tên là TRAINS.OUT. Tương ứng với mỗi dòng dữ liệu vào (từ dòng thứ hai trở đi trong file input) là một dòng thông báo (được ghi trên một dòng của file output) là “Possible” hoặc “Impossible” tùy theo hoán vị các toa tầu tương ứng (trên dòng dữ liệu vào) có xảy ra được hay không.

Ví dụ

           

TRAINS.INP	TRAINS.OUT
4 3 1 4 2 3 2 1 4 1 3 4 2 1 4 2 3	Impossible Possible Possible Impossible

Bài toán: Hội chợ triển lãm

Một hội chợ triển lãm các mặt hàng của một số công ty và doanh nghiệp (gọi tắt là đơn vị). Nhu cầu về không gian thuê trưng bày sản phẩm của từng đơn vị  rất khác nhau, ví dụ đơn vị trưng bày các sản phẩm gạch lát cần diện tích rộng hơn so với đơn vị trưng bày sản phẩm mĩ nghệ đắt tiền. Do vậy bản đồ hội chợ khá phức tạp, và có dạng như hình dưới đây:

	1	2	3	4	5	6	7	8
1	1	1		1				2
2	1			1		1		2
3	1	1				1
4					1	1
5	1	1	1					2
6	1	1	1		1	1	1	2

Một vùng chỉ gồm các ô vuông ghi chữ số 1 kề cạnh nhau biểu diễn một gian hàng của một đơn vị nào đó. Hai gian hàng khác nhau không chung cạnh hay chung đỉnh tại bất kì ô vuông nào. Các ô vuông kề cạnh ghi chữ số 2 biểu diễn một cửa vào/ra của khu hội chợ. Các ô vuông không ghi chữ số nào (gọi là vị trí trống) biểu thị cho lối đi. Các ô vuông ghi số chữ số 2 cũng được xem như vị trí trống (đi được đến cửa ra/vào). Các gian hàng được bố trí sao luôn có đường đi giữa hai vị trí trống bất kì.

Yêu cầu: Từ bản đồ hội chợ, hãy cho biết

1) Hội chợ có bao nhiêu gian hàng?

2) Gian hàng có diện tích lớn nhất là bao nhiêu?

3) Một vị khách đang đứng tại một vị trí (trống) nào đó trong hội chợ. Hãy chỉ cho vị khách lối đi ngắn nhất để ra ngoài khu hội trợ. Người khách đến được vị trí nào đó của cửa ra/vào được xác nhận là ra được khu hội chợ.

 Dữ liệu vào cho trong một file văn bản có tên là HOICHO.INP:

- Dòng một ghi số m và n là số hàng và số cột của bản đồ.

- Dòng hai ghi cặp số u₀ và v0 biểu thị vị trí trống của vị khách.

- Trong m dòng tiếp theo, số thứ j trên dòng thứ i có giá trị bằng 0 hoặc 1 hoặc 2 là giá trị của  ô vuông ở dòng i cột j và tương ứng biểu thị đó là vị trí hoặc của lối đi hoặc thuộc vào một gian hàng hoặc thuộc vào cửa ra vào.

Dữ liệu ra ghi vào một file văn bản khác có tên là HOICHO.OUT.

- Dòng 1 ghi một số nguyên biểu thị số lượng gian hàng

- Dòng 2 ghi một số nguyên biểu thị diện tích của gian hàng chiếm nhiều không gian nhất.

- Dòng 3 ghi một dãy các cặp số nguyên theo dạng:

(x₁, y₁) à (x₂, y₂) à .... (x_k, y_k)  biểu thị đường đi ngắn nhất từ vị trí (u₀, v₀) đến cửa ra vào. (Trong đó (x₁, y₁) = (u₀, v₀)).

Ví dụ

HOICHO.INP	HOICHO.OUT
6  8 4  4 1     1     0     1     0     0     0     2 1     0     0     1     0     1     0     2 1     1     0     0     0     1     0     0 0     0     0     0     1     1     0     0 1     1     1     0     0     0     0     2 1     1     1     0     1     1     1     2	5 6 (4, 4) -> (5, 4) -> (5, 5) -> (5, 6) -> (5, 7) -> (5, 8)

3. Đề tài về Đồ thị

Bài toán: Mạng truyền tin an toàn

Người ta cần lắp đặt một mạng truyền tin của một trường đại học gồm n trạm và m đường truyền tin hai chiều trực tiếp giữa các trạm. Chi phí để lắp đặt giữa hai trạm i và j  là a[i,j], i, j = 1, 2, ..., n. Các bản tin thường được phát đi từ trạm S thuộc Trung tâm thông tin của nhà trường đến các trạm của các khoa. Để đảm bảo tính an toàn cho việc truyền tin, khoa Tin học của trường đã yêu cầu lắp đặt sao cho thông tin truyền giữa trạm S của Trung tâm và trạm T của Khoa đi theo hai con đường khác nhau (hai đường được gọi là khác nhau nếu chúng không có đường truyền chung). Khoa Tin học còn tư vấn để hai đường truyền tin giữa S và T có tổng chi phí lắp đặt là thấp nhất. Hãy lập trình chỉ ra hai đường truyền tin khác nhau đó mà tổng chi phí lắp đặt là nhỏ nhất.

            Dữ liệu vào cho trong file văn bản TWOWAYS.INP

- Dòng đầu tiên chứa bốn số nguyên dương N, M, S, T, trong đó N ≤ 200, 1≤ M  ≤ 1/2*N*(N-1). S và T tương ứng là trạm của Trung tâm thông tin và của trạm Khoa Tin học.

- M dòng tiếp theo, mỗi dòng miêu tả các đường truyền trực tiếp gồm ba số nguyên dương i, j,  k thể hiện chi phí lắp đặt đường truyền trực tiếp giữa hai trạm  i và j là k, (k ≤ 3000).

Dữ liệu ra Ghi vào file văn bản TWOWAYS.OUT

- Dòng đầu tiên ghi tổng chi phí nhỏ nhất của hai đường truyền đã tìm được.

- Dòng thứ hai biểu thị đường truyền thứ nhất.

- Dòng thứ ba biểu thị đường truyền thứ hai.

Mỗi đường truyền là một “đường đi”, gồm một dãy các trạm bắt đầu là trạm S và kết thúc là trạm T.

Ví dụ

TWOWAYS.INP	TWOWAYS.OUT
6  8  2  5 1  2  1 1  4  2 2  3  3 3  4  2 3  6  5 4  5  3 4  6  2 5  6  1	14 2  1  4  5 2  3  4  6  5

Bài toán: Mạng giao thông

Theo thiết kế, một mạng giao thông gồm n nút, có tên từ 1 đến n (n ≤ 100). Chi phí để xây dựng đường hai chiều trực tiếp  từ nút i đến nút j bằng a[i,j] = a[j,i]. Qui ước a[i,i]= 0 với mọi i. Hai tuyến đường khác nhau không cắt nhau tại hai điểm không là đầu mút. Hiện đã xây dựng được k tuyến đường.

Bài toán đặt ra như sau: Hệ thống đường đã xây dựng đã đảm bảo sự đi lại giữa hai nút bất kì chưa? Nếu chưa, hãy chọn một số tuyến đường cần xây dựng thêm sao cho:

1. Các tuyến đường xây dựng thêm cùng với các tuyến đường đã xây dựng đảm bảo sự đi lại giữa hai nút bất kì.

2. Tổng kinh phí xây dựng các tuyến đường thêm là ít nhất.

Dữ liệu vào cho trong file văn bản có tên là MGT.INP, trong đó dòng thứ nhất ghi hai số n và k. Trong k dòng tiếp theo, mỗi dòng ghi hai số là tên của hai nút, đó là hai đầu (mút) của một tuyến đường đã xây dựng. Cuối cùng là n dòng, dòng thứ i ghi n số a[i,1], a[i, 2], ..., a[i, n].

Dữ liệu ra ghi vào file văn bản có tên là MGT.OUT như sau: Dòng thứ nhất ghi số CP là chi phí xây dựng thêm nhỏ nhất đã tìm được. Nếu CP > 0, trong một số dòng tiếp theo, mỗi dòng ghi hai số là tên của hai nút, đó là hai đầu (mút) của một tuyến đường xây dựng thêm.

Ví dụ;

MGT.INP	MGT.OUT
5 4 1 2 2 3 3 1 4 5 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0	1 3 4

3. Đề tài về danh sách liên kết

Bài toán Quản lí hàng

Một mặt hàng gồm các thông tin sau đây:

- Mã hàng

- Tên hàng

- Đơn giá

- Số lượng

- Đơn vị tính

Viết chương trình trong đó có ít nhất các chức năng sau

1. Tạo một tệp QLHANG.DAT mới để chuẩn bị chứa thông tin các mặt hàng

2. Nhập một mặt hàng mới để ghi vào tệp QLHANG.DAT

3. Hiển thị thông tin các mặt hàng hiện có

4. Tìm kiếm một mặt hàng theo mã hàng và đưa ra các thông tin (nếu tìm thấy)

5. Đưa ra danh sách gồm tên hàng, đơn giá, số lượng và thành tiền.

Yêu cầu chương trình sử dụng danh sách liên kết để chứa thông tin các mặt hàng và đọc/ghi từ file văn bản trên đĩa.