2019独角兽企业重金招聘Python工程师标准>>> 编程之美- 中国象棋将帅问题-编程之家

问题描述：
在中国象棋规则中，将和帅规定只能在田字格中移动，且将和帅是不能碰面的，请求解出所有可能的符合规则的将帅位置。
限制条件：
只能使用一个字节的变量

问题解答：
刚看到问题时，觉得问题本身的逻辑关系很简单，限制条件才是本题的精妙之处，如何只用一个字节来表示所有需要用到变量，我们一步一步的分析；
首先，将题目中所提的场景使用数学方法描述为：
                                                               7    8    9
                    将的移动范围为 Matrix A  =4    5    6 
                                                               1    2    3
同理：
                                                               7    8    9
                    帅的移动范围为 Matrix B  =4    5    6 
                                                               1    2    3
如果没有限制条件，则本题解法很容易想到：
S1:a=将当前位置号；
S2:b=帅当前位置号；
S3: IF abs(a-b)%3 != 0 THEN 符合  ELSE 不符合；不能处于同一列，则比如A.7-B.1=6,6%3=0
但是，有了限制条件后，需要将a，b变为一个单字节的变量，这最先想到的就是利用除法，因为四则运算中只有除法可以将一个数变为两个, N/n = q…r N被除数，n除数，q商，r余数，这样我们就找到了使a，b变为一个数的方法。
根据A，B两个矩阵易知：1、总共存在81种可能的情况；2、重新将矩阵转为以0为开始，易于计算
设Num为某种情况的标号，则Num的范围为[0,80]共81种，a=Num/9，b=Num%9
则可以得到a，b，并利用S3就可以得到所有符合规则的解；
重新整理算法为：
for Num=0:80
     a=Num/9;
     b=Num%9;
     if(abs(a-b))!=0
        printf("a = %d, b = %d"a+1,b+1);

或者

int var = 81;
  while( var– )
  {
    if( var / 9 % 3 == var % 9 % 3 )//发生冲突
     continue;
    else
 printf(/** 打印可行的位置 **/);
  }

整数i可以由部两分组成，即var=(var/9)*9+var%9 ，其中var<n。我们注意到，在i从81到0变化的过程中，var%9的变化相当于最内层循环b，var/9的变话相对于最外层循环a。

 

package cglib;

public class jiekou {

    
      
    /**
     * @param args
     */  
    public static void main(String[] args) {  
        // TODO Auto-generated method stub  
        // 7 8 9
        // 4 5 6
        // 1 2 3
        
        // 7 8 9
        // 4 5 6
        // 1 2 3
       int i = 81;
       System.out.println(i);
        while((i–)!=0)
        {   
            System.out.println("while:"+i);
            if((i / 9) % 3 == (i % 9) % 3)
                continue;
           System.out.println("A = "+((i /9 )+1)+","+"B = "+((i%9)+1));
            
            
        }
        
     
          
    }
    }

 

输出：

