编程宝库 - 技术改变世界

编程宝库

Search

C语言编程技术

C++如何计算结构体与对象的大小

C语言计算大数相加的方法

C语言杨氏矩阵与杨辉三角的实现方法

一、杨氏矩阵

杨氏矩阵

1.杨氏矩阵的概念

在数学中，杨表（英语：Young tableau），又称杨氏矩阵。是对组合表示理论和舒伯特演算很有用的工具。它提供了一种方便的方式来描述对称和一般线性群的群表示，并研究它们的性质。杨表是剑桥大学数学家 Alfred Young 在1900年推提出。然后，它被弗罗贝尼乌斯应用对称群的研究中。他们的理论由许多数学家进一步发展，包括PercyMacMahon、W. V. D. Hodge、G. de B. Robinson、吉安-卡洛·罗塔、Alain Lascoux、Marcel-Paul Schützenberger 和 Richard P. Stanley 等。

2.杨氏矩阵的图解

3.杨氏矩阵的实现

在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

代码如下：

bool findNumberIn2DArray(int** matrix, int matrixSize, int* matrixColSize, int target)
{
  if(matrixSize==0||*matrixColSize==0)
  {
      return false;
  }
  int row=0;
  int col=*matrixColSize-1;
  while(row<matrixSize&&col>=0)
  {
      if(matrix[row][col]>target)
      {
          col--;
      }
      else if(matrix[row][col]<target)
      {
          row++;
      }
      else if(matrix[row][col]==target)
      {
          return true;
      }
  }
  return false;
}

二、杨辉三角

杨辉三角

1.杨辉三角的概念

杨辉三角，是二项式系数在三角形中的一种几何排列。在欧洲，这个表叫做帕斯卡三角形。帕斯卡（1623----1662）是在1654年发现这一规律的，比杨辉要迟393年，比贾宪迟600年。杨辉三角是中国古代数学的杰出研究成果之一，它把二项式系数图形化，把组合数内在的一些代数性质直观地从图形中体现出来，是一种离散型的数与形的结合。

2.杨辉三角的图解

3.杨辉三角的实现

给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。在杨辉三角中，每个数是它左上方和右上方的数的和。

代码如下：

#define _CRT_SECURE_NO_WARNINGS   1
#include<stdio.h>
int** generate(int numRows, int* returnSize, int** returnColumnSizes)
{
	int row = 0;
	int col = 0;
	//ret是一个指针,它指向的是由指针构成的数组，指针指向对应的杨辉三角的一行数；ret也是二维数组
	int** ret = (int**)malloc(sizeof(int*)*numRows);
	//指定要返回的行数
	*returnSize = numRows;
	//分配每一列的具体空间
	*returnColumnSizes = malloc(sizeof(int)*numRows);
	for (row = 0; row < numRows; row++)
	{
		/* 分配杨辉三角中每一行的具体空间 */
		ret[row] = malloc(sizeof(int)* (row + 1));
		// 分配杨辉三角中每一行的列数
		(*returnColumnSizes)[row] = row + 1;
		ret[row][row] = ret[row][0] = 1;
		for (col = 1; col < row; col++)
		{
			ret[row][col] = ret[row - 1][col - 1] + ret[row - 1][col];
		}
	}
	return ret;
}
int main()
{
	return 0;
}