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