本文主要是介绍组合数学 - 1的个数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
1的个数
Mean:
输入一个n,计算小于10^n的正整数中含有1的数的个数。
analyse:
这题是一道组合数学课后思考题。
基本思路: 组合数学乘法原则 + 容斥原理
n位数中,每位可选:{0,1,2,3,4,5,6,7,8,9},所以共有10^n种,其中要除掉每位都为0的情况,所以要减一。
其中每位上不选1的情况为:{0,2,3,4,5,6,7,8,9},所以共有9^n中,同样要除掉全部为0的情况。
Time complexity:O(n)
Source code:
//Memory Time
// 1347K 0MS
// by : Snarl_jsb
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<string>
#include<climits>
#include<cmath>
#define N 1000010
#define LL long long
using namespace std;
//输入一个n,求小于10^n的正整数中有多少个1;
int main()
{
// freopen("C:\\Users\\ASUS\\Desktop\\cin.txt","r",stdin);
// freopen("C:\\Users\\ASUS\\Desktop\\cout.txt","w",stdout);
int n;
while(cin>>n)
{
// if(n==1)
// puts("1");
int sol=1;
for(int i=1;i<=n;i++)
{
sol*=10;
}
sol--;
int res=1;
for(int i=1;i<=n;i++)
{
res*=9;
}
res--;
cout<<sol-res<<endl;
}
return 0;
}
这篇关于组合数学 - 1的个数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!