Trang 1 trên tổng số 3 123 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 21 kết quả

Đề tài: Chia hình chữ nhật thành các hình vuông

  1. #1
    Ngày gia nhập
    10 2007
    Nơi ở
    Huế
    Bài viết
    11

    Mặc định Chia hình chữ nhật thành các hình vuông

    Các bạn giúp mình bài này với:

    Cho 1 hình chữ nhật m x n hãy chia nó thành các hình vuông sao cho tổng số hình vuông là ít nhất
    Ví dụ: HCN 6 x 5 thì ta chia thành các hình vuông (3x3) (3x3) (2x2) (2x2) (2x2)

    Cái này mình có post ở diễn đàn tin học, post lại đây mong mọi người cùng giải quyết
    [COLOR="RoyalBlue"]Mẹ đời cho ta ngã để dạy ta nên người[/COLOR]

    My blog: [URL="http://mucdongblog.wordpress.com"]http://mucdongblog.wordpress.com[/URL]

  2. #2
    Ngày gia nhập
    07 2007
    Nơi ở
    Sơn La
    Bài viết
    133

    Trích dẫn Nguyên bản được gửi bởi {mucdong} Xem bài viết
    Các bạn giúp mình bài này với:

    Cho 1 hình chữ nhật m x n hãy chia nó thành các hình vuông sao cho tổng số hình vuông là ít nhất
    Ví dụ: HCN 6 x 5 thì ta chia thành các hình vuông (3x3) (3x3) (2x2) (2x2) (2x2)

    Cái này mình có post ở diễn đàn tin học, post lại đây mong mọi người cùng giải quyết
    Bạn có thể tham khảo đoạn code này.Nhưng hơi bận nên tôi chỉ code để chỉ ra là số ít nhất mà HCN đó có thể chia được thôi.
    Code:
    #include "iostream"
    using namespace std;
    
    int Try(int d,int r,int count){
       if(r==0) return 0;
       if(d%r==0) return d/r;   
       for(int i=r;i>r/2;i--)
       {
    	  int count1=1+Try((d-i)>i?(d-i):i,(d-i)>i?i:(d-i),count)+ Try(d,r-i,count);		  
    	  count=count>count1?count1:count;
       }	 	 
       return count;
    }
    void main(void){	
       int d,r;
       cout<<"Nhap chieu dai  HCN:";cin>>d;
       cout<<"Nhap chieu rong HCN:";cin>>r;
       cout<<"Nhu vay co the chia duoc so hinh vuong it nhat la:"<<Try(d,r,d);
       cout<<endl;
       return;
    }
    Để chỉ rõ được cấu hình của hình vuông thì bạn có thể làm như sau:
    1.Tạo linklist
    2.Mỗi bước tạo hình vuông thì đẩy nó vào linklist và đếm số cấu hình này lên
    3.Nếu thỏa mãn count>count1 thì lưu linklist này còn không thì phải giải phóng nó.
    Bạn có thể hình dung một cấu hình có thể tạo như sau:
    Code:
     struct HV{
       int count;
       int key;
       HV *next;
     };
    Đoạn này áp dụng bài toán đếm số phần tử của một chuỗi.
    Có gì chúng ta sẽ trao đổi tiếp sau nhé.
    Hix, măm măm cái đã.
    Trao đổi kiến thức sẽ giúp ta tiếp cận nhanh với kiến thức.

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

    Bạn có thể giải thích thêm về cách dùng link list không? Mình thấy bài này dùng QHD thì có lẽ hay hơn. Do mình chưa hiểu Link List nên ko biết nó hoạt động giống đệ qui không nhưng mình chạy thử với r và d > 100 thì chạy không nổi.!!

  4. #4
    Ngày gia nhập
    07 2007
    Nơi ở
    Sơn La
    Bài viết
    133

    Mình chưa học đến QHD , lúc vừa đọc đề bài thì mình cũng nghĩ đến QHD(vì trước đây trong diễn đàn có một bài toán (tôi không nhớ lắm), sau đó mọi người giải nó bằng QHĐ.chưa học nên mình duyệt đệ quy ở bài này.
    Còn cái linklist chỉ là để lưu lại các bước đã tạo được hình vuông với cạnh là Key thôi.
    Bạn có thể làm bằng QHD rồi post lên tôi tham khảo được không?Tôi đang học CTDL đến AVL thôi.
    Trao đổi kiến thức sẽ giúp ta tiếp cận nhanh với kiến thức.

  5. #5
    Ngày gia nhập
    07 2007
    Nơi ở
    Sơn La
    Bài viết
    133

    Mình vừa sửa lại cái hàm Try như sau:
    Code:
    int Try(int d,int r,int count){
       if(r==0) return 0;
       if(d%r==0) return d/r;   
       int min;
       if(d>2*r) min=r-1;else min =r/2;
       for(int i=r;i>min;i--)
       {
    	  int count1=1+Try((d-i)>i?(d-i):i,(d-i)>i?i:(d-i),count)+ Try(d,r-i,count);		  
    	  count=count>count1?count1:count;
       }	 	 
       return count;
    }
    Chúng ta cùng thảo luận nhé.Mình nghĩ vẫn chưa tối ưu hết .
    Trao đổi kiến thức sẽ giúp ta tiếp cận nhanh với kiến thức.

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

    Mặc định Chia hình chữ nhật thành các hình vuông

    Bạn cho mình chút thời gian nhé ! Do mình đang học bài cho thứ 2, mình CM gần ra cái 1 nhát cắt hoàn toàn mà {mucdong} đã thảo luận rồi, nhưng chưa triệt để vì chưa tổng quát lên dc mọi trường hợp, vì chỉ cần CM được điều này thì có thể áp dụng QHD, với lại mình cũng chưa cài đặt nữa, chỉ có ý tưởng thôi. Bạn có thể đọc vài ví dụ trong box mình post về QHD, nó cũng ko có gì đâu nhưng về mặt thời gian thì tốt hơn đệ qui rất nhiều.

  7. #7
    Ngày gia nhập
    10 2006
    Nơi ở
    In Your Bugs
    Bài viết
    823

    Tớ không thấy khoái bài này lắm. Anh em cứ phân tích tiếp.
    Về QHD thì cũng không có gì cả ? Hãy nhớ đến bài toán những chú thỏ hay dãy fibo , đấy chính là QHD. Hi vọng rox_Rook sẽ giải quyết "lát cắt" này thành công. Về tài liệu tớ cũng nhắn NT_OnlyLove xem lại sách của thầy Nguyễn Minh Hoàng (Tớ ko chắc là họ tên đều đúng.) Quyển này tớ có xem qua menu. Thấy cũng rất hay và đề cập đến cả QHD .

    Chúc anh em mau tiến bộ

  8. #8
    Ngày gia nhập
    08 2006
    Bài viết
    59

    Tui xin ké vô 1 chút,

    2 bạn rox_rook & kidkid có nhắc tới lát cắt hoàn toàn (xuyên suốt) nhưng tui không thấy phần thảo luận về "lát cắt" ở đâu !
    => tui đoán là ở diễn đàn bên kia ?

    Cho tới giờ tui đã thấy 2 cách giải được đề nghị:
    1) Chọn 1 kích thước cho hình vuông con (chiều dài cạnh là 1 sô nguyên) => trừ nó ra và đệ qui cho phần diện tích còn lại
    2) QHĐ: ở mỗi bước xài 1 lát cắt hoàn toàn xuyên suốt để chia hình chữ nhựt đang có ra làm 2 phần (chiều dài các cạnh cũng là số nguyên)

    Tui nghĩ nếu giải chặt chẽ thì:
    - với cách 1: phải chứng minh là chiều dài các cạnh là số nguyên là được rồi (lưu ý đề bài không cấm mình chọn chiều dài cạnh là 1 phân số như 5/2 chẳng hạn)
    - với cách 2 (QHĐ): phải chứng minh chỉ cần chọn chiều dài cạnh là số nguyên như ở cách 1 . Và phải chứng minh thêm là chỉ cần xài lát cắt hoàn toàn xuyên suốt là đủ rồi (có vẻ như bạn rox_rook đang thử chứng minh cái này !?)

    (hiểu biết nông cạn; có gì sai sót mong được góp ý; xin cám ơn)

    -thân

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

    phải chứng minh chỉ cần chọn chiều dài cạnh là số nguyên như ở cách 1
    Điều này mình nghĩ đề bài nó sẽ cho mình hiểu là như vậy, vì thực sự mình cũng không nghĩ tới phải CM cái này.
    Vấn đề thứ 2, nhát cắt xuyên suốt mà mình các bạn bên ddth bàn luận mình nghĩ có lẽ nhầm 1 chỗ, nhát cắt ở đây là phải chia hình CN ra 2 hình chữ nhật riêng biệt ( chứ không phải 1 vuông và 1 HCN ) vì cơ bản nếu vuông thì nó sẽ là cơ sở của QHD rồi. Không biết bete nghĩ sao ?

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

    Mình có cách CM sau cho giải thiết nhát cắt hoàn toàn :
    - Khi ta có 1 nhát cắt của 1 hình chữ nhất Length x Width ta sẽ cho ra 1 hình con khác ( có thể là hình chữ nhật hoặc có thể là hình vuông ) từ đây ta luôn có được những kích thước khác nhau của hình mới sinh ra.
    - Nếu ta cắt có nhát cắt _cP ( theo chiều ngang thì ) thì ta có được hình còn lại hình ( Length - _cP, Width).
    + Nếu Length - _cP > Witdh ta xét [Length - _cP)/Width].
    + Nếu Length - _cP < Witdh ta xét [Width/ Length - _cP].
    Tỉ lệ này sẽ nói lên rằng với nhát cắt khác nhau thì sẽ cho số hình vuông khác nhau. Mặt khác tỉ lệ tói thiểu của 1 hình vuông sẽ có size = 1. Vậy số hình vuôn nhiều nhất chính là tỉ lệ này. (*)
    Dùng phản chứng : giả sử mọi vết cắt đều cho cùng 1 số hình vuông cố định. Dùng qui nạp cho trường hợp ( (L, W > 3) ta có đều này là sai.
    Xét tỉ lệ cho (L+1, W) hoặc (L, W+1 ), ta thấy tỉ lệ của nó sẽ thay đổi. Theo (*) ta có thể kết luận rằng luôn tồn tại 1 nhát cắtlàm cho số hình vuông là nhỏ hơn hoặc bằng 1 nhát khác.

    Hic, mình giải thích có vẻ lung tung quá nhỉ.
    Từ đây ta có thể áp dụng QHD :
    Gọi Rectangle[xPos][yPos] là số hình vuông cắt được nhỏ nhất có dài là xPos và rộng là yPos.

    Với giả thiết QHD là Rectangle[xPos][yPos] = 1 ( ta cắt được 1 hình vuông )
    Ta tính ma trận kết quả theo chiều dài và rộng như sau : ( vết cắt _cP )
    Chiều dọc : Rectangle[xPos][yPos] = min ( Rectangle[xPos][yPos], Rectangle[_cP][yPos] + Rectangle[xPos-_cP][yPos] )
    Chiều ngang :
    Rectangle[xPos][yPos] = min ( Rectangle[xPos][yPos], Rectangle[xPos][_cP] + Rectangle[xPos][yPos-_cP])

    Vậy Rectangle[length][width] sẽ là phương án.
    Ta dùng 2 mãng phụ : Dy[][], Dx[][] để lưu vết cắt của theo chiều dọc và ngang.
    Ta dùng thêm 1 hàm đệ qui để truy vết cắt dựa vào 2 mãng phụ như sau :
    PHP Code:
    void Square::Cut_Process(int xPosint yPos)
    {
          if ( 
    xPos == yPos )
          {
                
    cout << xPos << " x " << yPos;
                
    cout << "\n\n";
                
    Display (xPosyPos);
                
    cout << endl;
          }
          else
          {
                if ( 
    Dx[xPos][yPos] != )
                {
                      
    Cut_Process(xPos Dx[xPos][yPos], yPos);
                      
    Cut_Process(Dx[xPos][yPos], yPos);
                }
          
                else
                {
                      
    Cut_Process(xPosyPos Dy[xPos][yPos]);
                      
    Cut_Process(xPosDy[xPos][yPos]);
                }
          }

    Chú ý chỗ cắt ngược lại 2 phần :
    Cut_Process(xPos - Dx[xPos][yPos], yPos);
    Cut_Process(Dx[xPos][yPos], yPos);
    Lúc đầu cắt có 1 bên debug mãi không ra , hichic !

    Do QHD tốn nhiều không gian lưu trữ nên mình cấp phát động luôn cho nó, đây là toàn bộ văn bản cài đặt bằng C++:
    PHP Code:
    #include <iostream>
    #include <string>
    #include <sstream>

    using namespace std;

    class 
    Canvas
    {
      public:
          
    Canvas(int widthint height) : width(width),height(height)
          {
              
    text = new char *[height+1];
              for( 
    int x 0<= height; ++x)
              {
                  
    text[x] = new char[width+1];
                  for( 
    int j 0;<= width; ++j)
                      
    text[x][j]=' ';
              }
          }
     
       ~
    Canvas()
        {
            for( 
    int x 0<= heightx++)
                
    delete[] text[x];
           
    delete[] text;
        }
     
        
    void Draw_Rectangle(int x0int y0int widthint heightstring label)
        {
            for( 
    int i 0<= width; ++i)
                
    text[y0][x0+i] = text[y0+height][x0+i]='-';
       
            for( 
    int i 1height; ++i)
                
    text[y0+i][x0] = text[y0+i][x0+width]='|';
       
            for( 
    int i 0label.length(); ++i)
                
    text[y0+height/2][x0+width/2-label.length()/2+i] = label[i];
        }
     
        
    friend ostream operator<<(ostream &outputCanvas const &c);
      private :
          
    int heightwidth;
          
    char **text;
    };

    ostream &operator << (ostream &outputCanvas const &Obj)
    {
        for( 
    int i 0<= Obj.height;++i)
        {
            for( 
    int j 0;<= Obj.width;++j)
                
    output << Obj.text[i][j];
            
    output << '\n';
        }
        return 
    output;
    }

    class 
    RectangleIntoSquaresProblem
    {
      public :
          
    RectangleIntoSquaresProblem(int widthint height);
         ~
    RectangleIntoSquaresProblem();
     
          
    int solve();
          
    void Dynamic_Programming();
          
    void Show_Cut_Process(ostream &output) const;
          
    void Draw_Cut_Process(Canvas &cint x0int y0int xPosint yPos) const;
     
      private :
          
    int **Rectangle;
          
    int **Dx, **Dy;
          
    int heightwidth;
     
          static const 
    int MAX=1000;
    };

    RectangleIntoSquaresProblem::RectangleIntoSquaresProblem(int width,int height) : width(width), height(height)
    {
        
    Rectangle = new int *[width+1];
        
    Dy = new int *[width+1];
        
    Dx = new int *[width+1];
     
        for( 
    int x 0<= width; ++x)
        {
            
    Rectangle[x] = new int[height+1];
            
    Dx[x] = new int[height+1];
            
    Dy[x] = new int[height+1];
         
            for ( 
    int y 0<= heighty++)
            {
                
    Rectangle[x][y] = 0;
                
    Dx[x][y] = 0;
                
    Dy[x][y] = 0;
            }
        }
    }

    RectangleIntoSquaresProblem::~RectangleIntoSquaresProblem()
    {
        for( 
    int x 0<= widthx++){
            
    delete[] Rectangle[x];
            
    delete[] Dx[x];
            
    delete[] Dy[x];
        }
        
    delete[] Rectangle;
        
    delete[] Dx;
        
    delete[] Dy;
    }

    int RectangleIntoSquaresProblem::solve()
    {
        
    Dynamic_Programming();
        return 
    Rectangle[width][height];
    }

    void RectangleIntoSquaresProblem::Dynamic_Programming()
    {
        
    int _cP;
        for ( 
    int xPos 1xPos <= widthxPos++ )
        {
            for ( 
    int yPos 1yPos <= heightyPos++ )
            {
                if ( 
    xPos == yPos )
                {
                    
    Rectangle[xPos][yPos] = 1;
                }
                else
                {
                    
    Rectangle[xPos][yPos] = MAX;
                    for ( 
    _cP 1_cP <= xPos-1_cP++ )
                    {
                        if ( 
    Rectangle[xPos][yPos] > Rectangle[_cP][yPos] + Rectangle[xPos-_cP][yPos] )
                        {
                            
    Rectangle[xPos][yPos] = Rectangle[_cP][yPos] + Rectangle[xPos-_cP][yPos];
                            
    Dx[xPos][yPos] = _cP;
                            
    Dy[xPos][yPos] = 0;
                        }
                    }
                    
                    for ( 
    _cP 1_cP <= yPos-1_cP++ )
                    {
                        if (  
    Rectangle[xPos][yPos] > Rectangle[xPos][_cP] + Rectangle[xPos][yPos-_cP] )
                        {
                            
    Rectangle[xPos][yPos] = Rectangle[xPos][_cP] + Rectangle[xPos][yPos-_cP];
                            
    Dy[xPos][yPos] = _cP;
                            
    Dx[xPos][yPos] = 0;
                        }
                    }
                }
            }
        }             
    }

    void RectangleIntoSquaresProblem::Show_Cut_Process(ostream &output) const
    {
        
    Canvas Obj(4*width+12*height+1);
        
    Draw_Cut_Process(Obj00widthheight);
      
        
    output << Obj;
    }

    void RectangleIntoSquaresProblem::Draw_Cut_Process(Canvas &Objint x0int y0int xPosint yPos) const
    {
        if ( 
    xPos == yPos )
        {
            
    ostringstream oss;
            if( 
    xPos )
                
    oss << xPos << 'x' << yPos;
                
    Obj.Draw_Rectangle(4*x02*y04*xPos2*yPososs.str());
       
        }
        else
        {
            if ( 
    Dx[xPos][yPos] != )
            {
                
    Draw_Cut_Process(Objx0y0Dx[xPos][yPos], yPos);
                
    Draw_Cut_Process(Objx0 Dx[xPos][yPos], y0xPos Dx[xPos][yPos], yPos);
            }
            else
            {
                
    Draw_Cut_Process(Objx0y0xPosDy[xPos][yPos]);
                
    Draw_Cut_Process(Objx0y0 Dy[xPos][yPos], xPosyPos Dy[xPos][yPos]);
            }
        }
    }

    int main(void)
    {
        
    int WH;
        
    cout << "Enter the Width and Height: " << flush;
        
    cin >> >> H;
     
        
    RectangleIntoSquaresProblem problemInstance(W,H);
     
        
    cout << "The minimum number of squares required is " << problemInstance.solve() << "\n";
        
    problemInstance.Show_Cut_Process(cout);
        
    system("pause");

    Code này chạy được với length và width cỡ > 200 khoảng chừng 3s.
    Đã được chỉnh sửa lần cuối bởi rox_rook : 25-11-2007 lúc 10:07 AM.

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

  1. Bài tập C++ Nhập mảng 1 chiều, nếu phần tử nhập trùng nhau thì bắt nhập lại
    Gửi bởi danielh trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 3
    Bài viết cuối: 09-07-2011, 03:35 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