拼多多笔试1,3题分享

// first problem
double std3(int a,int b,int c){
    double mean = double(a+b+c) /3;
    double ret = (a-mean)*(a-mean) +(b-mean)*(b-mean)+(c-mean)*(c-mean);
    return ret;
}
double minstd(int num, int*numbers){
  sort(numbers,numbers+num);
  double ret = std3(numbers[0],numbers[1],numbers[2]),temp;
  for(int i=1; i<num-2;i++){
      temp = std3(numbers[i],numbers[i+1],numbers[i+2]);
      if (temp<ret)
        ret = temp;
  }
  return ret;
}

//third problem: 求递增且和邓素numsum 的序列个数;
void dfs(int numlen,int cur,int numSum,int &ret,int* nums){
    if(numSum<0 )
        return;
    if(cur == numlen){
        if (numSum ==0)
            ret +=1;
        return;
    }
    if(cur ==0){
        for(int i=1;i<=int((numSum)/numlen);i++){
            nums[0] = i;
            dfs(numlen,cur+1,numSum-i,ret,nums);
        }
    }
    else{
        for(int i=nums[cur-1]+1;i<=int(numSum/(numlen-cur));i++){
            nums[cur] = i;
            dfs(numlen,cur+1,numSum-i,ret,nums);
        }
    }
   return;
}

int count_sequences_satisfy_condition(int numlen, int numSum,unsigned long int** visited ){
    if(numlen==1)
        return 1;
    if(2*numSum<numlen*(numlen-1))
        return 0;
    if(numlen == 2){
        visited[numSum][2] = (numSum-1)/2;
        return (numSum-1)/2;
    }
    if(visited[numSum][numlen])
        return visited[numSum][numlen];
    int firstNumMax = numSum/numlen; 
    int sumcount = 0;
    for(int i=1;i<=firstNumMax;i++){
        visited[numSum-numlen*i][numlen-1] = count_sequences_satisfy_condition(numlen-1,numSum-numlen*i,visited);
        sumcount += visited[numSum-numlen*i][numlen-1];
    }
    return sumcount;
}