Từ 1 tới 5 trên tổng số 5 kết quả

Đề tài: Các bài tập lập trình C và giải thuật

  1. #1
    Ngày gia nhập
    08 2006
    Nơi ở
    Hải Phòng
    Bài viết
    218

    Mặc định Các bài tập lập trình C và giải thuật

    12.9. Nhà cao tầng
    Một quần thể nhà cao tầng được xây dựng trên một nền hình chữ nhật, trên đó đựơc chia thành M*N ô vuông (M dòng, N cột ). Các dòng đựơc đánh số từ 1 đến N. Người ta xem khu nhà được tạo bởi các khối có đáy là một ô vuông với những chiều cao nào đó mà người ta gọi là những đơn nguyên. Một đơn nguyên được xác định bởi toạ độ dòng, cột của ô đáy và chiều cao tương ứng. Một khối nhà được định nghĩa là một tập hợp các đơn nguyên có đáy tạo thành một miền gồm những ô vuông kề cạnh.
    Người ta đánh số các khối nhà bằng những số nguyên liên tiếp bắt đầu từ 1 theo trình tự duyệt các ô đáy theo từng dòng từ 1 đến M, và trên mỗi dòng, duyệt các ô đáy theo từng cột từ 1 đến N.
    Người ta muốn quét vôi các bức tường xung quanh tất cả các khối nhà. Hãy xác định
    * Số lượng các khối nhà
    * Tổng diện tích quét vôi
    * Khối nhà có diện tích quét vôi lớn nhất và giá trị của diện tích này.
    Dữ liêu vào cho trên file văn bản có dạng:
    M N
    H[1,1] H[1,2].... H[1,N]
    H[2,1].....
    ....
    H[M,1]...............H[M,N]
    trong đó H[i, j] là chiều cao của đơn nguyên [i, j] với các quy ước bằng 0 khi đơn nguyên này không có. Giải thiết rằng các giá trị này đêềulà những số nguyên và tính theo đơn vị một cạnh ô vuông. Các số trên cùng một dòng ghi cách nhau ít nhất một dấu cách.

    Kết quả ghi ra file văn bản gồm:
    * Dòng đầu ghi số lượng các khối nhà
    * Dòng thứ hai ghi tổng số diện tích quét vôi
    * Dòng thứ ba ghi số nhà của khối có diện tích quết vôi lớn nhất và giá trị của diện tích này ( ghi cách nhau ít nhất một dấu cách).
    Ví dụ:
    Input
    4 6
    1 2 3 0 2 1
    1 0 1 0 0 1
    2 1 1 0 0 1
    0 0 0 1 1 0

    Output
    3
    50
    1 30
    Ghi chú:
    * Các giá trị diện tích được tính theo đơn vị diện tích một ô vuông
    * Giới hạn kích thước: M, N <= 100, H[i, j] <=2000

  2. #2
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Sau đây là cách giải của anh, áp dụng thuật toán loang :
    Ý tưởng là ta xét 4 ô xung quanh 1 ô ví dụ ô H[r][c], vì là 1 đơn nguyên nên 2 ô kế nhau có cùng hàng và cùng cột thì thỏa mãn đề bài. Vậy có thể thấy những ô như :
    H[r+1][c]
    H[r-1][c]
    H[r][c+1]
    H[r][c+1]
    nếu khác 0 và -1 (viền bảng) thì thỏa mãn, từ đó ta có hàm loang như sau :

    C++ Code:
    1. void Spreading_Programming (int r, int c , int &s)
    2.  
    3.     {
    4.         H[r][c] = 0;
    5.         s = s + 4*tmp[r][c]; /*đầu tiên sơn xung quanh bốn bức tường của đơn nguyên*/
    6.    
    7.         /*Bỏ đi cạnh chung của những đơn nguyên cạnh nó, thằng nào thấp hơn thì chọn*/
    8.         s = s - min(tmp[r][c],tmp[r][c+1]) - min(tmp[r][c],tmp[r][c-1])  
    9.               - min(tmp[r][c],tmp[r+1][c]) - min(tmp[r][c],tmp[r-1][c]);
    10.        
    11.         if ( H[r+1][c] != 0 && H[r+1][c] != -1 ) Spreading_Programming (r+1, c, s);
    12.         if ( H[r-1][c] != 0 && H[r-1][c] != -1 ) Spreading_Programming (r-1, c, s);
    13.         if ( H[r][c+1] != 0 && H[r][c+1] != -1 ) Spreading_Programming (r, c+1, s);  
    14.         if ( H[r][c+1] != 0 && H[r][c-1] != -1 ) Spreading_Programming (r, c-1, s);
    15.  
    16. }

    Bài này thực ra không khó lắm nhưng chỗ này thì đúng là nhức cả đầu, hồi đầu anh cứ nghĩ là V[sơn] = cột*hàng*cao , debug mãi không ra kết quả. Phải vẽ ra cái hình mới hiểu được

    Anh nghĩ chắc đây là cái hay của bài này, không biết có phải không nhỉ ?

    Tiếp theo ta cứ loang theo vết của từng ô cho tới khi hết bảng ! Dùng 1 biến max_area để tính khối nhà có diện tích lớn nhất là xong !
    Còn 1 chỗ đáng chú ý là :
    H[r][c] = 0; /*tránh đi lại những ô đã đi qua, ví du dang xét ô H[1][3], ta kiểm tiếp tra ô [2][3], nhận thấy nó có khối nguyên ô [2][3], tiếp đến ta kiểm tra ô [3][5] thì không có khối nguyên, bỏ qua và quay lại xét sang ô [1][5] thì lại thấy đơn nguyên, loang lại ô [1][5] -> dẫn đến Stack Over Flow */
    nhưng vì gán H[r][c] = 0 cho nên khi tính diện tích ta lại mất đi chiều cao vì thế dùng 1 mãng phục tmp[r][c] ( chú ý không có viền cho mãng này ) là xong.

    Bài này có 2 vấn đề : 1 là phương pháp loang, 2 là công thức thể tích .

    Và sau đây là toàn bộ code :

    C++ Code:
    1. #include <iostream>
    2. #include <fstream>
    3. #include <iomanip>
    4.  
    5. #define FI "TOANHA.inp"
    6. #define maxx 100
    7.  
    8.  
    9. int H[maxx][maxx], tmp[maxx][maxx];
    10. int M, N; /*M represent Row, N represents Colunm*/
    11. int building;
    12. int max_area;
    13. int total_area;
    14.  
    15. void InputData()
    16.  
    17.     {
    18.         ifstream F;
    19.         F.open(FI);
    20.         F >> M >> N;
    21.         F.ignore();
    22.        
    23.         for ( int i = 1; i <= M; i++){
    24.                 for( int j = 1; j <= N; j++){
    25.                         F >> H[i][j];
    26.                 }
    27.             F.ignore();
    28.         }
    29.         F.close();
    30. }
    31.  
    32. void Initialization()
    33.  
    34.     {
    35.         /*Set range for the area*/
    36.         for ( int i = 0; i <= N+1; i++ ){
    37.                 H[0][i] = -1;
    38.                 H[M+1][i] = -1;
    39.         }
    40.      
    41.         for ( int i = 0; i <= M+1; i++ ){
    42.                 H[i][0] = -1;
    43.                 H[i][N+1] = -1;
    44.         }
    45.         /*Print map*/
    46.         for ( int i = 0; i <= M+1; i++ ){
    47.                 for ( int j = 0; j <= N+1; j++ ){
    48.                         cout << H[i][j] << setw(3);
    49.                 }
    50.                 cout << endl;
    51.         }
    52.        
    53.         /*Sub Array*/
    54.         for ( int i = 1; i <= M; i++)
    55.         {
    56.                 for( int j = 1; j <= N; j++ )
    57.                 {
    58.                         tmp[i][j] = H[i][j];
    59.                 }
    60.         }
    61. }
    62.  
    63. int min ( int a, int b )
    64.    
    65.     {
    66.         if ( a < b ) return a;
    67.         else         return b;
    68. }
    69.  
    70. void Spreading_Programming (int r, int c , int &s)
    71.  
    72.     {
    73.         H[r][c] = 0;        
    74.         s = s + 4*tmp[r][c]; /*Paint around the building, 4 sides*/
    75.    
    76.         /*Eleminate the share side of 2 building, which ones lower is chosen*/
    77.         s = s - min(tmp[r][c],tmp[r][c+1]) - min(tmp[r][c],tmp[r][c-1])  
    78.               - min(tmp[r][c],tmp[r+1][c]) - min(tmp[r][c],tmp[r-1][c]);
    79.        
    80.         if ( H[r+1][c] != 0 && H[r+1][c] != -1 ) Spreading_Programming (r+1, c, s);
    81.         if ( H[r-1][c] != 0 && H[r-1][c] != -1 ) Spreading_Programming (r-1, c, s);
    82.         if ( H[r][c+1] != 0 && H[r][c+1] != -1 ) Spreading_Programming (r, c+1, s);  
    83.         if ( H[r][c+1] != 0 && H[r][c-1] != -1 ) Spreading_Programming (r, c-1, s);
    84.  
    85. }
    86.  
    87. void Process()
    88.  
    89.     {
    90.        
    91.         int area;
    92.         building = 0;
    93.         max_area = 0;
    94.         total_area = 0;
    95.         for ( int i = 1; i <= M; i++)
    96.         {
    97.                 for( int j = 1; j <= N; j++)
    98.                 {
    99.                         if ( H[i][j] != -1 && H[i][j] != 0 ) /*If there's no "don nguyên*/
    100.                         {
    101.                                 area = 0;
    102.                                 Spreading_Programming ( i, j, area);
    103.                                
    104.                                 building = building + 1; /*Each time increases the number of building*/
    105.                                 total_area = total_area + area; /*Also increase total area*/
    106.                                 /*Chose building have maximum area*/
    107.                                 if ( area > max_area )
    108.                                 {
    109.                                         max_area = area;
    110.                                        
    111.                                 }
    112.                         }
    113.                 }
    114.         }
    115. }
    116.  
    117.  
    118. void OutputData()
    119.  
    120.     {
    121.        
    122.         cout << "There are : " << building << " buildings " << endl;
    123.         cout << "Total area is : " << total_area << endl;
    124.         cout << "The maximum area is : " << max_area << endl;
    125. }
    126.  
    127. void main()
    128.  
    129.     {
    130.         InputData();
    131.         Initialization();
    132.         Process();
    133.         OutputData();
    134.        
    135.         cin.get();
    136.  
    137. }
    Đã được chỉnh sửa lần cuối bởi rox_rook : 14-10-2007 lúc 02:58 PM.

  3. #3
    Ngày gia nhập
    06 2007
    Bài viết
    2

    Bài của bạn rox_rook còn thiếu một phần đấy là:
    bạn mới đếm được số ô vuông là đơn nguyên nhưng không đánh số được các khối nhà (block)
    Theo mình thì bài toán có thể giải quyết theo ý tưởng thế này:
    Mảng A, kích thước MxN trong đó:
    A[i][j] = 0 nếu H[i][j] = 0 (Không có nhà xây trên ô vuông này)
    A[i][j] = 1 nếu H[i][j] đã được chọn để tính vào tổng diện tích
    A[i][j] = -1 nếu H[i][j] chưa được chọn để tính tổng diện tích

    biến BlockCount: lưu số lượng các khối nhà

    Sử dụng thuật toán loang như bạn rox_rook giới thiệu:

    nếu còn tồn tại A[i][j] = -1
    Sử dụng thuật toán loang tại ô A[i][j]
    Tính toán tổng diện tích và diện tích Block lớn nhất
    Tăng biến BlockCount lên một đơn vị

  4. #4
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Kết quả ghi ra file văn bản gồm:
    * Dòng đầu ghi số lượng các khối nhà
    * Dòng thứ hai ghi tổng số diện tích quét vôi
    * Dòng thứ ba ghi số nhà của khối có diện tích quết vôi lớn nhất và giá trị của diện tích này ( ghi cách nhau ít nhất một dấu cách).
    Bài của bạn rox_rook còn thiếu một phần đấy là:
    bạn mới đếm được số ô vuông là đơn nguyên nhưng không đánh số được các khối nhà (block)
    Bạn check thử chưa code mình viết chưa nhỉ ?

  5. #5
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Output
    3
    50
    1 30
    Sorry, không thấy đường T_T ! Cám ơn ý kiến của bạn !

