【打印杨辉三角和二分查找

【打印杨辉三角和二分查找

• • 打印杨辉三角
  • • 方法一：使用一维数组，占用内存少
    • 方法二：使用递归函数法，程序最简，占用内存最少，最佳算法
  • 二分查找

打印杨辉三角

1）第一列和对角线上的元素都为1；
2）除第一列和对角线上的元素之外，其他的元素的值均为前一行上的同列元素和前一列元素之和。

方法一：使用一维数组，占用内存少

#define N 7

int main()
{
	int ar[N] = { 0 };
	int n = 0;
	printf("请输入杨辉三角形的行数（1 ~ 20）：");
	scanf("%d", &n);
	for (int i = 0; i < n; i++)		// 0...19: 20
	{
		printf("第%2d 行=> :", i + 1);
		for (int j = i; j >= 0; j--)// 倒放数据
		{
			if (i == j || j == 0)
			{
				ar[j] = 1;
				printf("%5d", ar[j]);
			}
			else
			{
				ar[j] = ar[j - 1] + ar[j];
				printf("%5d", ar[j]);
			}
		}
		printf("n");
	}
	return 0;
}

方法二：使用递归函数法，程序最简，占用内存最少，最佳算法

int Tri(int row, int col) //杨辉三角算法函数	   
{
	if (col == 1 || col == row)
	{
		return 1;
	}
	else
	{
		return (Tri(row - 1, col - 1) + Tri(row - 1, col));
	}
}
int main()
{
	int n = 0;
	printf("请输入杨辉三角形的行数（1 ~ 20）：");
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)	// 输出n行
	{
		printf("第%2d 行=> :", i);
		for (int j = 1; j <= i; j++)
		{
			printf("%6d", Tri(i, j));	//计算并输出杨辉三角形	
		}
		printf("n");
	}
	return 0;
}

运行结果：

二分查找

二分査找（也称 折半査找） ： 其优点是查找速度快，缺点是要求所要査找的数据必须是有序序列。该算法的基本思想是将所要査找的序列的中间位置的数据与所要査找的元素进行比较，如果相等，则表示査找成功，否则将以该位置为基准将所要査找的序列分为左右两部分。接下来根据所要査找序列的升降序规律及中间元素与所查找元素的大小关系，来选择所要査找元素可能存在的那部分序列，对其采用同样的方法进行査找，直至能够确定所要查找的元素是否存在。
————————————————

int BinaryFindValue(const int* br, int n, int val)
{
	int pos = -1;
	if (NULL == br || n < 1) return pos;
	int left = 0, right = n - 1;
	int mid = 0;
	while (left <= right)
	{
		mid = (left + right) / 2;

		if (val < br[mid])
		{
			right = mid - 1;
		}
		else if(val > br[mid])
		{
			left = mid + 1;
		}
		else
		{
			pos = mid;
			break;
		}
	}
	return pos;
}
int main()
{
	int ar[] = { 12,23,34,45,56,67,78,89,90,100,110,120 };
	int n = sizeof(ar) / sizeof(ar[0]);
	int val = 0;
	printf("请输入你需要查找的数据：");
	while (scanf("%d", &val), val >= 0)
	{
		int pos = BinaryFindValue(ar, n, val);
		if (pos != -1)
		{
			printf("%d => %d n", pos, ar[pos]);
		}
		else
		{
			printf("no val");
		}
	}
	return 0;
}

运行结果：

nice~