資料結構
網路
關係型資料庫管理系統
作業系統
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 次瀏覽
