一：杨氏矩阵
🐻何为杨氏矩阵？
杨氏矩阵，是对组合表示理论和舒伯特演算很有用的工具。它提供了一种方便的方式来描述对称和一般线性群的群表示，并研究它们的性质。杨氏矩阵是剑桥大学大学数学家阿尔弗雷德·扬在1900年提出。然后在1903年，它被用于格奥尔格·弗罗贝纽斯的对称群研究中。它的理论得益于许多数学家的贡献得到进一步发展，包括珀西·麦克马洪，W.V.D.霍奇，G.deB.罗宾逊，吉安·卡咯罗塔，阿兰拉斯克斯，马塞尔·保罗斯库森博格和理查德·P·史丹利。
杨氏矩阵最显著的特点是： 矩阵的每一行从左到右是递增的，矩阵的每一列从上到下是递增的。
如上图就是一个杨氏矩阵。
🐻题目描述：
编写程序，在杨氏矩阵中查找某一数字是否存在，若存在打印出坐标，若不存在，打印 “没找到” 。要求：时间复杂度小于O(N)
🐻思路一：
关于杨氏矩阵我们很容易想到可以用一个二维数组来表示，现在问题就变成了在一个二维数组中查找一个数字，我们很容易想到的就是遍历整个二维数组，这种方法当然没问题，但是但是它的时间复杂度是O(N^2)，不满足题目要求，因此需要换一种思路。
🐻思路二：
我们可以从杨氏矩阵的特点入手，来寻求解题方法。杨氏矩阵最显著的特点是： 矩阵的每一行从左到右是递增的，矩阵的每一列从上到下是递增的。因此我们不难发现：矩阵右上角的元素是第一行所有元素中最大的，同时也是最后一列所有元素中最小的。发现了这个特点以后，我们就可以让待查找的数字，与矩阵右上角的数字进行比较，如果待查找的数字比矩阵右上角的数字大，那待查找的数字就不可能在第一行，因为矩阵右上角的数字已经是第一行中最大的那个了，待查找的数字比矩阵右上角的数字还要大，此时就可以排除掉第一行的所有元素，在剩下的矩阵中查找。当待查找的数字比矩阵右上角的数字小的时候，那待查找的数字就不可能在矩阵的最后一列，因为矩阵右上角的数字已经是最后一列中最小的那个，待查找的数字比矩阵右上角的数字还要小，此时就可以排除掉矩阵最后一列的所有元素，在剩下的矩阵中查找。就一直这样让待查找的数字与矩阵右上角的数字作比较，最终就能比较出结果。分析的差不多了，接下来上代码。
void find_k(int arr[3][3], int r, int l, int k) { //右上角元素的坐标(x,y) int x = 0; int y = l - 1; //定义一个标志变量flag int flag = 0; //找到时把flag置为1 //最终通过看flag的值来看是否找到 while (x < r && y >= 0) { if (arr[x][y] > k)//待查找的元素比右上角的元素小 //此时就可以排除掉最右边的一整列 { y--; } else if (arr[x][y] < k)//待查找的元素比右上角的元素大 //此时就可以排除掉第一行所有元素 { x++; } else//找到了 { flag = 1; printf("找到了，坐标是：%d %d\n", x, y); break;//找到之后就要跳出循环 } } if (flag == 0) { printf("没找到"); } } int main() { int arr[3][3] = { 1,2,3,4,5,6,7,8,9 }; int r = sizeof(arr)/sizeof(arr[0]);//r表示行 int l = sizeof(arr[0])/4;//l表示列 int k = 0;//k表示待查找的数字 printf("请输入要查找的数字："); scanf("%d", &k); find_k(arr, r, l, k); return 0; }
上面的代码已经满足题目要求，但是我们发现，查找结果是直接在find_k函数中打印出来的，如果我们想在主函数中打印查找结果该怎么办呢？判断找没找到很容易实现，如果找到了，就让find_k函数返回 1 11 ，如果没有找到，就让find_k函数返回 0 00 ，在主函数中用一个变量 ret 来接收函数的返回值，最终判断 ret 的大小就知道找没找到了。问题的难点在于：如果找到了，如何把坐标返回到主函数中，坐标是由两个数字组成的，因此无法直接利用 return 返回，还有什么办法呢？我们可以通过传地址来解决这个问题，观察find_k函数的参数，可以发现 r 和 l 很适合来做这个差事，把r 和 l 的地址传过去，如果找到了就把坐标存到r 和 l里面去。分析的差不多了，接下来上代码：
int find_k(int arr[3][3], int* pr, int* pl, int k) { //右上角元素的坐标(x,y) int x = 0; int y = *pl - 1; while (x < *pr && y >= 0) { if (arr[x][y] > k)//待查找的元素比右上角的元素小 //此时就可以排除掉最右边的一整列 { y--; } else if (arr[x][y] < k)//待查找的元素比右上角的元素大 //此时就可以排除掉第一行所有元素 { x++; } else//找到了 { *pr = x; *pl = y; return 1;//找到之后就返回1 } } return 0; } int main() { int arr[3][3] = { 1,2,3,4,5,6,7,8,9 }; int r = sizeof(arr) / sizeof(arr[0]);//r表示行数 int l = sizeof(arr[0]) / 4;//l表示列数 int k = 0;//k表示待查找的数字 printf("请输入要查找的数字："); scanf("%d", &k); int ret = find_k(arr, &r, &l, k); if (ret == 0) { printf("没找到\n"); } else { printf("找到了，坐标是：%d %d\n", r, l); } return 0; }
本题到这里就结束了。请看下一题，剧透以下：下个题也性杨哦
二：杨辉三角
🐻何为杨辉三角？
杨辉三角，是二项式系数在三角形中的一种几何排列。在欧洲，这个表叫做帕斯卡三角形。帕斯卡（1623----1662）是在1654年发现这一规律的，比杨辉要迟393年，比贾宪迟600年。杨辉三角是中国古代数学的杰出研究成果之一，它把二项式系数图形化，把组合数内在的一些代数性质直观地从图形中体现出来，是一种离散型的数与形的结合
上图就是一个杨辉三角
🐻题目描述：
在屏幕上打印出杨辉三角
🐻解题思路：
首先应想到的是，利用二维数组来存储杨辉三角每一行的数值。接下来就该观察这些数值的特点了，不难发现二维数组的第 0 00 列和主对角线上的元素全是 1 11，对于这些位置上的元素我们可以直接把其初始化为 1 11 ，剩下位置上的元素是需要通过计算得到的，假设当前位置的下标是 i ,j，那么arr[i][j]的值就是其正上方和左上方的值的和，也就是公式：arr[i][j]=arr[i-1][j-1]+arr[i-1][j] 。其实从二维数组的第二行开始，主对角线上的元素也可以通过前面的公式计算得出，但此时必须保证公式中 arr[i-1][j] 的值是 0 00 ，如果当前的 arr[i][j] 是主对角线上的元素，那么 arr[i-1][j] 就不是杨辉三角中的一份子，但是为了计算出arr[i][j]，我们必须保证arr[i-1][j]的值是 0 00 ，这一点也很容易实现，在定义二维数组的同时，我们只初始化数组的第一个元素，把它初始化为 1 11 ，此时数组中剩下的元素就会被默认初始化为 0 00 ，这样问题就得以解决了。二维数组中的数值处理完了，接下来就该把这个二维数组打印出来了，杨辉三角只占用了二维数组的左下角这一片区域，所以只需要打印出左下角这片区域的内容即可，这片区域的坐标特点是：列标小于等于行标。分析的差不多了，接下来上代码：
int main() { int arr[10][10] = {1};//直接把第一个元素初始化成1，也就是杨辉三角的第一行 int i = 0; for (i = 1; i < 10; i++)//接下来从第二行开始 { arr[i][0] = 1;//每行的第一列都没有区别，直接给1，保证不会越界 int j = 0; for (j = 1; j <= i; j++)//从第二列开始 { arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j]; } } //打印 for (i = 0; i < 10; i++) { int j = 0; for (j = 0; j <=i; j++) { //只需要打印左下区的元素 //左下区元素小标的特点是：列标小于等于行标 printf("%d ", arr[i][j]); } //一行打印结束换行 printf("\n"); } return 0; }
🎶结语：
今天分享了两道杨性题目，杨氏矩阵和杨辉三角，这两道题都是已二维数组为基础，再结合各自的特点最终完成题解，由此可见拿到题目最主要的就是发现题目的特点，结合特点去解题往往会达到事半功倍的效果。
今天的分享到这里就结束啦，以上的内容如果对你有帮助的话，可以动动小手点赞、评论、收藏，你的支持就是我前进路上最大的动力！
