//
you're reading...
00 - Chủ đề chung

001. TÍNH TOÁN SONG SONG

Biểu thức đủ là một dãy ký tự gồm các biến ký hiệu bằng chữ cái thường tiếng Anh: a..z, các phép toán cộng ký hiệu +, nhân ký hiệu * và các dấu ngoặc (,). Được định nghĩa như sau:

  1. i) Mỗi biến a,b,…,z là một biểu thức đủ
  2. ii) Nếu X và Y là biểu thức đủ thì (X+Y) và (X*Y) cũng là biểu thức đủ.

iii) Những biểu thức nào không xây dựng được theo 2 nguyên tắc trên không là biểu thức đủ.

VD: Theo cách định nghĩa trên thì (a+(b+(c+d))) hoặc ((a+b)+(c*d)) là các biểu thức đủ.

Cho biết thời gian tính phép + là P, thời gian tính phép * là Q, người ta định nghĩa thời gian tính toán một biểu thức đủ như sau:

  • Nếu biểu thức đủ chỉ gồm 1 biến (a..z) thì thời gian tính toán là 0
  • Nếu X và Y là 2 biểu thức đủ; thời gian tính X là TX thời gian tính Y là TY thì thời gian tính (X+Y) là max(TX,TY)+P thời gian tính (X*Y) là max(TX,TY)+Q

Từ 1 biểu thức đủ người ta có thể biến đổi về một biểu thức tương đương bằng các luật:

  • Giao hoán: (X+Y) Û (Y+X); (X*Y) Û (Y*X)
  • Kết hợp: (X+(Y+Z)) Û ((X+Y)+Z); (X*(Y*Z)) Û ((X*Y)*Z)

Yêu cầu: Cho trước một biểu thức đủ E dưới dạng xâu ký tự hãy viết chương trình:

  1. Tìm thời gian tính toán biểu thức E
  2. Hãy biến đổi biểu thức E thành biểu thức E’ tương đương với nó sao cho thời gian tính E’ là ít nhất có thể.

Dữ liệu vào được đặt trong file văn bản PO.INP như sau:

  • Dòng thứ nhất ghi 2 số P, Q cách nhau 1 dấu cách (P,Q£100)
  • Tiếp theo là một số dòng, mỗi dòng ghi 1 biểu thức đủ.

Kết quả ra đặt trong file văn bản PO.OUT như sau:

Với mỗi biểu thức E trong file PO.INP ghi ra file PO.OUT 3 dòng

  • Dòng thứ nhất: Ghi thời gian tính toán E
  • Dòng thứ hai: Ghi biểu thức E’
  • Dòng thứ ba: Ghi thời gian tính toán E’

Chú ý: Để cho gọn, mỗi biểu thức đủ trong input/output file có thể viết mà không cần đến cặp dấu ngoặc ngoài cùng, dữ liệu vào được coi là đúng đắn và không cần kiểm tra

 

Ví dụ:

 

PO.INP PO.OUT
1 1

a+(a+(a+(a+(a+(a+(a+a))))))

(((a+(b+(c+d)))*e)*f)

(((((a*b)*c)*d)+e)+(f*g))

 

7

((a+a)+(a+a))+((a+a)+(a+a))

3

5

(e*f)*((a+b)+(c+d))

3

5

((a*b)*(c*d))+(e+(f*g))

3

 

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Chưa có phản hồi.

Gửi phản hồ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 Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

Các tác giả

Danh mục

Tháng Mười 2016
M T W T F S S
« Sep   Nov »
 12
3456789
10111213141516
17181920212223
24252627282930
31  

NCT Computer

Flickr Photos

sunset

Detroit Night

White-winged Scoter | Macreuse à ailes blanches

More Photos

Thống kê

  • 95,281 lượt xem

%d bloggers like this: