数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中计算包含数字 0 且最多有 d 位的正整数个数
给定一个数字 d，表示数字的位数。目标是找到包含数字 0 且最多有 d 位的正整数的个数。
我们首先找到至少包含一个 0 的 d 位数字的个数。假设 d=3。要创建一个至少包含一个 0 的三位数，可能的方式是 -
Here d1 can have 1 to 9 : 9 ways d2 can have 0-9 : 10 ways d3 can have 0-9 : 10 ways Total numbers possible: 9 x 10 x 10 = 9 x 102 For d digits, count of numbers: 9 x 10d-1 For d digits, numbers without any 0 are : 9d Total numbers having d digits with at least one 0 = 9 x 10d-1 - 9d = 9 x ( 10d-1 - 9d-1 )
让我们通过例子来理解
输入 - d=4
输出 - 包含数字 0 且最多有 'd' 位的正整数的个数为 - 2619
解释 - 至少包含一个 0 的 x 位数字 -
1 digit numbers : 0 2 digit numbers : 9 3 digit numbers : 171 4 digit numbers: 2439 Total= 9+171+2439 = 2619
输入 - d=1
输出 - 包含数字 0 且最多有 'd' 位的正整数的个数为 - 0
解释 - 从 1 到 9，没有数字包含 0。
下面程序中使用的方案如下
我们将使用两种方案。第一种是使用 for 循环的简单方案。从 1 位到 d 位遍历，并使用上面提到的公式计算数字。将返回值加到计数中。
获取表示位数的整数 d。
函数 total_count(int d)) 获取位数 d 并返回具有 d 位且至少包含一个 0 的数字的个数。
计算此类数字，例如 temp=9*(pow(10,d-1) - pow(9,d-1));
返回 temp。
函数 maximum_d(int d) 获取最大位数 d 并返回最多 d 位且至少包含一个 0 的数字的个数。
使用循环从 1 位数开始遍历，然后是 2 位数，依此类推，直到 d 位数。
对于每个 d，计算数字，例如 total_count(i)。将其添加到计数中。
最后我们将得到总计数。
返回计数作为结果。
高效方案
在这种方案中，我们将通过观察上述计算形成的等比数列来计算计数。
Solution is 9 x (10d-1 - 9d-1) = 9 x (10d - 1)- 9 x (9d-1) = 9 x (10i - 1) - 9 x (9i - 1) ( 1<=i<=d ) = g.p 1 - g.p 2 = 9x(10d-1)/(10-1) - 9x(9d-1)/(9-1) = (10d-1)- (9/8)*(9d-1)
将 d 作为最大位数。
函数 maximum_d(int d) 获取最大位数 d 并返回最多 d 位且至少包含一个 0 的数字的个数。
使用上述公式计算 temp_1 为 9*((pow(10,d)-1)/9)。
计算 temp_2 为 9*((pow(9,d)-1)/8)。
设置 count = temp_1 - temp_2。
返回计数作为结果。
示例（简单方案）
#include<bits/stdc++.h>
using namespace std;
int total_count(int d){
int temp = 9*(pow(10,d-1) - pow(9,d-1));
return temp;
}
int maximum_d(int d){
int count = 0;
for (int i=1; i<=d; i++){
count = count + total_count(i);
}
return count;
}
int main(){
int d = 5;
cout<<"Count of positive integers with 0 as a digit and maximum 'd' digits are: "<<maximum_d(d) << endl;
return 0;
}输出
如果我们运行上述代码，它将生成以下输出 -
Count of positive integers with 0 as a digit and maximum 'd' digits are: 33570
示例（高效方案）
#include<bits/stdc++.h>
using namespace std;
int maximum_d(int d){
int temp_1 = 9*((pow(10,d)-1)/9);
int temp_2 = 9*((pow(9,d)-1)/8);
int count = temp_1 - temp_2;
return count;
}
int main(){
int d = 4;
cout<<"Count of positive integers with 0 as a digit and maximum 'd' digits are: "<<maximum_d(d) << endl;
return 0;
}输出
如果我们运行上述代码，它将生成以下输出 -
Count of positive integers with 0 as a digit and maximum 'd' digits are: 2619
80 次浏览
