`
shuishou119800
  • 浏览: 7885 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

用桥梁模式实现螺旋矩阵算法

算法设计模式编程J# 
阅读更多

前两天写了一篇文章，分析了“内螺旋矩阵算法”的实现，讨论到了面向对象编程的可扩展性，于是今天用桥梁模式将代码做了些改造，具体如下：

package com.algo;

class Position {
	private int x;
	private int y;

	public Position(int x, int y) {
		this.x = x;
		this.y = y;
	}

	public int getX() {
		return x;
	}

	public void setX(int x) {
		this.x = x;
	}

	public int getY() {
		return y;
	}

	public void setY(int y) {
		this.y = y;
	}
}

/**
 * 螺旋走向接口
 */
abstract class Direction {
	protected StartPos startPos;
	protected Position pos;// 当期的位置
	protected Position periodPos;// 一个周期的开始位置
	protected int max;// 行列的最大值
	protected int min;// 行列的最小值
	protected int len;// 方阵的阶数

	private void init() {
		if (startPos == null || len <= 0)
			return;
		Position tempPos = startPos.getPos(len);
		pos = new Position(tempPos.getX(), tempPos.getY());
		periodPos = new Position(tempPos.getX(), tempPos.getY());
		max = len - 1;
		min = 0;
	}

	public void setStartPos(StartPos startPos) {// 设置开始位置并重新初始化
		this.startPos = startPos;
		init();
	}

	public void setLen(int len) {// 设置长度并重新初始化
		this.len = len;
		init();
	}

	public int getLen() {
		return len;
	}

	public Position getPos() {
		int currRow = pos.getX();
		int currCol = pos.getY();
		Position currPos = new Position(currRow, currCol);
		genNextPos();
		return currPos;
	}

	protected abstract void genNextPos();
}

/**
 * 顺时针螺旋实现
 */
class ClockwiseDir extends Direction {
	protected void genNextPos() {
		int row = pos.getX();
		int col = pos.getY();
		if (row == min && col < max) {
			col++;
		} else if (row < max && col == max) {
			row++;
		} else if (row == max && col > min) {
			col--;
		} else if (row > min && col == min) {
			row--;
		} else{
			return; //匹配不到任何条件，则直接跳出（指螺旋的最后一个位置）
		}
		if (row == periodPos.getX() && col == periodPos.getY()) {
			min++;
			max--;
			genNextPos();
			periodPos = new Position(pos.getX(), pos.getY());
		} else {
			pos.setX(row);
			pos.setY(col);
		}
	}
}

/**
 * 逆时针螺旋实现
 */
class AntiClockwiseDir extends Direction {
	protected void genNextPos() {
		int row = pos.getX();
		int col = pos.getY();
		if (row == min && col > min) {
			col--;
		} else if (row < max && col == min) {
			row++;
		} else if (row == max && col < max) {
			col++;
		} else if (row > min && col == max) {
			row--;
		} else{
			return; //匹配不到任何条件，则直接跳出（指螺旋的最后一个位置）
		}
		if (row == periodPos.getX() && col == periodPos.getY()) {
			min++;
			max--;
			genNextPos();
			periodPos = new Position(pos.getX(), pos.getY());
		} else {
			pos.setX(row);
			pos.setY(col);
		}
	}
}

/**
 * 螺旋起始位置接口
 */
interface StartPos {
	public Position getPos(int len);
}

/**
 * 起始位置为左上角的实现
 */
class TopLeft implements StartPos {
	public Position getPos(int len) {
		return new Position(0, 0);
	}
}

/**
 * 起始位置为右上角的实现
 */
class TopRight implements StartPos {
	public Position getPos(int len) {
		return new Position(0, len - 1);
	}
}

/**
 * 起始位置为左下角的实现
 */
class BottomLeft implements StartPos {
	public Position getPos(int len) {
		return new Position(len - 1, 0);
	}
}

/**
 * 起始位置为右下角的实现
 */
class BottomRight implements StartPos {
	public Position getPos(int len) {
		return new Position(len - 1, len - 1);
	}
}

public class HelixAlgo {
	public void print(Direction dir,int initVal,int step) {
		int len = dir.getLen();
		if (len <= 0) {
			System.out.println("请输入大于0的整数！");
			return;
		}
		int[][] helix = calculate(dir, len,initVal,step);
		for (int i = 0; i < helix.length; i++) {
			for (int j = 0; j < helix[i].length; j++) {
				System.out.print(helix[i][j] + "\t");
			}
			System.out.println("");
		}
	}

	private int[][] calculate(Direction dir, int len,int val,int step) {
		int[][] helix = new int[len][len];
		for (int i = 0; i < len * len; i++) {
			Position pos = dir.getPos();
			int row = pos.getX();
			int col = pos.getY();
			helix[row][col] = val;
			val+=step;
		}
		return helix;
	}

	public static void main(String[] args) {
		HelixAlgo algo = new HelixAlgo();
		int len = 5;
		Direction dir_clockwise = new ClockwiseDir();
		dir_clockwise.setLen(len); //用set方法动态地插入长度

		Direction dir_antiClockwise = new AntiClockwiseDir();
		dir_antiClockwise.setLen(len);

		System.out.println("\n左上角开始顺时针内旋(长度" + len + ")：");
		dir_clockwise.setStartPos(new TopLeft()); //用set方法动态地插入开始位置
		algo.print(dir_clockwise,1,1);
		System.out.println("\n右上角开始顺时针内旋(长度" + len + ")：");
		dir_clockwise.setStartPos(new TopRight());
		algo.print(dir_clockwise,1,1);
		System.out.println("\n右下角开始顺时针内旋(长度" + len + ")：");
		dir_clockwise.setStartPos(new BottomRight());
		algo.print(dir_clockwise,1,1);
		System.out.println("\n左下角开始顺时针内旋(长度" + len + ")：");
		dir_clockwise.setStartPos(new BottomLeft());
		algo.print(dir_clockwise,1,1);
		
		System.out.println("\n左上角开始逆时针内旋(长度" + len + ")：");
		dir_antiClockwise.setStartPos(new TopLeft());
		algo.print(dir_antiClockwise,1,1);
		System.out.println("\n右上角开始逆时针内旋(长度" + len + ")：");
		dir_antiClockwise.setStartPos(new TopRight());
		algo.print(dir_antiClockwise,1,1);
		System.out.println("\n右下角开始逆时针内旋(长度" + len + ")：");
		dir_antiClockwise.setStartPos(new BottomRight());
		algo.print(dir_antiClockwise,1,1);
		System.out.println("\n左下角开始逆时针内旋(长度" + len + ")：");
		dir_antiClockwise.setStartPos(new BottomLeft());
		algo.print(dir_antiClockwise,1,1);
		
		System.out.println("\n中心点开始顺时针外旋(长度" + len + ")：");
		dir_antiClockwise.setStartPos(new TopLeft());
		algo.print(dir_antiClockwise,len*len,-1);
		System.out.println("\n中心点开始逆时针外旋(长度" + len + ")：");
		dir_clockwise.setStartPos(new TopLeft());
		algo.print(dir_clockwise,len*len,-1);
	}
}

 

螺旋矩阵的解题思路就不多说了，不了解的可以看下我前面的文章“内螺旋矩阵算法分析”,这里主要说下为什么要用桥梁模式：

首先看看螺旋矩阵有哪些变化点：矩阵阶数（即边长），初始位置，和螺旋方向（顺时针，逆时针）

初始位置前面的文章在回复中已经提及，合法的初始位置只有四个既矩阵的四个角，否则会出现死胡同（可参考前面文章在10楼的回复）。

考虑到弹性，这三个变化点都应该是可以独立变化的，其中矩阵阶数只是个整数，它的变化比较方便，而另外两个可以用不同的接口封装，即上面代码的"StartPos"接口和"Direction"抽象类，这样两个变化点便可以独立的变化，因此想到了使用桥梁模式，把这两个变化点的耦合彻底移到对象层面，于是便有了mian函数中“dir_clockwise ”和“dir_antiClockwise”两个对象封装的多种输出。

其他就不多说了，代码可以运行，直接拷贝到机器上跑一下应该就明白了，有什么不足或者疑问欢迎大家一起讨论。

分享到：
带条件的排列组合算法分析
评论
4 楼 shuishou119800 2009-12-20  
re:3 楼 ilove2009

不可否认Direction接口下的确存在着“Bad Smell”（即genNextPos()方法中的分支结构），可如果将这些分支用多态的方式实现，则将产生很多的细粒度对象。无论什么样的设计思想，其目的都是为了在高效完成任务的基础上提高代码的弹性。一般来说，封装的粒度越小，代码的弹性越高，但生产效率也将随之下降。笔者认为系统设计的关键应该是在效率与弹性之间寻找一个平衡点，既不偏向于高效的过程化设计，也不要太偏向于纯粹的面向对象设计。而所谓的平衡点就是具体业务变化点。
此处以顺时针循环为例，ClockwiseDir类完全可以分解成（ClockwiseDir_Top,ClockwiseDir_Right,ClockwiseDir_Bottom,ClockwiseDir_Left），从而去除掉genNextPos()方法中“Bad Smell”。但这样的话，每增加一种新的流转类型（比如S形流转）就必须同时创建四个类。分析下这个业务的变化点，流转的类型可以一直扩展下去（平躺式S形流转，古文排版式流转。。。），矩阵的长度可以一直扩展下去（6阶，7阶，8阶。。。），这两者是独立的变化点，因此需要分离。可就流转类型而言，无论是那种流转都有着他们自己独有的规则（如顺时针螺旋的顶边对应的下一个方向一定是右边），换句话说，这些规则的生命周期局限于他们所属的流转类型，没有了ClockwiseDir的流转类型，ClockwiseDir_Top,ClockwiseDir_Right,ClockwiseDir_Bottom,ClockwiseDir_Left这些细粒度规则对象也就失去了他们存在的意义。因此笔者认为此处为了提高面向对象的纯度而将流转类型对象细分，是没有必要的，毕竟变化的点是在流转类型上。
再以人为例，每个特定的人身上都存在着很多对象（眼、耳、口、鼻。。。），对于一个以器官为研究对象的业务系统来说，将人分解成各种器官对象是必须的；可对于一个以人为研究对象的业务系统，将人分解成各种器官对象不仅意义不大且反倒会增加系统的复杂度。
设计的目的是为了解决问题，而不能为了设计而设计。
3 楼 ilove2009 2009-12-18  
面向对象的代码很少有if  else这样的语句，一般都是用多态来替代。感觉就是过程化的代码套上对象的外壳。

面向对象应该是用我们普通人的思维描述系统，数学化的方法描述不是。

比如你的代码是不是很自然地表达出生活中的场景，比如：
Snake sn = new Snake(size,new Right(size),new Point(1,1,"1"));  
这句在现实中训蛇员指定范围和方向、起点，让蛇开始游走，正常啊。而且这些属性都是随时可以变的。

再看Point类，有x、y、val属性，很自然，一个位置用xy坐标表示，这个点为啥要多个属性val呢，因为蛇走到那里点上可能拉陀屎也可能吐口水什么的，这正常啊。

再看，给定的范围、方向上，只有方向具体的子类才能知道下个点是什么、是否出界，责任很清晰啊。

只是next方法不是很清晰，因为下个方向是蛇和当前方向共同决定的。

2 楼 shuishou119800 2009-12-18  
re 1 楼 ilove2009

  能说的具体些吗？你觉得哪里需要改进？
1 楼 ilove2009 2009-12-18  
感觉面向对象不彻底，不自然。
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    螺旋矩阵matlab源程序

    对于顺时针螺旋矩阵的MATLAB实现，我们可以使用for循环来控制填充边界，并逐步改变边界。每次填充完一个边界后，通过循环变量的递增或递减，来调整填充下一个边界的起始和终止条件。在循环体内部，通过适当的索引...

    c语言程序设计 螺旋矩阵

    螺旋矩阵是一种特殊的矩阵排列方式，它在编程中常被用作练习数据结构和算法的问题。在C语言程序设计中，创建螺旋矩阵涉及到数组操作、循环控制以及条件判断等基本概念。接下来，我们将深入探讨这些知识点。 1. **...

    c语言螺旋矩阵大作业报告.docx

    本文将深入探讨如何用C语言实现不同类型的螺旋矩阵生成。 首先，螺旋矩阵的生成依赖于对二维数组的控制，特别是对数组边界的有效管理。对于**左上角顺时针螺旋矩阵**的生成，我们可以采用双层循环嵌套的方法，外层...

    螺旋矩阵类代码

    本文将深入探讨螺旋矩阵类代码的实现细节，并提供一个完整的C语言程序示例，帮助读者更好地理解这一概念。 螺旋矩阵是一种将矩阵元素按照顺时针或逆时针方向环绕中心点填充的矩阵。通常，它们从中心向外围螺旋般地...

    打印螺旋矩阵

    对于更大的矩阵，可以使用递归的Laplace展开方法或者LU分解等方法来计算。 对于N*N的矩阵，其行列式可以通过递归的方式计算，将矩阵对角线上的元素作为主元，将非主元所在行或列的元素通过减法移除，然后对剩下的...

    趣味矩阵算法实现源代码

    标题中的“趣味矩阵算法实现源代码”意味着我们将探讨一种用编程语言实现的，能够打印或操作特定模式矩阵的方法。这可能包括递归、循环或其他控制结构，以按照预设的规则填充和展示矩阵。 描述中的“算法分析与设计...

    C++实现:螺旋矩阵的实例代码

    这种实现方法既直观又高效，可以灵活适应不同大小的螺旋矩阵。 此外，在编程实践中，我们还可以通过增加参数或设计不同的函数来增强代码的复用性，比如设计一个可以生成任意大小螺旋矩阵的函数。这样，程序员在解决...

    MapReduce实现矩阵相乘算法

    本话题将深入探讨如何使用Hadoop MapReduce实现两个矩阵相乘的算法，这在数据分析、机器学习以及高性能计算中有着重要应用。 首先，理解矩阵相乘的基本原理至关重要。矩阵相乘不是简单的元素对元素相乘，而是对应...

    apriori改进算法，使用矩阵实现

    在这个“apriori改进算法，使用矩阵实现”的主题中，我们将深入探讨如何利用矩阵数据结构来优化Apriori算法的性能。 传统的Apriori算法工作原理是通过迭代的方式生成不同长度的候选集，然后在交易数据库中检查这些...

    Python实现打印螺旋矩阵功能的方法

    本文将深入探讨如何使用Python编程语言实现打印螺旋矩阵的功能，并讨论其核心概念与算法实现。 首先，让我们简单回顾螺旋矩阵的定义及其填充原理。假设我们有一个N×N的矩阵，我们将从矩阵的左上角开始填充。在第一...

    FPGA实现各种矩阵运算

    在"基于FPGA的矩阵运算实现.nh"文件中，可能详细阐述了如何设计和实现这些具体的FPGA矩阵运算方案，包括硬件架构、算法流程、性能评估等方面的内容。通过深入研究这个文档，读者可以更全面地了解如何利用FPGA技术...

    策略模式结合模板方法模式

    * 在使用策略模式结合模板方法模式时，需要注意算法实现的变化部分，确保算法实现的变化部分是可以扩展的。 * 使用策略模式结合模板方法模式可以使得策略模式更加灵活和可扩展，并且可以更好地解决一些共性问题。 ...

    C++实现稀疏矩阵与一般矩阵

    这种存储方法将非零元素以三元组 (行索引, 列索引, 值) 的形式存储，通常使用一个动态数组或链表来实现。这种方式减少了对内存的需求，因为只存储非零元素，对于稀疏矩阵来说非常高效。在C++中，我们可以创建一个...

    C语言 经典题目螺旋矩阵 实例详解

    在C语言中，实现螺旋矩阵通常涉及二维数组的处理。以下是对这个经典题目的详细解释。 首先，我们来看一下程序的主要部分： ```c #include #include int main() { int N, i, j, n, num = 1; int a[10][10] = {...

    基于MPI得并行矩阵乘法 Cannon算法实现

    通过这种方式，使用MPI和Boost实现的Cannon算法可以有效地利用多处理器资源，加速大矩阵的乘法运算，尤其适用于高性能计算环境。然而，实际应用中需要注意的问题包括负载平衡、通信开销以及缓存效率等，这些都是优化...

    FFT快速蝶形算法矩阵分解算法

    在"先进视频通信作业一——胡旭琰1101213413"这个压缩包中，很可能包含了一个使用MATLAB编写的程序，实现了上述的矩阵分解算法和FFT蝶形运算。这个程序可能用于视频通信领域，因为视频信号处理常涉及到频域分析，而...

    桥梁模式DEMO

    《桥梁模式DEMO》 ...在《DesignPattern1.8》这个压缩包中，可能包含了作者实现的桥梁模式DEMO代码，包括Java或其他编程语言的源文件，读者可以通过阅读和运行这些代码来更好地理解和掌握桥梁模式的使用。

    用十字链表实现稀疏矩阵的加法、减法以及乘法运算

    本文将详细介绍如何用十字链表实现稀疏矩阵的加法、减法和乘法运算。 稀疏矩阵的十字链表结构由三部分组成：行链表、列链表和主对角线链表。每个链表节点包含非零元素的行号、列号和值。这种结构可以快速定位和访问...

    python-leetcode面试题解之第59题螺旋矩阵II-题解.zip

    这个题解不仅展示了如何用Python实现螺旋矩阵，还涵盖了基本的数组操作、边界条件判断以及循环控制等核心编程概念。这对于求职面试来说是一个很好的问题，因为它测试了应聘者对基础数据结构和算法的理解，以及问题...

Magicbox
Global site tag (gtag.js) - Google Analytics