Ứng dụng cây nhị phân tìm kiếm trong bài toán biểu diễn phân số a/b dưới dạng số thập phân vô hạn tuần hoàn

Độ phức tạp để xây cây nhị phân tìm kiếm là:
log1 + log2 + … + logk = O(k*logk)

Độ phức tạp để tìm kiếm một phần tử: log1 + log2 + … + logk = O(k*logk)

Nếu sử dụng thuật toán bình thường để tìm kiếm thì độ phức tạp là:
1 + 2 + … + k = k(k+1)/2 = O(k^2)

Bạn có thể sửa lại code sau để xây dựng thuật toán mới bằng cách sử dụng Cây nhị phân tìm kiếm: https://tosonnguyen.wordpress.com/2014/05/25/bieu-dien-phan-so-ab-duoi-dang-so-thap-phan-vo-han-tuan-hoan/
(sửa code ở đoạn này for(it = L.begin(); it != L.end(); it++){)

Chú ý riêng: Trong toán học thì:
log1 + log2 + … + logk = logk!

Biểu diễn phân số a/b dưới dạng số thập phân vô hạn tuần hoàn

Biểu diễn phân số a/b dưới dạng số thập phân vô hạn tuần hoàn.

Đây là đề thi của Đại học Nha Trang.

Đề bài câu 1: http://clbth.ntu.edu.vn/phpbb/viewtopic.php?f=23&t=306&p=889&sid=77d0d20536df3846d823c82a0d4bcdf0#p889

Code:

#include<cstdio>
#include<iostream>
#include<list>

using namespace std;
int T, a, b, q, r, rr,rrr;
list<int> L;
bool isok;

int main(){
   list<int>::iterator it ;
   freopen("TEST.INP","r",stdin);
   freopen("TEST.OUT","w",stdout);
   cin >> T;
   for(int t = 0; t < T; t++){
      cin >> a >> b;
      L.clear();
   
      if(a >= b){
         cout << a / b;
         r = a - (a / b) * b;
      }
      else{
         cout << "0";
         r = a;
      }
      cout << ".";
      if(r == 0){
         cout << "0";   
      }
      // tim chu ki tuan hoan
      rr = r;
      L.push_back(r);
      while(true){
         if(r == 0) break;
         if(r < b){
            r *= 10;
         }
         if(r >= b){
            r = r - (r / b) * b;
         }
         isok = false;
         for(it = L.begin(); it != L.end(); it++){
            //cout << "it = " << *it << " r = " << r << endl;
            if(*it == r){
               rrr= r;
               isok = true;
               break;   
            }
         }
         if(isok) break;
         L.push_back(r);
      };
      // in lai ket qua
      L.clear();
      L.push_back(rr);
      r = rr;
      while(true){
         if(r == 0) break;
         if(r == rrr){
            cout << "(";
         }
         if(r < b){
            r *= 10;
         }      
         cout << r / b;
         if(r >= b){
            r = r - (r / b) * b;
         }
         isok = false;
         for(it = L.begin(); it != L.end(); it++){
            //cout << "it = " << *it << " r = " << r << endl;
            if(*it == r){
               isok = true;
               break;   
            }
         }
         if(isok) break;
         L.push_back(r);
      };
      if(r!= 0) cout << ")";
      cout << endl;
   }
   return 0;   
}

Chương trình Pascal với tham số dòng lệnh

Với ngôn ngữ C/C++ bạn đã từng gặp chương trình với đối số dòng lệnh. Bạn đã từng đặt câu hỏi tương tự đối với Pascal chưa?

Đây là câu trả lời:

File: toson.pas

program commandline(output);

var arguments : integer;

begin
    if ParamCount = 0 then
    begin
         writeln( 'No parameters supplied' );
    end
    else begin
         writeln('There are ', ParamCount, ' parameters' );
         for arguments := 1 to ParamCount do
             Writeln( 'Parameter ',arguments,' = ',ParamStr(arguments) );
    end;
    readln;

end.

Bạn có thể đổi: program commandline(output); thành program chuyentinhyeu(anhyeuem); hoặc: program khongyeuaica;

Chạy với đối số dòng lệnh: toson.exe chuyen gi se xay ra day

Nguồn: http://xoomer.virgilio.it/gciabu/engl/pascal/pas074.htm

[Bản cuối] Tiện ích sinh tests tự động cho phần mềm chấm điểm tự động của TS. Lê Minh Hoàng

Bản cuối cho phép các bạn dịch file nguồn bằng Free Pascal hoặc C++ hoặc C.

Yêu cầu hệ thống:
– Nếu file nguồn bằng Free Pascal thì phải có trình biên dịch Free Pascal. Sau đó cài đặt biến môi trường.
– Nếu file nguồn bằng C++ hoặc C thì phải có trình biên dịch g++/gcc. Sau đó cài đặt biến môi trường.
– Chương trình với hệ thống giao diện chạy trên hệ điều hành Windows.
– Nếu bạn chạy hệ điều hành họ Linux hãy liên lạc với mình để lấy file nhị phân. File này chạy ở chế độ dòng lệnh.

Download:
http://hoctincungthukhoa.com/index.php/ph-n-m-m/8-ti-n-ich-sinh-test-t-d-ng-cho-ph-n-m-m-ch-m-di-m-t-d-ng-themis-c-a-ts-le-minh-hoang

Chú ý: File .zip các bạn download về có hai bài: XAU và FIBO

1. File sinh tests Input: R_XAU.PAS. File sinh tests Output từ Input: XAU.PAS
2. File sinh tests Input: R_FIBO.PAS. File sinh tests Output từ Input: FIBO.CPP

Bài viết liên quan: https://tosonnguyen.wordpress.com/2013/10/13/tien-ich-sinh-test-tu-dong-cho-phan-mem-cham-diem-tu-dong-themis-cua-ts-le-minh-hoang/

Code vài chương trình chấm điểm tự động

Download: https://www.dropbox.com/s/kd3z28qczq0m7c5/Canh%20-%20thang%202.2014.zip

Chú ý: Bài 2 – LIST.PAS, nếu các bạn muốn sinh file Input hợp lý thì hãy cho độ dài của dãy dài, nhưng các phần tử trong dãy chỉ có giá trị nhỏ thôi. Chi tiết xem file R_LIST.PAS

Lại bàn về C và C++

C là ngôn ngữ hướng thủ tục thì C++ là ngôn ngữ hướng đối tượng. Sự khác biệt giữa này giúp cho việc đọc một chương trình trên C++ trong sáng và dễ hiểu hơn trên C nhiều khi “cái nào ở vị trí của cái đấy”, tiếng Việt mình gọi là “nồi nào úp vung lấy”. (Thực ra, C++ là ngôn ngữ lai, tức vừa là ngôn ngữ hướng thủ tục vừa là ngôn ngữ hướng đối tượng).

Download: https://www.dropbox.com/s/tebiewr0gzt1d54/Chuyen%20tu%20trung%20to%20sang%20hau%20to%20-%20class.zip

Bài viết liên quan:

1, https://tosonnguyen.wordpress.com/2014/02/19/viet-code-chuan-nhu-the-nao/
2, https://tosonnguyen.wordpress.com/2014/02/23/chuyen-bieu-thuc-tu-dang-trung-to-co-dau-ngoac-sang-tien-to/

Chuyển biểu thức từ dạng trung tố có dấu ngoặc sang tiền tố

Một người bạn nhờ mình làm bài chuyển từ dạng trung tố có dấu ngoặc sang hậu tố. Khi đó, mình nhận thấy có rất ít code chuyển với dạng tiền tố. Nên các bạn có thể đọc bài này.

Hãy chú ý: file văn bản sử dụng bộ font đặc biệt. Theo mình nó khá đẹp 😀

Download: https://www.dropbox.com/s/6eibhk3sqd2xsby/Chuyen%20tu%20trung%20to%20sang%20tien%20to.pdf

Tham khảo thêm (cái này có chứa code): https://tosonnguyen.wordpress.com/2014/02/19/viet-code-chuan-nhu-the-nao/