| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1334 人关注过本帖
标题:[讨论]矩阵题,intereting
只看楼主 加入收藏
live41
Rank: 10Rank: 10Rank: 10
等 级:贵宾
威 望:67
帖 子:12442
专家分:0
注 册:2004-7-22
结帖率:66.67%
收藏
 问题点数:0 回复次数:6 
[讨论]矩阵题,intereting

生成各种矩阵是竞赛时经常考的一种题目,如何用C语言或C++生成以下形式几种矩阵:

第一种矩阵:

1 2 9 10 4 3 8 11 5 6 7 12 16 15 14 13

第二种矩阵:(蛇形)

1 2 6 7 3 5 8 13 4 9 12 14 10 11 15 16

第三种矩阵:

1 2 3 4 12 13 14 5 11 16 15 6 10 9 8 7

第四种矩阵:

7 6 5 16 8 1 4 15 9 2 3 14 10 11 12 13

规律提示:

1.1->2 9->10 4<-3 8 11 5->6->7 12 16<-15<-14<-13 2.每个左上三角的数都是连续的 3.一个回旋阵,从外到里是连续的。 4.同样是回旋,从里到外是连续的。

大家先说明做哪个矩阵再贴算法。

搜索更多相关主题的帖子: intereting 矩阵 
2004-07-26 16:36
乌鸦丘比特
Rank: 1
等 级:新手上路
威 望:2
帖 子:625
专家分:0
注 册:2004-7-19
收藏
得分:0 

其实算法概括起来差不多:模拟

只要你模拟出数字的路径,矩阵也就可以生成了:(下面我简单说一下模拟算法,如果不懂或不对的地方请大家指出)

第一个:把路径反向模拟:从16到1,大家可以看到路径变向是在当前路径不通(没有下一个或下一个已经有数存在)

的情况下,前进分四种情况(横坐标加减和纵坐标加减)可以分别写4个递归移动函数(当前路径不通时停止调用)

当前路径不通需要调用一个判断函数来判断下一步该怎么做,这个题目的判断函数只要判断当前数的四边是否有空位

如果有把下一个数填上去然后扫描下一个数的四边,找到两个空位除掉填数方向的空位,向另外一个空位方向移动。

一直到填上1为止。

3。4两题和第一题大同小异,只要确定路径方向(1到16还时16到1)和判断函数(依矩阵情况而定)就可以了。

下面再说说第2题:模拟的移位函数只需要2个(右上和左下)当前路径不通时的判断函数只要执行向某个方向移一位

这里可以用下优先级:向下比向右优先,向左比向下优先,这样几可以解决问题了,然后还是一直模拟到填满。

可能讲的不够详细,不懂的请提出。


我喜欢创造,一只扑腾着翅膀向天空飞翔的乌鸦
2004-07-26 20:38
live41
Rank: 10Rank: 10Rank: 10
等 级:贵宾
威 望:67
帖 子:12442
专家分:0
注 册:2004-7-22
收藏
得分:0 

第一种矩阵算法:

#include<iostream.h> #include<iomanip.h>

void main() { const int N=20; int i=0,j=0,a[N][N]; int lap=1,m=1,n; while(1) { cout<<"\ninput matrix row N(N>=2): "; cin>>n; cout<<endl; if(n>=2) break; } a[i][j]=m++; lap++; while(lap<=n) { if(lap%2==0) { for(j++;i<lap;i++) a[i][j]=m++;i--; for(j--;j>=0;j--) a[i][j]=m++;j++; } else { for(i++;j<lap;j++) a[i][j]=m++;j--; for(i--;i>=0;i--) a[i][j]=m++;i++; } lap++; } for(i=0;i<n;i++) { for(j=0;j<n;j++) cout<<setw(4)<<setiosflags(ios::left)<<a[i][j]; cout<<endl; } cout<<endl; }

第二种矩阵算法:(蛇形)

#include<iostream.h> #include<iomanip.h>

