好长时间没有练算法了，笔试题1做，发现非常费劲，所以近日来找来《编程之美》1书来看看练练。为了鼓励自己多练，楼楼可能会出个专栏甚么的，感兴趣的同学我们可以1起抱团，楼楼也会保证每天都会更新。那今天呢，就是《编程之美》的第1题了，原题叫做“1”的数目，楼楼会把这道题还有相干的1些题都会记录下来，下面要开始了哦，Are you ready?
我相信如果是我们正在处于笔试或面试确当场，暴力穷举肯定是我们的第1个想法。1个1个算，算出1中出现“1”的个数，再算出2中出现“1”的个数，顺次类推，直到N中“1”的个数，然后相加得出最后的结论。我们看代码：
#include <iostream>
using namespace std;
int getOneShowTimes(unsigned int n) ;
int getOneShowSumTimes(unsigned int N) ;
int main()
{
unsigned int N = 123;
cout << "1出现的次数为：" << getOneShowSumTimes(N) << endl;
system("pause");
}
int getOneShowSumTimes(unsigned int N)
{
unsigned int count = 0;
for (unsigned int i = 0; i <= N; i++)
{
count += getOneShowTimes(i);
}
return count;
}
int getOneShowTimes(unsigned int n)
{
unsigned count = 0;
while(0 != n)
{
count += (n % 10) == 1 ? 1 : 0;
n /= 10;
}
return count;
}我们分析1下复杂度，外层循环要循环N次，内存循环要循环
下面我们想一想，有无更简单的办法呢？比如对1个3位数123而言，“1”只能在个位出现，或10位出现或千位出现。如果是依照这个原理来统计的，那我们可以完全将外层循环下降到
如123，那末
| 个位出现1 | 10位出现1 | 百位出现1 |
|---|---|---|
| 1 | 10 | 100 |
| 11 | 11 | 101 |
| 21 | 12 | 102 |
| 31 | 13 | 103 |
| 41 | 14 | 104 |
| 51 | 15 | … |
| 61 | 16 | |
| 71 | 17 | |
| 81 | 18 | |
| 91 | 19 | |
| 101 | 110 | |
| 111 | … | |
| 121 | 119 | 123 |
| 总计13次 | 总计20次 | 总计24次 |
| 料想公式 |
料想公式 |
料想公式 |
但是在这里有我们有几个特殊的情况需要特别斟酌，如相应的位数为0怎样办？比如51和50结果是完全不1样的。还有相应的位数为1怎样办？12和22的结果也是不1样的。我下面把结果罗列出来，大家也能够试着推导1下。
| 分情况 | 个位出现1 | 10位出现1 | 百位出现1 |
|---|---|---|---|
| bit = 0 | |||
| bit = 1 | |||
| bit > 1 |
总结1下，假定每位对应的权值为quan，如个位quan = 1,10位quan = 10，那末总的公式为
| bit=0 | bit=1 | bit>1 |
|---|---|---|
下面看代码：
package net.mindview.util;
public class MyThread {
public static void main(String[] args) {
int N = 123;
System.out.println("总共出现" + getOneShowTimes(N) + "次");
}
public static int getOneShowTimes(int N) {
int numPerBit; //存储每位的数目
int sumTimes = 0; //存储最后的结果
int quan = 1; //每位的权值，各位为1，10位为10，顺次类推
int tempN = N;
if (0 == N) {
return 0;
}
while(0 != tempN) {
numPerBit = tempN % 10;
sumTimes += getOneShowTimesPerBit(N, numPerBit, quan);
tempN /= 10;
quan *= 10;
}
return sumTimes;
}
public static int getOneShowTimesPerBit(int N, int numPerBit, int quan) {
if (0 == numPerBit) {
return N / (quan * 10) * quan;
} else if (1 == numPerBit) {
return (N / (quan * 10)) * quan + N % quan + 1;
} else {
return (N / (quan * 10) + 1 ) * quan;
}
}
}非常不好意思，这里的代码是Java的，由于原来就写好了，我就懒得再写成c++的了，请见谅哈！复杂度为
题目1是10进制，题目2是2进制。注意这里的区分。那我们一样写写看，看能不能找出甚么规律
假定N=3，那末我们看每位出现“1”的次数之和都是相等的，都是2次。那末结果就是2 * 2=4总共4次。其次，假定N=7，我们又惊奇地发现，所有小于7的数中每位出现“1”的次数之和也是相等的，每位出现“1”的次数之和为4，那末结果就是3 * 4 = 12次。那我们可以料想，当N=15时，总数为4 * 8 = 32次。这是非常理想的情况，那当N = 13呢？很easy，N=13，我们就先算N = 7。还剩下6个数，视察1下我们可以发现，剩下的6个数中“1”出现的次数=最小的6个数“1”出现的次数+6。那末我们就把问题降下来了，本来是要求左侧6个数中1出现的个数，转变成了求右侧6个数中1出现的个数。
| 本来要求的“1”出现的个数 | 简化以后要求的“1”出现的个数 |
|---|---|
| 1000 | 0000 |
| 1001 | 0001 |
| 1010 | 0010 |
| 1011 | 0011 |
| 1100 | 0100 |
| 1101 | 0101 |
那末剩下的6个数，又可以重复前面的步骤，先求N=3。
总结1下，假定不大于N的最小的2的次方数为