文档章节

编程之美- 中国象棋将帅问题

一贱书生
 一贱书生
发布于 2016/07/30 16:06
字数 3076
阅读 6
收藏 0

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

问题解答:
刚看到问题时,觉得问题本身的逻辑关系很简单,限制条件才是本题的精妙之处,如何只用一个字节来表示所有需要用到变量,我们一步一步的分析;
首先,将题目中所提的场景使用数学方法描述为:
                                                               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

 

© 著作权归作者所有

一贱书生
粉丝 19
博文 724
码字总数 600123
作品 0
私信 提问
1.2 中国象棋将帅的问题

题目: 下过中国象棋的朋友都知道,双方的“将”和“帅”相隔遥远,并且他们不能照面,在象棋残局中,许多高手能利用这一规则走出精妙的杀招,假设棋盘上只有“将”和“帅”二子(如图)(为...

刀狂剑痴
2015/08/27
63
0
C++ 开发的中国象棋 - CHessCHS

CHessCHS中国象棋 中国象棋(局域网):使用 VS2010 开发 目前仅支持局域网对战,能够通过局域网发现所有用户,并且显示在右侧的列表框中。用户可以自己选择对手方,并发起对战请求,对方同意...

HongXG
2018/11/19
0
0
中国象棋--GMChess

GMChess 是一款 Linux 下的中国象棋软件。 正值svn版本号100,发布GMChess的第一个版本0.10吧。目前只有读谱功能,支持qq象棋,联众象棋,中游象棋,象棋演播室等软件生成的棋谱。 使用方法:...

匿名
2009/03/26
10.5K
1
用VC6.0编得中国象棋无法运行

@红薯 你好,想跟你请教个问题:用VC6.0编得中国象棋无法运行,代码我已上传;如果你有时间你把具体实现的步骤告诉我行吗?谢谢了!

黑狼9
2012/11/07
123
2
Go并发编程之美- Load/Store操作

一、前言 go语言类似Java JUC包也提供了一些列用于多线程之间进行同步的措施,比如低级的同步措施有 锁、CAS、原子变量操作类。相比Java来说go提供了独特的基于通道的同步措施。本节我们先来...

加多
01/15
0
0

没有更多内容

加载失败,请刷新页面

加载更多

springmvc集成cas,并解决前后端分离情况

1.最近项目需要集成已经存在的cas系统。 但是目前已集成的系统都是jsp。而我们项目是前后端分离开发(伪),没有分开部署。 2.cas原理就不介绍了 网上例子很多。基本都是使用302重定向实现的...

起名字什么的太麻烦了
31分钟前
3
0
HDFS-原理

1. 写操作

叶枫啦啦
今天
2
0
聊聊elasticsearch的MembershipAction

序 本文主要研究一下elasticsearch的MembershipAction MembershipAction elasticsearch-6.7.1/server/src/main/java/org/elasticsearch/discovery/zen/MembershipAction.java public class M......

go4it
今天
3
0
Redis集群

Redis cluster tutorial Redis集群提供一种方式自动将数据分布在多个Redis节点上。 Redis Cluster provides a way to run a Redis installation where data is automatically sharded acros......

OSC首席混子
今天
3
0
AWS codecommit 触发jenkins工作

在gitlab和github上面都有直接发送webhook的配置,但是在AWS上面是没有的直接配置webhook触发jenkins构建的设置的。 通过查看AWS多个service的官方文档,找到了解决方案,方案如下: (1)在c...

守护-创造
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部