计算与人工智能概论-问题求解、科学计算与AI应用方法 习题及答案 第10章参考答案

一、简答题1.简述二分搜索算法的核心思想及实现过程。二分搜索是一种在有序数组中高效查找目标值的分治算法。其核心思想是：每次取当前搜索区间的中间元素，与目标值比较，若相等则找到；若中间值大于目标，则在左半区间继续搜索；若小于目标，则在右半区间搜索。如此反复将搜索范围减半，直至找到目标或区间为空。时间复杂度为O(logn)。实现过程：初始化左右边界left=0、right=n-1；当left<=right时，计算中点mid=(left+right)/2；若arr[mid]==target返回mid；若target<arr[mid]则right=mid-1，否则left=mid+1；循环结束未找到则返回-1。该方法也可用于求解非线性方程的根（如科学计算中的二分法）。简述二分法和牛顿迭代法求解方程根的异同点。二分法与牛顿迭代法均用于求解非线性方程f(x)=0的数值根，都通过迭代逼近满足精度要求的解。相同点在于：二者均要求函数连续，且依赖预设精度终止迭代。主要差异如下：（1）前提条件：二分法需初始区间[a,b]满足f(a)f(b)<0（函数变号），保证根存在；牛顿法需给定初始点x0且函数可导，导数f′(x)≠0。（2）收敛性：二分法全局收敛、稳定可靠，但速度慢（线性收敛，每次误差减半）；牛顿法局部收敛，对初值敏感，若初值接近真根则收敛极快（平方收敛），否则可能发散。（3）计算开销：二分法仅需计算函数值；牛顿法每步需计算函数值和导数值，实现更复杂。因此，二分法适用于对稳定性要求高的场景，牛顿法适用于高精度快速求解且能提供良好数值初值的情形。3.解释蒙特卡洛投点法计算圆周率π的基本思想。蒙特卡洛投点法计算圆周率π的基本思想基于几何概率：在一个边长为1的正方形内，内接一个半径为0.5的圆（圆心在正方形中心）。正方形面积为1×1=1；内接圆面积为π×(0.5)2=π/4。根据几何概率，若在正方形内随机均匀投掷大量点，则落入圆内的点数Nin与总投点数N之比，近似等于圆与正方形的面积之比：Nin/N≈π/4由此可得：π≈4×Nin/N通过生成大量随机点（如x,y∈[0,1]），统计满足(x−0.5)2+(y−0.5)2≤0.25的点数，代入上式即可估算π。投点越多，结果越接近真实值。该方法体现了用随机抽样估计确定性量的蒙特卡洛思想。4.梯度下降中学习率

