Mô tả bài toán

Cho trước một dãy các hình tam giác được vẽ theo quy luật nhất định. Hãy phân tích logic của chương trình và điền vào phần code còn thiếu.

Hình ảnh mẫu

Với rank = 3:

   * 
  * * 
 *   *  
* * * *

Với rank = 5:

               *                                                      
              * *                                                     
             *   *                                                    
            * * * *                                                   
           *       *                                                  
          * *     * *                                                 
         *   *   *   *                                                
        * * * * * * * *                                               
       *               *                                              
      * *             * *                                             
     *   *           *   *                                            
    * * * *         * * * *                                           
   *       *       *       *  
  * *     * *     * *     * *  
 *   *   *   *   *   *   *   * 
* * * * * * * * * * * * * * * *  

Phân tích thuật toán

Quan sát kỹ các hình mẫu, ta nhận thấy một quy luật quan trọng: mỗi hình tam giác cấp cao hơn được tạo thành từ 3 hình tam giác cấp thấp hơn. Cụ thể:

• Hình cấp 4 được tạo từ 3 hình cấp 3
• Hình cấp 5 được tạo từ 3 hình cấp 4
• Hình cấp 6 được tạo từ 3 hình cấp 5

Như vậy công thức truy hồi là: f[i] = f[i-1] * 3

Cấu trúc của một tam giác cấp N:

                               *                                      
                              * *                                     
                             *   *                                    
                            * * * *                                   
                           *       *                                  
                          * *     * *                                 
                         *   *   *   *                                
                        * * * * * * * *                               
                       *               *                              
                      * *             * *                             
                     *   *           *   *                            
                    * * * *         * * * *                           
                   *       *       *       *                          
                  * *     * *     * *     * *                         
                 *   *   *   *   *   *   *   *                        
                * * * * * * * * * * * * * * * *                       
               *                               *                      
              * *                             * *                     
             *   *                           *   *                    
            * * * *                         * * * *                   
           *       *                       *       *                  
          * *     * *                     * *     * *                 
         *   *   *   *                   *   *   *   *                
        * * * * * * * *                 * * * * * * * *               
       *               *               *               *              
      * *             * *             * *             * *             
     *   *           *   *           *   *           *   *            
    * * * *         * * * *         * * * *         * * * *           
   *       *       *       *       *       *       *       *          
  * *     * *     * *     * *     * *     * *     * *     * *         
 *   *   *   *   *   *   *   *   *   *   *   *   *   *   *   *        
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *       

Code mẫu

Chương trình C++ sử dụng đệ quy để vẽ hình như sau:

#define MAX_SIZE 70
 
void drawPattern(char pattern[][MAX_SIZE], int level, int startRow, int startCol)
{
    if (level == 1) {
        pattern[startRow][startCol] = '*';
        return;
    }
    
    int size = 1;
    int idx;
    for (idx = 0; idx < level - 1; idx++) {
        size *= 2;
    }
    
    // Điền vào đây: gọi đệ quy cho tam giác phía trên
    drawPattern(pattern, level - 1, startRow, startCol + size / 2);
    
    // Hai tam giác phía dưới
    drawPattern(pattern, level - 1, startRow + size / 2, startCol);
    drawPattern(pattern, level - 1, startRow + size / 2, startCol + size);
}
 
int main()
{
    char pattern[MAX_SIZE][MAX_SIZE];
    int r, c;
    
    for (r = 0; r < MAX_SIZE; r++) {
        for (c = 0; c < MAX_SIZE; c++) {
            pattern[r][c] = ' ';
        }
    }
    
    drawPattern(pattern, 6, 0, 0);
    
    for (r = 0; r < MAX_SIZE; r++) {
        for (c = 0; c < MAX_SIZE; c++) {
            printf("%c", pattern[r][c]);
        }
        printf("\n");
    }
    
    return 0;
}

Giải thích chi tiết

Trong hàm drawPattern, tham số level biểu thị cấp của tam giác, startRow là hàng bắt đầu, và startCol là cột bắt đầu.

Khi level = 1, ta vẽ một dấu sao duy nhất tại vị trí (startRow, startCol).

Với level > 1, ta cần vẽ 3 tam giác con:

1. Tam giác trên cùng: Vị trí bắt đầu tại hàng startRow, cột startCol + size/2
2. Tam giác dưới trái: Vị trí bắt đầu tại hàng startRow + size/2, cột startCol
3. Tam giác dưới phải: Vị trí bắt đầu tại hàng startRow + size/2, cột startCol + size

Biến size được tính bằng công thức: 2^(level-1), đại diện cho chiều cao và chiều rộng của tam giác cấp đó.

Đáp án

Phần code còn thiếu cần điền vào là:

drawPattern(pattern, level - 1, startRow, startCol + size / 2);

Lệnh này thực hiện đệ quy để vẽ tam giác nằm ở vị trí trên cùng của tam giác hiện tại, với tọa độ cột được dịch sang phải một khoảng bằng một nửa kích thước.