Các đề tài tương tự

  1. Giải thuật shaker sort. Giúp mình giải thuật với?
    Gửi bởi nguyenhai trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 6
    Bài viết cuối: 29-01-2015, 10:53 PM
  2. Giải thuật Giải thuật Chia để trị, hướng đi với giải thuật này thế nào?
    Gửi bởi maivivan13 trong diễn đàn Thắc mắc CTDL & Giải thuật
    Trả lời: 0
    Bài viết cuối: 23-10-2012, 10:22 PM
  3. Bài tập C Cần giải giúp 3 câu trong đề thi kĩ thuật lập trình C và Cấu trúc dữ liệu và giải thuật
    Gửi bởi nguyenthi0602 trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 2
    Bài viết cuối: 24-09-2012, 08:42 PM
  4. Giải thuật xắp xếp Quick sort, biểu diễn bằng hình ảnh giải thuật này?
    Gửi bởi yuklong trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 9
    Bài viết cuối: 09-06-2012, 09:20 AM
  5. Tài liệu về giải thuật mã hóa. Mã hóa file theo giải thuật DES. Ai có giúp mình?
    Gửi bởi daolong83 trong diễn đàn Công cụ, ebooks C#, ASP.NET, và Windows Mobile
    Trả lời: 6
    Bài viết cuối: 17-07-2009, 11:28 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn