Điểm giữa kỳ THDC lớp sáng thứ 5 kỳ 20151

Điểm chưa cộng

Điểm cuối kỳ CTDLGT SIE (chưa cộng cho những bạn chưa đủ 10)

Hạn cuối bảo vệ là sáng thứ 2 tuần tới lúc 11h00 tại 602 nhà B1

Điểm giữa kỳ THDC lớp chiều thứ 2 (chưa cộng)

Điểm giữa kỳ CTDLGT lớp LTU

Điểm chưa cộng!

Một số bài tập cộng điêm môn THDC 20151

Bài 1. Nhập vào một số nguyên, hãy in ra số đó theo cách nhóm theo bộ 3 số
VD. nhập vào 123456789 thì in ra 123,456,789
Nhập vào 12345 thì in ra 12,345

Bài 2, Nhập vào một chuỗi số, hãy kiểm tra xem đó có phải là một SDT di động hợp lệ hay không. (Kiểu nhập vào nên là xâu ký tự)

Bài 3. Nhập vào một số nguyên có 3 tới 9 chữ số, hãy in ra màn hình cách đọc số nguyên đó
VD. 112 ==> mot tram muoi hai
104 ==> mot tram le bon
12345 ==> muoi hai nghin ba tram bon muoi nam

Bài 4. Nhập vào một số nguyên, hãy in ra màn hình xem số đó được tạo nên từ các chữ số nào.
VD 123123123 thì in ra các chữ số tạo nên số đó là 1 2 3

Bài 5. Nhập vào một đoạn văn bản từ bàn phím, hãy in ra màn hình những từ có ký tự được in hoa.
VD. At first, researchers did not see an obvious relationship between coffee consumption and death rates. Study participants who drank between less than a cup of coffee and three cups a day had 5% to 9% lower risk of dying than those who drank no coffee. Those who drank more than three cups a day did not see any benefit. The finding was murky, like previous studies, some of which suggested a benefit and some did not.

Thì in ra màn hình  At, Study, Those, The

Bài 6. Nhập vào một câu xâu, hãy chuẩn hóa xâu đó sao cho

• Bắt đầu và kết thúc không được có dấu các trống
• Không có quá 2 dấu cách trống giữa 2 từ liên tiếp

Bài 7.  Nhập vào một địa chỉ email, kiểm tra xem đó có phải là email hợp lệ hay không.
VD email hợp lệ abcd@efgh.com

Bài 8. Nhập vào một mảng xâu ký tự biểu diễn họ tên của các thành viên trong lớp (số thành viên không quá 100). Hay sắp xếp và in ra danh sách sao cho họ tên theo thứ tự ABC

Bài 9 (2 Đ). Nhập vào một mảng xâu ký tự biểu diễn họ tên của các thành viên trong lớp (số thành viên không quá 100). Hay sắp xếp và in ra danh sách sao cho tên các thành viên theo thứ tự ABC

Bài 10. Nhập vào một đoạn văn bản gồm chữ cái và chữ số, dấu cách. Hãy thống kê tần số xuất hiện của các ký tự trong văn bản và in ra các ký tự theo thứ tự tần số xuất hiện giảm dần.
Chú ý: Có phân biệt ký tự hoa và thường

Bài 11. 

Một số bài code VD trên lớp

#include<stdio.h>
#include <conio.h>


// minh hoa toan tu logic tren bit
int main1()
{
int a = 5, b = 17;
// 5 = 0000 0000 0000 0000 0000 0000 0000 0101
// 17 = 0000 0000 0000 0000 0000 0000 0001 0001
//5^17 = 0000 0000 0000 0000 0000 0000 0001 0100

//5|17 = 0000 0000 0000 0000 0000 0000 0001 0101
//5&17 = 0000 0000 0000 0000 0000 0000 0000 0001
/*int c = a^b;
printf("%d ^ %d = %d", a, b, c);*/

/*
// 5 = 0000 0000 0000 0000 0000 0000 0000 0101
//~5 = 1111 1111 1111 1111 1111 1111 1111 1010
int d = ~a;
printf("~%d = %d", a, d);
*/
// 5 = 0000 0000 0000 0000 0000 0000 0000 0101
//5<<2 = 0000 0000 0000 0000 0000 0000 0001 0100
int d = a<<2;
printf("%d<<2 = %d", a, d);

_getch();
return 0;
}

========================================================
#include <stdio.h>
#include <stdlib.h>


// int ra man hinh co quy cach
int main2()
{
printf("1234567890123456789012345678901234567890\n");
printf("%5c\n", 'A');
printf("%-5c\n", 'A');
/*
printf("%f\n", 34.2);
printf("%7.2f\n", 34.2);
printf("%-7.2f\n", 34.2);
printf("%7.2f\n", 34.256);
printf("%.2f\n", 34.256);
*/
/*
printf("%5d\n", 4);
printf("%-5d\n", 4);
printf("%-5d\n", 123456);
*/
system("pause");
return 0;
}
========================================================
#include <stdio.h>
#include <stdlib.h>

