ݺߣ

ݺߣShare a Scribd company logo

Kiến thức cơ bản

•Download as DOC, PDF•
•
Dũng Hoàngc Nguyễn
Dũng Hoàngc Nguyễn

ok

1 of 4
A. KIẾN THỨC CƠ BẢN 1. Ôn tập tại các kiến thức và bài tập đã học phần NNLT Pascal - Chương Cấu trúc điều khiển - Chương Kiểu dữ liệu có cấu trúc (đặc biệt là Mảng 1, 2 và xâu kí tự) Ví dụ: Mảng 1 chiều chảng hạn … Một số thao tác cơ bản trên mảng một chiều: - Tìm phần tử thoả mãn điều kiện (lớn nhất, nhở nhất, tồn tại, là số nguyên tố, thân thiện, ...) - Tìm dãy con liên tiếp tăng dần, giảm dần, dương, âm dài nhất ... - Tìm dãy con liên tiếp K phần tử có tổng lớn nhất, nhỏ nhất ... - Số lượng các phần tử đôi một khác nhau, phần tử nào có số lượng nhiều, ít nhất - Tìm số nguyên dương bé nhất không xuất hiện trong dãy. 2. Tìm kiếm tuần tự, nhị phân 3. Sắp xếp nổi bọt (buble sort), nhanh (quicksort) và đếm phân phối (countting) 4. Tìm uscln, bscnn của 2 số a và b, của dãy số a1, a2 ...an, hiển thị phân số tối giản 5. Số ước, tổng các ước của số n 6. Số nguyên lớn - Cộng A+B, trừ (A-B), nhân (A x b). A,B nguyên dương lớn (A<B) - So sánh 2 số X và Y X, Y nguyên lớn - Cộng X+Y, Hiệu X-Y B thuộc longint hay int64 7. Dãy số Fibonacy, Catalan 8. Lý thuyết tập hợp Các nguyên lý đếm tổ hợp cơ bản: Nguyên lý cộng, nhân, bù trừ, Dirichle Các cấu hình tổ hợp: Chỉnh hợp lặp, chỉnh hợp không lặp, hoán vị và tổ hợp 9. Lý thuyệt và bài tập duyệt các cấu hình tổ hợp thường gặp – Áp dụng thuật toán vét cạn quay lui để tìm một cấu hình hoặc tất cả các cấu hình (nghiệm) - Chỉnh hợp lặp - Liệt kê các cấu hình chập k của n phần tử - Chỉnh hợp không lặp - Liệt kê các cấu hình chập k của n phần tử - Liệt kê hoán vị n phần tử - Liệt kê các tổ hợp chập k của n pt (k=1..n) - Bài tập ứng dụng SGK (4.1 – 4.10) - Bài toán tối ưu tổ hợp 10. Quy hoạch động cơ bản
B. MỘT SỐ BÀI TẬP VỀ SỐ HỌC 1. Chuyển đổi số n ở cơ số a về cơ số b (đặc biết 2, 10 và 16) - Cho 1 số nguyên không âm ở hệ thập phân, hãy đổi số đó sang dạng biểu diễn của hệ nhị phân, hệ cơ số 8 và hệ 16. - Cho một số ở hệ nhị phân (dữ liệu vào dưới dạng xâu nhị phân). Hãy đổi số đó sang hệ thập phân, hệ cơ số 8 và hệ cơ số 16. - Cho 1 số nguyên không âm N ở hệ thập phân (N<=255), hãy đổi số đó sang dạng xâu nhị phân độ dài 8, nếu không đủ 8 kí tự thì thêm kí tự 0 vào đầu Ví dụ: N=15 thì kết quả là: 00001111 2. Độ cao, độ dày và chiều dài của số nguyên n. Viết chương trình thực hiện: - Tính và hiển thị số n, độ cao H(n), độ dày D(n) và chiều dài L(n) . - Lật số nguyên (input: x = 1234, output: y = 4321). - Số gánh (12321, 2). (H(n) = tổng các chữ số của n, D(n) = tích các chữ số của n, L(n) = số chữ số của n) 3. Số nguyên tố - Kiểm tra tính nguyên tố của số k - Sàng nguyên tố Eratostheme - Liệt kê các số nguyên tố trong [a,b] - Phân tích số n thành các thừa số nguyên tố - Số nguyên tố cùng nhau - Tìm số nguyên tố có cùng độ cao, độ dày hoặc chiều dài 4. Số Fibonaci(n) - Tìm số Fibonacci thứ n>1. trong đó f0=0, f1=1, fn=fn-1 + fn-2 - Phân tích số nguyên M thành tổng các số Fibonaci (số lượng ít nhất) - Tìm các số Fibonaci trong đoạn [A..B] (A<B, tối đa 200 chữ số) Gợi ý: Dãy Fibonacci (chỉ số tính từ 0): 0, 1, 1, 2, 3, 5,… 5. N! - Giai thừa. - Tín n! (n có tối đa 200 chữ số) - Tính số chữ số 0 tận cùng của n! (Ví dụ: n=11, n!=39916800, số chữ số 0 tận cùng là 2) - Tìm chữ số khác 0 của N! (Ví dụ: n=11, n!=39916800, chữ số tận cùng khác 0 là 8) - Cho số p, tìm số mũ k lớn nhất để pk là ước của n! 6. Lũy thừa. Cho 2 số nguyên dương bất kì N ,M(1<=N<=100, 1<=M<=10). Hãy tìm k chữ số cuối cùng của N luỹ thừa M. (NM). 7. Số AMSTRONG Tìm các số có 3 chữ số sao cho tổng lập phương các chữ số bằng chính nó. (Ví dụ số 153=12+52+32). 8. Liệt kê các số hoàn thiện trong đoạn M..N. Một số có tỗng các ước nhỏ hơn nó bằng chính nó dc gọi là số hoàn thiện. (VD 6 có ước nhỏ hơn nó là 1,2,3. Tổng là 1+2+3=6). 9. Số tự nhiên có rất nhiều tính chất thú vị. Ví dụ với số 23, số đảo ngược của nó là 32. Hai số này có ước chung lớn nhất là 1. Những số như thế được gọi là số thân thiện, tức là số 23 được gọi là số thân thiện, số 32 cũng được gọi là số thân thiện. Hãy nhập vào 2 số nguyên a,b (10≤a≤b≤30000). Hãy đếm xem trong khoảng từ a đến b (kể cả a và b) có bao nhiêu số thân thiện.
Dữ liệu: Bao gồm một dòng chứa 2 số a,b. Hai số được cách nhau bằng một khoảng trắng Kết quả: Bao gồm một dòng là kết quả của bài toán. Ví dụ Dữ liệu 20 30 Kết quả 3 10. Bài 1: Tìm chữ số File vào DIGIT.INP File ra DIGIT.OUT File chương trình DIGIT.PAS Giới hạn thời gian 1 giây Cho dãy các số tự nhiên khác 0 viết liền nhau: 12345678910111213141516171819202122232425262728293031... Cho trước số nguyên dương k, hãy tìm chữ số thứ k trong dãy trên. Dữ liệu: File vào gồm các dòng, mỗi dòng ghi một số nguyên dương k (k ≤ 1.000.000.000). Kết quả: File ra gồm nhiều dòng, mỗi dòng ghi kết quả chữ số thứ k tìm thấy trong dãy ứng với số k đọc được trong file dữ liệu vào. Ví dụ: DIGIT.INP DIGIT.OUT 2 2 15 2 16 1 HD: - Xác định kí tự thứ k thuộc nhóm số có m chữ số, sau đó giảm k tổng số chữ số các nhóm từ 1 đến m-1, tức tìm chữ số thứ k của dãy ban đầu tương đương tìm chữ số thứ k sau khi giảm thuộc dãy số trong nhóm có m chữ số) - Xác định số x chứa chữa số thứ k, Số đầu nhóm có m chữ số+ (k-1) div m - Khi đó chữ số thứ k thuộc vị trí (k-1) mod m +1 trong số x 11. Tìm số
12. Các bài tập trong cuốn “tài liệu giáo khoa chuyên tin” Chuyên đề 2 …

