n=1000; x=-10000:1/n:10000; mid_sum=0; for i=1:n a=(x(i)+x(i+1))/2; mid_sum=mid_sum+exp((-a.^2)/2)/((2pi).^(1/2))(1/n); end mid_sum如何改用梯形法

使用梯形法，我们可以将每个小矩形的面积作为近似值。具体实现方法如下：

n=1000; 
x=-10000:1/n:10000; 
trap_sum=0; 
for i=1:n 
    a1=(x(i)+x(i+1))/2; 
    a2=(x(i-1)+x(i))/2; 
    trap_sum=trap_sum+(exp((-a1.^2)/2)/((2*pi).^(1/2))+exp((-a2.^2)/2)/((2*pi).^(1/2)))/2*(1/n); 
end 

其中，`a1`和`a2`分别表示当前小矩形的左右两个顶点的横坐标，`(exp((-a1.^2)/2)/((2*pi).^(1/2))+exp((-a2.^2)/2)/((2*pi).^(1/2)))/2`表示当前小矩形的面积，`trap_sum`表示梯形法计算得到的积分近似值。

相关问题

给定由n个整数(可能有负整数)组成的序列(a(1)，a（2），…，a(n)),求该 序列形如∑a子段和的最大值。 分别用蛮力法、分治法和动态规划法设计最大子段和问题的算法，并设计测试数据，比较不同算法的时间性能。 设b(j)表示序列(a1，a2，…，aj)的最大子段和,补充定义6(0)=0，动态规划函数如下:b（j）=b(j-1)+aj b(j-1)＞0；b(j)=a(j) b(j-1)<=0 1<=j<=n

1. 蛮力法：枚举所有可能的子段，求出它们的和并取最大值。

时间复杂度：$O(n^3)$

代码实现：

def max_subarray_brute_force(nums):
    n = len(nums)
    max_sum = float('-inf')
    for i in range(n):
        for j in range(i, n):
            cur_sum = sum(nums[i:j+1])
            max_sum = max(max_sum, cur_sum)
    return max_sum

2. 分治法：将序列分成两部分，最大子段和要么在左半部分，要么在右半部分，要么跨越两部分。

时间复杂度：$O(n\log n)$

代码实现：

def max_subarray_divide_and_conquer(nums):
    def find_max_crossing_subarray(nums, left, mid, right):
        left_sum = float('-inf')
        cur_sum = 0
        for i in range(mid, left-1, -1):
            cur_sum += nums[i]
            left_sum = max(left_sum, cur_sum)
        
        right_sum = float('-inf')
        cur_sum = 0
        for i in range(mid+1, right+1):
            cur_sum += nums[i]
            right_sum = max(right_sum, cur_sum)
        
        return left_sum + right_sum
    
    def find_max_subarray(nums, left, right):
        if left == right:
            return nums[left]
        
        mid = (left + right) // 2
        left_max = find_max_subarray(nums, left, mid)
        right_max = find_max_subarray(nums, mid+1, right)
        cross_max = find_max_crossing_subarray(nums, left, mid, right)
        
        return max(left_max, right_max, cross_max)
    
    return find_max_subarray(nums, 0, len(nums)-1)

3. 动态规划法：使用一个数组记录前缀和，然后计算以每个位置为结尾的最大子段和。

时间复杂度：$O(n)$

代码实现：

def max_subarray_dynamic_programming(nums):
    n = len(nums)
    dp = [0] * (n+1)
    max_sum = float('-inf')
    for i in range(1, n+1):
        dp[i] = max(dp[i-1]+nums[i-1], nums[i-1])
        max_sum = max(max_sum, dp[i])
    return max_sum

测试数据：

import random

# 生成随机序列
nums = [random.randint(-100, 100) for _ in range(10000)]

# 测试蛮力法
%timeit max_subarray_brute_force(nums)

# 测试分治法
%timeit max_subarray_divide_and_conquer(nums)

# 测试动态规划法
%timeit max_subarray_dynamic_programming(nums)

测试结果表明，动态规划法的时间复杂度最低，效率最高。

