算法练习题24——查找杨辉三角中的组合数

题目描述

杨辉三角中的每个元素是一个组合数。第 ( i ) 行的第 ( j ) 个元素表示组合数 ( C(i, j) ) ，即从 ( i ) 个元素中选 ( j ) 个元素的组合方式。已知一个正整数 ( N )，要求在杨辉三角中找到这个数，并输出它在杨辉三角中的具体位置。位置可以以第几行第几个元素的形式给出，或者将整个杨辉三角按顺序展开，输出 ( N ) 是展开后的第几个数。

输入：

        一个整数 ( N ) 

输出：

        输出整数 ( N ) 在杨辉三角中对应的位置，形式为：第几行的第几列，或者杨辉三角中的第几个元素。

解法一：逐项递推法

逐项递推法通过逐行计算杨辉三角中的所有组合数，直到找到目标数 ( N )。它直接从杨辉三角的第 0 行开始，依次计算每一行的组合数。

代码

import java.util.Scanner;public class FindInPascalTriangleByIteration {public static void main(String[] args) {// 读取输入的目标数 NScanner scanner = new Scanner(System.in);int N = scanner.nextInt();scanner.close();// 初始化位置计数，第0行第0列对应的位置为1int position = 1;// 遍历杨辉三角的每一行for (int i = 0; ; i++) {// 初始化当前行的第一个组合数C(i, 0) = 1long result = 1;// 遍历当前行的每一个元素 (即计算 C(i, j) 的值)for (int j = 0; j <= i; j++) {// 如果找到目标数N，则输出当前行和列的位置，并结束程序if (result == N) {System.out.println(i + " " + j);  // 输出行号i和列号jreturn;  // 结束程序}// 更新位置计数，表示组合数在杨辉三角中的顺序position++;// 计算下一个组合数C(i, j+1) 使用递推公式// result = C(i, j) = C(i, j-1) * (i - j) / (j + 1)if (j < i) {result = result * (i - j) / (j + 1);}}}}
}

解法二：二分查找法

二分查找法利用了组合数在每一行中先递增后递减的特性，可以对每一行中的组合数进行二分查找，快速定位目标数 ( N )。

代码

import java.util.Scanner;public class FindInPascalTriangleByBinarySearch {public static void main(String[] args) {// 读取输入的目标数 NScanner scanner = new Scanner(System.in);int N = scanner.nextInt();scanner.close();// 初始化位置计数int position = 1;  // 从第一元素开始计数// 遍历杨辉三角的行数for (int i = 0; ; i++) {// 如果这一行的中间最大值都比 N 小，则跳过这一行if (comb(i, i / 2) < N) {position += i + 1;  // 更新跳过的元素位置continue;}// 在这一行中使用二分查找来查找目标数 Nint left = 0;int right = i / 2;  // 只需要在行的左半部分查找while (left <= right) {int mid = left + (right - left) / 2;int value = comb(i, mid);  // 计算组合数 C(i, mid)if (value == N) {System.out.println(i + " " + mid);  // 输出行号 i 和列号 midreturn;  // 结束程序} else if (value < N) {left = mid + 1;  // 在右半部分继续查找} else {right = mid - 1;  // 在左半部分继续查找}}// 如果当前行没有找到目标数，更新位置计数position += i + 1;}}// 计算组合数 C(i, j)private static int comb(int i, int j) {long result = 1;for (int k = 0; k < j; k++) {result = result * (i - k) / (k + 1);  // 递推公式计算 C(i, j)}return (int) result;  // 返回组合数值}
}

总结

        逐项递推法适合处理较小的数据量，计算较为直观，但当杨辉三角行数较大时，效率较低。

        二分查找法利用组合数的单调性，显著提高查找效率，适合处理较大的数据范围。

这两种解法在不同场景下都可以使用，二分查找法尤其适合大规模数据下的查找问题。