// minh hoa if..else
int main3()
{
//1 nhap so kwh tieu thu
//2 tinh va in ra gia theo cong thuc
int soKwh; // so kwh
printf("Nhap vao so Kwh:");
scanf_s("%d", &soKwh);

int tien;
if (soKwh <= 50)
tien = soKwh * 500;
else if (soKwh <= 100)
tien = 50 * 500 + (soKwh - 50) * 1000;
else
tien = 50 * 500 +50*1000+ (soKwh - 100) * 2000;

printf("Tien phai tra cho so %d kwh la %d\n", soKwh, tien);

system("pause");
return 0;
}
========================================================

#include <stdio.h>
#include <stdlib.h>

// minh hoa switch..case
int main()
{
//1 nhap vao thang va in ra so ngay
int thang;
printf("Nhap vao thang can tra cuu:");
scanf_s("%i", &thang);
switch (thang)
{
case 2: printf("Thang co 28/29 ngay\n");
//break;
case 4: case 6: case 9: case 11: printf("Thang co 30 ngay\n");
break;
case 1: case 3: case 5: case 7: case 8: case 10: case 12:
printf("Thang co 31 ngay\n");
break;
default:
printf("%i la thang khong hop le\n", thang);
}

system("pause");
return 0;
}
========================================================
/*
Nhap vao mot so nguyen,
tinh tong cac chu so cua so nguyen do
VD: 1234 -> tong la 10
*/
#include <stdio.h>
#include <stdlib.h>

int main() {
int n, tong;
printf("Nhap vao mot so nguyen:");
scanf_s("%d", &n);

//tach tung chu so cua so nguyen? vd 1234
// chia lay phan du cho 10, (ta duoc 4)
//phan con lai la so chia lay phan nguyen cho 10 (duoc 123)
// lap toi khi phan nguyen bang 0 thi dung

/*
1234 ==> 123 va 4
123 ==> 12 va 3
12 ==> 1 va 2
1 ==> 0 va 1
*/
tong = 0;
int count=0;
while (n > 0)
{
/*count++;
printf("lan lap %d\n", count);
printf("Chu so don vi: %d\n", n % 10);
printf("So nguyen con lai: %d\n", n / 10);*/

tong = tong + n % 10;
n = n / 10;
}

printf("Tong cua cac chu so tao nen so la %d\n", tong);
system("pause");
return 0;
}
======================================================
/*
minh hoa switch .. case
*/
#include <stdio.h>
#include <stdlib.h>

int main4()
{
/*
nhap vao mot tuoi di hoc, va in ra trinh do va
cap hoc tuong ung
VD. 1-3 : mam non
4-5: mau giao
6-10: pho thong co so (tieu hoc)
11-15: trung hoc co so (trung hoc)
16-18: trung hoc pho thong (pho thong)
19-23: dai hoc
24->100: truong doi
*/
int n; // n>=1 va n<=100
printf("Nhap vao do tuoi:");
scanf_s("%d", &n);
while (n < 1 || n>100)
{
printf("Do tuoi khong hop le, nhap lai do tuoi:");
scanf_s("%d", &n);
}

if(n<=3)
printf("Hoc truong mam non");
else if(n<=5) //n>3 AND n<=5
printf("Hoc truong mau giao");
else if(n<=10)
printf("Hoc truong tieu hoc");
else if(n<=15)
printf("Hoc truong trung hoc");
else if(n<=18)
printf("Hoc truong pho thong");
else if (n <= 23)
printf("Hoc truong dai hoc");
else
printf("Hoc truong doi");

printf("\n");
system("pause");
return 0;
}

==================================================
/*
minh hoa switch .. case
*/
#include <stdio.h>
#include <stdlib.h>

int main3()
{
/*
nhap vao mot tuoi di hoc, va in ra trinh do va
cap hoc tuong ung
VD. 1-3 : mam non
4-5: mau giao
6-10: pho thong co so (tieu hoc)
11-15: trung hoc co so (trung hoc)
16-18: trung hoc pho thong (pho thong)
19-23: dai hoc
24->100: truong doi
*/
int n; // n>=1 va n<=100
printf("Nhap vao do tuoi:");
scanf_s("%d", &n);
while (n < 1 || n>100)
{
printf("Do tuoi khong hop le, nhap lai do tuoi:");
scanf_s("%d", &n);
}

switch (n)
{
case 1: case 2: case 3:
printf("Hoc truong mam non");
break;
case 4: case 5:
printf("Hoc truong mau giao");
break;
case 6: case 7: case 8: case 9: case 10:
printf("Hoc truong tieu hoc");
break;
case 11: case 12: case 13: case 14: case 15:
printf("Hoc truong trung hoc");
break;
default:
printf("Hoc truong doi");
break;
}
printf("\n");
system("pause");
return 0;
}

