202003 pmn的变形使用讲课

admin

1*2 的骨牌去覆盖2*2的格子有两种情况：
1 1
2 2
和
1 2
1 2
其实就是骨牌横着摆和竖着摆两种，1*2覆盖4*4的格子呢，有36种情况：
请你编程显示出来。
可以理解成间隔排列的加强版

admin

首先，显然想的到，枚举横着和竖着两种情况，知道第8块放下去为止
void pr(){ 打印棋盘}
void dfs(int i)
{  if (i>8) pr();
    else
    {
      横排
      竖排
    }
}

admin

棋盘怎么表示，我建议大家用a(0)-a(15)表示16个格子，当然也人想用a(1)(1)到 a(4)(4)，等下你就会发现a(0)-a(15)好！

admin

横着排，那么要求i不在最右一列，a(i)和 a(i+1)都==0
竖着排，那么要求i不在最后一行，a(i)和 a(i+4)都==0
那么其他的求和间隔排列一样了。

admin

程序和间隔拍列有相似，可以对比看看，

1. #include <iostream>
   
2. using namespace std;
   
3. int a[20],k=0,ans;
   
4. void pr()  ///很有水平
   
5. {
   
6.         cout<<endl<<++ans;
   
7.         for (int i=0; i<=15; i++)
   
8.         {
   
9.                 if (i%4==0) cout<<endl;
   
10.                 cout<<a[i]<<' ';
    
11.         }
    
12. }
    
13. void  dfs(int i)
    
14. {
    
15.         if (i>15) pr();
    
16.         else  if (a[i]>0)  dfs(i+1);
    
17.         else
    
18.         {
    
19.                 ///heng
    
20.                 if ( (i%4<3) && a[i+1]==0)
    
21.                 {
    
22.                         k++;
    
23.                         a[i]=a[i+1]=k; ///放
    
24.                         dfs(i+2);
    
25.                         a[i]=a[i+1]=0; ///还回来 同间隔排列
    
26.                         k--;
    
27.                 }
    
28.                 ///shu
    
29.                 if ((i/4<3) && a[i+4]==0)
    
30.                 {
    
31.                         k++;
    
32.                         a[i]=a[i+4]=k; ///放
    
33.                         dfs(i+1);
    
34.                         a[i]=a[i+4]=0; ///还回来 同间隔排列
    
35.                         k--;
    
36.                 }
    
37.         }
    
38. }
    
39. int main()
    
40. {
    
41.         dfs(0);
    
42.         return 0;
    
43. }

复制代码

admin

8皇后问题：8*8的国际象棋棋盘，摆8个皇后，相互不攻击，皇后攻击同一行，同一列，正反两斜对角线的子。
搜索，总共8个皇后，每个皇后8个位置可能，满足条件就行，和8选8有相似之处：
void  dfs(int i)
{  
    if(i>9)  pr();
    else for (int k=1;k<=8;k++)
      if (can(i,k))  第i行可以放在第k个位置
       {
            a(i)=k;dfs(i+1);
        }
}
那么重点就在写函数can(i,k) 上
暴力搜索
bool  can(int i,int k)
{  
     bool b=1;
     for (int j=1;j<=i-1;j++)  if a(j)==k  b=0;   前面i-1 行某个和我同列
     for (int j=1;j<=i-1;j++)  if j+a(j)==k+i  b=0;    前面i-1 行某个和我同对角线
     for (int j=1;j<=i-1;j++)  if ???  b=0;   前面i-1 行某个和我同反对角线
  returnb;
}

admin

这个8皇后请自己完成

admin

所谓因数分解，就是
100=2*50
100=2*2*25
100=4*25
***
所有的分解情况，这个题显然也可以递归
dfs(i)表示把i分解，要是i==1就不能分解了，否则，可以分解出一个j（i%j==0） 然后继续去分解dfs(i/j)。

admin

void  dfs(int i)
if i==1 return
else for (int j=a[x-1];j<=i;j++)  后面的因子大于等于前面一个
  if (i%j==0)  {a[x]=j;dfs(i/j);}

张溯源

我们还可以用这种方法来算二的一百次方的最少计算次数，和因数分解很像，上代码：