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

习总 发布于 2013/10/24 13:44
阅读 785
收藏 1

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 

......

那么当n=?时,左边开始大于右边。( n表示分母是几位数,不等式左右两边所有的分母为n位数的所有自然数 )

使用语言不限,问题不算难,要尽可能算得快


加载中
0
中山野鬼
中山野鬼

对于任意确定n,左侧存在一个 含9的数,比如 1/xxx9xxx,我们将 9替换为1,则在右侧总存在对应的 1/ xxx1xxx,例如,n =  8 时,左侧有  1/99922333 右侧总存在 1/11122333,左侧有 1/11111119 则右侧有 1/111111111

此时,左侧任意一个项,均存在右侧的对应项,且1对1对应,同时,右侧数的分母总小于左侧,此时, 右侧恒大于左侧。

哈。要么我上面的证明论述有错误,要么就是你在玩我。。

哈,我上面有个漏洞,当存在 1/19 和 1/91时, 均对应 1/11。但我仍然直觉认为,右侧恒大于左侧的,没时间细证明了。。

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
中山野鬼
中山野鬼

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

对于任意确定n,左侧存在一个 含9的数,比如 1/xxx9xxx,我们将 9替换为1,则在右侧总存在对应的 1/ xxx1xxx,例如,n =  8 时,左侧有  1/99922333 右侧总存在 1/11122333,左侧有 1/11111119 则右侧有 1/111111111

此时,左侧任意一个项,均存在右侧的对应项,且1对1对应,同时,右侧数的分母总小于左侧,此时, 右侧恒大于左侧。

哈。要么我上面的证明论述有错误,要么就是你在玩我。。

哈,我上面有个漏洞,当存在 1/19 和 1/91时, 均对应 1/11。但我仍然直觉认为,右侧恒大于左侧的,没时间细证明了。。

哈。我的直觉是错的。。。。n位到n+1演变时, 左侧所有项可在最小位增加 0到9,而右侧所有项,只能增加0到8,同时,n位时,右侧所有项需要移动到左侧加9.。。
0
Xsank
Xsank
不要被分数所迷惑
0
hecaptain
hecaptain

首先要保证含9的数量比不含9的多,可以算出n要大于7

然后从n大于7开始计算,然后考虑用欧拉常数计算多个倒数之和

应该还有方法估算出不含9的和占所有的百分比。。

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

怎么做的啊,这是什么代码?
redraiment
redraiment
回复 @习总 : 好吧,我的确没仔细看。
习总
习总
回复 @redraiment : 估计你没有仔细看啊,n=1时,就是所有的1位数,n=2时是所有的2位数,左边是某一位含9的,左边是任意位都不含9的
redraiment
redraiment
回复 @习总 : 题目给出的n=1、2、3三个例子好像没有统一规律。当n=1时,应该是1/9<1/1;n=3时,按照n=2的规律应该从1/899之后才是分母+1,而它却是从889开始就依次加一。所以不晓得楼主想要说的是什么样的规律。
redraiment
redraiment
回复 @习总 : 这个问题可以先通过寻找上界,再二分查找。从2,开始,一次检查n=4、8、16、……;找到第一个不符合条件的做为上界;然后用二分查找法来找到临界区即可。
0
zengxiangwei
zengxiangwei



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
我采用的穷举法,最后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;
}

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

@习总 这道题目规模比我想想的要小,用不上之前说的方法,直接穷举就很快。以下是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
redraiment
redraiment
回复 @习总 : 但按照以往的经验来说,Ruby比Python慢
习总
习总
回复 @redraiment : 哦,我就觉得嘛Python不太可能这么快
redraiment
redraiment
回复 @习总 : 不是,我同样用的是1.0 / 2
习总
习总
回复 @redraiment : python2.7的话1/2得到的是0,不是0.5,莫非是这个原因?或者程序改错了
redraiment
redraiment
回复 @习总 : 我照着这段代码直接翻译成Python后,运行到n=6时就结束了,莫非是精度问题?哈~不过Ruby比Python慢...
下一页
返回顶部
顶部