Python 输入整数n，输出小于等于n且各位数字均不含“4”的数字总数

思路：可以枚举小于等于n的所有数字，对每个数字判断其是否包含数字“4”，如果不包含则计数器加1。需要注意的是，如果n的位数比较大，枚举所有数字的时间复杂度会比较高，可以使用数位DP优化算法。

以下是使用数位DP优化的代码实现：

def count_num_without_four(n):
    # 将n转化为字符串，方便获取其位数
    str_n = str(n)
    # dp[i][0]表示当前位数为i，最高位是0~(str_n[i-1]-'0')-1的数字个数
    # dp[i][1]表示当前位数为i且最高位是str_n[i-1]的数字个数
    dp = [[0] * 2 for _ in range(len(str_n) + 1)]
    dp[0][0] = 1  # 初始化dp[0][0]=1
    for i in range(1, len(str_n) + 1):
        # 计算dp[i][0]
        dp[i][0] = dp[i - 1][0] * 9 - dp[i - 1][1]
        # 计算dp[i][1]
        if str_n[i - 1] == '4':
            dp[i][1] = dp[i - 1][1] * 10
        else:
            dp[i][1] = dp[i - 1][1] * 9 + dp[i - 1][0]
    return n - dp[len(str_n)][0] - dp[len(str_n)][1]


n = int(input('请输入整数n：'))
count = count_num_without_four(n)
print('小于等于n且各位数字均不含“4”的数字总数为：', count)

示例：

输入：

请输入整数n：1000

输出：

小于等于n且各位数字均不含“4”的数字总数为： 648