Giải đề thi Olympic tin học
Các bài giải ở đây là tài liệu để các bạn tham khảo, không phải là các bài mẫu, có thể có nhiều sai sót, mong các bạn cùng góp ý trao đổi.
Giải đề thi Olympic tin học khối cao đẳng 2015
Bài 1: Phương trình. Lời giải
Bài 2: Dãy đồng đẳng . Lời giải
Bài 3: Số N3S . Lời giải
Giải đề thi Olympic tin học khối cao đẳng năm 2014
Giải đề thi Olympic tin học khối cao đẳng năm 2012
Bài 2: Sản Phẩm Bài giải
Bài 3: Xóa Số Bài giải
Bài 4: Giải phóng mặt bằng Bài giải
Giải đề thi Olympic tin học khối cao đẳng năm 2011
Bài 2: Robot. Bài giải
Bài 3: Olympic Bài giải
Giải đề thi Olympic tin học khối cao đẳng năm 2009
Bài 3: Vòng tay. Bài giải
Chia sẻ nếu thấy hữu ích
Giải đề thi Olympic tin học: Bài 1 cao đẳng 2014
Viết chương trình đọc vào hai số thực dương a và b và tính tổng tất cả các số nguyên không nhỏ hơn a và không lớn hơn b.
Dữ liệu: Vào từ file văn bản SUM.INP gồm một dòng chứa hai số thực dương a, b.
Kết quả: Đưa ra file văn bản SUM.OUT gồm một dòng chứa một số nguyên là tổng tất cả các số nguyên không nhỏ hơn a và không lớn hơn b.
Ví dụ:
SUM.INP
0.3 2.89
SUM.OUT
3
Chú ý:
– Có 50% số test có 0 < a ≤ b ≤ 1000;
– Có 50% số test còn lại có 0 < a ≤ b ≤ 109 .
Giải
Đây là một bài toán dễ, theo cách thông thường, ta lấy ceil(a) và floor(b) rồi dùng vòng lặp for chạy từ ceil(a) đến floor(b) rồi cộng các số lại là xong. Tuy nhiên, theo cách này ta không thể thực hiện được khi khoảng cách từ a tới b lên tới 109 .
Các bạn nhớ lại kiến thức hồi phổ thông mình đã học nhé: 1+2+3+…+n = mấy các bạn nhỉ ?
Đặt ra = ceil(a); fb = floor(b) ta có kết quả bài toán là: tổng = ra + (ra+1) + (ra+2)+…+fb, có cả thảy có fb-ra+1 toán hạng.
Suy ra tổng = (fb-ra+1)*ra + (1+2+…+fb-ra)
Đặt fb-ra = hieu ta có: tổng = (hieu+1)*ra +hieu*(hieu+1)/2. Đây là công thức cuối cùng của bài toán. Dùng công thức này ta không phải thực hiện bất cứ vòng lặp for nào mà thời gian tính toán nhanh nhất và tối ưu nhất.
Toàn bộ source code bài toán như sau:
#include <iostream>
#include <fstream>
#include <math.h>
using namespace std;
int main() {
ifstream infile("sum.inp");
ofstream outfile("sum.out");
float a,b;
unsigned long long ra,rb,tong,hieu;
infile >> a>>b;
ra=(unsigned long) ceil(a);
rb=(unsigned long) floor(b);
hieu=rb-ra;
tong=(hieu+1)*ra+(hieu)*(hieu+1)/2;
outfile<<tong;
return 0;
}
Quá là đơn giản phải không các bạn. Bạn nào có ý kiến hay cách khác thì cùng reply bình luận nha. Chúc các bạn thành công
Olympic tin học: Xử lý số lớn trong lập trình C/C++
Để xử lý số lớn chúng ta sẽ chuyển sang xử lý chuỗi ký tự.
Trong code dưới đây các bạn chú ý phuơng thức str.insert(int pos, int n, int ch); chèn n lần ký tự ch vào vị trí pos của chuỗi str;
Ngoài ra còn có 2 phương thức khác là :
str.insert(int pos, char* s); chèn s (mảng ký tự kết thúc ‘’) vào vị trí pos của str;
str.insert(int pos, string s); chèn chuỗi s (kiểu string) vào vị trí pos của chuỗi str;
#include <string>
#include <iostream>
using namespace std;
int stringToNum(char c) // chuyen char sang so
{
return c - '0';
}
char numToString(int n) // chuyen so sang char
{
return (char)(n+48);
}
void chuanHoa(string &a, string &b) // lam 2 xau co do dai bang nhau
{
int l1 = a.length(), l2 = b.length();
if (l1 >= l2)
{
b.insert(0, l1-l2, '0'); // chen vao dau cua b cac ky tu '0'
}
else
{
a.insert(0, l2-l1, '0'); // chen vao dau cua a cac ky tu '0'
}
}
string sum(string a, string b) // tong 2 so
{
string s = "";
chuanHoa(a,b); // chuan hoa
int l = a.length();
int temp = 0;
for (int i=l-1; i>=0; i--) // duyet va cong
{
temp = stringToNum(a[i]) + stringToNum(b[i]) + temp; // tinh tong tung doi mot
s.insert(0,1,numToString(temp%10)); // gan phan don vi vao
temp = temp/10; // lay lai phan hang chuc
}
if (temp>0) // neu hang chuc > 0 thi them vao KQ
{
s.insert(0,1,numToString(temp));
}
return s;
}
// nhan so co 1 chu so voi so co nhieu chu so (VD 4 va 7826), lam tuong tu nhu phep cong
string nhanNho(char a, string b)
{
string s = "";
int temp = 0;
for (int i=b.length()-1; i>=0; i--)
{
temp = stringToNum(a) * stringToNum(b[i]) + temp;
s.insert(0,1,numToString(temp%10));
temp = temp/10;
}
if (temp>0)
{
s.insert(0,1,numToString(temp));
}
return s;
}
string nhan(string a, string b) // nhan 2 so lon
{
string s = "";
int l = a.length();
string s1[l];
for (int i=l-1; i>=0; i--) // nhan tung chu so cua a voi b sau do cong don vao
{
s1[i] = nhanNho(a[i], b); // nhan tung so cua a voi b
s1[i].insert(s1[i].length(), l-i-1, '0');
s = sum(s, s1[i]); // cong don theo cach cong so lon
}
return s;
}
int main(int argc, char **argv)
{
string a, b, s;
cout<<"Nhap a va b"<<endl;
getline(cin, a);
getline(cin, b);
s = sum(a,b);
cout<<"Tong cua a va b : "<<s<<endl;
s = nhan(a,b);
cout<<"Tich cua a va b : "<<s<<endl;
return 0;
}
Olympic tin học: Các site hữu ích cho việc luyện thi Olympic tin học
Trang chủ của cuộc thi http://www.olp.vn
Luyện tập http://vnoi.info
Giải bài toán trực tuyến http://vn.spoj.com
Tham gia các cuộc thi trực tuyến : http://ipsc.ksp.sk hoặc http://acm.timus.ru
Thêm một trang nữa : http://codeforces.com
Cũng có thể vào http://congdongcviet.com để học hỏi thêm
Thực hành Java: Bài 12. Thao tác với mảng 1 chiều
Bài 12. Viết chương trình nhập vào một mảng số nguyên có n phần tử
- a) Xuất giá trị các phần tử của mảng.
- b) Tìm phần tử có giá trị lớn nhất, nhỏ nhất.
- c) Đếm số phần tử là số chẵn
- d) Tìm các phần tử là số nguyên tố.
- e) Sắp xếp mảng tăng dần
- f) Tìm phần tử có giá trị x
Hướng dẫn
Kế thừa kiến thức từ các bài trước như nhập, xuất dữ liệu, tìm số nguyên tố, đếm số phần tử để giải quyết bài toán này. Bên cạnh đó, ta sử dụng lớp có sẵn của java như java.lang.Math.sqrt chứa các hàm toán học (ở đây ta dùng hàm sqrt()), java.util.Arrays chứa các xử lý mảng như sắp xếp, tìm kiếm…Các bạn cần chú ý tìm kiếm ở đây là tìm kiếm nhị phân trên một mảng đã sắp xếp.
package baitap12;
import static java.lang.Math.sqrt;
import java.util.Arrays;
import java.util.Scanner;
public class Baitap12 {
static boolean nguyento(int gh){
if (gh<3) {
return true;
}
for (int i = 3; i <= sqrt(gh); i++) {
if (gh%i==0) {
return false;
}
}
return true;
}
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
int arrInt[];
int n;
Scanner input =new Scanner(System.in);
System.out.println("nhap so phan tu n=: ");
n=input.nextInt();
arrInt = new int[n];
for (int i = 0; i < n; i++) {
System.out.println("nhap a[" +i+"] =");
arrInt[i]=input.nextInt();
}
for (int i = 0; i < n; i++) {
System.out.print(" a[" +i+"] =" + arrInt[i]+";");
}
int min=arrInt[0];
int max=arrInt[0];
for (int i = 0; i < n; i++) {
if (arrInt[i]<min) {
min=arrInt[i];
}
if (arrInt[i]>max) {
max=arrInt[i];
}
}
System.out.println("gia tri nho nhat: "+min);
System.out.println("gia tri lon nhat: "+max);
int dem=0;
for (int i = 0; i < n; i++) {
if (arrInt[i]%2==0) {
dem++;
}
}
System.out.println("so phan tu chan la: "+dem);
for (int i = 0; i < n; i++) {
if (nguyento(arrInt[i])) {
System.out.println("phan tu a["+i+"] ="+arrInt[i]+"nguyen to");
}
}
Arrays.sort(arrInt);
for (int i = 0; i < n; i++) {
System.out.print(" a[" +i+"] =" + arrInt[i]+";");
}
//------------------tim kiem nhi phan-------------------
int x;
System.out.println("nhap x: ");
x=input.nextInt();
int vitri = Arrays.binarySearch(arrInt,x);
System.out.println("vi tri cua " +x+"trong mang la "+vitri);
}
}
Thực hành Java: Bài 13. Thao tác với ma trận
Bài 13. Cho ma trận số nguyên cấp n x m. Cài đặt các hàm thực hiện các chức năng sau:
- a) Nhập ma trận.
- b) In ma trận.
- c) Tìm phần tử nhỏ nhất.
- d) Tìm phần tử lẻ lớn nhất.
- e) Tìm dòng có tổng lớn nhất.
Hướng dẫn
Bài tập này nhằm mục đích giúp các bạn quen với các thao tác trên mảng 2 chiều. Các thuật toán trong bài này không có gì phải phân tích thêm. Toàn bộ code bài tập như sau:
import java.util.Scanner;
public class Baitap13 {
static int n,m,matrix[][];
public static void nhapmatrix(){
Scanner input = new Scanner(System.in);
System.out.println("nhap so hang: ");
n=input.nextInt();
System.out.println("nhap so cot: ");
m=input.nextInt();
matrix=new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
System.out.print(" a["+i+","+j+"]=");
matrix[i][j]=input.nextInt();
}
System.out.println();
}
}
public static void xuatmatrix(){
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
System.out.print(matrix[i][j] +" ");
}
System.out.println("");
}
}
public static int minmatrix(){
int min=matrix[0][0];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (matrix[i][j]<min) {
min=matrix[i][j];
}
}
}
return min;
}
public static int minle(){
int minle=1000;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if ((matrix[i][j]<minle)&&(matrix[i][j]%2==1)) {
minle=matrix[i][j];
}
}
}
return minle;
}
public static int tongdong(int row){
int tong=0;
for (int i = 0; i < m; i++) {
tong+=matrix[row][i];
}
return tong;
}
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
int max = tongdong(0),chiso=0;
nhapmatrix();
xuatmatrix();
System.out.println("phan tu nho nhat "+minmatrix());
System.out.println("phan tu le nho nhat: " + minle());
for (int i = 0; i < n; i++) {
if (max<tongdong(i)) {
max=tongdong(i);
chiso=i;
}
}
System.out.println("dong co tong lon nhat la dong "+chiso+" co gia tri:"+max);
}
}
Thực hành Java: Bài 10. Hãy viết chương trình tính tổng các chữ số của một số nguyên bất kỳ. Ví dụ: Số 8545604 có tổng các chữ số là: 8+5+4+5+6+0+4= 32.
Theo đề bài, ta chỉ cần tính tổng các chữ số của một số nguyên. Nhưng ta có thể mở rộng bài toán với số thực, số lớn bằng cách sử dụng mảng.
Code tôi viết ở đây là tính toán cho số nguyên. Toàn bộ code chương trình như sau:
package baitap10;
import java.util.Scanner;
public class Baitap10 {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
int n,tong=0;
System.out.println("nhap vao so nguyen n");
Scanner input = new Scanner(System.in);
n=input.nextInt();
while (n>0) {
tong+=n%10;
n= n/10;
}
System.out.println("tong cac chu so cua n la: "+tong);
}
}
Thực hành Java: Bài 9. Dãy số Fibonacci được định nghĩa như sau: F0 =1, F1 = 1; Fn = Fn-1 + Fn-2 với n>=2. Hãy viết chương trình tìm số Fibonacci thứ n.
Bài toán tìm số fibonaci thứ n có nhiều cách giải, có thể dùng đệ quy, dùng mảng lưu trữ… Ở đây tôi dùng phương pháp thủ công nhưng đơn giản, chỉ với một vòng lặp for. Đây chỉ là code tham khảo, các bạn nên viết lại bằng các cách khác.
package baitap9;
import java.util.Scanner;
public class Baitap9 {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
int n,sothuN=1;
int f0=1;
int f1=1;
Scanner input = new Scanner(System.in);
n = input.nextInt();
if (n>1) {
for (int i = 2; i <=n; i++) {
sothuN=f0+f1;
f0=f1;
f1=sothuN;
}
}
System.out.println("so thu "+n +" la " + sothuN);
}
}
Thực hành Java: Giải các bài tập lập trình Java
Bài 1: Cài đặt JDK và Netbean IDE.Giải bài tập 1
Bài 2. Viết chương trình in ra tổng của 10 số chẵn đầu tiên (sử dụng vòng lặp for hoặc while).Giải bài tập 2
Bài 4. Viết chương trình giải phương trình bậc hai. Giải bài tập 4
Bài 6. Viết chương trình tính tổng S = 1 + 1/2 + 1/3 + … + 1/n với n nguyên dương được nhập từ bàn phím. Giải bài tập 6
Bài 8. Viết chương trình tính tổng S = 1 /1! + 2 /2! + ….+ n / n! Giải bài tập 8
Bài 9. Dãy số Fibonacci được định nghĩa như sau: F0 =1, F1 = 1; Fn = Fn-1 + Fn-2 với n>=2. Hãy viết chương trình tìm số Fibonacci thứ n. Giải bài tập 9
Bài 10. Hãy viết chương trình tính tổng các chữ số của một số nguyên bất kỳ. Ví dụ: Số 8545604 có tổng các chữ số là: 8+5+4+5+6+0+4= 32. Giải bài tập 10
Bài 12. Viết chương trình nhập vào một mảng số nguyên có n phần tử Giải bài tập 12
- a) Xuất giá trị các phần tử của mảng.
- b) Tìm phần tử có giá trị lớn nhất, nhỏ nhất.
- c) Đếm số phần tử là số chẵn
- d) Tìm các phần tử là số nguyên tố.
- e) Sắp xếp mảng tăng dần
- f) Tìm phần tử có giá trị x
Bài 13. Cho ma trận số nguyên cấp n x m. Cài đặt các hàm thực hiện các chức năng sau: Giải bài tập 13
- a) Nhập ma trận.
- b) In ma trận.
- c) Tìm phần tử nhỏ nhất.
- d) Tìm phần tử lẻ lớn nhất.
- e) Tìm dòng có tổng lớn nhất.
Bài tập về xâu ký tự
Hướng dẫn:
Các bạn cần lưu ý là khi chúng ta khởi tạo một String thì Java sẽ tạo ra một chuỗi ký tự và đặt vào đâu đó trong bộ nhớ, còn khi ta gán một String cho một biến thì biến đó sẽ trỏ đến vị trí của String đã khai báo .
Ví dụ:
String s="Hello";
String s1=s;
String s2=new String("Hello");
String s3="Hello";
System.out.println("s=s1: "+(s==s1));
System.out.println("s=s2: "+(s==s2));
System.out.println("s=s3: "+(s==s3));
Kết quả:
s=s1: true s=s2: false s=s3: true
Các bạn có thể hình dung s,s1,s2,s3 chỉ là các con trỏ lưu địa chỉ của chuỗi kiểu String, ở ví dụ trên s,s1,s3 cùng
trỏ đến một chuỗi trong bộ nhớ còn s2 trỏ đến chuỗi khác(được cấp phát bộ nhớ bằng từ khóa new). Mặc dù nội dung các
chuỗi giống nhau nhưng s2 trỏ đến một ví trí khác trong bộ nhớ.
vì String là không thể thay đổi nên khi thao tác với chuỗi các bạn cần lưu ý nó không giống như các kiểu dữ liệu cơ bản khác
Bài 15. Viết chương trình nhập vào một xâu ký tự và một ký tự ch. Đếm và in ra màn hình số lần xuất hiện của ký tự ch trong xâu ký tự đó. Giải bài tập 15
Bài 17. Nhập vào một xâu. Tạo ra xâu đảo ngược với xâu đã nhập. Giải bài tập 17
Bài 20. Nhập vào một xâu. Đếm xem trong xâu có bao nhiêu ký tự chữ cái, bao nhiêu ký tự chữ số và bao nhiêu từ (các từ ngăn cách với nhau bởi khoảng trắng). Giải bài 20
Bài 21. Nhập vào một xâu. Loại bỏ tất cả các khoảng trắng dư thừa trong xâu. Giải bài 21
Bài 22. Nhập một xâu từ bàn phím. Hãy xóa tất cả các nguyên âm trong xâu. Giải bài tập 22
Bài 23. Nhập vào một số điện thoại theo định dạng (091) 022-6758080. In ra màn hình mã Quốc gia (091), mã vùng (022) và số điện thoại (6758080). Giải bài 23
Bài 24. Nhập một xâu từ bàn phím. Hãy tạo ra một xâu có các từ đối xứng với xâu vừa nhập. Giải bài tập 24
Ví dụ: Nhập: “ Nha Trang Khanh Hoa”. In ra: “Hoa Khanh Trang Nha”
Bài tập Hướng đối tượng
Bài 1. Viết lớp HinhTron có các phương thức tính chu vi và diện tích. Viết hàm main để test lớp này. Giải bài 1-OOP
Bài 2. Xây dựng lớp HinhTamGiac theo yêu cầu sau: Giải bài 2-OOP
| HinhTamGiac |
| – ma : int
– mb : int – mc : int |
| + HinhTamGiac()
+ HinhTamGiac(a: int, b: int, c: int) + getCanhA() : int + setCanhA(v : int) : void + getCanhB() : int + setCanhB(v : int) : void + getCanhC() : int + setCanhC(v : int) : void + laTamGiac() : boolean + laTamGiac(int, int, int) : boolean + getChuVi() : int + getDienTich() : double |
Trong đó:
- ma, mb, mc là ba cạnh của tam giác.
- Hàm khởi tạo HinhTamGiac(int, int, int): yêu cầu kiểm tra:
- nếu giá trị truyền có số âm thì thông báo và gán thuộc tính tương ứng bằng 0;
- nếu 3 giá trị truyền vào không lập thành một hình tam giác thì thông báo “Không phải hình tam giác” và gán 3 thuộc tính bằng 0.
HD : ba giá trị lập thành một hình tam giác khi và chỉ khi tổng hai cạnh bất kỳ luôn lớn
hơn cạnh còn lại.
- Các hàm setCanhA, setCanhB, setCanhC cũng yêu cầu phải kiểm tra giá trị gán có là số dương và lập thành tam giác hay không, nếu không thì không gán (giữ lại giá trị cũ).
- Hàm getChuVi(), getDienTich(): tính chu vi và diện tích của tam giác.
- Hàm laTamGiac(): trả về giá trị true khi ba giá trị ma, mb, mc lập thành một hình tam giác, ngược lại trả về giá trị false.
- Hàm laTamGiac(int, int, int): trả về giá trị true khi ba giá trị a, b, c lập thành một hình tam giác, ngược lại trả về giá trị false.
Viết hàm main để kiểm tra lớp HinhTamGiac theo yêu cầu: Cho nhập vào 3 giá trị số nguyên và khởi tạo hình tam giác có các cạnh ứng với 3 giá trị này. Nếu 3 giá trị này không lập thành tam giác thì thông báo, ngược lại thì tính và xuất ra chu vi và diện tích của nó.
Bài 3. Xây dựng lớp NhanVien theo yêu cầu sau: Giải bài 3-OOP
| NhanVien |
| – maNV : String
– soSP : int |
| + NhanVien()
+ NhanVien (ma: String, sp : int) + getMaNV() : String + setMaNV(ma : String) : void + getSoSP() : int + setSoSP(sp : int) : void + coVuotChuan() : boolean + getTongKet() : String + getLuong(): double + XuatTieuDe() : static void + toString() : String
|
Trong đó:
- Trong các hàm khởi tạo và các hàm setSoSP, khi gán giá trị cho thuộc tính soSP thì cần kiểm tra giá trị đó có phải là số dương không, nếu là số dương thì mới gán giá trị cho thuộc tính, ngược lại thì gán bằng 0.
- Hàm coVuotChuan() : trả về true nếu soSP > 500, ngược lại trả về false.
Giải thích: hàm này dùng để kiểm tra xem số lượng sản phẩm của nhân viên có vượt quá số lượng chuẩn hay không.
- Hàm getTongKet() : trả về chữ “Vượt” khi soSP > 500, ngược lại để trống (có thể sử dụng hàm coVuotChuan() để kiểm tra).
- Hàm getLuong() : trả về lương của một nhân viên, lương ăn theo sản phẩm với đơn giá cơ bản cho 1 sản phẩm là 20000, và nếu số sản phẩm của nhân viên vượt chuẩn thì phần vượt chuẩn được tính đơn giá là 30000.
- Hàm XuatTieuDe() : xuất tiêu đề gồm các cột : mã nhân viên, số sản phẩm, lương, tổng kết.
- Hàm toString() : trả về chuỗi chứa thông tin của nhân viên gồm các cột: Mã nhân viên (maNV), Số sản phẩm (soSP), Lương và Tổng kết.
Viết hàm main để kiểm tra lớp NhanVien theo yêu cầu sau: Tạo 2 nhân viên với các thuộc tính cho người dùng nhập vào. Xuất ra các thông tin của họ, gồm mã, số sản phẩm, lương, tổng kết.
Thực hành Java: Bài 8 Viết chương trình tính tổng S = 1 /1! + 2 /2! + ….+ n / n!
Trước hết, ta nên viết một hàm tính n!
//---------ham tinh giai thua--------------
public static double giaithua(int n){
double tmp=1;
if (n>1) {
for (int i = 2; i <= n; i++) {
tmp *= i;
}
}
return tmp;
}
Và khai báo một biến toàn cục n. Bạn có thể viết thêm method nhập để gọi cho tiện nhưng ở bài này tôi viết chung vào phương thức main. Toàn bộ code của bài tập như sau:
package baitap8;
import java.util.Scanner;
public class Baitap8 {
public static int n;
//---------ham tinh giai thua--------------
public static double giaithua(int n){
double tmp=1;
if (n>1) {
for (int i = 2; i <= n; i++) {
tmp *= i;
}
}
return tmp;
}
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
float tong = 0.0f;
Scanner reader = new Scanner(System.in);
System.out.print("Nhập số tự nhiên N = ");
n = reader.nextInt();
for (int i = 1; i <= n; i++) {
tong+= i/giaithua(i);
}
System.out.println("tong day so la: " + tong);
}
}
Các bạn có thể sử dụng nhiều cách khác nhau để nhập dữ liệu vào như BufferedReader, JOptionPane thay vì sử dụng lớp Scanner như bài này.
Lập trình căn bản và nâng cao 