寒武纪2019秋招软件岗试题（二）

随着 n 逐渐增大，Darts函数的输出结果逐渐接近于____。

double rand_double() {

        return rand() / (double)RAND_MAX

}

double Darts(int n) {

      int k = 0

      double x, y

      for (int i = 0 i < n i++) {

      x = rand_double()

      y = x

      if ((x * x + y * y) <= 1.0)

      k++

   }

   return k * 4.0 / n

}

 同余与模，完善下列程序计算 (a^n) % mod

int pow_mod(int a, int n, int mod) {

  if (n == 0) return ________

  int x = ________

  long long ans = (long long)x * x % mod

  if (n % 2 == 1) ans =________

  return (int)ans

}

下面的程序完成了以下功能：在非降序列中二分查找一个数，当v存在时返回它出现的第一个位置，如果不存在，返回这样一个下标i，在此处插入v（原来的元素A[i], A[i+1],…全部向后移动一个位置）后序列仍然有序：

#include<iostream>

using namespace std

int lower_bound（int *A, int l, int r, int v） {

    int mid

    while (l < r) {

        mid =                    

        if (             ) r = mid

        else l = mid + 1

    }

return l

}

int main() {

    int A[10] = {0, 0, 1, 2, 4, 5, 10, 20, 20, 30}

// 在 A 数组里用lower_bound查找 40

    cout << lower_bound(           ) << endl

    return 0

}

下面的程序实现了，使用优先队列的dijkstra算法求解起点为0的单源最短路问题。有定义如下：

typedef pair<int, int> pii

priority_queue<pii, vector<pii>, greater<pii> > q

pair在比较时会先比较第一个数，再比较第二个数，因此q是一个小元素优先的优先队列。对于图中节点x，first[x]代表其第一条出边的编号。对于图中编号为e的边，v[e]代表这条边的终点，w[e]代表这条边的权值。

试完善以下代码：

bool done[MAXN]

for (int i = 0 i < n i++) d[i] = (i == 0 ? 0 : INF)

memset(done, false, sizeof(done))

q.push(make_pair(d[0], 0))

while(!q.empty()) {

        pii u = q.top() q.pop()

        int x = u.second

        if (done[x])              

        done[x] = true

        for (int e = first[x] e != -1 e = next[e])

          if (                       ) {

          }

}

以下判断素数的代码在int表示的所有正数范围内是正确的么？为什么？如何改进？

bool is_prime(int n) {

  assert(n >= 1)

  for (int i = 2 (i * i) <= n i++)

    if (n % i == 0) return false

  return true

}

C语言函数strcat的定义如下：

char *strcat (char *dest, const char *src)

在C++的工程项目中，一般头文件里都会出现类似于下列的代码，而且命名基于所在项目源代码树的全路径

#ifndef CAMB_INCLUDE_TEST_H_

#define CAMB_INCLUDE_TEST_H_

…   // code

#endif  // CAMB_INCLUDE_TEST_H_