void main() { const int MAXLEN=10; int nLen; int nSnake[MAXLEN][MAXLEN]; do { cout<<"\ninput an integer less then "<<MAXLEN<<": "; cin>>nLen; cout<<endl; }while(nLen>MAXLEN); int i=0,j=0,s=1,nNum=1; //s标记升降方向,斜向上为升(s==1),斜向下为降(s==-1) while(1) { if(s==1) { nSnake[i][j]=nNum; if(i-1<0) { if(j+1==nLen) i++; else j++; s=-1; } else if(j+1==nLen) { i++; s=-1; } else { i--; j++; } } else { nSnake[i][j]=nNum; if(j-1<0) { if(i+1==nLen) j++; else i++; s=1; } else if(i+1==nLen) { j++; s=1; } else { i++; j--; } } nNum++; if(nNum>nLen*nLen) break; } for(i=0;i<nLen;i++) { for(j=0;j<nLen;j++) cout<<setw(4)<<setiosflags(ios::left)<<nSnake[i][j]; cout<<endl; } cout<<endl; }

第三种矩阵算法:

#include<iostream.h> #include<iomanip.h>

void main() { const int N=20; int i=0,j=0,a[N][N],n; int m=1,x1,x2,y1,y2,s=1; //x1,x2,y1,y2为上、下、左、右边界 //s标记数组元素升降,s==1为升,s==-1为降 while(1) { cout<<"\ninput matrix row N(N>=2): "; cin>>n; cout<<endl; if(n>=2) break; } x1=0;y1=0;x2=n;y2=n; while(1) { if(s==1) { for(j;j<y2;j++) a[i][j]=m++; j--;i++;y2--; for(i;i<x2;i++) a[i][j]=m++; i--;j--;x2--; s=-1; } else { for(j;j>=y1;j--) a[i][j]=m++; j++;i--;y1++; for(i;i>=x1+1;i--) a[i][j]=m++; i++;j++;x1++; s=1; } if(m>n*n) break; } for(i=0;i<n;i++) { for(j=0;j<n;j++) cout<<setw(4)<<setiosflags(ios::left)<<a[i][j]; cout<<endl; } cout<<endl; }

第四种矩阵算法:

#include<iostream.h> #include<iomanip.h>

void main() { const int N=20; int i=0,j=0,a[N][N],n; int m,x1,x2,y1,y2,s; //x1,x2,y1,y2为上、下、左、右边界 //s标记数组元素升降,s==1为升,s==-1为降 while(1) { cout<<"\ninput matrix row N(N>=2): "; cin>>n; cout<<endl; if(n>=2) break; } m=n*n; x1=0;y1=0;x2=n;y2=n; if(n%2==0) {j=n-1;y2=n-1;s=1;} else {i=n-1;y1=1;s=-1;} while(1) { if(s==1) { for(i;i<x2;i++) a[i][j]=m--; i--;j--;x2--; for(j;j>=y1;j--) a[i][j]=m--; j++;i--;y1++; s=-1; } else { for(i;i>=x1;i--) a[i][j]=m--; i++;j++;x1++; for(j;j<y2;j++) a[i][j]=m--; j--;i++;y2--; s=1; } if(m<1) break; } for(i=0;i<n;i++) { for(j=0;j<n;j++) cout<<setw(4)<<setiosflags(ios::left)<<a[i][j]; cout<<endl; } cout<<endl; }

2004-07-27 12:40
live41
Rank: 10Rank: 10Rank: 10
等 级:贵宾
威 望:67
帖 子:12442
专家分:0
注 册:2004-7-22
收藏
得分:0 

输入一个数(这里以3为例)打印以下距阵(回字矩阵):

1 1 1 1 1 1 1 2 2 2 2 1 1 2 3 3 2 1 1 2 3 3 2 1 1 2 2 2 2 1 1 1 1 1 1 1

#include<iostream.h> #include<iomanip.h> void main() { int n,a,b,i,j; cout<<"\ninput the number of the laps: "; cin>>n; cout<<endl; for(i=1;i<=2*n;i++) { for(j=1;j<=2*n;j++) { a=i>n?(2*n+1-i):i; b=j>n?(2*n+1-j):j; cout<<setw(3)<<(a=(a<b)?a:b); } cout<<'\n'; } cout<<endl; }

以1 1 1 1为例,分成两部分: 1 1 1 1 1 1 2 2 1 2 1 1 2 2 1 2 2 1 2 2 1 1 2 1 1 1 1 1 1 1 1 1

对应的数组坐标为: (0,3) (0,0)(0,1)(0,2)(0,3) (1,2)(1,3) (1,0)(1,1)(1,2) (2,1)(2,2)(2,3) (2,0)(2,1) (3,0)(3,1)(3,2)(3,3) (3,0)

对应的判断为: if((i+j)>=m) if((i+j)<=m)

a[i][j]=(i>=j)?(m-i):(m-j); a[i][j]=(i<=j)?(i+1):(j+1);

这样就可以确定赋值给上半边还是下半边了!

接下来的问题就是打印输出了!

if(j==(m-1)) cout<<endl;

2004-07-27 12:41
wonderfulday
Rank: 1
等 级:新手上路
帖 子:97
专家分:0
注 册:2004-7-28
收藏
得分:0 

顶了再说


2004-08-07 03:23
proton
Rank: 1
等 级:新手上路
帖 子:8
专家分:0
注 册:2004-7-30
收藏
得分:0 

不用矩阵:(第一次写递归,多多指教)

#include <stdio.h> #include <conio.h> char key='y'; int n=0;

unsigned long complete(int x,int y); void come(); unsigned long min(int d,int f); unsigned long conduct1(int t); unsigned long conduct2(int t);

main() { while(key=='y'||key=='Y') {come(); printf("\nDo you want to continue?(y/n)\n"); key=getche(); } }

void come() { int i=0,j=0; printf("Input the N.\n"); scanf("%d",&n); printf("\n"); for(i=0;i<n;i++) {for(j=0;j<n;j++) {printf("%d\t",complete(j,i));} printf("\n"); } }

unsigned long min(int d,int f) { unsigned long c; c=d>f?f:d; return (c); }

unsigned long conduct1(int t) {int res=0; if(t==0) res=1; else if(t%2==0) res=conduct1(t-1)+2*t; else res=conduct1(t-1)+1; return (res); }

unsigned long conduct2(int t) {int res=0,m; m=n-1-t; if(t==(n-1)) res=n*n; else if((t%2)==0) res=conduct2(t+1)-1; else res=conduct2(t+1)-2*m; return (res); }

unsigned long complete(int x,int y) { unsigned long mx=0,my=0,base=0,re=0; mx=min(x,n-x-1); my=min(y,n-y-1); if(x+y<=n-1) { base=conduct1(x+y); if((x-y)%2==0) re=base-y; else re=base+y; }

else { base=conduct2((x+y)-(n-1)); if((x-y)%2==0) re=base+(n-1-y); else re=base-(n-1-y); } return (re); }

(改一下come函数,还可以有输入n值,行号,列号,输出数字的程序)


Never was and never will be
2004-08-08 10:50
wanyy1228
Rank: 1
等 级:新手上路
帖 子:52
专家分:0
注 册:2004-8-8
收藏
得分:0 

都太强了!


2004-08-08 22:06
快速回复:[讨论]矩阵题,intereting
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.015346 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved