杨氏矩阵（C语言）

文章目录

• • 问题
  • 技术名词解释
  • 思路
  • 关键代码
  • 运行代码

问题

有一个数字矩阵，矩阵的每行从左到右是递增的，矩阵从上到下是递增的，请编写程序在这样的矩阵中查找某个数字是否存在。

要求：时间复杂度小于O(N);

技术名词解释

杨氏矩阵： 矩阵的每行从左到右是递增的，每列从上到下是递增的。是对组合表示理论和舒伯特演算很有用的工具。它提供了一种方便的方式来描述对称和一般线性群的群表示，并研究它们的性质。杨氏矩阵是剑桥大学大学数学家阿尔弗雷德·扬在1900年提出。然后在1903年，它被用于格奥尔格·弗罗贝纽斯的对称群研究中。它的理论得益于许多数学家的贡献得到进一步发展，包括珀西·麦克马洪，W.V.D.霍奇，G.deB.罗宾逊，吉安·卡咯罗塔，阿兰拉斯克斯，马塞尔·保罗斯库森博格和理查德·P·史丹利。

思路

定义一个二维数组arr[3][4]={1，2，3，4，5，6，7，8，9，10，11，12}。

关键代码

1、如果第一次输入不相等，则通过while循环找到所在下标，条件肯定包括a！=arr[i][col-1]、i<row和col>=0。

    int a = 0;
    printf("请输入你想找的数：");
    scanf("%d", &a);
    int i = 0, count = 1;
    while (a != arr[i][col - 1] && i < row && col >= 0)
    {
        if (a < arr[i][col - 1])
        {
            col--;
            count++;
        }
        else
        {
            count++;
            i++;
        }
    }

2、第一次相等或者通过while循环之后通过if实现下标、比较次数和是否找到的打印。

    if (a == arr[i][col - 1])
    {
        printf("下标为(%d,%d)\n", i, col - 1);
        printf("比较了%d次\n", count);
        return 1;
    }
    else
    {
        printf("比较了%d次\n", count);
        return 0;
    }

运行代码

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<windows.h>

int Young_tableau(int arr[4][4], int row, int col)
{
	printf("****************\n");
	Sleep(100);
	printf("****寻找开始****\n");
	Sleep(100);
	printf("****************\n");
	Sleep(100);

	int a = 0;
	printf("请输入你想找的数：");
	scanf("%d", &a);
	int i = 0, count = 1;
	while (a != arr[i][col - 1] && i < row && col >= 0)
	{
		if (a < arr[i][col - 1])
		{
			col--;
			count++;
		}
		else
		{
			count++;
			i++;
		}
	}
	if (a == arr[i][col - 1])
	{
		printf("下标为(%d,%d)\n", i, col - 1);
		printf("比较了%d次\n", count);
		return 1;
	}
	else
	{
		printf("比较了%d次\n", count);
		return 0;
	}
}
int main()
{
	int arr[4][4] = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16 };
	int row = 4, col = 4;
	int ret=Young_tableau(arr, row, col);
	if (ret == 1)
	{
		printf("找到了\n");
	}
	else
	{
		printf("找不到了\n");
	}
	return 0;
}