用c++写 DS查找—折半查找求阶乘函数后K个零 时间限制1s 内存限制128MB 题目描述 f(x) 是 x! 末尾是 0 的数量，给定 K，找出多少个非负整数 x ，能满足 f(x) = K 。（x! = 1 * 2 * 3 * ... * x，且 0! = 1 ） 例如， f(3) = 0 ，因为 3! = 6 的末尾没有 0 ；而 f(11) = 2 ，因为 11!= 39916800 末端有 2 个 0 。

折半查找的思路是利用有序数组的性质，从中间位置开始比较，不断缩小查找范围，直到找到目标元素或者查找范围为空。

对于本题，我们可以使用折半查找来寻找阶乘函数末尾有 K 个零的最小非负整数 x。具体思路如下：

1. 定义一个函数 count(x)，用于计算 x! 末尾的 0 的个数。

2. 定义左右边界 l 和 r，初始时分别为 0 和 K。

3. 在 [l, r] 中使用折半查找，寻找第一个使得 count(mid) >= K 的 mid 值，这个 mid 值就是最小的满足条件的非负整数 x。

4. 如果找到了 mid，那么 [l, mid - 1] 中可能还会有满足条件的 x，因此需要继续在这个区间内进行折半查找，直到找到最小的满足条件的 x。

5. 如果找不到 mid，那么 [mid + 1, r] 中也不会有满足条件的 x，因此可以直接退出查找。

6. 最后计算 [0, mid] 中满足条件的 x 的个数，即为所求。

下面是具体实现的 C++ 代码：

相关问题

用c++写折半查找求阶乘函数后K个零

这里给出一个用C++实现的求阶乘函数后K个零的折半查找算法。

#include <iostream>
using namespace std;

// 计算n的阶乘后有多少个0
int countZero(int n) {
    int count = 0;
    while (n > 0) {
        count += n / 5;
        n /= 5;
    }
    return count;
}

// 折半查找
int findK(int k) {
    int left = 0, right = 5 * k;
    while (left < right) {
        int mid = (left + right) / 2;
        if (countZero(mid) >= k) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

int main() {
    int k = 5;
    int res = findK(k);
    cout << "阶乘后" << k << "个零的位置为：" << res << endl;
    return 0;
}

这里的思路是先写一个计算n的阶乘后有多少个0的函数countZero，然后利用折半查找在0到5*k之间查找第一个满足countZero(mid)>=k的mid，最后返回mid即可。

E. DS查找—折半查找求阶乘函数后K个零

折半查找算法可以用来求解阶乘函数后K个零的问题。具体思路如下：

1. 定义一个函数count_zeros(n)，用来计算n!中末尾0的个数。

2. 因为末尾0的个数是由2和5的乘积决定的，所以我们可以先计算n!中5的个数，然后再算2的个数。

3. 对于一个正整数n，它可以分解为n = 5^p * m，其中m是不含5因子的整数，p是整数。因此，n!中5的个数就是p = floor(n/5) + floor(n/25) + floor(n/125) + ...，其中floor(x)表示不大于x的最大整数。

4. 对于n!中2的个数，可以按照类似的方法计算，即p = floor(n/2) + floor(n/4) + floor(n/8) + ...。

5. 因为2的个数一定比5的个数多，所以我们只需要计算5的个数即可。

6. 然后我们可以使用折半查找算法来查找阶乘函数后K个零的位置，具体步骤如下：

a. 定义一个函数binary_search(left, right, target)，其中left表示左边界，right表示右边界，target表示要查找的目标值。

b. 在[left, right]区间内进行二分查找，找到第一个使count_zeros(mid) >= K的mid值。

c. 如果找到了mid值，则阶乘函数后K个零的位置就是mid，否则阶乘函数中不存在K个零。

下面是一个Python实现的代码示例：

def count_zeros(n):
    """计算n!中末尾0的个数"""
    count = 0
    while n > 0:
        n //= 5
        count += n
    return count

def binary_search(left, right, target):
    """折半查找算法"""
    while left <= right:
        mid = (left + right) // 2
        if count_zeros(mid) >= target:
            right = mid - 1
        else:
            left = mid + 1
    return left if count_zeros(left) == target else -1

def factorial_k_zeros(K):
    """求阶乘函数后K个零的位置"""
    return binary_search(0, K * 5, K)

# 测试
print(factorial_k_zeros(1))  # 输出：5
print(factorial_k_zeros(2))  # 输出：10
print(factorial_k_zeros(3))  # 输出：15

在上面的代码中，我们首先定义了一个函数count_zeros(n)，用来计算n!中末尾0的个数。然后定义了一个函数binary_search(left, right, target)，用来进行折半查找。最后，我们定义了一个函数factorial_k_zeros(K)，用来求解阶乘函数后K个零的位置。在测试中，我们分别求解了阶乘函数后1个、2个、3个零的位置。