More Related Content

Kiến thức cơ bản

  • 1. A. KIẾN THỨC CƠ BẢN 1. Ôn tập tại các kiến thức và bài tập đã học phần NNLT Pascal - Chương Cấu trúc điều khiển - Chương Kiểu dữ liệu có cấu trúc (đặc biệt là Mảng 1, 2 và xâu kí tự) Ví dụ: Mảng 1 chiều chảng hạn … Một số thao tác cơ bản trên mảng một chiều: - Tìm phần tử thoả mãn điều kiện (lớn nhất, nhở nhất, tồn tại, là số nguyên tố, thân thiện, ...) - Tìm dãy con liên tiếp tăng dần, giảm dần, dương, âm dài nhất ... - Tìm dãy con liên tiếp K phần tử có tổng lớn nhất, nhỏ nhất ... - Số lượng các phần tử đôi một khác nhau, phần tử nào có số lượng nhiều, ít nhất - Tìm số nguyên dương bé nhất không xuất hiện trong dãy. 2. Tìm kiếm tuần tự, nhị phân 3. Sắp xếp nổi bọt (buble sort), nhanh (quicksort) và đếm phân phối (countting) 4. Tìm uscln, bscnn của 2 số a và b, của dãy số a1, a2 ...an, hiển thị phân số tối giản 5. Số ước, tổng các ước của số n 6. Số nguyên lớn - Cộng A+B, trừ (A-B), nhân (A x b). A,B nguyên dương lớn (A<B) - So sánh 2 số X và Y X, Y nguyên lớn - Cộng X+Y, Hiệu X-Y B thuộc longint hay int64 7. Dãy số Fibonacy, Catalan 8. Lý thuyết tập hợp Các nguyên lý đếm tổ hợp cơ bản: Nguyên lý cộng, nhân, bù trừ, Dirichle Các cấu hình tổ hợp: Chỉnh hợp lặp, chỉnh hợp không lặp, hoán vị và tổ hợp 9. Lý thuyệt và bài tập duyệt các cấu hình tổ hợp thường gặp – Áp dụng thuật toán vét cạn quay lui để tìm một cấu hình hoặc tất cả các cấu hình (nghiệm) - Chỉnh hợp lặp - Liệt kê các cấu hình chập k của n phần tử - Chỉnh hợp không lặp - Liệt kê các cấu hình chập k của n phần tử - Liệt kê hoán vị n phần tử - Liệt kê các tổ hợp chập k của n pt (k=1..n) - Bài tập ứng dụng SGK (4.1 – 4.10) - Bài toán tối ưu tổ hợp 10. Quy hoạch động cơ bản
  • 2. B. MỘT SỐ BÀI TẬP VỀ SỐ HỌC 1. Chuyển đổi số n ở cơ số a về cơ số b (đặc biết 2, 10 và 16) - Cho 1 số nguyên không âm ở hệ thập phân, hãy đổi số đó sang dạng biểu diễn của hệ nhị phân, hệ cơ số 8 và hệ 16. - Cho một số ở hệ nhị phân (dữ liệu vào dưới dạng xâu nhị phân). Hãy đổi số đó sang hệ thập phân, hệ cơ số 8 và hệ cơ số 16. - Cho 1 số nguyên không âm N ở hệ thập phân (N<=255), hãy đổi số đó sang dạng xâu nhị phân độ dài 8, nếu không đủ 8 kí tự thì thêm kí tự 0 vào đầu Ví dụ: N=15 thì kết quả là: 00001111 2. Độ cao, độ dày và chiều dài của số nguyên n. Viết chương trình thực hiện: - Tính và hiển thị số n, độ cao H(n), độ dày D(n) và chiều dài L(n) . - Lật số nguyên (input: x = 1234, output: y = 4321). - Số gánh (12321, 2). (H(n) = tổng các chữ số của n, D(n) = tích các chữ số của n, L(n) = số chữ số của n) 3. Số nguyên tố - Kiểm tra tính nguyên tố của số k - Sàng nguyên tố Eratostheme - Liệt kê các số nguyên tố trong [a,b] - Phân tích số n thành các thừa số nguyên tố - Số nguyên tố cùng nhau - Tìm số nguyên tố có cùng độ cao, độ dày hoặc chiều dài 4. Số Fibonaci(n) - Tìm số Fibonacci thứ n>1. trong đó f0=0, f1=1, fn=fn-1 + fn-2 - Phân tích số nguyên M thành tổng các số Fibonaci (số lượng ít nhất) - Tìm các số Fibonaci trong đoạn [A..B] (A<B, tối đa 200 chữ số) Gợi ý: Dãy Fibonacci (chỉ số tính từ 0): 0, 1, 1, 2, 3, 5,… 5. N! - Giai thừa. - Tín n! (n có tối đa 200 chữ số) - Tính số chữ số 0 tận cùng của n! (Ví dụ: n=11, n!=39916800, số chữ số 0 tận cùng là 2) - Tìm chữ số khác 0 của N! (Ví dụ: n=11, n!=39916800, chữ số tận cùng khác 0 là 8) - Cho số p, tìm số mũ k lớn nhất để pk là ước của n! 6. Lũy thừa. Cho 2 số nguyên dương bất kì N ,M(1<=N<=100, 1<=M<=10). Hãy tìm k chữ số cuối cùng của N luỹ thừa M. (NM). 7. Số AMSTRONG Tìm các số có 3 chữ số sao cho tổng lập phương các chữ số bằng chính nó. (Ví dụ số 153=12+52+32). 8. Liệt kê các số hoàn thiện trong đoạn M..N. Một số có tỗng các ước nhỏ hơn nó bằng chính nó dc gọi là số hoàn thiện. (VD 6 có ước nhỏ hơn nó là 1,2,3. Tổng là 1+2+3=6). 9. Số tự nhiên có rất nhiều tính chất thú vị. Ví dụ với số 23, số đảo ngược của nó là 32. Hai số này có ước chung lớn nhất là 1. Những số như thế được gọi là số thân thiện, tức là số 23 được gọi là số thân thiện, số 32 cũng được gọi là số thân thiện. Hãy nhập vào 2 số nguyên a,b (10≤a≤b≤30000). Hãy đếm xem trong khoảng từ a đến b (kể cả a và b) có bao nhiêu số thân thiện.
  • 3. Dữ liệu: Bao gồm một dòng chứa 2 số a,b. Hai số được cách nhau bằng một khoảng trắng Kết quả: Bao gồm một dòng là kết quả của bài toán. Ví dụ Dữ liệu 20 30 Kết quả 3 10. Bài 1: Tìm chữ số File vào DIGIT.INP File ra DIGIT.OUT File chương trình DIGIT.PAS Giới hạn thời gian 1 giây Cho dãy các số tự nhiên khác 0 viết liền nhau: 12345678910111213141516171819202122232425262728293031... Cho trước số nguyên dương k, hãy tìm chữ số thứ k trong dãy trên. Dữ liệu: File vào gồm các dòng, mỗi dòng ghi một số nguyên dương k (k ≤ 1.000.000.000). Kết quả: File ra gồm nhiều dòng, mỗi dòng ghi kết quả chữ số thứ k tìm thấy trong dãy ứng với số k đọc được trong file dữ liệu vào. Ví dụ: DIGIT.INP DIGIT.OUT 2 2 15 2 16 1 HD: - Xác định kí tự thứ k thuộc nhóm số có m chữ số, sau đó giảm k tổng số chữ số các nhóm từ 1 đến m-1, tức tìm chữ số thứ k của dãy ban đầu tương đương tìm chữ số thứ k sau khi giảm thuộc dãy số trong nhóm có m chữ số) - Xác định số x chứa chữa số thứ k, Số đầu nhóm có m chữ số+ (k-1) div m - Khi đó chữ số thứ k thuộc vị trí (k-1) mod m +1 trong số x 11. Tìm số
  • 4. 12. Các bài tập trong cuốn “tài liệu giáo khoa chuyên tin” Chuyên đề 2 …