81
while:80
while:79
A = 9,B = 8
while:78
A = 9,B = 7
while:77
while:76
A = 9,B = 5
while:75
A = 9,B = 4
while:74
while:73
A = 9,B = 2
while:72
A = 9,B = 1
while:71
A = 8,B = 9
while:70
while:69
A = 8,B = 7
while:68
A = 8,B = 6
while:67
while:66
A = 8,B = 4
while:65
A = 8,B = 3
while:64
while:63
A = 8,B = 1
while:62
A = 7,B = 9
while:61
A = 7,B = 8
while:60
while:59
A = 7,B = 6
while:58
A = 7,B = 5
while:57
while:56
A = 7,B = 3
while:55
A = 7,B = 2
while:54
while:53
while:52
A = 6,B = 8
while:51
A = 6,B = 7
while:50
while:49
A = 6,B = 5
while:48
A = 6,B = 4
while:47
while:46
A = 6,B = 2
while:45
A = 6,B = 1
while:44
A = 5,B = 9
while:43
while:42
A = 5,B = 7
while:41
A = 5,B = 6
while:40
while:39
A = 5,B = 4
while:38
A = 5,B = 3
while:37
while:36
A = 5,B = 1
while:35
A = 4,B = 9
while:34
A = 4,B = 8
while:33
while:32
A = 4,B = 6
while:31
A = 4,B = 5
while:30
while:29
A = 4,B = 3
while:28
A = 4,B = 2
while:27
while:26
while:25
A = 3,B = 8
while:24
A = 3,B = 7
while:23
while:22
A = 3,B = 5
while:21
A = 3,B = 4
while:20
while:19
A = 3,B = 2
while:18
A = 3,B = 1
while:17
A = 2,B = 9
while:16
while:15
A = 2,B = 7
while:14
A = 2,B = 6
while:13
while:12
A = 2,B = 4
while:11
A = 2,B = 3
while:10
while:9
A = 2,B = 1
while:8
A = 1,B = 9
while:7
A = 1,B = 8
while:6
while:5
A = 1,B = 6
while:4
A = 1,B = 5
while:3
while:2
A = 1,B = 3
while:1
A = 1,B = 2
while:0

 

  其实这个问题还可以进行一些扩展，即如何利用一个变量达到三重循环的效果。也就是说，如果给定下面的循环：

  int counter = 0;
  for( int i = 0; i < 5; i++ )
 for( int j = 0; j < 4; j++ )
   for( int k = 0; k < 3; k++ )
   {
    System.out.println("counter="+counter+"/t, i="+i+", j="+j+", k="+k);
    counter++;
   }
   其结果如下：
 counter=0 , i=0, j=0, k=0
 counter=1 , i=0, j=0, k=1
 counter=2 , i=0, j=0, k=2
 counter=3 , i=0, j=1, k=0
 counter=4 , i=0, j=1, k=1 
    ….中间略
    counter=59  , i=4, j=3, k=2
  
  实际上就是对原始的中国象棋将帅问题进行了一个扩展，即在棋盘上添加一个“王”，其行走规则和将帅 一样。于是棋盘变成了三国争霸:-) ，将帅王可以走动的格子数分别为3、4、5，它们之间的互斥条件可以按需要设定。
  
   这时，就需要只用一个变量遍历一个三重循环。
  
   只用一个变量解决扩展的中国象棋将帅问题，我们的代码应该是如下的样子：
   int var = 3*4*5;
   while( var– )
   {
     if( /** 冲突条件 **/ )//发生冲突
      continue;
     else   
         printf(/** 打印可行的位置 **/);
   }

   在冲突条件中，我们需要知道var取得某个特定的值（即第var+1次循环）的时候的i，j，k分别是多少（这样我们才能判定将帅位置是否冲突）
  
   从上例的结果中我们可以看到，counter的值（即当前的循环次数）和三元组（i，j，k）是一一对应的，越是外层的循环变化越慢，他们满足什么关系呢？
  
   k的取值最好确定，我们都知道是var%3。
   在原始的将帅问题中我们知道,j的值应该是 var/3，但是由于j上面还有一层循环，就需要做些调整，变成var/3%4
   最外层循环i的值则为(var/(3*4))%5.
     
     即：k=var%3      //其下没有循环了
             j=var/3   //其下有几个循环长度为3的循环
            i=var/(3*4). //其下有几个循环长度为3*4的循环
 
  于是4重循环的公式我们也可以轻松得出：
  for( int i = 0; i < 5; i++ )
     for( int j = 0; j < 4; j++ )
       for( int k = 0; k < 3; k++ )
         for( int p = 0; p < 2; p++ )
    
   p=var%2 //其下没有循环了
   k=var/2      //其下有几个循环长度为2的循环
   j=var/(2*3)) //其下有几个循环长度为2*3的循环
   i=var/(2*3*4)//其下有几个循环长度2*3*4的循环
  
   下面就是一个变量实现三重循环

