## 【算法问题】当n=?时，n位含9的数的倒数和开始大于不含9的？

n=1时： 1/9 < 1/8+1/7+1/6+1/5+1/4+1/3+1/2+1

n=2时： 1/19 + 1/29 + 1/39 +...+ 1/89 + 1/90 + 1/91 + ... + 1/98 + 1/99 < 1/10 +1/11+1/12 +... + 1/88

n=3时： 1/109 + 1/119 + 1/129 + ... + 1/889 + 1/890 + 1/891 + ...+ 1/999 < 1/100 + 1/101 + 1/102 + ...+ 1/888

......

0
0

0
```N: 2, left: 0.294417641446448, right: 2.0539916222249173
N: 3, left: 0.4892219177097479, right: 1.817871425200977
N: 4, left: 0.6696709629108647, right: 1.633364212583175
N: 5, left: 0.8328467045790778, right: 1.4697833892399725
N: 6, left: 0.9798065352355224, right: 1.322783057766752
N: 7, left: 1.1120827703007445, right: 1.1905027726933806
N: 8, left: 1.231132820706344, right: 1.0714523172875223```
0

#### 引用来自“中山野鬼”的答案

0

0

0
```N: 2, left: 0.294417641446448, right: 2.0539916222249173
N: 3, left: 0.4892219177097479, right: 1.817871425200977
N: 4, left: 0.6696709629108647, right: 1.633364212583175
N: 5, left: 0.8328467045790778, right: 1.4697833892399725
N: 6, left: 0.9798065352355224, right: 1.322783057766752
N: 7, left: 1.1120827703007445, right: 1.1905027726933806
N: 8, left: 1.231132820706344, right: 1.0714523172875223
Find N: 8
Begin: 2013-10-24 15:56:10.6633147 +0800 CST, End: 2013-10-24 15:56:56.7453147 +0800 CST, Cost: 46.082s```

0

#### 引用来自“nowayout”的答案

```N: 2, left: 0.294417641446448, right: 2.0539916222249173
N: 3, left: 0.4892219177097479, right: 1.817871425200977
N: 4, left: 0.6696709629108647, right: 1.633364212583175
N: 5, left: 0.8328467045790778, right: 1.4697833892399725
N: 6, left: 0.9798065352355224, right: 1.322783057766752
N: 7, left: 1.1120827703007445, right: 1.1905027726933806
N: 8, left: 1.231132820706344, right: 1.0714523172875223
Find N: 8
Begin: 2013-10-24 15:56:10.6633147 +0800 CST, End: 2013-10-24 15:56:56.7453147 +0800 CST, Cost: 46.082s```

0
```

1:  left: 0.111111 right: 2.71786
2:  left: 0.294418 right: 2.05399
3:  left: 0.489222 right: 1.81787
4:  left: 0.669671 right: 1.63336
5:  left: 0.832847 right: 1.46978
6:  left: 0.979807 right: 1.32278
7:  left: 1.11208 right: 1.1905
8:  left: 1.23113 right: 1.07145
n = 8

#include <iostream>

using namespace std;

double countRec(long long num)
{
return  1/double(num);
}

bool isContainNine(long long num)
{
int temp = num;;
while(temp > 0)
{
int t = temp % 10;
temp = temp / 10;
if(t == 9) return true;
}
return false;
}

int main()
{
long long i;
long long t = 1;
int counter = 1;
double suma ,sumb ;
while(true)
{
suma = 0;sumb =0;
for(i = t;i < 10*t; i++)
{
if(isContainNine(i))  suma += countRec(i);
else  sumb += countRec(i);
}
cout << counter  << ": " << " left: " << suma <<" right: "
<< sumb <<endl;
if(suma > sumb)  break;
t = t * 10;
counter ++;
}
cout<< "n =" <<counter << endl;
return 0;
}

```
@习总 我没想到其它的效率高的算法，因为要计算倒数和，效果不是太好，不知道有什么快速计算倒数和的方法
Thanks.
0

@习总 这道题目规模比我想想的要小，用不上之前说的方法，直接穷举就很快。以下是C代码：

```#include <stdio.h>

typedef enum {
false = 0,
true = !false
} bool;

double sum;

void calc(int level, int limit, int n, bool contains9) {
if (level < limit) {
int i;
for (i = level == 0? 1: 0; i < 10; i++) {
calc(level + 1, limit, n * 10 + i, contains9 || i == 9);
}
} else {
sum += (contains9? -1.0: 1.0) / n;
}
}

int main(void) {
int i = 0;

do {
i++;
sum = 0.0;
calc(0, i, 0, false);
} while (sum > 0);
printf("n = %d\n", i);

return 0;
}```

```λ time ./main
n = 8
./main  0.51s user 0.00s system 99% cpu 0.517 total```