编程之美变形记——“49”的个数

本文主要是介绍编程之美变形记——“49”的个数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

昨天在杭电poj上看到一个道题。题目总结出来就是，给定一个正整数N，求出从1到N（包含N）之间49出现的个数。

举例：如N=101

则1到101之间101个数中，49出现一次。同时，409，4009（这样的数字不合法）。看到第一眼就想起来编程之美2.4有一道求“1”的个数的题目，这道题其实就是把“1”换成了49。

我第一眼想到的是用49进制，不过仔细考虑一下之后是不合适的。然后想了一个小时左右没想出来。虽然说就是变了个形，不过无奈本人智商不够，所以到了晚上睡觉前也暂时没有好的思路。

然而早晨一觉醒来，刷牙时脑海里忽然浮现出了解体思路。说到这里，真是觉得人应该多睡觉。高二有次数列求和的题，也是午睡的时候忽然想起了解题思路。

具体思路就是，每次处理两位。第一次处理个位十位，第二次处理十位百位，依此类推。处理之后再分类讨论：

我们用三个变量

HighNum   LowerNum  CurrentNum

分别表示当前位的高位数字，低位数字和当前位数字

然后就是一个分类讨论

if(CurrnetNum>49).........
if(Current==49)..........
if(Current<49)...........

至于为什么分类讨论，地球人都知道，看了编程之美2.4的人也会知道。

至于代码实现，我贴一个自己的。欢迎来拍砖，如果你用Iphone6S拍我，我更开心。

#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
int Calc(int num){int Factor=1;int LowerNum=0;int CurrentNum=0;int HighNum=0;int Count=0,Index=1;while(num/Factor!=0){if(Index<2)LowerNum=num-(num/Factor)*Factor;if(Index<2)CurrentNum=(num/Factor)%10;else{int temp=(num/Factor)%10;CurrentNum=temp*10+CurrentNum;}HighNum=num/(Factor*10);if(Index<2)Factor*=10;Index++;if(Index>2){cout<<"HighNum: "<<HighNum<<"\tFactor: "<<Factor<<"\tCurrentNum is: "<<CurrentNum<<endl;if(CurrentNum<49)Count+=HighNum*(Factor/10);if(CurrentNum==49)Count+=HighNum*(Factor/10)+LowerNum+1;if(CurrentNum>49)Count+=(HighNum+1)*(Factor/10);Index=1;}           }cout<<"Count: "<<Count<<endl;return Count;
}
int main(int argc,char **argv){int num;printf("enter a num:\n");scanf("%d",&num);printf("Total \"49\" is :%d\n",Calc(num));return 0;
}