α的作用是什么？过大或过小会导致什么问题？ 在梯度下降算法中，学习率α决定了每次迭代时参数沿梯度反方向更新的步长大小。作用：控制优化过程中参数调整的幅度，直接影响收敛速度和稳定性。 α过大：更新步长太大，可能导致参数在最优值附近剧烈震荡甚至发散；可能跳过最小值，使损失函数值不降反升，无法收敛。 α过小：更新步长太小，导致收敛速度极其缓慢，需要大量迭代才能接近最优解；容易陷入局部平坦区域，训练效率低下。 因此，学习率需适中：通常通过实验或采用自适应策略（如学习率衰减、Adam等）来平衡收敛速度与稳定性。梯度下降法为何可能收敛到局部极小值而非全局极小值？如何缓解此问题。 梯度下降法可能收敛到局部极小值而非全局极小值，原因在于其贪心的局部搜索机制： 算法每一步仅依据当前点的梯度（即局部一阶导数信息）决定下降方向，一旦到达某个局部极小点（梯度接近零），就会停止更新，无法感知其他区域是否存在更低的全局极小值。尤其在非凸函数（具有多个极小值）的优化问题中，这一局限性尤为明显。 缓解策略包括： 多起点随机初始化：从多个不同的初始点运行梯度下降，选择结果中最优的解，增加找到全局极小值的概率。 引入动量（Momentum）：在更新时加入历史梯度的累积项，帮助算法“冲过”浅层局部极小值或鞍点。 使用自适应学习率方法：如Adam、RMSprop等，能根据参数的历史梯度动态调整步长，提升跳出局部极小的能力。 采用启发式或随机优化算法：如模拟退火、遗传算法、粒子群优化等，允许一定概率接受“上升”移动，增强全局探索能力。 改进目标函数或模型结构：在机器学习中，设计更平滑或近似凸的损失函数，可减少局部极小值的数量。6.从一维函数推广到高维函数时，梯度下降的更新公式有何变化？二、编程题1.二分法求方程根 请使用二分法求方程fx#include<stdio.h>#include<math.h>//定义函数f(x)=-sin(x)*e^x+15*cos(x)*sqrt(x)doublef(doublex){return-sin(x)*exp(x)+15.0*cos(x)*sqrt(x);}intmain(){doublea=2.0,b=5.0;doublet;constdoubleeps=1e-8;//二分法迭代while(1){t=(a+b)/2.0;doubleft=f(t);if(fabs(ft)<=eps){break;//满足精度要求}//判断根在左半还是右半区间if(f(a)*ft<0){b=t;//根在[a,t]}else{a=t;//根在[t,b]}}printf("%.5f\n",t);return0;}2.二分法求方程根函数fx=x#include<stdio.h>#include<math.h>doublef(doublex){returnx*x-10*x+3;}doublefind_root(doublea,doubleb,doubleeps){doublemid;while(1){mid=(a+b)/2.0;doublefmid=f(mid);if(fabs(fmid)<=eps){returnmid;}if(f(a)*fmid<0){b=mid;}else{a=mid;}}}intmain(){constdoubleeps=0.0001;doubleroot1=find_root(0.0,1.0,eps);//左侧根doubleroot2=find_root(9.0,10.0,eps);//右侧根printf("%.6f\n",root1);printf("%.6f\n",root2);return0;}3.重复序列二分搜索 请使用二分法在已排序的重复数据序列A中，查找比指定的元素x小的最大的数，给出该数在序列A中最后一次出现的下标，找不到输出-1。示例：序列A：1,1,1,1,1,2,2,2,2,2,4,4,4,4，x值为2，比2小的最大的数是1，最后出现的下标位置为4。#include<stdio.h>intmain(){intn,x;scanf("%d%d",&n,&x);int*A=(int*)malloc(n*sizeof(int));for(inti=0;i<n;i++){scanf("%d",&A[i]);}intleft=0,right=n-1;//二分查找最后一个A[i]<x的位置while(left<=right){intmid=left+(right-left)/2;if(A[mid]<x){left=mid+1;//向右找更大的下标}else{right=mid-1;//当前及右边不满足，向左}}//循环结束时，right是最后一个满足A[i]<x的下标if(right>=0){printf("%d\n",right);}else{printf("-1\n");}free(A);return0;}4.二分法进行数字查找 请使用二分法在一个升序序列中查找两个数，使得两者的立方和等于给定的数X。如果找到了，请输出这两个数，并用空格分隔；如果没有找到，请输出-1。#include<stdio.h>#include<stdlib.h>#include<math.h>//二分查找函数：在升序数组A中查找值key，存在返回1，否则0intbinary_search(intA[],intn,intkey){intleft=0,right=n-1;while(left<=right){intmid=left+(right-left)/2;if(A[mid]==key){return1;}elseif(A[mid]<key){left=mid+1;}else{right=mid-1;}}return0;}intmain(){intn;longlongX;//X可能很大scanf("%d%lld",&n,&X);int*A=(int*)malloc(n*sizeof(int));for(inti=0;i<n;i++){scanf("%d",&A[i]);}//遍历每个afor(inti=0;i<n;i++){longlonga=A[i];longlongcube_a=a*a*a;longlongneed=X-cube_a;//处理need的立方根doubleroot;intb_candidate[3];intcount=0;if(need==0){b_candidate[0]=0;count=1;}elseif(need>0){root=cbrt((double)need);intb0=(int)round(root);b_candidate[0]=b0-1;b_candidate[1]=b0;b_candidate[2]=b0+1;count=3;}else{//need<0root=cbrt((double)(-need));intb0=(int)round(root);b_candidate[0]=-b0-1;b_candidate[1]=-b0;b_candidate[2]=-b0+1;count=3;}//检查候选bfor(intk=0;k<count;k++){longlongb=b_candidate[k];//防止溢出：先检查b是否在合理范围（可选）if(b*b*b==need){//在数组中二分查找bif(binary_search(A,n,(int)b)){printf("%lld%lld\n",a,b);free(A);return0;}}}}printf("-1\n");free(A);return0;}5.牛顿迭代法求方程根求fx=x3−x−1在[-10,10]之间的近似根，已知f(-10)<0，f(10)>0，函数在该区间有且仅有一个根。要求近似根带入函数f(x)后，#include<stdio.h>#include<math.h>doublef(doublex){returnx*x*x-x-1;}doubledf(doublex){return3*x*x-1;}intmain(){doublex=1.5;//初始值constdoubleeps=1e-6;constintmax_iter=100;for(inti=0;i<max_iter;i++){doublefx=f(x);if(fabs(fx)<=eps){break;}doubledfx=df(x);if(fabs(dfx)<1e-12){//防止导数为零break;}x=x-fx/dfx;}printf("%.4f\n",x);return0;}6.蒙特卡洛方法求定积分用蒙特卡罗方法求函数fx=(x#include<stdio.h>#include<stdlib.h>#include<math.h>#include<time.h>//自定义被积函数f(x)=x/25.0+1.0/5doublef(doublex){returnx/25.0+1.0/5.0;}//蒙特卡洛积分函数doublemonte_carlo_integral(double(*func)(double),doublea,doubleb,intN){//确定ymax：在[a,b]上采样找最大值（因函数简单，也可直接计算）doubleymax=0.0;intsteps=1000;for(inti=0;i<=steps;i++){doublex=a+(b-a)*i/steps;doubley=func(x);if(y>ymax)ymax=y;}srand(time(NULL));//初始化随机种子intcount=0;for(inti=0;i<N;i++){doublex=a+(b-a)*((double)rand()/RAND_MAX);//[a,b]doubley=ymax*((double)rand()/RAND_MAX);//[0,ymax]if(y<=func(x)){count++;}}return(b-a)*ymax*((double)count/N);}intmain(){doublea=0.0,b=1.0;intN=1000000;//投点数，越大越精确doubleresult=monte_carlo_integral(f,a,b,N);printf("%.4f\n",result);return0;}7.蒙特卡洛方法求圆周率考虑一个圆的方程x#include<stdio.h>#include<stdlib.h>#include<time.h>intmain(){constintN=10000000;//投点数，越大越精确intcount=0;srand(time(NULL));//初始化随机种子for(inti=0;i<N;i++){doublex=(double)rand()/RAND_MAX;//[0,1)doubley=(double)rand()/RAND_MAX;//[0,1)if(x*x+y*y<=1.0){count++;}}doublepi=4.0*count/N;printf("%.6f\n",pi);return0;}8．梯度下降算法求一元函数极值采用梯度下降算法求一元函数fx#include<stdio.h>#include<math.h>doublef(doublex,doublek){returnx*x-k*x+5.0;}doubledf(doublex,doublek){return2.0*x-k;//导数}intmain(){doublek;scanf("%lf",&k);doublex=0.0;//初始猜测值doublealpha=0.01;//学习率constdoublegrad_tol=1e-8;constintmax_iter=100000;for(inti=0;i<max_iter;i++){doublegrad=df(x,k);if(fabs(grad)<grad_tol){