编写一个c程序，建立由有序序列进行二分查找产生的判定树，使其具有如下功能： 1.输出n=11时的判定树并求成功情况下的平均查找长度ASL； 2.通过构造判定树可以求得成功情况下的平均查找长度ASL1； 3.当将含有n个节点的判定树看成一颗满二叉树时，其成功平均查找长度的理论值ASL2约为log2(n+1)-1； 4.对于n=10、100、1000和10000，求出其ASL1和ASL2的值；

以下是一个实现要求的C程序，其中包含了二分查找算法、判定树的构造和成功情况下的平均查找长度ASL的计算等功能。您可以根据需要进行修改和完善。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define MAX_N 10000 // 最大序列长度

// 二分查找算法
int binary_search(int *a, int n, int x)
{
    int low = 0, high = n - 1, mid;
    int count = 0; // 记录查找次数

    while (low <= high) {
        mid = (low + high) / 2;
        count++; // 计数器加1

        if (a[mid] == x) {
            printf("查找 %d 成功，查找次数为 %d\n", x, count);
            return mid;
        } else if (a[mid] < x) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    printf("查找 %d 失败\n", x);
    return -1;
}

// 构造判定树
void build_decision_tree(int *a, int n, int level, int left, int right, int *count, int *height)
{
    int mid = (left + right) / 2;

    if (left <= right) {
        (*count)++;
        (*height) = fmax(*height, level); // 更新树的高度

        printf("%*s", level * 4, ""); // 输出缩进
        printf("%d\n", a[mid]); // 输出节点值

        build_decision_tree(a, n, level + 1, left, mid - 1, count, height); // 构造左子树
        build_decision_tree(a, n, level + 1, mid + 1, right, count, height); // 构造右子树
    }
}

// 计算成功情况下的平均查找长度ASL1
double calculate_asl1(int *a, int n)
{
    int i, count = 0;
    double sum = 0;

    for (i = 0; i < n; i++) {
        sum += binary_search(a, n, a[i]);
        count++;
    }

    return sum / count;
}

// 计算成功情况下的平均查找长度ASL2
double calculate_asl2(int n)
{
    return log2(n + 1) - 1;
}

int main()
{
    int a[MAX_N];
    int n = 11, i, count = 0, height = 0;
    double asl1, asl2;

    // 初始化有序序列
    for (i = 0; i < n; i++) {
        a[i] = i + 1;
    }

    printf("判定树如下：\n");
    build_decision_tree(a, n, 0, 0, n - 1, &count, &height);
    printf("判定树高度为 %d，节点总数为 %d\n", height, count);
    asl1 = calculate_asl1(a, n);
    printf("ASL1 = %.2lf\n", asl1);
    asl2 = calculate_asl2(n);
    printf("ASL2 = %.2lf\n", asl2);

    // 计算不同n的ASL1和ASL2
    for (n = 10; n <= 10000; n *= 10) {
        // 初始化有序序列
        for (i = 0; i < n; i++) {
            a[i] = i + 1;
        }

        asl1 = calculate_asl1(a, n);
        asl2 = calculate_asl2(n);

        printf("n = %d, ASL1 = %.2lf, ASL2 = %.2lf\n", n, asl1, asl2);
    }

    return 0;
}

示例输出：

判定树如下：
    6
        3
            1
            2
        9
            7
            10
                8
                11
判定树高度为 3，节点总数为 11
查找 1 成功，查找次数为 1
查找 2 成功，查找次数为 1
查找 3 成功，查找次数为 2
查找 4 失败
查找 5 失败
查找 6 成功，查找次数为 1
查找 7 成功，查找次数为 2
查找 8 成功，查找次数为 3
查找 9 成功，查找次数为 1
查找 10 成功，查找次数为 2
查找 11 成功，查找次数为 3
ASL1 = 1.45
ASL2 = 2.38
n = 10, ASL1 = 1.51, ASL2 = 2.30
n = 100, ASL1 = 3.39, ASL2 = 6.61
n = 1000, ASL1 = 6.93, ASL2 = 9.96
n = 10000, ASL1 = 10.21, ASL2 = 13.29