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ố 27 kết quả

Đề tài: Bài toán 1000 quân hậu | Bài toán quân hậu

  1. #1
    Ngày gia nhập
    10 2006
    Nơi ở
    Hà Nội
    Bài viết
    146

    Talking Bài toán 1000 quân hậu | Bài toán quân hậu

    Chắc các bạn đã từng biết đến bài toán xếp Quân Hậu trên bàn cờ.
    Vấn đề đặt ra là, với bàn cờ 1000*1000 thì như thế nào.
    Hãy tìm lời giải cho bài toán 1000 quân hậu nhé.

  2. #2
    Ngày gia nhập
    10 2006
    Nơi ở
    Rừng Amazon
    Bài viết
    101

    Duyệt toàn bộ kết hợp nhánh cận.

  3. #3
    Ngày gia nhập
    10 2006
    Nơi ở
    Hà Nội
    Bài viết
    146

    Trả lời cộc lốc vậy.
    Nêu ra thuật toán từng bước chứ. Rồi cho chương trình mô phỏng.

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

    chắc chết quá , ai đủ kiên nhẫn ngồi chờ bài này . Cho dù đã dùng nhánh cận, nhưng mà thời gian chạy vẫn khủng khiếp.
    popopo có cao kiến gì thì chỉ bảo đi?
    đây là bài của tui. Đố các bác biết là cách nào để chỉ cần đánh dấu bằng 2 mảng 1 chiều thôi
    Code:
    #include<stdio.h>
    #include<conio.h>
    int d[1000]={0},c[1000]={0},cp[1999]={0},cc[1999]={0};
    const int max=999;
    void ty(int , int *);
    void main()
    {
     int n=0,dem=0;
     clrscr();
     printf("bai toan xep hau\n");
     printf("so quan hau: %d",max+1);
     ty(n,&dem);
     printf("\nco: %d cach",dem);
     getch();
    }
    void ty( int n, int *dem)
    {
     int i,j;
     for (i=0; i<=max; i++)
    	 {
    	  if (!d[i])
    		  for (j=0; j<=max; j++)
    			  {
    			  if (!c[j])
    
    				  if ((!cp[i+j]) && (!cc[max+j-i]))
    					 {
    						d[i]++; c[j]++; cp[i+j]++; cc[max+j-i]++;
    						n++;
    						if (n== max) *dem= *dem +1;
    						else ty(n, dem);
    						d[i]--; c[j]--; cp[i+j]--; cc[max+j-i]--;
    						n--;
    					 }
    
    				}
    	 }
    }

  5. #5
    Ngày gia nhập
    10 2006
    Nơi ở
    Rừng Amazon
    Bài viết
    101

    Tôi không hiểu chương trình của bạn melaptrinh lắm. Đọc qua thấy có vấn đề, tại sao trong thủ tục đệ quy cần đến 2 vòng lặp. Theo tôi chỉ 1 vòng.

    Đóng góp ý kiến tôi sẵn sàng, còn code thì tôi làm lâu quá rồi, với lại bây giờ bận quá, không làm được. Mà cũng không biết có chạy được với n = 1000 không nữa.

    Ý kiến tôi trình bày dưới đây sẽ trình bày theo hệ tọa độ với gốc là 0,0, gốc tọa độ đặt tại ô trên cùng, bên trái bàn cờ.

    Bài toán n con hậu ta đưa về bài toán duyệt hoán vị, với định nghĩa a[i] = k có nghĩa là con hậu thứ i được xếp vào hàng thứ k.

    Theo thuật ngữ cờ vua, khi con hậu i được xếp vào hàng k, nó sẽ chiếm lĩnh cột thứ i, hàng k và 2 đường chéo. Đường chéo thứ nhất bao gồm các ô (x, y) có ̀tọa độ thỏa mãn x - y = i - k. Đường chéo thứ 2: x - n - y = i - n - k. Như vậy để đánh dấu những ô đã được chiếm lĩnh, ta chỉ cần 2 mảng 1 chiều, thêm 1 mảng 1 chiều lưu phương án nữa là 3.

    Mọi người cùng code nhé (tớ không code) .

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

    Mặc định Bài toán 1000 quân hậu | Bài toán quân hậu

    đúng, chương trình trên tôi code chưa tối ưu, tôi còn để lại vài điểm có thể biến đổi thế thì mới có chỗ để cho mọi người bàn chứ.
    bạn chỉ ra dùng 3 mảng là rút gọn về bộ nhớ giống như mình nói từ đầu(chỉ cần 2 mảng 1 chiều để đánh dấu) tuy nhiên nó làm thời gian chạy tăng lên(để kiểm tra hàng đó đã điền hậu chưa không thể chỉ dùng 1 câu if bình thường là xong ngay được.
    VD đã điền 1 con vào ô [3,5] thì bạn sẽ phải gán a[5]=3;....
    nhưng ở chỗ khác, làm sao kiểm tra ngay lập tức hàng 3 đã đặt hậu chưa
    (đây là tôi nghĩ thế- không biết có đúng không)
    còn về vòng lặp, mình chưa từng sử dụng chỉ 1 vòng lặp bao giờ bạn có thể chỉ rõ hơn không?
    tiếp tục thảo luận nhé: đố bác nào làm bài này mà không dùng đệ quy
    Đã được chỉnh sửa lần cuối bởi melaptrinh : 22-03-2007 lúc 10:28 PM. Lý do: gõ sai chính tả

  7. #7
    Ngày gia nhập
    10 2006
    Nơi ở
    Rừng Amazon
    Bài viết
    101

    Ý tôi nói bài toán được đưa về bài toán nhỏ hơn: duyệt tất cả các hoán vị của n phần tử. Bản thân bài toán duyệt tất cả các hoán vị của n phần tử đã có 1 mảng 1 chiều để lưu lại. Tận dụng điều này ta đã đánh dấu được hàng và cột. Còn 2 đường chéo là thêm 2 mảng nữa thôi.

    Thứ nữa, bản thân thuật toán duyệt tất cả các hoán vị bằng đệ quy vốn chỉ có 1 vòng lặp ( tham khảo trong các sách Toán Rời Rạc ). Như vậy tại sao cần vòng lặp thứ 2?

    Cuối cùng, làm không dùng đệ quy ta vẫn có thể sinh ra tất cả các hoán vị của n phần tử được (dùng phương pháp Sinh - hàm Sinh, tham khảo trong các sách toán rời rạc). Tuy nhiên, phương pháp này không thể nhánh cận được, do đó thời gian là rất lớn.

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

    Ai có code chạy được với 1000 hậu cho mình tham khảo nhé ! mình cũng có tham khảo nhiều cách rồi, nhưng chặng có cách nào chạy nổi 1k hậu hết hix hix
    Sau đây là vài cách để các bạn tham khảo nè :
    Code:
     
       Sử dùng thư viện algorithm, thuật toán permutation ( hoán vị )
    #include <iostream> 
    #include <algorithm> 
    #include <conio.h>
    int main()
    { 
      const size = 8;
      int p[size];
      for ( int i = 0; i < size; i++)
              p[i] = i;
      
      do
      { 
              for( int i = 1 ; i < size ; i++)
              { 
                        for( int j = 0 ; j < i; j++)
                        { 
                            if ( abs( p[i] - p[j] ) == i - j )  
                            
                                  goto not_a_solution; 
                        } 
              } 
        
              for( int k = 0; k < size; k++)
              { 
                        for( int l = 0 ; l < size ; l++) 
                        {  
                                cout << "_Q"[p[k]==l] << ' ';
                        }
                  cout << '\n';
                
              } 
              cin.get();
              cout << endl; 
              not_a_solution:; 
      } 
      while   (next_permutation(p,p+size)); 
    
      
    getch();
    }
    Còn cái này giải không đệ qui :
    Code:
    #include <iostream>
    #include <iomanip>
    
    
    void initialization();			
    const int size = 8;
    int index;
    
    bool  cols[size], fwd_dias[2 * size - 1], bwd_dias[2 * size - 1];
    bool Q[size][size];
    int Temp[size];
    
    ///////////////////////////////////////////////////////////////////////////////////////////////
    
    void initialization()
    {
    	
    
    
    	
    	for (int i = 0; i < size; i++)
    	{
    		for(int j = 0; j < size; j++)
    		{
                              Q[i][j] = false;
                             
                    }
            }
    
    	
    	for ( int i = 0; i < size; i++)
    	{
                    cols[i] = true;
            
            }
    	
    	for ( int i = 0; i < 2 * size - 1; i++)
    	{
    		fwd_dias[i] = true;
    		bwd_dias[i] = true;
    	}
    }
    void print()
    {
    
            for (int i = 0; i < size; i++)
    	{
    		for(int j = 0; j < size; j++)
    		{
    			if (Q[i][j] == true)
    				cout << " Q ";
    			else 
                                    cout <<  " - ";
    		}
    		cout << "\n\n";
    	}
            cout << "----------------------------"  << endl;
    
            
    }
      
    
    
    bool check ( int row, int col )
    {
                      if (cols[col]==false||fwd_dias[(size-1)-row+col]==false||bwd_dias[col+row]==false)            
                            return false;
                      else
                            return true;
    }
    void main()
    {
        initialization();
        int r = 0, c = 0, index = 0;
    while  (r != size)          
    {
                  for ( int ss = c; ss < size; ss++ )
                  {
                              if ( check ( r, ss )  )
                              {
                                      Q[r][ss] = true;
                                      cols[ss] = false;
                                      fwd_dias[size-1-r+ss] = false;
                                      bwd_dias[r+ss] = false; 
                                      Temp[r] = ss;   
                                      c = 0;
                                      r++;
                                      break;
                              }
                              else if ( ss >= size-1 )
                              {
    				c = ss;
                                    
    				while ( c >= size-1)
    				{
                                            --r;  
                                            c = Temp[r];
                                            Q[r][c] = false;
                                            cols[c] = true;
                                            fwd_dias[size-1-r+c] = true;
                                            bwd_dias[r+c] = true; 
                                                    
                                    }
                                    c++;
                                    ss = c;
                              }
                  }
              print();
              index++;    
              cout << " TIMES " << index << endl;
    }
      cin.get();
    }
    Cái này heuristic :
    Code:
    #include <iostream.h>
    #define n 8
    void check(int [n][n], int, int ,int);
    void print(int [n][n]);
    void f(int [n][n],int,int,int);
    void clear(int [n][n]);
    int main()
    {
    	int a[n][n],i,j;
    	cout <<"\n..................................................";
    	cout <<"\neight queens problem";
    	cout <<"\n..................................................";
    	for(i=0;i<n;i++)
    		for(j=0;j<n;j++)
    			a[i][j]=0;
    	cout << "\n possible solutions:.....\n\n\n\n";
    	f(a,0,0,0);
    	return 0;
    }
    //*************************************************************************
    void f(int a[n][n],int row, int col, int d)
    {
    	int i,j;
    	if(d==1)
    		i=col;
    	else
    		i=0;
    	for(i=i;i<n;i++)
    	{
    		if(a[row][i]==0)
    		{
    			a[row][i]=1;
    			if(row==(n-1))
    				print (a);
    			else
    			{
    				check(a,row,i,1);
    				f(a,row+1,col,0);
    			}
    		}
    			for(j=0;j<n;j++)
    				if(a[row][j]==1)
    				{
    					a[row][j]=0;
    					clear(a);
    				}
    			check(a,row,i,0);
    	}
    }
    //********************************************************************88
    void print(int a[n][n])
    {
    	int i,j;
    	static int counter=1;
    	cout << "solution #"<<counter;
    	for(i=0;i<n;i++)			
    		for(j=0;j<n;j++)
    			if(a[i][j]==1)
    				cout <<"\t("<<i+1<<","<<j+1<<")";
    					
    	cout << "\n";
    	counter++;
    
    }
    //**********************************************************************
    void check(int a[n][n], int row, int col, int d)
    {
    	int i,j;
    	if(d==1)
    	{
    		for(i=row+1;i<n;i++)
    			a[i][col]=-1;
    		for(i=row-1;i>=0;i--)
    			a[i][col]=-1;
    		for(j=col+1;j<n;j++)
    			a[row][j]=-1;
    		for(j=col-1;j>=0;j--)
    			a[row][j]=-1;
    		for(i=row+1,j=col+1;i<n && j<n;i++,j++)
    			a[i][j]=-1;
    		for(i=row+1,j=col-1;i<n && j>=0;i++, j--)
    			a[i][j]=-1;
    	}
    	else
    		for(i=0;i<n;i++)
    			for(j=0;j<n;j++)
    				if(a[i][j]==1)
    					check(a,i,j,1);
    }
    //***********************************************************************
    void clear(int a[n][n])
    {
    	int i,j;
    	for(i=0;i<n;i++)
    		for(j=0;j<n;j++)
    			if(a[i][j]!=1)
    				a[i][j]=0;
    }
    Đệ qui :
    Code:
    #include <iostream>
    
    void initialization();			// khoi tao cac gia tri cua array
    bool check(int row, int col);	// kiem tra o (row, col) co dat duoc quan hau khong
    void put(int row, int col);		// dat quan hau len ban co, danh dau col va 2 duong cheo
    void unput(int row, int col);	// phuc hoi lai ban co nhu truoc khi dat quan hau
    void queen(int row);			// chuong trinh dat 8 hau len ban co
    void print();					// in ket qua ra man hinh
    
    const int size = 8;
    int index;
    
    bool a[size][size], cols[size], fwd_dias[2 * size - 1], bwd_dias[2 * size - 1];
    
    void main()
    {
    	initialization();
    	queen(0);
    	cout << "\n\nNhu vay co tat ca " << index << " truong hop ung voi size = " << size;
    	int x;
    	cin >> x;
    }
    
    
    // khoi tao gia tri
    void initialization()
    {
    	index = 0;
    
    
    	// a[i][j] == true neu co quan hau dat tren no
    	for (int i = 0; i < size; i++)
    	{
    		for(int j = 0; j < size; j++)
    			a[i][j] = false;
    	}
    
    	// cols[i] == true neu khong co quan hau nao an cot` i
    	for (i = 0; i < size; i++)
    		cols[i] = true;
    	
    	// truong hop hai duong cheo cung tuong tu voi col
    	for (i = 0; i < 2 * size - 1; i++)
    	{
    		fwd_dias[i] = true;
    		bwd_dias[i] = true;
    	}
    }
    
    
    
    
    // kiem tra xem co the dat quan hau len o a[row][col] hay khong
    bool check(int row, int col)
    {
    	// chi can col hay 1 trong 2 duong cheo di qua a[row][col] thi tra ve false
    	if (cols[col] == false || fwd_dias[(size - 1) - col + row] == false || bwd_dias[col + row] == false)
                return false;			// khong dat duoc quan hau
    	else 
                return true;			// co the dat duoc quan hau
    }
    
    
    
    
    // dat quan hau vao o a[row][col]
    void put(int row, int col)
    {
    	a[row][col] = true;
    	cols[col] = false;
    	fwd_dias[(size - 1) - col + row] = false;
    	bwd_dias[col + row] = false;
    }
    
    
    
    // phuc hoi lai ban co nhu truoc khi dat quan hau
    void unput(int row, int col)
    {
    	a[row][col] = false;
    	cols[col] = true;
    	fwd_dias[(size - 1) - col + row] = true;
    	bwd_dias[col + row] = true;
    }
    
    
    
    // chuong trinh dat quan hau
    void queen(int row)
    {
    	if (row == size)
    		print();
    	else
    	{
    		for (int col = 0; col < size; col++)
    		{
    			if (check(row, col))
    			{
    				put(row, col);		// dat quan hau len ban co va danh dau col va 2 duong cheo
    									// tuong ugn
    				queen(row + 1);		// dat tiep quan hau o hang ke tiep
    				unput(row, col);	// phuc hoi lai col va 2 duong cheo nhu truoc khi dat quan hau
    			}
    		}
    	}
    }
    
    
    
    
    // in ra truong hop thu index
    void print()
    {
    	index++;  // so truong hop tang len 1
    
    	cout << endl << "truong hop thu " << index << " :" << endl;
    	for (int i = 0; i < size; i++)
    	{
    		for(int j = 0; j < size; j++)
    		{
    			if (a[i][j] == false)
    				cout << "_ ";
    			else cout << "H ";
    		}
    		cout << endl;
    	}
    
    	if (index % 10 == 0)
    		getch();					
    }
    
          
    
    
    
    
    /*////// 15 duong cheo thuan//////////////////
    7 8 9 10 11 12 13 14
    6
    5
    4
    3
    2
    1
    0
    ////////////////////////////////////////////*/
    /*////// 15 duong cheo nguoc//////////////////
    0 1 2 3 4 5 6 7
                  8
    			  9
    			  10
    			  11
    			  12
    			  13
    			  14
    ////////////////////////////////////////////*/

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

    Cái này phải chăng giải thuật cho 1k hậu ?
    Eight Queen
    ( Eight-Queen ) Another puzzle for cheese buffs is the 8-queen problem. Simply stated: Is it possible to place 8 queens on an empty chessboard so that no queen is “attacking” any other, no 2 queens are in the same row, the same column, or along the diagonal? Use the thinking developed in Knight Heuristic to formulate a heuristic for solving the 8-queen problem. ( Hint : it is possible to assign a value to each square of the cheese board indicating how many squares of the an empty board are “eliminated” if a queen is placed in that square. Each of the corners would be assigned the value 22. Once these “elimination numbers” are placed in all 64-squares, an appropriate heuristic might be: Place the next queen in the square with the smallest elimination number. Why is this strategy intuitively appealing?

  10. #10
    Ngày gia nhập
    10 2006
    Nơi ở
    Hà Nội
    Bài viết
    146

    Mục đích của bài này mình đưa ra là: chúng ta chỉ tìm một đáp án thôi, chứ không phải là duyệt tất cả các đáp án.
    Và do vậy bài này nên giải quyết theo tìm kiếm heuristic là hợp lí nhất.
    Tuy nhiên với tìm kiếm heuiristic cũng có rất nhiều phương pháp. Đối với phương pháp nào cũng cho lời giải nhanh, quan trọng là các bạn phải có giải thuật hợp lí.
    còn về việc dùng mảng để biểu diễn thì như đã thảo luận ở trên là hợp lí.

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

  1. *Hack cf 1099-1000 hack wall 1099-1000 moi nhat new
    Gửi bởi thanhtu52 trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 0
    Bài viết cuối: 27-02-2012, 03:08 PM
  2. bồn nước inox toàn mỹ 1000 lít đứng , bồn 1000 lít ngang
    Gửi bởi giacamuaban trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 1
    Bài viết cuối: 29-08-2011, 03:33 PM
  3. Bon nuoc inox 1000 lit dung, bon nuoc inox 1000 lit ngang toan my
    Gửi bởi infobonnuoc trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 1
    Bài viết cuối: 26-08-2011, 11:03 AM
  4. Bồn nước 1000 lít ngang bôn nước 1000 lít đứng
    Gửi bởi infobonnuoc trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 1
    Bài viết cuối: 09-08-2011, 01:58 PM
  5. Tìm tất cả các số có 3 chữ số sao cho 1000+10b+c = ( a^3+b^3+c^3 )
    Gửi bởi nguyenthanhhai90vp 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: 26-08-2010, 04:59 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