1からnまでの正の整数の中で1が現れる回数を統計します

1からnまでの正の整数の中で1が現れる回数を統計します
1、最も直感的な考え方で、1からnまでの整数ごとに1が現れる回数を求め、加算すればよい.10進数ごとに1が現れる回数を求めるには、まずこの数の桁数が1であるかどうかを判断し、この数が10より大きい場合は、10で割った後に1であるかどうかを判断し、その整数が1を含む個数を求めるまで循環する.
コードは次のとおりです.

#include "stdafx.h"
#include "stdlib.h"
#include <iostream>
#include <string>
#include <stack>
#include <math.h>
using namespace std;

//     1     
int NumberOf1(unsigned int n)
{
	int number = 0;	
	while(n)
	{	
		if(n % 10 == 1)		
			number ++;	
		n = n / 10;	
	}

	return number;
}

// 1 n      1      
int NumberOf1Between1AndN_Solution1(unsigned int n)
{
	int number = 0;	
	for(unsigned int i = 1; i <= n; ++ i)		
		number += NumberOf1(i);	

	return number;
}

void main()
{
	cout<<NumberOf1Between1AndN_Solution1(21345)<<endl; //18821
}

2、上記の考え方には非常に明らかな欠点があり、数字ごとに1がその数字に現れる回数を計算しなければならないので、時間複雑度はO(n)である.入力nが非常に大きい場合,大量の計算が必要であり,演算効率が低い.不要な計算を避けるためにいくつかの法則を見つけてみましょう.
        例として少し大きい数字21345を用いて解析した.1から21345までのすべての数字を2つのセグメント、すなわち1〜1345と1346〜21345に分けた(セグメントの利点は、1345ビット21345が最上位を除去した結果、再帰演算が容易であるためである).
        まず1346-21345中1の出現回数を見てみましょう.1の出現は2つの状況に分けられる:1つの状況は1が最高位(万位)に現れる.1から21345までの数字のうち、1は10000-1999という10000の数字の万位に現れ、合計10000(10^4)回現れた.もう1つのケースは、1が最上位を除く他のビットに現れることである.例では1346-21345で、この20000個の数字のうち後ろの4桁のうち1が2000回(2*10^3、うち2の1位の数値、10^3は数字の後ろの4桁の数字のうちの1桁が1であるため、残りの3桁の数字は0から9までの10個の数字を任意に選択することができ、配列の組み合わせから総回数が2*10^3であることがわかる).
        1から1345までのすべての数字のうち1が現れる回数については,再帰的に求めることができる.これも私たちが1-21345を1-1345と1346-21345の2つのセグメントに分ける理由です.21345の最高位を取り除くと1345になるので、再帰的な考え方を採用するのに便利です.
        ここまで分析すると、前述の例では、最上位は1より大きい数字であり、このとき最上位1が現れる回数は10^4(5桁に対して)であることに注意する必要があります.しかし、最高位が1だったら?たとえば12345と入力して、10000から12345までの数字の中で、1が万位に現れる回数は10^4回ではなく、2346回、つまり最上位の数字を除いた残りの数字に1を加えます.
前の分析に基づいて、以下のコードを書くことができます.リファレンスコードでは、プログラミングの便利さのために数字を文字列に変換しました.

#include "stdafx.h"
#include "stdlib.h"
#include <iostream>
#include <string>
#include <stack>
#include <math.h>
using namespace std;

//1 n      1    
int CharNumberOf1(const char *strN)
{
	int numFirstDigit=0,numOtherDigit=0,numRecursive=0;
	int len=strlen(strN);
	int firstDigit=*strN-'0'; 
	if(len==1&&firstDigit==0)
		return 0;
	if(len==1&&firstDigit>0)
		return 1;
	//   1   
	if(firstDigit==1)
		numFirstDigit=atoi(strN+1)+1;
	else
		numFirstDigit=pow(10,len-1);
	//    1   
	numOtherDigit=firstDigit*(len-1)*pow(10,len-2);
	//     1   
	numRecursive=CharNumberOf1(strN+1);

	return numFirstDigit+numOtherDigit+numRecursive;
}

//1 n     1    
int NumberOf1(int n)
{
	char strN[50];
	sprintf(strN,"%d",n);

	return CharNumberOf1(strN);
}

void main()
{
	cout<<NumberOf1(21345)<<endl; //18821
}