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

一、选择题1.关于算法的描述，以下选项正确的是（）。A.算法必须使用特定编程语言实现。B.算法与程序是同一概念的不同表述。C.算法是一组有限且明确的解决问题的规则序列。D.算法的主要目标是优化硬件资源利用率。参考答案：C2.正确的算法设计流程是（）。A.建立模型→验证有效性→选择数据结构→消除无效计算B.定义控制结构→分析时间复杂度→建立数学模型C.建立数学模型→设计数据结构→设计控制结构→优化算法D.枚举所有解→编程实现→验证正确性参考答案：C3.问题规模为n时，若一个算法重复执行某个步骤的次数为：2(n-1)+6n2+logn，则该算法的时间复杂度为（）。A.O(n2)B.O(2n)C.O(logn)D.O(n2+2n)参考答案：B4.下面代码片段中，其时间复杂度为（）。intsum=0;for(inti=0;i<n;i++){for(intj=0;j<i;j++){sum+=i*j;}}printf("sum:%d\n",sum);A.O(n2)B.O(n)C.O(0.5n2)D.O(0.5n)参考答案：A5.如下代码片段中，设问题规模为n，其时间复杂度为________。intx=0;intk=n;while(k>1){x=x+k;k=k/2;}A.O(1)B.O(n)C.O(n²)D.O(logn)参考答案：D6.下面代码片段中，设问题规模为n，其时间复杂度为（）。intx=0;for(inti=0;i<n*n*n;i++){x=x+j;}for(inti=0;i<n;i++){for(intj=0;j<i*i*2;j++){x=x*j;}}A.O(n)B.O(n2)C.O(n3)D.O(n4)参考答案：C二、编程题1.成比例的三位数。将1,2,3,...,9共9个数分成3组，分别组成3个三位数，且使这3个三位数构成A:B:C的比例，其中A、B、C是输入的3个整数，且A<B<C，试求出所有满足条件的3个三位数，若无解，输出No。示例：A、B、C分别是1、2、3，则满足条件的共有4组：192384576，219438657，273546819，327654981。#include<stdio.h>#include<stdlib.h>intA,B,C;intdigits[9]={1,2,3,4,5,6,7,8,9};intused[9]={0};intcurrent[9];intsolutions[1000][3];//足够大，最多几十组intsol_count=0;//比较函数，用于qsortintcmp(constvoid*a,constvoid*b){int*x=(int*)a;int*y=(int*)b;if(x[0]!=y[0])returnx[0]-y[0];if(x[1]!=y[1])returnx[1]-y[1];returnx[2]-y[2];}//回溯生成全排列voidbacktrack(intpos){if(pos==9){//构造三个三位数intx=current[0]*100+current[1]*10+current[2];inty=current[3]*100+current[4]*10+current[5];intz=current[6]*100+current[7]*10+current[8];//检查比例：x:y:z=A:B:Cif(x*B==y*A&&y*C==z*B){solutions[sol_count][0]=x;solutions[sol_count][1]=y;solutions[sol_count][2]=z;sol_count++;}return;}for(inti=0;i<9;i++){if(!used[i]){used[i]=1;current[pos]=digits[i];backtrack(pos+1);used[i]=0;}}}intmain(){scanf("%d%d%d",&A,&B,&C);sol_count=0;backtrack(0);if(sol_count==0){printf("No\n");}else{//排序结果qsort(solutions,sol_count,sizeof(solutions[0]),cmp);//去重并输出（虽然理论上不会重复，但保险）for(inti=0;i<sol_count;i++){//跳过重复（相邻比较）if(i>0&&solutions[i][0]==solutions[i-1][0]&&solutions[i][1]==solutions[i-1][1]&&solutions[i][2]==solutions[i-1][2]){continue;}printf("%d%d%d\n",solutions[i][0],solutions[i][1],solutions[i][2]);}}return0;}2.数字三角形最小路径乘积在数字三角形中寻找一条从顶部到底边的路径，使得路径上所经过的数字的乘积最小，路径上的每一步都只能往左下或右下走，只需求出最小的乘积，不需要给出具体路径。示例：5层的数字三角形如下所示：238122471485265其最小路径乘积为24。#include<stdio.h>#definemax(a,b)((a)>(b)?(a):(b))intn;//数字三角形层数intA[100][100];//存储数字三角形的数组intDP[100][100];//存储状态值的动态规划表格intmain(){freopen("input.txt","r",stdin);//将标准输入重定向到文件scanf("%d",&n);//读取数字三角形层数for(inti=0;i<n;i++){for(intj=0;j<=i;j++){ scanf("%d",&A[i][j]);//内循环读取三角形的第i行，j为列号 if(i==n-1)DP[i][j]=A[i][j];//初始状态 }}for(inti=n-2;i>=0;i--){//从倒数第2层开始递推 for(intj=0;j<=i;j++){ DP[i][j]=max(DP[i+1][j],DP[i+1][j+1])+A[i][j];//状态转移 } }printf("%d\n",DP[0][0]);//输出最终结果return0;}3.数字三角形中避开障碍的路径总数给定一个数字三角形（层数n≥1），某些位置设置了障碍物（用-1表示）。从三角形顶部出发：每次只能向左下或右下移动；不能经过障碍物位置（值为-1）；必须到达三角形最底层的任意非障碍位置。计算所有能避开障碍到达底层的路径总数。示例1：4层的数字三角形如下所示：11-1121-1-111​​一条路径：1→1→2→1，输出值为1。​​示例2：3层的数字三角形如下所示：23-1456​​两条路径：2→3→4和2→3→5，输出值为2。#include<stdio.h>#include<stdlib.h>intmain(){intn;scanf("%d",&n);//动态分配三角形和dp数组int**tri=(int**)malloc(n*sizeof(int*));longlong**dp=(longlong**)malloc(n*sizeof(longlong*));for(inti=0;i<n;i++){tri[i]=(int*)malloc((i+1)*sizeof(int));dp[i]=(longlong*)calloc(i+1,sizeof(longlong));//初始化为0for(intj=0;j<=i;j++){scanf("%d",&tri[i][j]);}}//起点是障碍？if(tri[0][0]==-1){printf("0\n");gotocleanup;}dp[0][0]=1;//填充dp表for(inti=1;i<n;i++){for(intj=0;j<=i;j++){if(tri[i][j]==-1){dp[i][j]=0;//障碍，不可达}else{//来自左上(i-1,j-1)if(j-1>=0){dp[i][j]+=dp[i-1][j-1];}//来自正上(i-1,j)if(j<=i-1){dp[i][j]+=dp[i-1][j];}}}}//统计最后一行的路径总数longlongtotal=0;for(intj=0;j<n;j++){if(tri[n-1][j]!=-1){total+=dp[n-1][j];}}printf("%lld\n",total);cleanup:for(inti=0;i<n;i++){free(tri[i]);free(dp[i]);}free(tri);free(dp);return0;}4.最大子序列和给定一个整数数组（可能包含负数），请编写程序，找出数组中连续子序列的最大和（子序列至少包含一个元素）。如果所有整数都是负数，则结果为0。示例1：包含9个元素的序列：-21-34-121-54，其​​最大子序列和为4+(-1)+2+1=6。​​示例2：包含5个元素的序列：-1-2-3-4-5，其​​最大子序列和为0。#include<stdio.h>intmain(){intn;scanf("%d",&n);longlongcurrent_sum=0;longlongmax_sum=0;//初始为0，满足全负返回0的要求for(inti=0;i<n;i++){intx;scanf("%d",&x);current_sum+=x;if(current_sum<0){current_sum=0;//放弃前面的负贡献}if(current_sum>max_sum){max_sum=current_sum;}}printf("%lld\n",max_sum);return0;}5.最大子序列积对于一个浮点数序列A，只包含正数，找到一个子序列，使得该子序列中元素的乘积是最大的；输出这个最大的乘积。示例：包含8个元素的序列：40.1230.7122，其最大子序列乘积为16.80。#include<stdio.h>intmain(){intn;scanf("%d",&n);doublex;scanf("%lf",&x);//第一个数doublecurrent=x;doublemax_product=x;for(inti=1;i<n;i++){scanf("%lf",&x);//以当前元素结尾的最大乘积if(current*x>x){current=current*x;}else{current=x;}if(current>max_product){max_product=current;}}printf("%.2f\n",max_product);return0;}6.多数元素 给定一个大小为n的正整数数组，数组中有一个元素出现的次数大于n/2，这个元素被称为多数元素。找出并返回这个多数元素，若不存在多数元素，输出-1。提示：用分治算法每次将数组分割为两个数组。示例1：包含5个元素的数组：31151，其多数元素为1。示例2：包含6个元素的数组：7127473，其多数元素为-1。#include<stdio.h>#include<stdlib.h>//统计元素x在arr[l..r]中的出现次数intcountInRange(int*arr,intl,intr,intx){intcount=0;for(inti=l;i<=r;i++){if(arr[i]==x)count++;}returncount;}//分治函数：返回[l,r]区间内的多数元素候选（可能不是真正的多数）intmajorityDivide(int*arr,intl,intr){//Basecase:onlyoneelementif(l==r){returnarr[l];}intmid=l+(r-l)/2;intleft_cand=majorityDivide(arr,l,mid);intright_cand=majorityDivide(arr,mid+1,r);//Ifbothhalvesagreeonthemajoritycandidateif(left_cand==right_cand){returnleft_cand;}//Otherwise,checkwhichcandidateismajorityincurrentrangeintleft_count=countInRange(arr,l,r,left_cand);intright_count=countInRange(arr,l,r,right_cand);intlen=r-l+1;if(left_count>len/2){returnleft_cand;}if(right_count>len/2){returnright_cand;}//Nomajorityinthissegmentreturn-1;//Use-1toindicatenocandidate}intmain(){intn;scanf("%d",&n);int*arr=(int*)malloc(n*sizeof(int));for(inti=0;i<n;i++){scanf("%d",&arr[i]);}if(n==0){printf("-1\n");free(arr);return0;}intcandidate=majorityDivide(arr,0,n-1);//Finalverification:candidatemustappearmorethann/2timesif(candidate==-1){printf("-1\n");}else{inttotal_count=countInRange(arr,0,n-1,candidate);if(total_count>n/2){printf("%d\n",candidate);}else{printf("-1\n");}}free(arr);return0;}7.统计逆序对给定一个整数数组，统计其中逆序对的数量（逆序对定义为：若i<j且arr[i]>arr[j]，则(i,j)为一个逆序对）。要求使用分治算法实现，时间复杂度优于O(n²)。示例：包含5个元素的数组：35214，其逆序对为(3,2),(3,1),(5,2),(5,1),(5,4),(2,1)，总共6个。#include<stdio.h>#include<stdlib.h>//归并并统计跨越逆序对longlongmerge(int*arr,intl,intmid,intr){intn1=mid-l+1;intn2=r-mid;int*left=(int*)malloc(n1*sizeof(int));int*right=(int*)malloc(n2*sizeof(int));for(inti=0;i<n1;i++)left[i]=arr[l+i];for(intj=0;j<n2;j++)right[j]=arr[mid+1+j];inti=0,j=0,k=l;longlonginv_count=0;while(i<n1&&j<n2){if(left[i]<=right[j]){arr[k++]=left[i++];}else{arr[k++]=right[j++];//left[i]>right[j],且left[i..n1-1]都>right[j]inv_count+=(n1-i);}}while(i<n1)arr[k++]=left[i++];while(j<n2)arr[k++]=right[j++];free(left);free(right);returninv_count;}//分治函数：返回[l,r]区间内的逆序对数量longlongcountInversions(int*arr,intl,intr){longlonginv_count=0;if(l<r){intmid=l+(r-l)/2;inv_count+=countInversions(arr,l,mid);inv_count+=countInversions(arr,mid+1,r);inv_count+=merge(arr,l,mid,r);}returninv_count;}intmain(){intn;scanf("%d",&n);int*arr=(int*)malloc(n*sizeof(int));for(inti=0;i<n;i++){scanf("%d",&arr[i]);}longlongresult=countInversions(arr,0,n-1);printf("%lld\n",result);free(arr);return0;}8.硬币找零给定不同面额的