GESP C++ 5级 2024.03
唯一分解定理描述的内容是
任意整数都可以分解为素数的乘积
每个合数都可以唯一分解为一系列素数的乘积
两个不同的整数可以分解为相同的素数乘积
以上都不对
给定序列：1，3，6，9，17，31，39，52，61，79，81，90，96。使用以下代码进行二分查找查找元素 82时，需要循环多少次，即最后输出的 times 值为
int binarySearch(const std::vector& arr, int target) {
int left = 0;
int right = arr.size() - 1;
int times = 0;
while (left <= right) {
times ++;
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
cout << times << endl;
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
cout << times << endl;
return -1;
}
2
5
3
4
贪心算法的核心思想是
在每一步选择中都做当前状态下的最优选择
在每一步选择中都选择局部最优解
在每一步选择中都选择全局最优解
以上都对
下面的 C++ 代码片段用于计算阶乘。请在横线处填入（ ），实现正确的阶乘计算。
int factorial(int n) {
if (n == 0 || n == 1) {
return 1;
} else {
_________________________________ // 在此处填入代码
}
}
return n * factorial(n - 1);
return factorial(n - 1) / n;
return n * factorial(n);
return factorial(n / 2) * factorial(n / 2);
下面的代码片段用于在双向链表中删除一个节点。请在横线处填入（ ），使其能正确实现相应功能。
void deleteNode(DoublyListNode*& head, int value) {
DoublyListNode* current = head;
while (current != nullptr && current->val != value) {
current = current->next;
}
if (current != nullptr) {
if (current->prev != nullptr) {
___________________________________ // 在此处填入代码
} else {
head = current->next;
}
if (current->next != nullptr) {
current->next->prev = current->prev;
}
delete current;
}
}
if (current->next != nullptr) current->next->prev = current->prev;
current->prev->next = current->next;
delete current->next;
current->prev = current->next;
辗转相除法也被称为
高斯消元法
费马定理
欧几里德算法
牛顿迭代法
下面的代码片段用于将两个高精度整数进行相加。请在横线处填入（ ），使其能正确实现相应功能。
string add(string num1, string num2) {
string result;
int carry = 0;
int i = num1.size() - 1, j = num2.size() - 1;
while (i >= 0 || j >= 0 || carry) {
int x = (i >= 0) ? num1[i--] - '0' : 0;
int y = (j >= 0) ? num2[j--] - '0' : 0;
int sum = x + y + carry;
carry = sum / 10;
_______________________________________
}
return result;
}
result = to_string(sum % 10) + result;
result = to_string(carry % 10) + result;
result = to_string(sum / 10) + result;
result = to_string(sum % 10 + carry) + result;
下面的代码片段用于计算斐波那契数列。该代码的时间复杂度是
int fibonacci(int n) {
if (n <= 1) {
return n;
} else {
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
下面的代码片段用于判断一个正整数是否为素数。请对以下代码进行修改，使其能正确实现相应功能。
bool isPrime(int num) {
if (num < 2) {
return false;
}
for (int i = 2; i * i < num; ++i) {
if (num % i == 0) {
return false;
}
}
return true;
}
num < 2 应该改为 num <= 2
循环条件 i * i < num 应该改为 i * i <= num
循环条件应该是 i <= num
循环体中应该是 if (num % i != 0)
在埃拉托斯特尼筛法中，要筛选出不大于 n 的所有素数，最外层循环应该遍历什么范围
vector sieveOfEratosthenes(int n) {
std::vector isPrime(n + 1, true);
std::vector primes;
_______________________ {
if (isPrime[i]) {
primes.push_back(i);
for (int j = i * i; j <= n; j += i) {
isPrime[j] = false;
}
}
}
for (int i = sqrt(n) + 1; i <= n; ++i) {
if (isPrime[i]) {
primes.push_back(i);
}
}
return primes;
}
for (int i = 2; i <= n; ++i)
for (int i = 1; i < n; ++i)
for (int i = 2; i <= sqrt(n); ++i)
for (int i = 1; i <= sqrt(n); ++i)