========================================================

#include <stdio.h>
#include <stdlib.h>

// minh hoa break, continue
int main()
{
/*
for (int i = 0; i < 10; i++)
for (int j = 1; j <= 10000; j++)
{
printf("Vong lap i = %d, j = %d\n", i, j);
if (j >= 5) break; //chi co tac dung voi vong lap cua j
}
*/
for (int i = 0; i < 5; i++)
for (int j = 1; j <= 20; j++)
{
if (j % 5) continue; //chi co tac dung voi vong lap cua j
//bo qua lenh phia sau khi
//j khong chia het cho 5
printf("Vong lap i = %d, j = %d\n", i, j);

}

system("pause");
return 0;
}

==================================================

#include <stdio.h>
#include <stdlib.h>

// minh hoa mang phan tu kieu so thuc (n<=100)
// 1. nhap mang
// 2. tim min, max
// 3. sap xep mang va in ra theo thu tu tang va giam dan
//  (cung voi mang ban dau) ==> tao ra mang copy
int main()
{
double A[100], B[100];
int n;

//0<n va n<=100
printf("Nhap vao so phan tu cua mang:");
scanf_s("%d", &n);
while (n<=0 || n>100)
{
printf("Hay nhap nhap so luong hop le:");
scanf_s("%d", &n);
}

//nhap vao mang
printf("Nhap vao gia tri tung phan tu:\n");
for (int i = 0; i < n; i++)
{
printf("A[%d]=", i);
scanf_s("%lf", &A[i]);
}

// tim min va max
double max=A[0];
for (int i = 0; i < n; i++)
{
if (max < A[i]) max = A[i];
}

double min = A[0];
for (int i = 0; i < n; i++)
{
if (min > A[i]) min = A[i];
}

printf("Gia tri lon nhat la %.2lf\n", max);
printf("Gia tri nho nhat la %.2lf\n", min);

// tao ban copy cua mang ban dau
for (int i = 0; i < n; i++)
B[i] = A[i];

for (int i = n; i >= 2; i--)
for (int j = 0; j < i - 1; j++)
{
if (A[j] > A[j + 1])
{
double phu = A[j];
A[j] = A[j + 1];
A[j + 1] = phu;
}
}

printf("Mang ban dau: \n");
for (int i = 0; i < n; i++)
{
printf("%.2lf, ", B[i]);
}
printf("\n");
printf("Mang sau khi sap xep: \n");
for (int i = 0; i < n; i++)
{
printf("%.2lf, ", A[i]);
}
printf("\n");
system("pause");
return 0;
}
=======================================================
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/*
nhap vao mot ten
tach ra ho va ten

VD. Nguyen Tan Dung
Ho: Nguyen Tan
Ten : Dung
*/
int main()
{
char fullname[50];
//nhap vao ten
printf("Nhap vao ten:");

gets_s(fullname); //nhap duoc xau co dau cach trong


//scanf_s("%s", fullname); // khong co dau &
//==> khong nhap duoc xau co dau cach trong

printf("Xau vua nhap: %s\n", fullname);

//Tach ra phan ten va phan Ho
//1. Tim vi tri dau cach trong cuoi cung
int vitri = 0;
int i = 0;
while (i < strlen(fullname))
{
if (fullname[i] == ' ')vitri = i;
i++;
}

printf("Vi tri dau cach trong cuoi cung: %d\n", vitri);
// Phan Ho tu vi tri 0 toi Dau cach trong cuoi cung
char surname[50];
printf("Ho: ");
for (i = 0; i < vitri; i++)
{
surname[i] = fullname[i];
}
surname[i] = '\0';
printf("%s", surname);

printf("\n");

// Phan ten tu dau cach trong cuoi cung toi het
printf("Ten: ");

// in tung ky tu!, dung strncpy
for (i = vitri+1; i < strlen(fullname); i++)
printf("%c", fullname[i]);
printf("\n");
system("pause");
return 0;
}

============================================================
#include <stdlib.h>
#include <stdio.h>

/*
minh hoa mang struct dung luu tru thong tin sinh vien
*/
typedef struct TTSV
{
char hoten[50];
char shsv[15];
float gk, th, ck;
float hp; //tinh theo cong thuc 0.2*(gk+th) + 0.6*ck
} SV;

//dung typedef de dinh nghia lai ten cau truc cho ngan
//typedef struct TTSV SV;

