avatar
给父母申请绿卡# Visa - 签证
m*f
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?
avatar
y*9
2
父母在美国,给父母申请绿卡,五月三号显示寄到USCIS, 目前还没有存我们的支票,
考察过以前的帖子和经验,基本都是两周内肯定有消息, 不知道最近审理速度是不是
变的慢了, 请问是不是正常?
avatar
h*i
3
f(13)=5
avatar
m*f
4
1, 10, 11, 12, 13
6

【在 h*********i 的大作中提到】
: f(13)=5
avatar
s*x
5
1 10 11 12 13

【在 h*********i 的大作中提到】
: f(13)=5
avatar
n*g
6
有趣

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?

avatar
S*N
7

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?

avatar
j*7
8
f(n) = f(n-1)+y(n)
y(n) is the number of 1 in n
Is it good enough?
avatar
g*y
9
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?

avatar
a*r
10
999999999
avatar
n*r
11
这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?

avatar
g*y
12
呵呵,你不说我们还没注意到,"whole number"~

【在 n******r 的大作中提到】
: 这chinglish...
:
: of

avatar
n*r
13
"whole number"反应了半天才知道是啥意思,"the next largest n"还没明白啥意思

【在 g*******y 的大作中提到】
: 呵呵,你不说我们还没注意到,"whole number"~
avatar
a*r
14
f(10^k)=k*10^(k-1) + 1
avatar
m*f
15
网上看到转贴得, 不是我写的, 没注意

【在 n******r 的大作中提到】
: 这chinglish...
:
: of

avatar
m*f
16
事实上下一个f(n) = n的数好像是199981, 最优应该有logn的算法

【在 a*****r 的大作中提到】
: 999999999
avatar
a*r
17
Yes, I was wrong.
f(10^10-1) = 10^10
avatar
a*r
18
199981 is actually right.
avatar
f*r
19
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"还没明白啥意思
avatar
b*e
20
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?

avatar
b*e
21
Such numbers are finite. So it's really O(n), in a strict sense.

【在 m*****f 的大作中提到】
: 事实上下一个f(n) = n的数好像是199981, 最优应该有logn的算法
avatar
c*a
22
whole number有啥问题?

【在 g*******y 的大作中提到】
: 呵呵,你不说我们还没注意到,"whole number"~
avatar
m*f
23
O(logn)是肯定的, brute force解法就是O(n)阿

【在 b***e 的大作中提到】
: Such numbers are finite. So it's really O(n), in a strict sense.
avatar
l*r
24
could you explain the algorithm?

【在 a*****r 的大作中提到】
: 199981 is actually right.
avatar
H*M
25
觉得有点奇怪
他们就写那么一个式子
是一个现有的成熟的算法还是,你们现场想出来的?
解释一下吧
我想到的就是recursion的那个O(n)算法
你们怎么都这么牛
就说一个式子

【在 l*******r 的大作中提到】
: could you explain the algorithm?
avatar
t*e
26
这个在《编程之美》里面有,可以下载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?

avatar
c*g
27
什么叫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?

avatar
m*0
28
programming pearl?

【在 t******e 的大作中提到】
: 这个在《编程之美》里面有,可以下载pdf看,或者买一本。
:
: of

avatar
m*f
29
我下载的不全, 请问你有全的pdf吗?

【在 t******e 的大作中提到】
: 这个在《编程之美》里面有,可以下载pdf看,或者买一本。
:
: of

avatar
h*r
30
no. I finished reading this book. not in that book. (unless in the question
part) : )

【在 m********0 的大作中提到】
: programming pearl?
avatar
b*e
31
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)阿
avatar
H*M
32
你不要老claim something吧,你总得给点proof或者说明什么的

【在 b***e 的大作中提到】
: Sorry, typo. I mean O(1). There are only finite number of integers n
: such that fn(n) = n.

avatar
b*e
33
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)算法
: 你们怎么都这么牛
: 就说一个式子

avatar
b*e
34
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或者说明什么的
avatar
c*d
35
应该是再也没有了吧
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?

avatar
m*f
36
事实上有不少...

【在 c*******d 的大作中提到】
: 应该是再也没有了吧
: 9以下的恰好有 1个
: 99以下的恰好有20个
: 999以下的恰好有300个
: 9999以下的恰好有4000个
: 一般的,k个9以下的恰好有k*10^{k-1}个
: 所以f(n)增长速度怎么都赶不上n
:
: of

avatar
c*d
37
受教了,多谢!

【在 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

avatar
b*e
38
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

avatar
p*7
39
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
相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。