Giải đề thi Olympic Tin học Cấp Khoa lần 7 bằng C++/CLI

Giải đề thi Olympic Tin học Cấp Khoa lần 7 bằng C++/CLI

Bài viết này của tôi nằm trong series ‘các bài tập tham khảo’. Series này chia sẻ một số cách tiếp cận, hiện thực mức căn bản nhất, tóm tắt nhất các bài tập, bài tập lớn ngành Khoa học máy tính, trường ĐH Mở Tp.HCM. Tôi hy vọng sẽ hữu ích với các bạn sinh viên IT đang chập chững trong học tập.

Tham gia hoạt động học thuật ngoại khóa là 1 cách nâng cao thêm kiến thức chuyên môn của bản thân mà ít tốn kém. Hằng năm, Trường Đại học Mở Tp.HCM nói chung và Khoa Công nghệ thông tin nói riêng đều có tạo cơ hội phát tiển cho sinh viên. Các hoạt động nổi bật phải kể đến là Cuộc thi nghiên cứu khoa học, Cuộc thi Olympic Tin học cấp khoa, Cuộc thi tin học Đường đua số,… Vừa qua, Cuộc thi Olympic Tin học lần 7 (năm 2013) đã diễn ra thu hút sự quan tâm của các bạn sinh viên yêu thích lập trình, thuật toán. Thành phần dự thi năm nay đa phần là sinh viên năm 1 nên đề thi cũng dễ chịu hơn các năm trước.

Tóm tắt đề thi

Câu 1 – nén và giải nén chuỗi:  

Cho chuỗi kí tự, nén những chuỗi con trong nó có ít nhất 3 ký tự giống nhau rồi dùng số lượng các ký tự giống nhau đó đặt phía trước. Giải nén thì làm ngược lại. Chương trình làm nhiệm vụ nén từng dòng trong file DATA1.INP (dòng đầu tiên là số lượng chuỗi bên dưới) rồi ghi vào file ENCODE.OUT. Tương tự đối với DATA2.INP thì sẽ giải nén cho ra DECODE.OUT

clip_image001[4]

clip_image002[4]

Câu 2 – tam giác số:

Tìm tổng các phần tử có giá trị lớn nhất khi đi từ trên đỉnh tam giác xuống đáy bằng cách sang trái hoặc phải như trong hình:

 

 

 

5

 

 

 

 

 

4

 

3

 

 

 

9

 

5

 

7

 

8

 

13

 

6

 

15

 

 Đâu vào là 1 file TRIANGLE.INP (dòng đầu tiên là số dòng), tiếp theo là các số trong tam giác. Xuất kết quả ra TRIANGLE.OUT

clip_image003[4]

Đề thi 120 phút, không sử dụng tài liệu, yêu cầu sinh viên viết chương trình trên ngôn ngữ C++, dịch bằng Visual C++ 6.0.

Giải

Tuy nhiên vì muốn làm mới mẻ hơn, thay vì dùng VC++ 6.0, bài viết này tôi sẽ giải theo C++/CLI để tận dụng 1 số khả năng của .NET framework. Cũng lưu ý trước là tôi chọn C++/CLI không phải vì C++/CLI mạnh hơn hay đáng để phát triển hơn là C++ chuẩn mà lí do đơn giản là tôi chỉ muốn thay đổi cách tiếp cận giải quyết vấn đề để bớt nhàm chán hơn thôi.

Câu 1: Suy nghĩ truyền thống sẽ thấy mỗi chuỗi như thế chỉ cần vòng lặp quét qua, bên trong có thể gồm những vòng lặp con để tìm những chuỗi giống nhau. Tiến bộ hơn về mặt kĩ thuật, người ta sẽ nghĩ ngay đến sử dụng giải pháp Regular Expression (viết tắt là Regex, nhiều người dịch là ‘biểu thức quy tắc’). Những phiên bản trình dịch C++ và thư viện STL cũ kĩ chưa hỗ trợ Regex. Mãi đến C++ 11 thì Regex cơ bản mới được tích hợp trong STL. Tuy vậy trình dịch GCC vẫn chưa hỗ trợ. Thế nên, các lập trình viên C++ hay sử dụng thư viện Boost. Trong khi đó sử dụng C++/CLI do Microsoft phát triển tận dụng được .NET framework mạnh mẽ, bao gồm việc hỗ trợ Regex.

using namespace System;
using namespace System::IO;
using namespace System::Text::RegularExpressions;

//hàm callback để nén chuỗi con
String^ EncodeMatchCallback(Match^ match)
{
	String^ sa = match->Value;
	return sa->Length.ToString() + sa[0]; 
}

//hàm callback để giải nén chuỗi con
String^ DecodeMatchCallback(Match^ match)
{
	int count = int::Parse(match->Groups["digit"]->Value);
	char character = match->Groups["char"]->Value[0];
	return gcnew String(character, count);
}

