正文

行列式和它的全排列2006-01-07 12:06:00

【评论】 【打印】 【字体：大 中 小】 本文链接：http://blog.pfan.cn/goal00001111/9390.html

分享到：

/*创建行列式（电脑随机输入数据），输出该行列式和它的全排列，并输出其值*/

#include <stdio.h>
#include <stdlib.h>
#define N 3
#define M 6

typedef struct node
{
 int data;  //存储元素的值
 int x;    //存储元素的横坐标
 int y;    //存储元素的纵坐标      
} array;

array Stack[M][N+1]; //全局变量，存储全排列的乘积项
int sum=0, count=0; //全局变量，分别存储行列式的值和乘积项的个数

void Create(int H[][N]);  //构造一个行列式
void PrintH(const int H[][N]); //输出行列式
void Solve(const int H[][N], array S[], int i, int NiXu); //采用递归方式求行列式的全排列
bool Judge(const array S[], int line, int len); //判断行列式的元素的纵坐标是否重复
void Save(const array S[]); //把每一个乘积项存储到全局变量Stack[][]
void PrintS(const array S[][N+1]); //输出行列式的全排列 

int main(void)
{
 array SL[N+1]; //栈，存储行列式的每一个乘积项的元素（因子）
 int H[N][N]; //存储行列式
 
 Create(H);  //构造一个行列式
 PrintH(H);  //输出行列式
 Solve(H, SL, 0, 0); //采用递归方式求行列式的全排列
 printf("%d =\n", sum); //输出该行列式的值
 PrintS(Stack); //输出行列式的全排列 
 
  system("pause");
  return 0;
}
void Create(int H[][N])
{
 int i, j;
 
 for(i=0; i<N; i++)
  for(j=0; j<N; j++)
   H[i][j] = rand()%10;
}
void PrintH(const int H[][N])
{
 int i, j;
 
 for(i=0; i<N; i++)
 {
  for(j=0; j<N; j++)
   printf("%d ", H[i][j]);
  printf("\n");
 }
}
void Solve(const int H[][N], array S[], int i, int NiXu)//采用递归方式求行列式的全排列
{
 array CS[N];  //栈，存储S[]的拷贝
 int j, k, top = i;
 int mul, CNiXu; //mul存储每一个乘积项的值，CNiXu累积每一个乘积项的逆序数
        
 for(j=0; j<N; j++)
 {
  if(Judge(S, j, top))//如果当前元素的纵坐标不与栈中存储的元素重复，将其入栈 
  {
   S[top].x = i;
   S[top].y = j;
   S[top].data = H[i][j];
   CNiXu = NiXu; //把逆序数复制到CNiXu
   for(k=0; k<top; k++)
   {
    if(j < S[k].y) //累积逆序数
     CNiXu++;
   }
   for(k=0; k<=top; k++) //复制栈
    CS[k] = S[k];
   if(i<N-1)  //如果未分析到该乘积项的最后一个元素，递归继续分析
    Solve(H, CS, i+1, CNiXu);
   else  //否则计算该乘积项的值，并存储到栈中
   {   
    for(mul=1, k=0; k<=top; k++)
     mul *= S[k].data;
    if(CNiXu%2==0) //如果逆序数为偶数，该乘积项为正，用0表示
    {
     S[N].data = 0;
     sum += mul;
    }
    else  //否则为负，用1表示
    {
     S[N].data = 1;
     sum -= mul;
    }  
    Save(S);//把该乘积项存储到局变量Stack[][] 
   }
  }
 }
}
bool Judge(const array S[], int line, int len)
{
 int i;
 
 for(i=0; i<len; i++)
  if(line == S[i].y)
   return 0;
 return 1;
}
void Save(const array S[])
{
 int i;
 
 for(i=0; i<=N; i++)
  Stack[count][i] = S[i];
 count++;  
}
void PrintS(const array S[][N+1])
{
 int i, j, k;
 
 for(i=0; i<M-1; i++)
 {
  if(S[i][N].data == 0)
   printf(" + ");
  else if(S[i][N].data == 1)
   printf(" - "); 
  for(j=0; j<N-1; j++)
   printf("%d*", S[i][j].data);
  printf("%d", S[i][j].data);
 }
 if(S[i][N].data == 0)
  printf(" + ");
 else if(S[i][N].data == 1)
  printf(" - "); 
 for(j=0; j<N-1; j++)
  printf("%d*", S[i][j].data);
 printf("%d", S[i][j].data);
}
/*创建行列式（人工输入数据），输出该行列式和它的全排列，并输出其值*/

