cstriker1407的笔记本

好记性不如铅笔头

java, 编程, 编程之美

《编程之美》读书笔记:象棋将帅问题

最近在学习《 编程之美 》这本书,书中提到了很多很经典的算法问题和实现,学起来真是耗费脑细胞啊。书中的算法实现使用C编写的,这里作者自己写了一部分java的实现,如果有错误,还请各位读者批评指正。截图版权属于原作者。

github:

https://github.com/cstriker1407/think_in_java 】

1.2中国象棋将帅问题

这里作者备份下一部分java实现,最后的结果不一定符合题目要求:

最简单的Java实现,4个for循环:

for (int lieA = 1; lieA <= 3; lieA++)
{
	for (int hangA = 1; hangA <= 3; hangA++)
	{
		for (int lieB = 1; lieB <= 3; lieB++)
		{
			if (lieB == lieA)
			{
				continue;
			}
					
			for (int hangB = 1; hangB <= 3; hangB++)
			{
				int A = lieA * 100 + hangA; 
				int B = lieB * 100 + hangB; 
				System.out.println("A:" + A +"   B:" + B);
			}
		}
	}
}

使用9字格进行遍历方法A:

for (int posA = 1; posA <= 9; posA++)
{
	for (int posB = 1; posB <= 9; posB++)
	{
		if (posA %3 == posB % 3)
		{
			continue;
		}
		
//		int A = ((posA -1)%3+1) * 100 + ((posA - 1)/3 + 1); 
//		int B = ((posB -1)%3+1) * 100 + ((posB - 1)/3 + 1); 
//		System.out.println("A:" + A +"   B:" + B);
		System.out.println("posA:" + posA +"   posB:" + posB);
	}
}

 使用9字格进行遍历方法B:

/*
为什么是9*9,考虑到A,B的最大值均为9,那么可以确定,A*B的所有值都不会超过9*9,因此
当totalNum从81开始递减的时候,可以保证totalNum/9的值从9开始递减,
由余法运算规则可知,任何数%9都不会比9大,因此totalNum从81开始递减时,totalNum/9的值从9开始递减。	 
 */
int totalNum = 9*9;
while (totalNum-- != 0)
{
//	totalNum / 9 =>A
//	totalNum % 9 =>B
	if ( totalNum/9 % 3 == totalNum % 9 %3 )
	{
		continue;
	}
	System.out.println("posA:" + (totalNum/9+1) +"   posB:" + (totalNum%9+1));
}

 一点思考:

从遍历方法A和遍历方法B上我们可以看到,两层for循环其实是可以合成一层的,只是计算量不会缩小。

比如原始两层循环:

int m = 5;
int n = 3;
for (int i = 0; i < m; i++)
{
	for (int j = 0; j < n; j++)
	{
		System.out.println("m:" + i + "   n:" + j);
	}
}

 合成一层循环:

for (int idx = 0; idx < m*n; idx++)
{
	System.out.println("m:" + idx/n + "   n:" + idx%n); 
}

Leave a Reply

5 × 3 =

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据

Theme by Anders Norén

苏ICP备16032087号