int main9()
{
SV lop[100];
int n; // so thanh vien thuc su (n>0 va n<=100)

//nhap thong tin cac thanh vien lop
printf("Nhap so thanh vien cua lop:");
scanf_s("%d", &n);
while (n <= 0 || n > 100)
{
printf("Hay nhap so luong hop le:");
scanf_s("%d", &n);
}
char buffer[100];

// dung vong lap for der nhap thong tin tung thanh vien
for (int i = 0; i < n; i++)
{
gets_s(buffer);
printf("Nhap vao thong tin thanh vien thu %d:\n", i + 1);
printf("Ho ten:"); fflush(stdin);// do bo nho dem truoc khi nhap xau
gets_s(lop[i].hoten);

printf("SHSV:"); fflush(stdin);// do bo nho dem truoc khi nhap xau
gets_s(lop[i].shsv);

printf("Diem giua ky:");
scanf_s("%f", &lop[i].gk);

printf("Diem thuc hanh:");
scanf_s("%f", &lop[i].th);

printf("Diem cuoi ky:");
scanf_s("%f", &lop[i].ck);
}

// tinh diem hoc phan
for (int i = 0; i < n; i++)
{
if (lop[i].gk < 3 || lop[i].th < 3)
lop[i].hp = 0;
else
lop[i].hp = 0.2*(lop[i].gk + lop[i].th) + 0.6*lop[i].ck;
}

//dem so luong sinh vien khong qua va in ra thong tin sinh vien qua
printf("Ket qua hoc tap:\n");
int sosinhvienkodat = 0;
printf("%30s %10s %4s %4s %4s %4s\n","Ho ten   ","SHSV  ","GK ","TH ","CK ","HP ");
for (int i = 0; i < n; i++)
{
if (lop[i].hp < 4) sosinhvienkodat++;
else
{
printf("%30s %10s %.2f %.2f %.2f %.2f\n", lop[i].hoten,
lop[i].shsv, lop[i].gk, lop[i].th, lop[i].ck, lop[i].hp);
}
}
printf("Tong so sinh vien khong dat: %d\n", sosinhvienkodat);

// sap xep va in ra thong tin sinh vien theo diem hoc phan giam dan
for (int i = n; i >= 2; i--)
for (int j = 0; j < i-1; j++)
{
if (lop[j].hp < lop[j + 1].hp)
{
SV phu = lop[j];
lop[j] = lop[j + 1];
lop[j + 1] = phu;
}
}
printf("\n========================================\n");
printf("Danh sach sinh vien voi diem hp giam dan:\n\n");
printf("%30s %10s %4s %4s %4s %4s\n", "Ho ten   ", "SHSV  ", "GK ", "TH ", "CK ", "HP ");
for (int i = 0; i < n; i++)
{
printf("%30s %10s %.2f %.2f %.2f %.2f\n", lop[i].hoten,
lop[i].shsv, lop[i].gk, lop[i].th, lop[i].ck, lop[i].hp);
}
system("pause");
return 0;
}

====================================================================

#include <stdlib.h>

#include <stdio.h>

#include <math.h>

/*

minh hoa ham xu ly tam giac

*/

double tinhChuvi(double a, double b, double c)

{

if (a <= 0 || b <= 0 || c <= 0) return -1; //Canh khong hop le

if (a + b <= c || b + c <= a || a + c <= b)

return -2;// khong tao thanh tam giac

return a + b + c;

}

double tinhDienTich(double a, double b, double c)

{

if (a <= 0 || b <= 0 || c <= 0) return -1; //Canh khong hop le

if (a + b <= c || b + c <= a || a + c <= b) 

return -2;// khong tao thanh tam giac

double p = tinhChuvi(a, b, c) / 2;

return sqrt(p*(p - a)*(p - b)*(p - c));

}

int main10()

{

double x, y, z;

printf("Nhap vao do dai 3 canh tam giac:");

scanf_s("%lf%lf%lf", &x, &y, &z);

if (tinhChuvi(x, y, z) < 0) printf("Tam giac khong hop le!\n");

else printf("Chu vi tam giac : %lf\n", tinhChuvi(x, y, z));

if (tinhDienTich(x, y, z) < 0) printf("Tam giac khong hop le!\n");

else printf("Dien tich tam giac : %lf\n", tinhDienTich(x, y, z));

system("pause");

return 0;

}

=========================================================

#include <stdio.h>

#include <stdlib.h>

/*

mih hoa doc so co tu 1->3 chu so

*/

//hàm đọc chữ số

void docChuSo(int a)

{

if (a == 0) printf("khong");

else if (a == 1)printf("mot");

else if (a == 2)printf("hai");

else if (a == 3)printf("ba");

else if (a == 4)printf("bon");

else if (a == 5)printf("nam");

else if (a == 6)printf("sau");

else if (a == 7)printf("bay");

else if (a == 8)printf("tam");

else if (a == 9)printf("chin");

else printf("ERROR!!!");

}

// kiem tra so can doc co phai so tuf 1->3 chu so hay khong

// ham tra ve -1 neu khong hop le, nguoc lai tra ve 0

int kiemTra(int n)

{

if (n>999 || n<-999) return -1;

else return 0;

}

// doc so co tu 1->3 chu so