编程之美- 中国象棋将帅问题-编程之家int var = 2*3*4*5;
编程之美- 中国象棋将帅问题-编程之家while( var— > 0){
编程之美- 中国象棋将帅问题-编程之家 System.out.println("var="+var+" , i="+((var/(2*3*4))%5)+
编程之美- 中国象棋将帅问题-编程之家                                                    ", j ="+((var/(2*3))%4)+",
编程之美- 中国象棋将帅问题-编程之家                                                       k="+((var/2)%3)+",
编程之美- 中国象棋将帅问题-编程之家                                                       p="+var%2);
编程之美- 中国象棋将帅问题-编程之家}
编程之美- 中国象棋将帅问题-编程之家

   
   结果是：
   var=119 , i=4, j=3, k=2, p=1
   var=118 , i=4, j=3, k=2, p=0
   var=117 , i=4, j=3, k=1, p=1
   …中间略
   var=5 , i=0, j=0, k=2, p=1
   var=4 , i=0, j=0, k=2, p=0
   var=3 , i=0, j=0, k=1, p=1
   var=2 , i=0, j=0, k=1, p=0
   var=1 , i=0, j=0, k=0, p=1
   var=0 , i=0, j=0, k=0, p=0  

所以归纳总结

对于 b*a = i ，我们可以用如下公式展开

    loop1=i%b;
    loop2=(i/b)%a 

 

其中loop1是内层循环，loop2是外层循环

那么如果 a 本身就是 j*k 组成的呢？

由于 j*k = i/b  ，套用公式得到

   

    loop1= (i/b)%j

    loop2= ((i/b)/j)%k 

 

由此可以得出N重时的公式,假设 an * a(n-1) * ……. * a3 * a2 * a1 =  N

 

    loop1=N%a1—相当于最小因子

    loop2=(N/(a1))%a2

    loop3=(N/(a1a2))%a3

    …..

    loopN=(N/(a1…..an))%an

则对于给定的 an * a(n-1) * ……. * a3 * a2 * a1 =  N ，展开式是 ( Nzk 意思是N的展开 )

Nzk =  (N/(a1…..an))%an +  " ,  "+  …..  (N/(a1a2))%a3 + " , " +  (N/(a1))%a2 + " , " +  N%a1

得出

Nzk  =  ((N/(a1…..an))%an +  " ,  "+  …..  (N/(a1a2))%a3 + " , " +  (N/(a1))%a2 )+ " , " +  N%a1

得出

Nzk =   (an * a(n-1) * ……. * a3 * a2)zk    +  " , " +  N%a1

————   (an * a(n-1) * ……. * a3 * a2)zk 就相当于 (N/(a1…..an))%an +  " ,  "+  …..  (N/(a1a2))%a3 + " , " +  (N/(a1))%a2 ，也就是（N-1） zk

得出

Nzk =  (N/a1)zk  +  " , " +  N%a1

至此得出了递归公式，

N的展开式 = （N/（N的最后一个因数）） 的展开式 +  （ N 模（N的最后一个因数））

 

package cglib;

import java.util.ArrayList;

public class jiekou {

    static void singleLineLoop(ArrayList<Integer> args,int amount){  
          
        //如果数组只剩一个元素，则已经到了an , 用 amount % an 即可，  
        //因为 amount 就是 (N/(a1…..an))  
        if (args.size() == 1){  
            System.out.print("" + (amount%args.get(0)) + "/n");
            System.out.println();  
            return;  
        }         
                  
        //输出当前数组的最后一个元素  
        System.out.print("" + ((amount%args.get(args.size()-1))) + " , " );  
        //继续递归调用  
        singleLineLoop(new ArrayList(args.subList(0, args.size()-1)),amount/args.get(args.size()-1));  
    }  
      
    static void multiLoop(ArrayList<Integer> args,int amount){  
          
        while(amount–>0){  
            System.out.print("var (" + amount +") :" );  
              
            // N%a1部分  
            System.out.print("" + ((amount%args.get(args.size()-1))) + " , " );  
              
            //递归实现(N/a1)zk  
            singleLineLoop(new ArrayList(args.subList(0, args.size()-1)),amount/args.get(args.size()-1));  
        }  
          
    }  
      
    /**
     * @param args
     */  
    public static void main(String[] args) {  
        // TODO Auto-generated method stub  
          
        ArrayList<Integer> li = new ArrayList<Integer>();     
       li.add(2);  
       li.add(3);  
       li.add(4);  
       li.add(5);  
        int amount = 2*3*4*5;
        
     
   
 
        multiLoop(li,amount);  
          
    }
    }   

输出：

var (119) :4 , 3 , 2 , 1/n
var (118) :3 , 3 , 2 , 1/n
var (117) :2 , 3 , 2 , 1/n
var (116) :1 , 3 , 2 , 1/n
var (115) :0 , 3 , 2 , 1/n
var (114) :4 , 2 , 2 , 1/n
var (113) :3 , 2 , 2 , 1/n
var (112) :2 , 2 , 2 , 1/n
var (111) :1 , 2 , 2 , 1/n
var (110) :0 , 2 , 2 , 1/n
var (109) :4 , 1 , 2 , 1/n
var (108) :3 , 1 , 2 , 1/n
var (107) :2 , 1 , 2 , 1/n
var (106) :1 , 1 , 2 , 1/n
var (105) :0 , 1 , 2 , 1/n
var (104) :4 , 0 , 2 , 1/n
var (103) :3 , 0 , 2 , 1/n
var (102) :2 , 0 , 2 , 1/n
var (101) :1 , 0 , 2 , 1/n
var (100) :0 , 0 , 2 , 1/n
var (99) :4 , 3 , 1 , 1/n
var (98) :3 , 3 , 1 , 1/n
var (97) :2 , 3 , 1 , 1/n
var (96) :1 , 3 , 1 , 1/n
var (95) :0 , 3 , 1 , 1/n
var (94) :4 , 2 , 1 , 1/n
var (93) :3 , 2 , 1 , 1/n
var (92) :2 , 2 , 1 , 1/n
var (91) :1 , 2 , 1 , 1/n
var (90) :0 , 2 , 1 , 1/n
var (89) :4 , 1 , 1 , 1/n
var (88) :3 , 1 , 1 , 1/n
var (87) :2 , 1 , 1 , 1/n
var (86) :1 , 1 , 1 , 1/n
var (85) :0 , 1 , 1 , 1/n
var (84) :4 , 0 , 1 , 1/n
var (83) :3 , 0 , 1 , 1/n
var (82) :2 , 0 , 1 , 1/n
var (81) :1 , 0 , 1 , 1/n
var (80) :0 , 0 , 1 , 1/n
var (79) :4 , 3 , 0 , 1/n
var (78) :3 , 3 , 0 , 1/n
var (77) :2 , 3 , 0 , 1/n
var (76) :1 , 3 , 0 , 1/n
var (75) :0 , 3 , 0 , 1/n
var (74) :4 , 2 , 0 , 1/n
var (73) :3 , 2 , 0 , 1/n
var (72) :2 , 2 , 0 , 1/n
var (71) :1 , 2 , 0 , 1/n
var (70) :0 , 2 , 0 , 1/n
var (69) :4 , 1 , 0 , 1/n
var (68) :3 , 1 , 0 , 1/n
var (67) :2 , 1 , 0 , 1/n
var (66) :1 , 1 , 0 , 1/n
var (65) :0 , 1 , 0 , 1/n
var (64) :4 , 0 , 0 , 1/n
var (63) :3 , 0 , 0 , 1/n
var (62) :2 , 0 , 0 , 1/n
var (61) :1 , 0 , 0 , 1/n
var (60) :0 , 0 , 0 , 1/n
var (59) :4 , 3 , 2 , 0/n
var (58) :3 , 3 , 2 , 0/n
var (57) :2 , 3 , 2 , 0/n
var (56) :1 , 3 , 2 , 0/n
var (55) :0 , 3 , 2 , 0/n
var (54) :4 , 2 , 2 , 0/n
var (53) :3 , 2 , 2 , 0/n
var (52) :2 , 2 , 2 , 0/n
var (51) :1 , 2 , 2 , 0/n
var (50) :0 , 2 , 2 , 0/n
var (49) :4 , 1 , 2 , 0/n
var (48) :3 , 1 , 2 , 0/n
var (47) :2 , 1 , 2 , 0/n
var (46) :1 , 1 , 2 , 0/n
var (45) :0 , 1 , 2 , 0/n
var (44) :4 , 0 , 2 , 0/n
var (43) :3 , 0 , 2 , 0/n
var (42) :2 , 0 , 2 , 0/n
var (41) :1 , 0 , 2 , 0/n
var (40) :0 , 0 , 2 , 0/n
var (39) :4 , 3 , 1 , 0/n
var (38) :3 , 3 , 1 , 0/n
var (37) :2 , 3 , 1 , 0/n
var (36) :1 , 3 , 1 , 0/n
var (35) :0 , 3 , 1 , 0/n
var (34) :4 , 2 , 1 , 0/n
var (33) :3 , 2 , 1 , 0/n
var (32) :2 , 2 , 1 , 0/n
var (31) :1 , 2 , 1 , 0/n
var (30) :0 , 2 , 1 , 0/n
var (29) :4 , 1 , 1 , 0/n
var (28) :3 , 1 , 1 , 0/n
var (27) :2 , 1 , 1 , 0/n
var (26) :1 , 1 , 1 , 0/n
var (25) :0 , 1 , 1 , 0/n
var (24) :4 , 0 , 1 , 0/n
var (23) :3 , 0 , 1 , 0/n
var (22) :2 , 0 , 1 , 0/n
var (21) :1 , 0 , 1 , 0/n
var (20) :0 , 0 , 1 , 0/n
var (19) :4 , 3 , 0 , 0/n
var (18) :3 , 3 , 0 , 0/n
var (17) :2 , 3 , 0 , 0/n
var (16) :1 , 3 , 0 , 0/n
var (15) :0 , 3 , 0 , 0/n
var (14) :4 , 2 , 0 , 0/n
var (13) :3 , 2 , 0 , 0/n
var (12) :2 , 2 , 0 , 0/n
var (11) :1 , 2 , 0 , 0/n
var (10) :0 , 2 , 0 , 0/n
var (9) :4 , 1 , 0 , 0/n
var (8) :3 , 1 , 0 , 0/n
var (7) :2 , 1 , 0 , 0/n
var (6) :1 , 1 , 0 , 0/n
var (5) :0 , 1 , 0 , 0/n
var (4) :4 , 0 , 0 , 0/n
var (3) :3 , 0 , 0 , 0/n
var (2) :2 , 0 , 0 , 0/n
var (1) :1 , 0 , 0 , 0/n
var (0) :0 , 0 , 0 , 0/n

 

转载于:https://my.oschina.net/u/2822116/blog/724035