thảo luận Nhờ cao nhân giải giùm bài toán này

casy.DanTruong

Junior Member
Như tít, bác nào đưa ý tưởng thôi cũng được ạ :cry:. Đề bài như sau:
Implement a simple spreadsheet application. The sheet contains a list of cells, which are labeled by a letter from A-Z followed by an integer. ex A1, B12, C33...
For each cell, it can be either an integer or a mathematic formula is written in Reverse Postfix Notation and can also refer to other cells.
Input:
The first line: an integer N indicating the number of cells
Each 2 lines of the N*2 subsequence lines will have the structure:
  • first-line: cell name, ex A1, B1...
  • second-lime: cell content
Output:
For each of the cells, output its name along with its final calculated value (rounded down in INT format).
If there is any circular dependency between the cells, output an error specifying all of the cells in the cycle. You can assume that there is at most one cycle in the input.
sample input 0:
3
A1
5
A2
A1 5 * b1 +
B1
6
out put 0:
A1
5
A2
31
B1
6
sample input 1:
2
A1
A2 2 +
A1
A1 5 +
OUT OU1 1:
circular depndency: A1, A2
 

nipevt

Senior Member
Như tít, bác nào đưa ý tưởng thôi cũng được ạ :cry:. Đề bài như sau:
Implement a simple spreadsheet application. The sheet contains a list of cells, which are labeled by a letter from A-Z followed by an integer. ex A1, B12, C33...
For each cell, it can be either an integer or a mathematic formula is written in Reverse Postfix Notation and can also refer to other cells.
Input:
The first line: an integer N indicating the number of cells
Each 2 lines of the N*2 subsequence lines will have the structure:
  • first-line: cell name, ex A1, B1...
  • second-lime: cell content
Output:
For each of the cells, output its name along with its final calculated value (rounded down in INT format).
If there is any circular dependency between the cells, output an error specifying all of the cells in the cycle. You can assume that there is at most one cycle in the input.
sample input 0:
3
A1
5
A2
A1 5 * b1 +
B1
6
out put 0:
A1
5
A2
31
B1
6
sample input 1:
2
A1
A2 2 +
A1
A1 5 +
OUT OU1 1:
circular depndency: A1, A2


xem mỗi cell nó refer tới cell nào khác, thì tạo đồ thị có hướng. VD A2 refer tới A1, B1 thì tạo thêm cạnh B1->A2, A1->A2 vào đồ thị. Nếu là số thì không tạo mới.

rồi dùng topological sort để kiểm tra circular dependency và lấy ra thứ tự tính toán.
 
Top