void docSo(int n)

{

int a, b, c;// phan tram, chuc va don vi

if (kiemTra(n) == -1)

printf("Loi! So khong hop le.\n");

else

{

if (n<0) {

printf("am ");

n = -n;

}

c = n % 10; n = n / 10;

b = n % 10; n = n / 10;

a = n % 10;

if (a>0) { docChuSo(a); printf(" tram "); }

if (a>0 && b == 0 && c!=0)printf("le ");

if (b == 1) { printf("muoi "); }

if (b>1) { docChuSo(b); printf(" muoi "); }

if(c!=0) docChuSo(c);  

printf("\n");

}

}

int main11(void)

{

docSo(-115);

docSo(-125);

docSo(-105);

docSo(-5);

docSo(25);

docSo(15);

docSo(110);

docSo(100);

docSo(10);

system("pause");

return 0;

}

===================================================

#include <stdio.h>

#include <stdlib.h>

void increase(int x)

{

x = x * 2;

}

void increase(int A[], int size)

{

for (int i = 0; i < size; i++)

A[i] = A[i] * 2;

}

void printArray(int A[], int size)

{

for (int i = 0; i < size; i++)

printf("%d ", A[i]);

}

int main12()

{

int a = 5;

printf("Gia tri ban dau cua a:%d\n", a);

increase(a);

printf("Gia tri cua a sau khi goi ham:%d\n", a);

int A[] = { 1,3,5,7,4 };

printf("Mang ban dau:"); 

printArray(A, 5);

printf("\n");

increase(A, 5);

printf("Mang sau khi goi ham:");

printArray(A, 5);

printf("\n");

system("pause");

return 0;

}

=========================================================

#include <stdio.h>

#include <stdlib.h>

void sort(int a[], int n)

{

int i, j, temp;

for (i = 0; i < n - 1; ++i)

for (j = i + 1; j < n; ++j)

if (a[i] < a[j]) {

temp = a[i];

a[i] = a[j];

a[j] = temp;

}

}

void display(int A[], int size)

{

int i;

for (i = 0; i<size; i++)

printf("%d ", A[i]);

printf("\n");

}

int main(void)

{

int i;

int array[16] = { 34, -5, 6, 0, 12, 100, 56, 22,

44, -3, -9, 12, 17, 22, 6, 11 };

printf("Mang ban dau:\n");

display(array, 16);

sort(array, 16);

printf("Mang sau khi sap xep:\n");

display(array, 16);

system("pause");

return 0;

}

Một số đề kiểm tra cũ môn THDC

Bài tập CTDL Cuối kỳ SIE 20151

Bài 5 điểm

Bài 1. Cho một tập văn bản tiếng Anh ( 200 văn bản)

Hãy thống kê tần số các n-gram có trong văn bản (từ 1-gram, 2-gram tới 5-gram) và in ra màn hình các gram có

• Tần số xuất hiện nhiều nhất trên toàn bộ văn bản (mỗi gram có thể được tính nhiều lần nếu xuất hiện trong cùng 1 văn bản)
• Xuất hiện trong nhiều văn bản nhất (mỗi gram chỉ được tính xuất hiện trong 1 văn bản 1 lần)

Chú ý: 

1. các gram được tính trong phạm vi 1 câu hoặc một phần của câu và được ngăn cách bằng các dấu câu như . , " : ; ? !

The military previously called the bombing an incident of "collateral damage," a description Campbell's story would seem to support.

thì các phần của câu gồm 

The military previously called the bombing an incident of 

collateral damage

a description Campbell's story would seem to support

2. Có một số ngoại lệ như từ viết tắt và số

We have now learned that on October 3, Afghan forces advised that they were taking fire from enemy positions and asked for air support from U.S. forces," he said Monday

U.S là một gram chứ ko tách thành 2

So far this year, more than 130,000 migrants and refugees have crossed to Europe from the north African coast. More than 2,700 have drowned.

số tính liền chứ không ngăn cách ra

Bài 2.

Cho một tập văn bản tiếng Anh ( 5000 văn bản)

• Thống kê tần số các n-gram có trong văn bản (từ 1-gram).
• Hai gram được coi là tương đồng nhau nếu nó xuất hiện cùng nhau trong nhiều văn bản. Hãy nhập vào 2 1-gram và in ra màn hình độ tương đồng của 2 1-gram đó

độ tương đồng của 2 gram đươc tính bằng 

#số văn bản chứa đông thời 2 gram đó / #văn bản chứa 1 trong 2 gram

Chú ý: Ta chỉ xét 1-gram trong bài toán này

Một số yêu cầu thêm như:

• In ra văn bản chứa 1 hoặc cả 2 gram
• Chỉ xét các văn bản có độ dài ít hơn 500 từ
• chỉ xét các văn bản mà gram đó xuất hiện nhiều hơn 2 lần

