Công cụ bảo vệ mã nguồn .NET mạnh nhất, không thể unpack, miễn phí cho các khách hàng đầu tiên đăng ký.
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
    Công cụ bảo vệ mã nguồn .NET mạnh nhất hiện tại, miễn phí cho các khách hàng đầu tiên đăng ký.

  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ông cụ bảo vệ mã nguồn .NET mạnh nhất hiện tại, miễn phí cho các khách hàng đầu tiên đăng ký.

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