m*****f
发帖数: 1243 | 1 Consider a function which, for a given whole number n, returns the number of
ones required when writing out all numbers between 0 and n.
For example, f(13)=6. Notice that f(1)=1. What is the next largest n such
that f(n)=n? |
h*********i
发帖数: 2605 | |
m*****f
发帖数: 1243 | 3 1, 10, 11, 12, 13
6
【在 h*********i 的大作中提到】
: f(13)=5
|
s*x
发帖数: 3328 | 4 1 10 11 12 13
【在 h*********i 的大作中提到】
: f(13)=5
|
n****g
发帖数: 14743 | 5 有趣
of
【在 m*****f 的大作中提到】
: Consider a function which, for a given whole number n, returns the number of
: ones required when writing out all numbers between 0 and n.
: For example, f(13)=6. Notice that f(1)=1. What is the next largest n such
: that f(n)=n?
|
S*********N
发帖数: 6151 | 6
of
f(0)=0
【在 m*****f 的大作中提到】
: Consider a function which, for a given whole number n, returns the number of
: ones required when writing out all numbers between 0 and n.
: For example, f(13)=6. Notice that f(1)=1. What is the next largest n such
: that f(n)=n?
|
j**7
发帖数: 59 | 7 f(n) = f(n-1)+y(n)
y(n) is the number of 1 in n
Is it good enough? |
g*******y
发帖数: 1930 | 8 not good enough
有logN的算法：
f(n) = f(n/10)*10 + n/10
这个式子只是个近似，边界值处理要注意一下
【在 j**7 的大作中提到】
: f(n) = f(n-1)+y(n)
: y(n) is the number of 1 in n
: Is it good enough?
|
a*****r
发帖数: 55 | |
n******r
发帖数: 1247 | 10 这chinglish...
of
【在 m*****f 的大作中提到】
: Consider a function which, for a given whole number n, returns the number of
: ones required when writing out all numbers between 0 and n.
: For example, f(13)=6. Notice that f(1)=1. What is the next largest n such
: that f(n)=n?
|
|
|
g*******y
发帖数: 1930 | 11 呵呵，你不说我们还没注意到，"whole number"~
【在 n******r 的大作中提到】
: 这chinglish...
:
: of
|
n******r
发帖数: 1247 | 12 "whole number"反应了半天才知道是啥意思，"the next largest n"还没明白啥意思
【在 g*******y 的大作中提到】
: 呵呵，你不说我们还没注意到，"whole number"~
|
a*****r
发帖数: 55 | |
m*****f
发帖数: 1243 | 14 网上看到转贴得， 不是我写的， 没注意
【在 n******r 的大作中提到】
: 这chinglish...
:
: of
|
m*****f
发帖数: 1243 | 15 事实上下一个f(n) = n的数好像是199981, 最优应该有logn的算法
【在 a*****r 的大作中提到】
: 999999999
|
a*****r
发帖数: 55 | 16 Yes, I was wrong.
f(10^10-1) = 10^10 |
a*****r
发帖数: 55 | 17 199981 is actually right. |
f*********r
发帖数: 68 | 18 Please read the question carefully before attempting to think it's Chinglish
. There is nothing wrong with the term "whole number" and "the next largest
n".
【在 n******r 的大作中提到】
: "whole number"反应了半天才知道是啥意思，"the next largest n"还没明白啥意思
|
b***e
发帖数: 1419 | 19 199981
number of
such
【在 m*****f 的大作中提到】
: Consider a function which, for a given whole number n, returns the number of
: ones required when writing out all numbers between 0 and n.
: For example, f(13)=6. Notice that f(1)=1. What is the next largest n such
: that f(n)=n?
|
b***e
发帖数: 1419 | 20 Such numbers are finite. So it's really O(n), in a strict sense.
【在 m*****f 的大作中提到】
: 事实上下一个f(n) = n的数好像是199981, 最优应该有logn的算法
|
|
|
c******a
发帖数: 198 | 21 whole number有啥问题？
【在 g*******y 的大作中提到】
: 呵呵，你不说我们还没注意到，"whole number"~
|
m*****f
发帖数: 1243 | 22 O(logn)是肯定的, brute force解法就是O(n)阿
【在 b***e 的大作中提到】
: Such numbers are finite. So it's really O(n), in a strict sense.
|
l*******r
发帖数: 511 | 23 could you explain the algorithm?
【在 a*****r 的大作中提到】
: 199981 is actually right.
|
H*M
发帖数: 1268 | 24 觉得有点奇怪
他们就写那么一个式子
是一个现有的成熟的算法还是,你们现场想出来的?
解释一下吧
我想到的就是recursion的那个O(n)算法
你们怎么都这么牛
就说一个式子
【在 l*******r 的大作中提到】
: could you explain the algorithm?
|
t******e
发帖数: 1293 | 25 这个在《编程之美》里面有，可以下载pdf看，或者买一本。
of
【在 m*****f 的大作中提到】
: Consider a function which, for a given whole number n, returns the number of
: ones required when writing out all numbers between 0 and n.
: For example, f(13)=6. Notice that f(1)=1. What is the next largest n such
: that f(n)=n?
|
c*****g
发帖数: 1137 | 26 什么叫the next largest? 第二大的？
of
【在 m*****f 的大作中提到】
: Consider a function which, for a given whole number n, returns the number of
: ones required when writing out all numbers between 0 and n.
: For example, f(13)=6. Notice that f(1)=1. What is the next largest n such
: that f(n)=n?
|
m********0
发帖数: 2717 | 27 programming pearl?
【在 t******e 的大作中提到】
: 这个在《编程之美》里面有，可以下载pdf看，或者买一本。
:
: of
|
m*****f
发帖数: 1243 | 28 我下载的不全, 请问你有全的pdf吗?
【在 t******e 的大作中提到】
: 这个在《编程之美》里面有，可以下载pdf看，或者买一本。
:
: of
|
h***r
发帖数: 726 | 29 no. I finished reading this book. not in that book. (unless in the question
part) : )
【在 m********0 的大作中提到】
: programming pearl?
|
b***e
发帖数: 1419 | 30 Sorry, typo. I mean O(1). There are only finite number of integers n
such that fn(n) = n.
【在 m*****f 的大作中提到】
: O(logn)是肯定的, brute force解法就是O(n)阿
|
|
|
H*M
发帖数: 1268 | 31 你不要老claim something吧,你总得给点proof或者说明什么的
【在 b***e 的大作中提到】
: Sorry, typo. I mean O(1). There are only finite number of integers n
: such that fn(n) = n.
|
b***e
发帖数: 1419 | 32 First see that:
f(10^n-1) = 10^(n-1) * n
e.g., f(9) = 1, f(99) = 20, f(999) = 300, ...
For the first several iterations, apparently f(n) < n always. So the
hope is one day, f(n) will catch up. Let's understand that the first
catch-up must happen in the form of "1x...", because that's where n -
f(n) is reducing.
So now, the question is, what's the "x.." after 1. Consider the length
of it. Can it be "1xx"? No, since at 99 you are down by 99-20 = 79,
and during 100 ~ 199, you can only catch u
【在 H*M 的大作中提到】
: 觉得有点奇怪
: 他们就写那么一个式子
: 是一个现有的成熟的算法还是,你们现场想出来的?
: 解释一下吧
: 我想到的就是recursion的那个O(n)算法
: 你们怎么都这么牛
: 就说一个式子
|
b***e
发帖数: 1419 | 33 f(10^100 - 1) = 100 * 10^99 = 10^101
So after 10^100, n will never again catch up with f(n).
It is not hard to see that f(n)/n is O(log(n)).
【在 H*M 的大作中提到】
: 你不要老claim something吧,你总得给点proof或者说明什么的
|
c*******d
发帖数: 255 | 34 应该是再也没有了吧
9以下的恰好有 1个
99以下的恰好有20个
999以下的恰好有300个
9999以下的恰好有4000个
一般的，k个9以下的恰好有k*10^{k-1}个
所以f(n)增长速度怎么都赶不上n
of
【在 m*****f 的大作中提到】
: Consider a function which, for a given whole number n, returns the number of
: ones required when writing out all numbers between 0 and n.
: For example, f(13)=6. Notice that f(1)=1. What is the next largest n such
: that f(n)=n?
|
m*****f
发帖数: 1243 | 35 事实上有不少...
【在 c*******d 的大作中提到】
: 应该是再也没有了吧
: 9以下的恰好有 1个
: 99以下的恰好有20个
: 999以下的恰好有300个
: 9999以下的恰好有4000个
: 一般的，k个9以下的恰好有k*10^{k-1}个
: 所以f(n)增长速度怎么都赶不上n
:
: of
|
c*******d
发帖数: 255 | 36 受教了，多谢！
【在 b***e 的大作中提到】
: First see that:
: f(10^n-1) = 10^(n-1) * n
: e.g., f(9) = 1, f(99) = 20, f(999) = 300, ...
: For the first several iterations, apparently f(n) < n always. So the
: hope is one day, f(n) will catch up. Let's understand that the first
: catch-up must happen in the form of "1x...", because that's where n -
: f(n) is reducing.
: So now, the question is, what's the "x.." after 1. Consider the length
: of it. Can it be "1xx"? No, since at 99 you are down by 99-20 = 79,
: and during 100 ~ 199, you can only catch u
|
b***e
发帖数: 1419 | 37 Dude,
r = k * 10^(k-1) / 10^k = k / 10
When k -> infinity, r -> infinity. I told you fn/n is O(log(n)). Didn't
you see that?
【在 c*******d 的大作中提到】
: 应该是再也没有了吧
: 9以下的恰好有 1个
: 99以下的恰好有20个
: 999以下的恰好有300个
: 9999以下的恰好有4000个
: 一般的，k个9以下的恰好有k*10^{k-1}个
: 所以f(n)增长速度怎么都赶不上n
:
: of
|
p********7
发帖数: 549 | 38 I got an idea about it.
前10个数0－9 有1个1
前100个数0－99有20个1
前1000个数0－999有20＊10＋100＝ 300
。。。
前100000个数0－99999有50000个1
前200000个数0－199999有50000＋100000＋50000 ＝ 200000
f(199999) = 200000
so go back one by one，get the right one
more explanation
前20 0－19 有12个
前200 0－199 有20＋100＋20 ＝ 140
前2000 0－1999 有300＋1000＋300 ＝ 1600
只有在n的最高位是1的情况下，f(n)增加速度是高于n，其他时候都是低于n |
