• 2007-11-12

    [Code]昨晚做完的一道题 - [Code]

    版权声明:转载时请以超链接形式标明文章原始出处和作者信息及本声明
    http://www.blogbus.com/sgzxy-logs/10762459.html

        以下这题是我认识某ACM牛没完全解决的。虽然我的算法修炼很低级,不过做些比较数学化的题目有时候还是会有感觉,有兴趣的可以试试:

        现在有f(x)这一函数,其中x为自然数,函数统计的是:[0,x]范围中包含的数字"1"的位数,比如自然数"11"包含2"1"。例如f(1)=1f(10)=2f(11)=4

       现在编程求解:下一个满足f(x)=xx值是多少(第一个是x=1)?

    分享到:

    历史上的今天:

    评论

  • 貌似一样
  • 输入的范围?
    小的话直接枚举...
    大的话感觉先求是几位
    然后再从高到低位确认是哪个数字..
    1位数1个
    2位数20个
    3位300个
    4位4000个
    ……
    回复小龙女说:
    此题需要用的公式已经推出来了,如下:
    (1)f(10^n) = n*10^(n-1) + 1;

    (2)f(k * 10^n) = k*n*10^n-1 + 10^n k∈[2,9]

    (3)f{ k[0]*10^n + k[1]*10^(n-1) + ... + k[n-m]*10^m } =

    f( k[0]*10^n + k[1]*10^(n-1) + ... + k[n-m-1]*10^(m+1) } + f( k[n-m]*10^m ) + [Count]*k[n-m]*10^(m-1)

    注:[Count]是一变量,记录的是[ k[0], k[n-m-1] ]的范围内,k[i]=1的数量(i=0,1,2...,n-m-1)

    不过此题最关键是要实现用计算机去找,而非手动……同时尽量避免单纯的逐1穷举……我后来发现我的做法有问题,不是公式问题,而是我从公式得出的一些结论出现问题,导致找到的值不是最小的(范围是无限的,总之是找到1之后下一个满足题目f(x)=x)。其实从公式(2)很容易就可以解出f(200000) = 200000,不过没法证明这是最小的。
    2007-11-21 23:23:58
  • 恩。。呵呵,找天我试试