Bài 3. Cho một tập văn bản tiếng Anh ( 5000 văn bản)

• Thống kê tần số các n-gram có trong văn bản (từ 1-gram), và số lượng văn bản mà mỗi gram xuất hiện.
• Độ quan trọng của một gram được tính bằng TF-IDF = (tần số xuất hiện của từ/tổng số từ)*log(tổng số văn bản/số văn bản từ đó xuất hiện). Từ nào có TF-IDF lớn là từ quan trọng.
• Sắp xếp độ quan trọng của các từ theo TF-IDF và chỉ lấy 30% từ có TF-IDF quan trọng nhất.  

FILE văn bản:
https://drive.google.com/file/d/0B5nb3v94xY_WaV9PejV0MUx6dDg/view?usp=sharing

Bài tập giữa kỳ CTDLGT SIE 20151

Loại bài 1 điểm

Bài 1. Cho 2 số nguyên lớn (số lượng chữ số từ 10 tới 1000). Hãy viết hàm thực hiện các phép toán cơ bản như cộng, trừ, nhân, chia hai số nguyên này.

VD. một số có thể là 123454124545887154956584454878544648454


Bài 2. Một đa thức bậc n có thể được biểu diễn bằng một danh sách liên kết đơn

P(n) = a0 + a1*n + a2*x^2 + .. + an*x^n

Hãy viết các hàm thực hiện việc cộng, trừ và nhân hai đa thức bậc n là P(n) và Q(n).
Chú ý. Các đa thức này cần được biểu diễn bằng danh sách liên kết đơn

Bài 3. Đầu vào là một xâu ký tự
Hãy tìm và đưa ra màn hình các ký tự cơ bản để tạo nên xâu ban đầu

VD. Xâu đầu vào là abbcacfcba
Thì các ký tự cơ bản để tạo ra xâu là abcf

Bài 4. Cho một danh sách số nguyên và một giá trị x. Hãy xây dựng chương trình tìm và in ra màn hình các phần tử chênh lệch với x giá trị k. một cách nhanh nhất.

VD. Danh sách ban đầu 1,2,5,3,7,4
với x = 3 và k =1 thì chương trình sẽ in ra 4 và 5

Loại bài 2 điểm

Bài 1. Cho một dãy số nguyên, hãy đưa ra các khoảng liên tục trong dãy
VD. Dãy đầu vào là 1,8,9,2,3,11,5,7,12
Thì đầu ra là 1-3, 5, 7-9, 11-12

Gợi ý bài tập THDC

Gợi ý bài tập THDC

Bài tập giữa kỳ và cuối kỳ môn khai phá dữ liệu

Bài tập giữa kỳ


Bài tập cuối kỳ

Bài tập lớn CTDLGT cho lớp VUW-IT

Bài 1. (Phát triển từ bài tìm danh từ riêng) Tìm xem danh từ riêng nào được đề cập đến nhiều nhất trong một tập văn bản ( khoảng 50-100 văn bản).

• Các danh từ riêng bao gồm cả danh từ nối và không được nối.

Từ đó đưa ra xem danh từ nào đang là hot trend. (các danh từ được đề cập đến nhiều nhất trong nhiều văn bản)

• Chú ý việc các danh từ viết tắt (cùng xuất hiện trong văn bản)

Tập văn bản (50-100) văn bản do sinh viên lấy từ các nguồn như BBC.com hoặc CNNNews.com hoặc VOANews.com

Có thể sử dụng chung tập dữ liệu nếu cùng làm một bài (Miễn là không dùng chung code :D )

Bài 2. Tìm tập danh từ riêng theo chủ đề

Đầu vào là một tập văn bản tiếng Anh thuộc nhiều chủ đề (>=3 chủ đề), mỗi chủ đề khoảng (10-20 văn bản). Các chủ đề như

• Thể thao
• Chính trị
• Khoa học công nghệ
• Kinh doanh

Với mỗi một chủ đề ta tìm các danh từ riêng và đưa ra tập danh từ riêng đăc jtrung cho từng chủ đề dựa trên tần số xuất hiện.

Danh từ riêng nào xuất hiện đồng thời trong nhiều chủ đề khác nhau ?

Danh từ đó có đặc điểm gì ?

Bài tập giữa kỳ cho lớp VUW-IT 20142

Bài 1. Thống kê tần số xuất hiện và vị trí xuất hiện (theo câu hoặc dòng) của các danh từ riêng trong văn văn tiếng Anh.

Chương trình đọc vào 1 trong 5 file văn bản đính kèm, hiển thị ra các danh từ riêng trong văn bản đó.

Chương trình cho phép người dùng nhập vào một danh từ riêng, in ra màn hình kết quả:

• Tần số xuất hiện
• Vị trí xuất hiện

Nếu danh từ đó có xuất hiện trong văn bản đã cho.

