最近在
http://suanfa.group.iteye.com/group/topic/27110看到一个逆时针矩阵。大致意思是说如果给定M*N的矩阵,在矩阵中采用逆时针方式填充数据。比如
3*3矩阵结果是:
1 8 7
2 9 6
3 4 5
3*4矩阵结果是:
1 10 9 8
2 11 12 7
3 4 5 6
4*6矩阵结果是:
1 16 15 14 13 12
2 17 24 23 22 11
3 18 19 20 21 10
4 5 6 7 8 9
6*4矩阵结果是:
1 16 15 14
2 17 24 13
3 18 23 12
4 19 22 11
5 20 21 10
6 7 8 9
这种问题首先想到的是个数学问题,最好的办法是总结出规律,直接定位。如
f(x,y)=z (其中x,y是矩阵的坐标,z是对应的数值,如 f(2,3)=19表示第3行第4列的值是19),只要找到这样的f函数即可。
另外这个方法符合递归的特性,比如最外面一圈的数据(一个长方形)与第二圈的数据(也是一个长方形)有相同的特性,都是按“下-->右-->上-->左”的方式填充的,左上角数据最小,第一行第二个数据最大,...。这样就可以用递归的方式来实现了“先填充外层矩形,如果矩形不是空心的,再递归填充里面的矩阵”。
还有一种方法是按题目的说法(逆时针输出),用模拟的方法来实现,“当前位置填充--->找到下一位置--->当前位置填充--->找到下一位置-->...”由于数据是连续的,每次只要找到“下一个填充位置”就可以了。下一位置怎么找?与当前填充方向有关。即有4种填充策略,每个填充完后返回下一个要使用的策略。
实际应用中应该优先考虑第一种方法,这样效率极高。
第二种方法也还可以,代码应该会比较简洁。
我这里对第三种方法进行了尝试,完整代码如下
public class Dir {
public class Position{
public int row;
public int col;
public Position(int row,int col){
this.row=row;
this.col=col;
}
}
public static final Dir DOWN=new Dir(){
protected Dir getNext() {
return Dir.RIGHT;
}
public Dir fill(int[][] arr,Position pos) {
int temp=arr[pos.row][pos.col];
pos.row++;
//从当前位置往下填充所有为0的单元格,遇到不为0(表示已经填充过了)时停止
for(int i=pos.row,len=arr.length;i<len;i++){
if(arr[i][pos.col]==0){
arr[i][pos.col]=++temp;
pos.row=i;
}else{
break;
}
}
return this.nextDir(arr, pos);
}
};
public static final Dir RIGHT=new Dir(){
protected Dir getNext() {
return Dir.UP;
}
public Dir fill(int[][] arr,Position pos) {
int temp=arr[pos.row][pos.col];
pos.col++;
//从当前位置往右填充所有为0的单元格,遇到不为0(表示已经填充过了)时停止
for(int i=pos.col,len=arr[0].length;i<len;i++){
if(arr[pos.row][i]==0){
arr[pos.row][i]=++temp;
pos.col=i;
}else{
break;
}
}
return this.nextDir(arr, pos);
}
};
public static final Dir UP=new Dir(){
protected Dir getNext() {
return Dir.LEFT;
}
public Dir fill(int[][] arr,Position pos) {
int temp=arr[pos.row][pos.col];
pos.row--;
//从当前位置往上填充所有为0的单元格,遇到不为0(表示已经填充过了)时停止
for(int i=pos.row;i>=0;i--){
if(arr[i][pos.col]==0){
arr[i][pos.col]=++temp;
pos.row=i;
}else{
break;
}
}
return this.nextDir(arr, pos);
}
};
public static final Dir LEFT=new Dir(){
protected Dir getNext() {
return Dir.DOWN;
}
public Dir fill(int[][] arr,Position pos) {
int temp=arr[pos.row][pos.col];
pos.col--;
//从当前位置往左填充所有为0的单元格,遇到不为0(表示已经填充过了)时停止
for(int i=pos.col;i>=0;i--){
if(arr[pos.row][i]==0){
arr[pos.row][i]=++temp;
pos.col=i;
}else{
break;
}
}
return this.nextDir(arr, pos);
}
};
public Dir fill(int[][] arr,Position pos){
return null;// to be implemented
}
/** 下一个方向是什么 */
protected Dir getNext() {
return null;// to be implemented
}
protected Dir nextDir(int[][] arr,Position pos){
return (arr[pos.row][pos.col]==arr.length*arr[0].length)?null:this.getNext();
}
}
测试代码如下
public class Test {
public static void main(String[] args) {
// 4行6列的数组
int M = 4, N = 6;
int[][] arr = new int[M][N];
arr[0][0] = 1;
//初始方向向下
Dir d = Dir.DOWN;
//初始位置左上角
Position pos = d.new Position(0,0);
//开始填充
do {
d = d.fill(arr, pos);
} while (d != null);
//输出结果
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
System.out.print((arr[i][j] < 10 ?" ":"")+arr[i][j]+" ");
}
System.out.println();
}
}
}
运行结果为:
1 16 15 14 13 12
2 17 24 23 22 11
3 18 19 20 21 10
4 5 6 7 8 9
完全正常。
以上代码中使用了“模板方法模式+变种的单例模式(4个实例)”。还有“匿名内部类”的使用。
分享到:
相关推荐
会动的一个逆时针从小到大排数的矩阵,c++的mfc的简单运用
这是一个c语言的作业,能够输出逆时针蛇形矩阵,很好用!!
数字逆时针螺旋式输出,这个描述还要20字以上的说。。。。。
从中心开始,逆时针打印 n*n 矩阵
用Swift3实现n*n阶矩阵逆时针输出
用c语言实现矩阵不同方式的输出,应用循环语句,嵌套定义。三种方式之间的转换。
主要介绍了java实现的顺时针/逆时针打印矩阵操作,涉及java基于数组的矩阵存储、遍历、打印输出等相关操作技巧,需要的朋友可以参考下
主要介绍了Java实现的按照顺时针或逆时针方向输出一个数字矩阵功能,涉及java基于数组遍历、运算的矩阵操作技巧,需要的朋友可以参考下
2.给定N的值,从矩阵的右上角输出逆时针螺旋矩阵 例如N=4时,输出: 4 3 2 1 5 14 13 12 6 15 16 11 7 8 9 10 3. 给定N的值,从内到外顺时针旋转 例如N=3时,输出: 7 8 9 6 1 2 5 4 3 4.给定N的值,从内到外逆...
点云三维坐标点 旋转矩阵 推导流程
主要介绍了java实现的n*n矩阵求值及求逆矩阵算法,结合具体实例形式分析了java基于数组的矩阵定义、遍历、运算等相关操作技巧,需要的朋友可以参考下
自己写的一个小程序,输入一个整数N,输出N阶逆时针蛇形矩阵
顺时针旋转为标为r1,r2,r3,r4,逆时针旋转标为R1,R2,R3、R4,共8种旋转方式,即顺时针旋转为r和逆时针旋转标记为R .例如,从矩阵(S),通过旋转序列r1R4r2R3就变为了矩阵(E)。现在,要求从矩阵(S)以最短的方法变为矩阵(T...
将螺旋分别做成了不同块划分来写的,分别使用4个三角形的形状的数字 组成一个正方形,没个 循环控制一个三角形的数字
将矩阵旋转90度 编写一个函数,该函数采用下面左侧所示的4x4矩阵并将其旋转90度。
下l3970002006-2007第一学期《Java语言程序设计》实验题目 1、试卷分析软件设计(第1次实验,2+4学时) 使用if语句、while语句等基本语言要素设计一个Java程序,帮助教师进行试卷分析。该程序必须能: ...
定义一个方阵类Array,实现对方阵进行顺时针90度旋转。 定义一个方阵类Array,实现对方阵进行顺时针90度旋转。如图所示。 具体要求如下: (1)私有数据成员 l int a[4][4]:用于存放方阵。...l Array (int a1[][4],...
“旋转”,输入框填入的是角度制,只能填整数,使图形顺时针或逆时针旋转。 “错切”,可填入小数,分别是与x方向和y方向的相关性。 “对称”,有关于x、y、原点对称三种变换,由于图形具有一定的对称性,所以把图形...
输入一个正整数N(N不大于100),输出一个n行的蛇形矩阵。 示例输入: 5 示例输出: 1 3 6 10 15 2 5 9 14 4 8 13 7 12 11 解法一: while True: try: N = int(input()) tmp_begin = 1 # 第一行的数 for i in ...
输入两个不大于10的整数m和n,输出m×n的逆时针形式的螺旋矩阵,输出数字占2位,数字间用1个空格分割。(类名SpiralMatrix)