c语言 一个n*n的方阵 要求每行每列元素只有一个1 其他都是0,输出所有可能结果。我要思路!打出主要代码
啊,这个其实是比较显然的。
每一行、每一列只有1个1,其它都是0的矩阵叫:permutation matrix,中文叫:置换矩阵。
每一个置换矩阵表示了一个置换变换。
置换可以分解为轮换,设n阶矩阵分解为k个轮换,每个轮换里分别有:
m1、m2、……、mk个元素,其中:m1+m2+……+mk = n
那么,A^m1 也就是置换 m1 次后,第1个轮换里那些元素就轮换回去了。
同理,A^m2 后,第2个轮换里那些元素就轮换回去了。
……
所以,取 m=m1*m2*……*mk ,所有元素就都轮换回去了,也就是 A^m = E。
#include "stdio.h"
long doit(int *a,int m,int n){
long sum=0;
int i,cf;
if (m>n) return(1);
for(a[m]=1;a[m]<=n;a[m]++){
cf=0;
for(i=1;i<m;i++)
if(a[m]==a[i]) {cf=1;break;}
if (cf==0) sum+=doit(a,m+1,n);
}
return(sum);
}
void main()
{
int a[100],n;
long sum;
printf("矩阵N*N,N=?
");
scanf("%d",&n);
sum=doit(a,1,n);
printf("sum=%ld
",sum);
return;
}
本题有点类似高斯8皇后问题
N=2 时
0* *0
*0 0* 两种方案
N=4时有24种。。。。
更简单的说法N方阵有N!种方案可实现
是一种排列组合
如6*6的方阵,相当于123456这6个数字有多少种排列组合一样。每一种组合的
第一位数字代表第1行所在列数
第二位数字代表第2行所在列数
……
100
010
001
把他换成普通数组实际上就是 123
那么321就是
001
010
100
同理132就是
100
001
010
那么你这个问题应该可以转成 n个数的排列问题。那么a[n] 假设a[0]=1代表第一行第1个数是1 a[1]=3 代表第二行第三个数是1 a[i]=n代表第i+1行第n个数是1. 这样的话你再转成矩阵赋值输出就可以了。。数组排列问题百度上有很多
xmhpearl 说的没错,不过这个答案不是唯一解把例如
1 0 0
0 1 0
0 0 1 是一种
0 1 0
1 0 0
0 0 1 也可以吧
如果标准的话应该取随机数。
思路是在第一行里面随意任人选一个比如m列,打1;
然后再第二行里出m列外任选一个n,打1;
然后第三行m,n外任选一个打1;
以此类推。
这样每次生成的仿真随即但满足题目要求
代码我这里就不写了。
哦不好意,没看到需要所有解,那么我补充一下。
既然这样就不用随即了,应该是遍历所有可能性。
当第一行选0列时 第二行可选1 - n
让后第二行选1的话,第三行就是 2 - n,选2的话就是 1 ,3 -n像这样一层一层遍历所有可能性就可以了。
需要代码的话,有空贴上来
主要思路:在第一行随机选一个数输出为1,然后再第二行随机选另外的一个数输出为1,依次类推
主要代码:
srand((unsigned)time(NULL));
for(i=0;i<n;i++)
{
while(b[m=rand()%n+1]);
b[m]=i;
} //将不重复的随机数存放在一个数组里面
for(i=0;i<n;i++)
{ for(j=0;j<n;j++)
{
if(b[i]==j)
printf("%d",1);
else
printf("%d",0);
}
printf("\n");
}
这个代码运行一次只会输出一种结果,但是你每次运行都会有不同的结果。直到把所有的结果都运行输出后,再运行就会出现一样的结果了。
// vc2010测试通过,回溯法。
#include <iostream>
#include <vector>
using namespace std;
// 打印矩阵
void print_m( const vector< vector< int > > &m, int n )
{
for( int i = 0; i < n; i++ )
{
for( int j = 0; j < n; j++ )
cout << m[i][j];
cout << endl;
}
cout << endl;
}
// 判断当前矩阵是否合法(即current_line, current_col位置是否可以填1)
bool is_current_line_col_right( vector< vector< int > > &m, const int &n, int current_line, int current_col )
{
for ( int i = 0; i < current_line; i++ )
if ( m[i][current_col] )
return false;
return true;
}
// 尝试在当前行填一个1
void try_set_current_line( vector< vector< int > > &m, const int &n, int current_line )
{
for ( int i = 0; i < n; i++ )
{
if ( is_current_line_col_right( m, n, current_line, i ) )
{
m[current_line][i] = 1;
if ( current_line == n - 1 ) // 最后1行
print_m( m, n );
else
try_set_current_line( m, n, current_line + 1 );
m[current_line][i] = 0;
}
}
}
// 找出所有合法的n*n矩阵,并打印出来
void find_all_matrixes( int n )
{
vector< vector< int > > m;
m.resize( n );
for ( int i = 0; i < n; i++ )
m[i].resize( n );
try_set_current_line( m, n, 0 );
}
void main()
{
find_all_matrixes( 3 );
find_all_matrixes( 4 );
}
用I【k】【h】;数组,用扫面方式进行K,H与每个数的比较
罗例延诺:[答案] #include #define N 15 void main() { int iArr[N][N] = {0}; /*魔法阵数组*/ /*定义变量,i,j为循环控制变,iNum表示数组的行数... if (iPox == 0) /*如果上一个数的行数为第一行,则下一个数的行数为最下一行,列数同样加1;*/ { if (iPoy != iNum-1) /*上一个数...
嘉荫县13744775039: 求解 一个N*N的二维数组,要求输出它每一行的最大值 (用C++写的) - ?
罗例延诺: #include<iostream> using name space std; void mai() {int a[n][n],i,j;int max;cout<<"输入n的值:"<<endlcin>>n;for(i=0;i<n;i++) //输入数组for(j=0;j<n;j++){cout<<“输入a[i][j]的值:";cin>>a[i][j];}for(i=0;i<n;i++) //求出每行的最大...
嘉荫县13744775039: C语言如何打印输出一个NxN的矩阵,请注意矩阵的排列要求 - ?
罗例延诺: C语言用一个双重循环就可以打印输出N*N的矩阵,比如: int i,j; for(i=0;i<10;i++){for(j=0;j<10;j++)printf("*");printf("\n"); }
嘉荫县13744775039: 用C语言编程序:生成一个N*N的矩阵,每个成员a[i][j]=i*N+j(i=0...N - 1,j= - ?
罗例延诺: #include<stdio.h> int main() {int N,a[100][100],i,j,sum;float average;printf("请输入N:\n");scanf("%d",&N);for(i=0;i<N;i++){for(j=0;j<N;j++){a[i][j]=i*N+j;}}sum=0;j=N-1;for(i=0;i<N;i++){sum=sum+a[i][j];j--;}// average=1.0*sum/N...
嘉荫县13744775039: 用C语言编写个N*N矩阵,由外层到内层依次:第一层全是1;第二层全是2;第三层是3; - ?
罗例延诺: if(N%2==0 && N>0){for(i=0;i<N/2;i++){for(j=i;j<N-i;j++){a[i][j]=a[N-1-i][j]=i+1; a[j][i]=a[j][N-1-i]=i+1;}} }
嘉荫县13744775039: 用C语言怎么写一个n*n的矩阵x,查找第一行全为0的行,输出行号 - ?
罗例延诺: for(i=0; i<n; i++)for (j=0; j<n; j++) {if(x[i][j] != 0)break;if(j == n-1) {printf("%d\n", i);return 0;}}
嘉荫县13744775039: C语言.输入一个m*n的矩阵,计算每行的和. - ?
罗例延诺: #include "stdio.h" int main() {int a[10][10];int m,n,tmp,i,j,sum[10]={0};scanf("%d %d",&m,&n);for(i=0;i<m;i++) //输入for(j=0;j<n;j++)scanf("%d",&a[i][j]);for(i=0;i<n;i++) //交换{tmp=a[m-1][i];a[m-1][i]=a[0][i];a[0][i]=tmp;}for(i=0;i...
嘉荫县13744775039: c 语言1、 N行N列的方阵中(N及方阵由键盘输入),每行都有最大的数,求这N个最大数中最小的一个. - ?
罗例延诺: #include<stdio.h> #define N 10 int main() { int i,j,max,temp; int a[N][N]; int b[N]; for(i=0;i<N;i++) { for(j=0;j<N;j++) scanf("%d",&a[i][j]); } for(i=0;i<N;i++) { max=a[i][0]; for(j=0;j<N;j++) { if(a[i][j]>max) max=a[i][j]; } b[i]=max; } printf("各行最大的是:")...
嘉荫县13744775039: C语言 输出N*N的一个魔方阵(各行各列及对角线的和都相等)矩阵 都是什么意思?每一句的解释 - ?
罗例延诺: #include<stdio.h> #include<stdlib.h> #define MAXSIZE 20 void main(void) { int matrix[MAXSIZE][MAXSIZE]; /* the magic square */ int count; /* 1..n*n counting */ int row; /* row index */ int column; /* column index */ int order; /* input order */ char line[...
嘉荫县13744775039: c语言输入一个正整数,打印n*n方阵 - ?
罗例延诺: 程序不能运行的主要原因是定义数组的时候用变量做下标,其他的错误我用注释给出了 #include<stdio.h> int main() {int n,i,j,sum=0;//sum要初始化int a[6][6]={0};//数组不能用变量做下标printf("请输入方阶的阶数n<n<=n<=6>:\n");scanf(...