Chú ý: Các danh từ riêng nếu đứng cạnh nhau thì cần được nối lại với nhau

Bài 2. Thống kê tần số xuất hiện và vị trí xuất hiện (theo câu hoặc dòng) của các từ trong văn văn tiếng Anh.

Chương trình đọc vào 1 trong 5 file văn bản đính kèm, hiển thị ra :

• Các từ
• Tần số xuất hiện
• Độ dài từ và tần số của các từ theo độ dài 9độ dài của 1 từ là số ký tự trong từ đó)

Chương trình cho phép người dùng nhập vào một từ, in ra màn hình kết quả:

• Tần số xuất hiện
• Vị trí xuất hiện

Nếu từ đó có xuất hiện trong văn bản đã cho.

Có lựa chọn thống kê phân loại chữ hoa/thường hoặc không phân loại hoa/thường.

Chú ý. Các từ trong văn bản được ngăn cách nhau bởi dấu cách trống.

Bài 3. Cho một văn bản và một tập từ điển tiếng Anh. Kiểm tra xem trong văn bản tiếng anh đó có bao nhiêu từ lỗi chính tả (bỏ qua những từ có chữ hoa, hoặc chữ số).

Những từ lỗi là những từ không có trong từ điển.

Nếu đề xuất được phương án sửa từ sai sẽ được cộng điểm.

Tài liệu download tại

https://www.dropbox.com/s/uitdzw9q84x093o/VUW-IT%2020142.rar?dl=0

Bài tập lớn CTDL & GT cho lớp chiều thứ 2 (tiết 1-4)

Bài tập lớn CTDL & GT cho lớp chiều thứ 2 (tiết 1-4)

Yêu cầu chung:

• Sinh viên tự đề xuất thuật toán dựa trên yêu cầu của đề bài
• Tự chọn CTDL phù hợp và giải thích vì sao mình chọn CTDL đó
• Đánh giá hiệu quả về thời gian và bộ nhớ của thuật toán 

Đây là các đề bài xuất phát từ yêu cầu thực tế, rất khó có thuật toán cho kết quả chính xác 100% (Điểm đánh giá sẽ ưu tiên các thuật toán nào cho kết quả tốt hơn)

Dữ liệu đầu vào:

Dữ liệu cho tất cả cacsc bài tập ở dưới được Download theo link sau: https://www.dropbox.com/s/k7y57sqsy5qzrkl/TechCrunch_Files.rar?dl=0

• Các tập dữ liệu đầu vào được lấy từ các bài viết mới gần đây trên trang công nghệ TechCrunch, và ở dạng ngôn ngữ tiếng Anh.
• Các bài viết được tổ chức thành từng file riêng theo dạng 0001.txt, 0002.txt,... (có khoảng gần 5K bài viết)
• Format của mỗi bài viết gồm
• Dòng đầu tiên là tiêu đề : title
• Dòng tiếp là tác giả: author
• Dòng tiếp là ngày được xuất bản : publish date
• Các dòng tiếp theo là nội dung bài viết 
• Trong bài viết có nhiều ngoại lệ (exception), sinh viên nên tự phát hiện và loại bỏ để tăng độ chính xác (VD. các thông tin phụ ở cuối bài viết) 

Dữ liệu đầu ra:

• Sinh viên nên tổ chức dữ liệu đầu ra dưới dạng file văn bản để dễ theo dõi

Sinh viên có thể dùng các hệ quản trị CSDL đễ hỗ trợ tổ chức và lưu trữ dữ liệu (tuy nhiên điều này không được khuyến khích)

Bài 1. Phát hiện các danh từ riêng, tên riêng trong các văn bản

Sắp xếp các danh từ này theo tần số xuất hiện trên toàn bộ tập văn bản, và trên số lượng văn bản mà nó xuất hiện

Hai cặp danh từ được coi là cùng xuất hiện nếu chúng xuất hiện gần nhau (trong khoảng cách 2-3 câu)

Những danh từ nào có tần số xuất hiện nhiều nhất?

• Trên toàn bộ tập văn bản (mỗi từ được tính nhiều lần nếu xuất hiện nhiều lần ở cùng 1 văn bản)
• Trên nhiều văn bản nhất (mỗi từ chỉ được tính 1 lần xuất hiện trong 1 văn bản)

Cặp danh từ nào được xuất hiện nhiều nhất?

VD với văn bản

A recent article in TechCrunch characterized nascent upstarts in the restaurant industry as wide-eyed idealists with little reality of the harsh, high-touch operating environment in which they operate. Having worked in the tech, food and health worlds for most of my career, I believe the article misrepresented the significant progress being made across the industry. On almost every front within hospitality — be it point of sale, loyalty, delivery or sourcing — change is in the air.

