Question

一道数据结构题

一道数据结构题请问，2题的圈3，划线处，怎样由前面的求和公式，得到后面的（1/6）n^3，求过程，谢谢

Answer 1

#include#include#include#include#define THRESHOLD 1e-6void quickSort(double a[],int l, int r){ if(l>=r) return; int i=l; int j=r; double k=a[l]; while(i=a[i]) i++; a[j]=a[i]; } a[i]=k; quickSort(a, l, i-1); quickSort(a, i+1, r);}void sort(double a[], int n){ quickSort(a, 0, n-1);}int binSearch(double a[], double x, int n){ int l=0, h=n; while(l<=h) { int mid=(l+h)/2; double diff=a[mid]-x; if(fabs(diff)THRESHOLD) h=mid-1; else l=mid+1; } return -1;}int main(){ srand((unsigned)time(NULL)); double a[1000]; for(int i=0;i<1000;i++) a[i]=rand()/(RAND_MAX+1.0); printf("Generate 1000 random real numbers done.\n"); sort(a, 1000); printf("Sort done, input a 6 decimal places number between 0 and 1 to search: "); double d; scanf("%lf",&d); int find=binSearch(a, d, 1000); if(find==-1) { printf("%f is not in array a.\n", d); } else { printf("Found a[%d]=%f\n", find, d); } return 0;}