作業(yè)答案-華東理工大學(xué)計算機(jī)科學(xué)與工程系(參考版)
2025-06-22 01:24本頁面
【正文】 前綴和：n個元素{x1,x2,…,xn}，前綴和是n個部分和，這里Si=x1＋x2…＋xi, 1≤i≤n 求解前綴和算法:輸入：n=2k的數(shù)組A,k為非負(fù)整數(shù)輸出：數(shù)組C，其中C(0,j)是第j和前綴和(1≤j≤n)begin (1)for j=1 to n pardo //初始化 B[0,j]=A[j] end if (2)for h=1 to logn do //正向遍歷 for j=1 to n/2h pardo B[h,j]=B[h1,2j1]*B[h1,2j] end for end for(3)for h=logn to 0 do //反向遍歷 for j=1 to n/2h pardo (i) if j=even then //該結(jié)點為其父結(jié)點的右兒子 C[h,j]=C[h+1,j/2] end if (ii) if j=1 then //該結(jié)點為最左結(jié)點 C[h,1]=B[h,1] end if (iii)
公司管理相關(guān)推薦
鄂ICP備17016276號-1