For all the talk of the Aloha and MICROS point of sale (POS) systems dominanting in restaurants, a bevy of newcomers have been making inroads. Square, with its slick reader and now retail POS terminal, carries the most gravitas among the mobile POS companies for good reason: it inks deals with large retailers: Starbucks in 2012, then Whole Foods, Uniqlo and Godiva in 2014. Granted, none of these establishments switched over an entire store to Square, but these relationships suggest large retailers will embrace new technology.

Danh từ riêng được in đậm

• là các từ có ít nhất 1 chữ in hoa
• Không chấp nhận các từ ở đầu câu hoặc đầu đoạn
• Các từ hoa liền nhau (ngăn cách bởi 1 dấu cách trống) nên nối thành 1 từ dài
• Các từ hoa liền nhau ngăn cách từ >= 2 dấu cách trống thì nên tách riêng ra.
• Nếu mà phân biệt được các từ viết tắt thì càng tốt (các từ mà tất cả các ký tự đều viết hoa)

Cặp danh từ trong phạm vi 2 câu là

• {Aloha - MICROS} - POS
• POS - {Starbucks - Whole Foods - Uniqlo - Godiva} 
• {Starbucks - Whole Foods - Uniqlo - Godiva} - Square

Bài 2. Thống kê tên thương hiệu (sản phẩm)/ công ty được đề cập trong bài báo

Với các danh từ riêng trong bài báo ta cần phân ra được thành

• Tên địa điểm, vị trí
• Tên người
• Tên sản phẩm/ tên công ty

Làm sao phân biệt được tên địa điểm, tên người với các tên riêng khác ?

• Tên địa điểm, vị trí, thời gian: gần đó thường có các giới từ như at, in, on
• Tên người: gần đó thường có sở hữu cách:'s hoặc of
• Tên sản phẩm/ tên công ty:

Nếu không làm được ==> tự xây dựng từ điển tên công ty/ sản phẩm bằng tay (không khải thi cho lắm nếu chạy trên dữ liệu thực tế - khoảng vài tỷ bài viết)

Công ty / sản phẩm nào được đề cập đến nhiều nhất ?

Bài 3. sản phẩm nào là của công ty nào được đề cập trong các bài báo?

VD. Apple : iphone, ipad,....

Làm thế nào biết được sản phẩm nào của công ty nào?

• Phát hiện tên công ty
• Tên sản phẩm
• Thường có các từ đặc trưng để kết nối như: a product of, a service of,....

Bài 4. Tìm các bài viết đánh giá tốt hoặc xấu về một sản phẩm/ thương hiệu của công ty

• Phát hiện ra các tên công ty, tên sản phẩm
• Các tính từ đánh giá như : good, bad, worse,, (sinh viên tự xây dựng từ điển) 

Các tính từ này phải nằm gần các câu chứa các danh từ thương hiệu (trong phạm vi khoảng 2-3 câu)

Bài 5. Hai văn bản được coi là có liên quan đến nhau nếu có tập danh từ riêng trùng nhau nhiều

• Tìm các tập danh từ riêng của 2 văn bản
• Xác định tập danh từ riêng trùng nhau của 2 văn bản
• Quyết định xem 2 văn bản có liên quan đến nhau hay không dựa trên ngưỡng (số lượng từ trùng nhau trên tổng số danh từ riêng của cả 2 văn bản). Ngưỡng này do sinh viên tự đề xuất!

Với 1 bài đang đọc, hãy đưa ra danh sách các bài viết có liên quan (được sắp xếp theo thứ tự độ liên quan giảm dần)

Để đảm bảo yêu cầu về thời gian xử lý, sinh viên có thể cần tính trước độ liên quan của các bài viết và đưa vào file tạm.

Bài 6. n-gram là các cụm từ liên tiếp nhau (ở đây ta quan tâm tới 2-gram và 3-gram)

Ta chỉ xét các n-gram trong phạm vi một bộ phận câu (bị ngăn cách bởi các dấu câu như  dấu ! dấu . dấu : dấu - ) 

Dấu , được bỏ qua

VD. Với văn bản 

I believe the article misrepresented the significant progress being made across the industry. On almost every front within hospitality — be it point of sale, loyalty, delivery or sourcing — change is in the air.

Ta có các bộ phận câu như

• I believe the article misrepresented the significant progress being made across the industry
• On almost every front within hospitality
• be it point of sale, loyalty, delivery or sourcing
• change is in the air

Với câu 

• change is in the air

Ta có các 3-gram là:

1. change is in
2. is in the
3. in the air

Hai văn bản liên quan đến nhau (thường là trùng nhau hoặc cùng một chủ đề) nếu có số lượng n-gram trùng nhau nhiều.

Hãy tìm các văn bản trùng/ có liên quan đến văn bản hiện tại dựa trên 3-gram (hoặc 2-gram)

Ngưỡng trùng do sinh viên tự đề xuất.

Danh sách nộp bài tập tuần lớp CTDLGT chiều thứ 2 [Update hàng tuần vào CN]