Cheat sheet cho Linux, Emacs và GCC

Cheat sheet cho Linux, Emacs và GCC

• Linux:
• Emacs
• Gcc

Links:

https://drive.google.com/folderview?id=0B5nb3v94xY_WT3YtTHJwVWxWcDg&usp=sharing

Bài tập giữa kỳ môn CTDL GT 20152

Bài tập giữa kỳ

Bài 1. Hoàn thiện hàm tìm dãy tăng dài nhất cài đặt dùng đệ quy

VD. dãy 1, 3, 2, 5, 6, 4, 7, 8, 9, 4, 5, 2, 1, 3, 4

Thì dãy tăng dài nhất là 4, 7, 8, 9 với độ dài 4.

Yêu cầu:

• in ra độ dài và giá trị các phần tử trong dãy tăng
• trong trường hợp có 2 dãy tăng cùng độ dài thì in ra cả 2.

Bài 2. Cho một mảng số nguyên A và một số s. Hãy xây dựng chương trình tìm hai số a,b không trùng nhau trong A sao cho có tổng đúng bằng s.

VD. A[]={1, 3, 5, 7, 6, 4, 2} và s=10 thì chương trình trả về 3 ,7 hoặc 6, 4

Yêu cầu:

• Loại bỏ các cặp số bị trùng

Bài 3. Xâu palindrome là xâu đối xứng
VD adbda hoặc abccba

Cho một xâu bất kỳ, hãy tìm và đưa ra xâu con palindrome dài nhất một cách nhanh nhất

VD. abcdcbbcdbccadbca thì xâu con là palindrome dài nhất là dcbbcd

Yêu cầu:

• Trường hợp có nhiều thì cần in ra tất cả các xâu con palindrome có độ dài dài nhất
• Thực hiện với thời gian O(n)

Bài 4. Chỉ dùng các phép toán -1 (trừ đi 1) và * 2 (nhân với 2), hãy xây dựng thuật toán biến đổi 1 số nguyên n thành 1 số nguyên m một cách nhanh nhất (dùng ít thao tác nhất)

VD. 4 thành 6 cần 2 thao tác là

(4-1)*2

Bài 5. Biểu diễn đa thức bậc n dùng danh sách liên kết đơn

Hãy viết các hàm cộng, trừ, nhân và chia hai đa thức

Bài 6. Xây dựng thuật toán tìm đường đi trong ma trận cho mê cung được mô tả bằng ma trận 20×20 dùng backtracking.

Đầu vào là ô (1,1) và đầu ra là ô (20,20)
Chỉ có thể đi ở các ô có giá trị 1 và theo hướng lên, xuống, trái và qua phải

1100000000000001111
1111111110111110000
0001000110101010000
1111000110101010000
1111000010101010000
0010000110101010000
1111000110101010000
1000000110101011111
1111110110101010001
1111010110101010001
1111010010100000001
1111011101111010001
1111110110101110000
0001000111101111111
1111000110101010001
1110000110101010101
1111000110101010111

Bài 7. Cho một dãy số nguyên A với số lượng phần tử là n
A[]={5,3,4,7,8,9,2,4,5}
Hãy in các dãy con tăng/giảm với độ dài dãy từ 3 đến n
VD. Với mang A trên thì

Dãy tăng độ dài 3 là: 3,4,7 và 7,8,9 và 2,4,5
Dãy tăng độ dài 4 là: 3,4,7,8 và 4,7,8,9
Dãy tăng độ dài 5 là: 3,4,7,8,9

Bài 8. Cho đầu vào là một danh sách các từ (gồm chữ cái và chữ số, có phân biệt chữ hoa và thường). Hãy viết chương trình nhập và giá trị nguyên n và in ra màn hình các từ chỉ khác nhau đúng n ký tự. Các từ ngắn hơn thì được coi là có dấu cách trống phía sau.

VD từ abc và abcde khác nhau 2 ký tự
abD và abcD khác nhau 2 ký tự

Danh sách các từ này được nhập vào từ file input.txt

Bài 9. Cho ma trận chỉ gồm 1 và 0 được nhập vào từ file.
Hãy in ra màn hình diện tích vùng chứa các số 0 lớn nhất

1111111110111110000
0001000110101010000
1111000110101010000
1111000010101010111
0010000111101010000
1111001110101010000
1000001110111111111
1111110110101010001
1111010110101010001
1111010010101010001

Ví dụ với hình trên thì diện tích lớn nhất là 21

Bài 10. Cho hai danh sách các khoảng liên tục. Hãy viết chương trình trộn hai danh sách này để được một danh sách các khoảng liên tục

Đầu vào:
Arr1 = [3-11, 17-25, 58-73];
Arr2 = [6-18, 40-47];

Đầu ra:
Arr3 = [3-25, 40-47, 58-73];

Chú ý: Các khoảng này đã được sắp theo thứ tự tăng dần cho trước

Bài 11. Cho một mảng chứa toàn số 0 và 1 và một giá trị nguyên k. Tìm đoạn con liên tục chứa nhiều số 1 nhất sau khi lật k bit 0 thành 1.

Ví dụ mảng đầu vào là {1,1,0,0,1,1,1,0,1,1}
k = 1 (chỉ được lật 1 bit 0 thành 1)

Độ dài đoạn lớn nhất là 6 (Nếu ta lật bit 0 tại vị trí chỉ số 7, ta sẽ có đoạn con chứa các bit 1 dài nhất là 6)

Bài 12. Xây dựng hàm kiểm tra xem có thể xáo trộn các ký tự trong 1 xâu ký tự đầu vào sao cho hai ký tự liên tiếp không được giống nhau

Ví dụ

apple >> alpep, so valid
b>> b, valid
bb>> bb, invalid/impossible
aab >> aba, valid
aaaabbcc >> acabacab, valid
etc.

Bài 13. Cho đầu vào là 2 xâu ký tự.

• Xâu target chỉ chứa các ký tự chữ cái và số
• xâu pattern chứa các mẫu bao gồm kyws tự chữ cái, chữ số và dâu ? và *

Xây dựng hàm kiểm tra xem xâu target có tuân theo mẫu mô tả bởi xâu pattern hay không.

Dấu ? thay cho 1 ký tự hoặc 1 chữ số
Dấu * thay cho 1 chuỗi ký tự hoặc số (có thể rỗng)

Ví dụ với các trường hợp sau thì hàm trả về giá trị TRUE.

isMatching("abab", "abab")
isMatching("abab", "a**b")
isMatching("ababab", "ab*b")
isMatching("", "*")
isMatching("aaaaaab", "*?*b") 

Đ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.