int main(array<System::String ^> ^args)
{
	int lineNum, i, j;
	String^ inputStr;
	StreamReader^ reader;
	StreamWriter^ writer;
	Regex^ regex;
	
	//Nén
	reader = gcnew StreamReader("DATA1.INP");
	writer = gcnew StreamWriter("ENCODE.OUT");
	lineNum = int::Parse(reader->ReadLine());
	regex = gcnew Regex("(.)\\1{2,}"); //regex đại diện cho những chuỗi con có 3 kí tự bất kì giống nhau
	for (int i = 0; i < lineNum; i++)
	{
		inputStr = reader->ReadLine();
		writer->WriteLine(regex->Replace(inputStr, gcnew MatchEvaluator(&EncodeMatchCallback)));
	}
	reader->Close();
	writer->Close();

	//Giải nén
	reader = gcnew StreamReader("DATA2.INP");
	writer = gcnew StreamWriter("DECODE.OUT");
	lineNum = int::Parse(reader->ReadLine());
	regex = gcnew Regex("(?<digit>\\d+)(?<char>.)"); //regex đại diện cho chuỗi con có định dạng (số)(kí tự) có đặt tên nhóm.
	for (int i = 0; i < lineNum; i++)
	{
		inputStr = reader->ReadLine();
		writer->WriteLine(regex->Replace(inputStr, gcnew MatchEvaluator(&DecodeMatchCallback)));
	}
	reader->Close();
	writer->Close();

    return 0;
}

 

Câu 2: Nếu đã từng giải các bài toán tin học kinh điển, thì chắc anh em sẽ nhận ra đây là một trong những bài toán kinh điển cho thuật toán quy hoạch động. Thể hiện qua công thức:

b[n][j] = a[n][j]; với 0<=j<=n-1

b[i][j] = max(a[i+1][j], a[i+1][j+1]); với 0<=i<n, 0<=j<=i

Tinh thần là theo công thức trên, cách thể hiện là tùy mỗi người. Nếu như chỉ quan tâm đến kết quả cuối cùng thì chúng ta cũng sẽ chỉ cần 1 mảng b 1 chiều đơn giản như sau:

clip_image001[6]

 

using namespace System;
using namespace System::IO;

int main(array<System::String ^> ^args)
{
    int lineNum, i, j;
	
	array<String^>^ inputStrs = File::ReadAllLines("TRIANGLE.INP");
	lineNum = int::Parse(inputStrs[0]);
	array<int>^ maxValue = gcnew array<int>(lineNum);
	Converter<String^, int>^ strToIntConverter = gcnew Converter<String^, int>(int::Parse);
	for (i = lineNum; i >= 2; i--)
	{
		array<int>^ curNums = Array::ConvertAll(inputStrs[i]->Split(' '), strToIntConverter);
		for (j = 0; j < curNums->Length - 1; j++)
		{
			maxValue[j] += curNums[j];
			if(maxValue[j] < maxValue[j+1] + curNums[j+1])
				maxValue[j] = maxValue[j+1] + curNums[j+1];
		}
	}
	int rootValue = int::Parse(inputStrs[1]);
	maxValue[0] += rootValue;
	File::WriteAllText("TRIANGLE.OUT", String::Format("Tong duong di lon nhat tu {0} den hang {1} la {2}.", rootValue, lineNum, maxValue[0]));

    return 0;
}

Có 1 nhược điểm khi dùng các API Console của .NET framework là khi nhập vào là chuỗi và cần có khâu phân tích, chuyển đổi thành những biến số nguyên, số thực… vấn đề mà với operator>> của istream lại cực kì đơn giản.

Nhấn mạnh 1 lần nữa. Mỗi ngôn ngữ, công nghệ hay kĩ thuật đều có cái hay riêng. Tôi luôn tự nhủ rằng “đừng tự biến mình thành nô lệ của 1 phe nào cả, tập chấp nhận, học hỏi và áp dụng những thứ thực sự là cần thiết đối với gì mình đang làm là một trong những quy luật cơ bản để phát triển năng lực bản thân”. Mong điều này sẽ mang đến những suy nghĩ mới mẻ. Chào thân ái!

One response to “Giải đề thi Olympic Tin học Cấp Khoa lần 7 bằng C++/CLI

  1. #include
    #include
    #include
    using namespace std;
    main()
    {
    ifstream f(“fileGoc.inp”);
    ofstream f1(“fileNen.out”);
    char a[200], b;
    int k, i;
    while (! f.eof())
    {
    i=0;
    f>>a;
    while (i != strlen(a))
    {
    k=0;
    for (int j =i; j1) f1<<k;
    b = a[i];
    f1<<b;
    break;
    }
    }
    i+=k;
    }
    cout<<"————\n";
    f1<<' ';
    }
    }

    tôi viết đoạn code này cho bài 1 nhưng thiếu ký tự cuối bạn nào xem tôi sai chỗ nào giúp t!!! tks

    Số lượt thích

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Đăng xuất /  Thay đổi )

Google photo

Bạn đang bình luận bằng tài khoản Google Đăng xuất /  Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất /  Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất /  Thay đổi )

Connecting to %s