给父母申请绿卡 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Visa - 签证

给父母申请绿卡

给父母申请绿卡# Visa - 签证

m*f2019-05-17 07:05

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?

y*92019-05-17 07:05

2 楼

父母在美国，给父母申请绿卡，五月三号显示寄到USCIS，目前还没有存我们的支票，
考察过以前的帖子和经验，基本都是两周内肯定有消息，不知道最近审理速度是不是
变的慢了，请问是不是正常？

h*i2019-05-17 07:05

3 楼

f(13)=5

m*f2019-05-17 07:05

4 楼

1, 10, 11, 12, 13
6

【在 h*********i 的大作中提到】

: f(13)=5

s*x2019-05-17 07:05

5 楼

1 10 11 12 13

【在 h*********i 的大作中提到】

: f(13)=5

n*g2019-05-17 07:05

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?

S*N2019-05-17 07:05

7 楼

of
f(0)=0

【在 m*****f 的大作中提到】

j*72019-05-17 07:05

8 楼

f(n) = f(n-1)+y(n)
y(n) is the number of 1 in n
Is it good enough?

g*y2019-05-17 07:05

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?

a*r2019-05-17 07:05

10 楼

999999999

n*r2019-05-17 07:05

11 楼

这chinglish...

of

【在 m*****f 的大作中提到】

g*y2019-05-17 07:05

12 楼

呵呵，你不说我们还没注意到，"whole number"~

【在 n******r 的大作中提到】

: 这chinglish...
:
: of

n*r2019-05-17 07:05

13 楼

"whole number"反应了半天才知道是啥意思，"the next largest n"还没明白啥意思

【在 g*******y 的大作中提到】

: 呵呵，你不说我们还没注意到，"whole number"~

a*r2019-05-17 07:05

14 楼

f(10^k)=k*10^(k-1) + 1

m*f2019-05-17 07:05

15 楼

网上看到转贴得，不是我写的，没注意

【在 n******r 的大作中提到】

: 这chinglish...
:
: of

m*f2019-05-17 07:05

16 楼

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

【在 a*****r 的大作中提到】

: 999999999

a*r2019-05-17 07:05

17 楼

Yes, I was wrong.
f(10^10-1) = 10^10

a*r2019-05-17 07:05

18 楼

199981 is actually right.

f*r2019-05-17 07:05

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"还没明白啥意思

b*e2019-05-17 07:05

20 楼

199981

number of
such

【在 m*****f 的大作中提到】

b*e2019-05-17 07:05

21 楼

Such numbers are finite. So it's really O(n), in a strict sense.

【在 m*****f 的大作中提到】

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

c*a2019-05-17 07:05

22 楼

whole number有啥问题？

【在 g*******y 的大作中提到】

: 呵呵，你不说我们还没注意到，"whole number"~

m*f2019-05-17 07:05

23 楼

O(logn)是肯定的, brute force解法就是O(n)阿

【在 b***e 的大作中提到】

: Such numbers are finite. So it's really O(n), in a strict sense.

l*r2019-05-17 07:05

24 楼

could you explain the algorithm?

【在 a*****r 的大作中提到】

: 199981 is actually right.

H*M2019-05-17 07:05

25 楼

觉得有点奇怪
他们就写那么一个式子
是一个现有的成熟的算法还是,你们现场想出来的?
解释一下吧
我想到的就是recursion的那个O(n)算法
你们怎么都这么牛
就说一个式子

【在 l*******r 的大作中提到】

: could you explain the algorithm?

t*e2019-05-17 07:05

26 楼

这个在《编程之美》里面有，可以下载pdf看，或者买一本。

of

【在 m*****f 的大作中提到】

c*g2019-05-17 07:05

27 楼

什么叫the next largest? 第二大的？

of

【在 m*****f 的大作中提到】

m*02019-05-17 07:05

28 楼

programming pearl?

【在 t******e 的大作中提到】

: 这个在《编程之美》里面有，可以下载pdf看，或者买一本。
:
: of

m*f2019-05-17 07:05

29 楼

我下载的不全, 请问你有全的pdf吗?

【在 t******e 的大作中提到】

: 这个在《编程之美》里面有，可以下载pdf看，或者买一本。
:
: of

h*r2019-05-17 07:05

30 楼

no. I finished reading this book. not in that book. (unless in the question
part) : )

【在 m********0 的大作中提到】

: programming pearl?

b*e2019-05-17 07:05

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)阿

H*M2019-05-17 07:05

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.

b*e2019-05-17 07:05

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

b*e2019-05-17 07:05

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或者说明什么的

c*d2019-05-17 07:05

35 楼

应该是再也没有了吧
9以下的恰好有 1个
99以下的恰好有20个
999以下的恰好有300个
9999以下的恰好有4000个
一般的，k个9以下的恰好有k*10^{k-1}个
所以f(n)增长速度怎么都赶不上n

of

【在 m*****f 的大作中提到】

m*f2019-05-17 07:05

36 楼

事实上有不少...

【在 c*******d 的大作中提到】

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

c*d2019-05-17 07:05

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

b*e2019-05-17 07:05

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 的大作中提到】

p*72019-05-17 07:05

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