#include <stdio.h>
#include <stdlib.h>
#define N 4  //行列式的行（列）数
#define M 24  //行列式的乘积项个数，M = N！

typedef struct node
{
 int data;  //存储元素的值
 int x;    //存储元素的横坐标
 int y;    //存储元素的纵坐标      
} array;

array Stack[M][N+1]; //全局变量，存储全排列的乘积项
int sum=0, count=0; //全局变量，分别存储行列式的值和乘积项的个数

void Create(int H[][N]);  //构造一个行列式
void PrintH(const int H[][N]); //输出行列式
void Solve(const int H[][N], array S[], int i, int NiXu); //采用递归方式求行列式的全排列
bool Judge(const array S[], int line, int len); //判断行列式的元素的纵坐标是否重复
void Save(const array S[]); //把每一个乘积项存储到全局变量Stack[][]
void PrintS(const array S[][N+1]); //输出行列式的全排列 

int main(void)
{
 array SL[N+1]; //栈，存储行列式的每一个乘积项的元素（因子）
 int H[N][N]; //存储行列式
 
 Create(H);  //构造一个行列式
 PrintH(H);  //输出行列式
 Solve(H, SL, 0, 0); //采用递归方式求行列式的全排列
 printf("%d =\n", sum); //输出该行列式的值
 PrintS(Stack); //输出行列式的全排列 
 
  system("pause");
  return 0;
}
void Create(int H[][N])
{
 int i, j;
 
 puts("请按标准格式输入行列式：每行N个数值，用空格隔开");
 for(i=0; i<N; i++)
 {
  for(j=0; j<N; j++)
   scanf("%d", &H[i][j]);
  fflush(stdin);
 } 
}
void PrintH(const int H[][N])
{
 int i, j;
 
 for(i=0; i<N; i++)
 {
  for(j=0; j<N; j++)
   printf("%d ", H[i][j]);
  printf("\n");
 }
}
void Solve(const int H[][N], array S[], int i, int NiXu)//采用递归方式求行列式的全排列
{
 array CS[N];  //栈，存储S[]的拷贝
 int j, k, top = i;
 int mul, CNiXu; //mul存储每一个乘积项的值，CNiXu累积每一个乘积项的逆序数
        
 for(j=0; j<N; j++)
 {
  if(Judge(S, j, top))//如果当前元素的纵坐标不与栈中存储的元素重复，将其入栈 
  {
   S[top].x = i;
   S[top].y = j;
   S[top].data = H[i][j];
   CNiXu = NiXu; //把逆序数复制到CNiXu
   for(k=0; k<top; k++)
   {
    if(j < S[k].y) //累积逆序数
     CNiXu++;
   }
   for(k=0; k<=top; k++) //复制栈
    CS[k] = S[k];
   if(i<N-1)  //如果未分析到该乘积项的最后一个元素，递归继续分析
    Solve(H, CS, i+1, CNiXu);
   else  //否则计算该乘积项的值，并存储到栈中
   {   
    for(mul=1, k=0; k<=top; k++)
     mul *= S[k].data;
    if(CNiXu%2==0) //如果逆序数为偶数，该乘积项为正，用0表示
    {
     S[N].data = 0;
     sum += mul;
    }
    else  //否则为负，用1表示
    {
     S[N].data = 1;
     sum -= mul;
    }  
    Save(S);//把该乘积项存储到局变量Stack[][] 
   }
  }
 }
}
bool Judge(const array S[], int line, int len)
{
 int i;
 
 for(i=0; i<len; i++)
  if(line == S[i].y)
   return 0;
 return 1;
}
void Save(const array S[])
{
 int i;
 
 for(i=0; i<=N; i++)
  Stack[count][i] = S[i];
 count++;  
}
void PrintS(const array S[][N+1])
{
 int i, j, k;
 
 for(i=0; i<M-1; i++)
 {
  if(S[i][N].data == 0)
   printf(" + ");
  else if(S[i][N].data == 1)
   printf(" - "); 
  for(j=0; j<N-1; j++)
   printf("%d*", S[i][j].data);
  printf("%d", S[i][j].data);
 }
 if(S[i][N].data == 0)
  printf(" + ");
 else if(S[i][N].data == 1)
  printf(" - "); 
 for(j=0; j<N-1; j++)
  printf("%d*", S[i][j].data);
 printf("%d", S[i][j].data);
}

阅读(3103) | 评论(1)


版权声明：编程爱好者网站为此博客服务提供商，如本文牵涉到版权问题，编程爱好者网站不承担相关责任，如有版权问题请直接与本文作者联系解决。谢谢！

评论

loading...
您需要登录后才能评论，请 登录 或者 注册