4、 分治法： 编写程序： 用二分法在有序表{3,4,10,13,33,42,46,63,76,78,95,96,120}中查找一个给定的数。

以下是使用分治法在有序表中查找给定数的程序示例：

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1

arr = [3, 4, 10, 13, 33, 42, 46, 63, 76, 78, 95, 96, 120]
target = 33

index = binary_search(arr, target)
if index != -1:
    print("找到了，索引为：", index)
else:
    print("未找到")

该程序使用二分法在有序表中查找给定的数。首先，将要查找的数与有序表的中间元素进行比较，如果相等，则返回该元素的索引；如果要查找的数小于中间元素，则在左半部分继续查找；如果要查找的数大于中间元素，则在右半部分继续查找。重复这个过程，直到找到要查找的数或者确定该数不存在于有序表中。

相关问题

分治法输入实例:5,2,1,4,3 输出: max1 = 5, max2 = 4

分治法是一种方法论，用于解决复杂问题。其主要思想是将问题分解成若干个相互独立且相同类型的子问题，再将子问题的解合并起来得到原问题的解。

对于给定的输入实例：5,2,1,4,3，我们可以使用分治法来找出其中的两个最大值。

首先，将输入实例平均分成两部分，分别是5,2,和1,4,3。

然后，分别对这两部分进行递归调用，分别找出每部分的最大值。

对于第一部分5,2，我们可以看出最大值为5，次大值为2。

对于第二部分1,4,3，我们可以看出最大值为4，次大值为3。

最后，将两部分的最大值和次大值进行比较，找出整个输入实例的最大值和次大值。

在本例中，最大值为5，次大值为4。

通过这个例子，我们可以看出分治法的思想，将一个大问题拆分成小问题来解决，并将小问题的解合并起来得到整个问题的解。这种方法的时间复杂度相对较低，能够快速解决复杂问题。

用C语言及递归分治法写一个程序：n对括号有多少种匹配方式

以下是用C语言及递归分治法实现n对括号匹配的程序：

#include <stdio.h>

// 递归函数，求解n对括号的匹配方式
int count(int n) {
    // 如果n为0，则括号已经匹配完毕，返回1
    if (n == 0) {
        return 1;
    }
    
    int i, j, res = 0;
    // 枚举左右括号的数量
    for (i = 0, j = n - 1; i < n; i++, j--) {
        res += count(i) * count(j);
    }
    
    return res;
}

int main() {
    int n;
    printf("请输入括号对数：");
    scanf("%d", &n);
    printf("%d对括号有%d种匹配方式。\n", n, count(n));
    return 0;
}

程序中的count函数采用递归分治法，枚举左右括号的数量，然后计算左右括号的匹配方式数相乘，最终返回所有情况的总和。程序运行时，先输入括号对数，然后输出匹配方式数。