A(n,n)
n行n列的二维数组
求A(1,a)+(2,b)+(3,c)+……+(n,z)
其中a不等于b不等于c不等于……不等于z
就是说每行取一个元素,取出的元素不能在同一列上,不能取(1,1),(2,2)……(n,n)
求和,枚举。
一共应该有(n-1)!种情况
最后要得到所有这样的和,S1,S2……S(n-1)!
有不清楚的地方写出来,我再说明,好的加分。
//用全排列的方法求解,排除掉全排列中行号和列号相同的即可
//由于每次测试可能输入较多数据,使用freopen进行重定向,这样可以节省调试时间,在工程文件夹中建立一个名为
//t.txt的文件,然后以如下格式输入数据:
//2 //这个是矩阵的大小
//12 22 //下面是每行的数据
//32 20
//如果需要手动输入测试数据,将freopen 这行代码注释掉即可。
//另外,为了观察结果,输出了较多的提示信息,可以自行修改
#include <stdio.h>
#define MAX 100
int perm[MAX+1] ;//存放所有的排列数
int data[MAX+1][MAX+1] ; //数据
int count = 1 ;
void permutation(int perm[], int n, int curr)
{
int i ;
int sum ;
if(curr==n)
{
sum = 0 ;
for(i = 1; i <=n ;i++)
{
//列号在perm[i]中
if(i == perm[i])
return ;
else
{
sum += data[i][perm[i]] ;
}
}
for(i = 1; i <= n; i++)
printf("A[%d][%d]=%d ", i, perm[i], data[i][perm[i]]) ;
printf("\nS%d=%d\n\n", count++, sum) ;
return ;
}
for(i = curr; i <= n; i++)
{
int t ;
t = perm[curr] ;
perm[curr] = perm[i] ;
perm[i] = t ;
permutation(perm, n, curr+1) ;
t = perm[curr] ;
perm[curr] = perm[i] ;
perm[i] = t ;
}
}
int main()
{
freopen("t.txt", "r", stdin) ;
int i, j ;
int n ;
scanf("%d", &n) ;
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++)
scanf("%d", &data[i][j]) ;
for(i = n; i >= 1; i--)
perm[i] = i ;
permutation(perm, n, 1) ;
return 0 ;
}
//我写的可能有些问题,没时间改了,楼主自己改改看吧。我的结果好像不是(n-1)!个。
//由于每次测试可能输入较多数据,使用freopen进行重定向,这样可以节省调试时间,在工程文件夹中建立一个名为
//t.txt的文件,然后以如下格式输入数据:
//2 //这个是矩阵的大小
//12 22 //下面是每行的数据
//32 20
//如果需要手动输入测试数据,将freopen 这行代码注释掉即可。
//另外,为了观察结果,输出了较多的提示信息,可以自行修改
#include <stdio.h>
#define MAX 100
int perm[MAX+1] ;//存放所有的排列数
int data[MAX+1][MAX+1] ; //数据
int count = 1 ;
void permutation(int perm[], int n, int curr)
{
int i ;
int sum ;
if(curr==n)
{
sum = 0 ;
for(i = 1; i <=n ;i++)
{
//列号在perm[i]中
if(i == perm[i])
return ;
else
{
sum += data[i][perm[i]] ;
}
}
for(i = 1; i <= n; i++)
printf("A[%d][%d]=%d ", i, perm[i], data[i][perm[i]]) ;
printf("\nS%d=%d\n\n", count++, sum) ;
return ;
}
for(i = curr; i <= n; i++)
{
int t ;
t = perm[curr] ;
perm[curr] = perm[i] ;
perm[i] = t ;
permutation(perm, n, curr+1) ;
t = perm[curr] ;
perm[curr] = perm[i] ;
perm[i] = t ;
}
}
int main()
{
freopen("t.txt", "r", stdin) ;
int i, j ;
int n ;
scanf("%d", &n) ;
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++)
scanf("%d", &data[i][j]) ;
for(i = n; i >= 1; i--)
perm[i] = i ;
permutation(perm, n, 1) ;
return 0 ;
}
//我写的可能有些问题,没时间改了,楼主自己改改看吧。我的结果好像不是(n-1)!个。
温馨提示:答案为网友推荐,仅供参考
第1个回答 2014-10-07
#include<stdlib.h>
#include<stdio.h>
int*flag;
int*b;
int*arr;
int sum=0;
int*M;
int n;
void Resort(int s)
{
int i;
if(s>n)return ;
if(s==n)
{
for(int j=0;j<n;j++)
{
if(j==b[j])return;
}
for( j=0;j<n;j++)
{
sum+=*(M+j*n+b[j]);
}
return; }
for(i=0;i<n;i++)
{
if(flag[i]==0)
{
b[s]=arr[i];
flag[i]=1;
Resort(s+1);
flag[i]=0; }
}}
int main()
{
printf("输入维数n: ");
scanf("%d",&n);
M=(int*)malloc(n*n*sizeof(int));
printf("输入矩阵: \n");
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
scanf("%d",M+j+i*n);
}
}
flag=(int*)malloc(n*sizeof(int));
arr=(int*)malloc(n*sizeof(int));
b=(int*)malloc(n*sizeof(int));
for(i=0;i<n;i++)
{
arr[i]=i;
flag[i]=0;
}
Resort(0);
printf("the sum is %d",sum);
return 0;
}
#include<stdio.h>
int*flag;
int*b;
int*arr;
int sum=0;
int*M;
int n;
void Resort(int s)
{
int i;
if(s>n)return ;
if(s==n)
{
for(int j=0;j<n;j++)
{
if(j==b[j])return;
}
for( j=0;j<n;j++)
{
sum+=*(M+j*n+b[j]);
}
return; }
for(i=0;i<n;i++)
{
if(flag[i]==0)
{
b[s]=arr[i];
flag[i]=1;
Resort(s+1);
flag[i]=0; }
}}
int main()
{
printf("输入维数n: ");
scanf("%d",&n);
M=(int*)malloc(n*n*sizeof(int));
printf("输入矩阵: \n");
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
scanf("%d",M+j+i*n);
}
}
flag=(int*)malloc(n*sizeof(int));
arr=(int*)malloc(n*sizeof(int));
b=(int*)malloc(n*sizeof(int));
for(i=0;i<n;i++)
{
arr[i]=i;
flag[i]=0;
}
Resort(0);
printf("the sum is %d",sum);
return 0;
}
第2个回答 2014-10-07
有点像行列式求值问题,但是是加法...
二维数组的定义是怎样的? n的大小固定吗? c++语言语法行不?
我的思路是递归法,有点类似于代数余子式分解法
先找出一个不重复数字序列如n=5时 2,3,5,4,1就是一个可行数列
则Si= A(1,2)+A(2,3)+A(3,5)+A(4,4)+A(5,1)
现在要做的就是找出所有不重复的数列
设F(1,2,3,4,5)是找出1,2,3,4,5的所有不重复数列
则F(1,2,3,4,5)= 1,F(2,3,4,5) + 2,F(1,3,4,5) +3,F(1,2,4,5)+ 4,F(1,2,3,5) + 5,F(1,2,3,4)
则可将n阶问题分成n个n-1阶子问题
我不知道你具体的数据结构是如何, 算法应该是这样追问
二维数组的定义是怎样的? n的大小固定吗? c++语言语法行不?
我的思路是递归法,有点类似于代数余子式分解法
先找出一个不重复数字序列如n=5时 2,3,5,4,1就是一个可行数列
则Si= A(1,2)+A(2,3)+A(3,5)+A(4,4)+A(5,1)
现在要做的就是找出所有不重复的数列
设F(1,2,3,4,5)是找出1,2,3,4,5的所有不重复数列
则F(1,2,3,4,5)= 1,F(2,3,4,5) + 2,F(1,3,4,5) +3,F(1,2,4,5)+ 4,F(1,2,3,5) + 5,F(1,2,3,4)
则可将n阶问题分成n个n-1阶子问题
我不知道你具体的数据结构是如何, 算法应该是这样追问
n大小不固定,C++可以。
比如n=5,就会有1,2,3,4,5或者2,3,5,4,1这样的。
就是找出所有不同数列,不过越简单越好
对啊,上面那个递归算法就是解决这个问题的啊
本回答被网友采纳第3个回答 2014-10-07
"每行取一个元素,取出的元素不能在同一列上"
那个数应该是P(n,n),也就是n!个啊,怎么会是(n-1)!追问
那个数应该是P(n,n),也就是n!个啊,怎么会是(n-1)!追问
因为不能取第一行第一列,第二行第二列,……,第n行第n列。