- 浏览: 75955 次
文章分类
最新评论
-
wodentt:
....为什么楼主都英文的博客
用java解决百度之星移动火柴的问题 part 1 -
wensonzhou86:
思路明确,代码清晰,通俗易懂
visit 淘宝面试题:如何充分利用多核CPU,计算很大的List中所有整数的和 -
carydeepbreathing:
代码比较干净
visit 淘宝面试题:如何充分利用多核CPU,计算很大的List中所有整数的和 -
meiowei:
yangguo 写道i don't think it is a ...
用java解决百度之星移动火柴的问题 part 2 -
yangguo:
i don't think it is a good way ...
用java解决百度之星移动火柴的问题 part 2
The roadmap to compute all fixed points of f(x) is to start from boundaries 1, or 10^10, and keep acting f on it. If x is a boundary point, first compare x and f(x) to see whether we should generate the series using f or f inverse. Once we know which one to use, then keep doing that until we get a fixed point. Then start from the next integer again.
In order to do these, we need a few functions:
1. function f:
This is basically a direct translate of the formula (A) and (B) in Lemma 4.
2. inverse of f:
Obviously the next one is f inverse. Since f is not single valued, we have to have a better definition on the inverse. We define the inverse of f for a given y as the smallest x such that x < y <= f(x), so we could step as far as possible.
The tricky part here is to figure out the power k. Here in order to know whether we should use formula (A) or (B), we need to check whether the to-be-found x has leading 1. So the helper function is
where we define the following
The other missing piece is the function foundRoot(). This is used in formula (A), which can be simplified in the form x + f(x) = y, with unknown x. We need a function to find the root x.
Two other small functions are:
which computes the number of 1's in x, and
which computes the power for the performance reason. With all of these in places, the only thing left is a "conductor" method:
The result is:
-----> found a fixed point: x=1111111110
-----> found a fixed point: x=535200001
-----> found a fixed point: x=535200000
-----> found a fixed point: x=535199990
-----> found a fixed point: x=535199989
-----> found a fixed point: x=535199988
-----> found a fixed point: x=535199987
-----> found a fixed point: x=535199986
-----> found a fixed point: x=535199985
-----> found a fixed point: x=535199984
-----> found a fixed point: x=535199983
-----> found a fixed point: x=535199982
-----> found a fixed point: x=535199981
-----> found a fixed point: x=535000001
-----> found a fixed point: x=535000000
-----> found a fixed point: x=513199998
-----> found a fixed point: x=502600001
-----> found a fixed point: x=502600000
-----> found a fixed point: x=501599990
-----> found a fixed point: x=501599989
-----> found a fixed point: x=501599988
-----> found a fixed point: x=501599987
-----> found a fixed point: x=501599986
-----> found a fixed point: x=501599985
-----> found a fixed point: x=501599984
-----> found a fixed point: x=501599983
-----> found a fixed point: x=501599982
-----> found a fixed point: x=501599981
-----> found a fixed point: x=500200001
-----> found a fixed point: x=500200000
-----> found a fixed point: x=500199990
-----> found a fixed point: x=500199989
-----> found a fixed point: x=500199988
-----> found a fixed point: x=500199987
-----> found a fixed point: x=500199986
-----> found a fixed point: x=500199985
-----> found a fixed point: x=500199984
-----> found a fixed point: x=500199983
-----> found a fixed point: x=500199982
-----> found a fixed point: x=500199981
-----> found a fixed point: x=500000001
-----> found a fixed point: x=500000000
-----> found a fixed point: x=117463825
-----> found a fixed point: x=35200001
-----> found a fixed point: x=35200000
-----> found a fixed point: x=35199990
-----> found a fixed point: x=35199989
-----> found a fixed point: x=35199988
-----> found a fixed point: x=35199987
-----> found a fixed point: x=35199986
-----> found a fixed point: x=35199985
-----> found a fixed point: x=35199984
-----> found a fixed point: x=35199983
-----> found a fixed point: x=35199982
-----> found a fixed point: x=35199981
-----> found a fixed point: x=35000001
-----> found a fixed point: x=35000000
-----> found a fixed point: x=13199998
-----> found a fixed point: x=2600001
-----> found a fixed point: x=2600000
-----> found a fixed point: x=1599990
-----> found a fixed point: x=1599989
-----> found a fixed point: x=1599988
-----> found a fixed point: x=1599987
-----> found a fixed point: x=1599986
-----> found a fixed point: x=1599985
-----> found a fixed point: x=1599984
-----> found a fixed point: x=1599983
-----> found a fixed point: x=1599982
-----> found a fixed point: x=1599981
-----> found a fixed point: x=200001
-----> found a fixed point: x=200000
-----> found a fixed point: x=199990
-----> found a fixed point: x=199989
-----> found a fixed point: x=199988
-----> found a fixed point: x=199987
-----> found a fixed point: x=199986
-----> found a fixed point: x=199985
-----> found a fixed point: x=199984
-----> found a fixed point: x=199983
-----> found a fixed point: x=199982
-----> found a fixed point: x=199981
-----> found a fixed point: x=1
It takes 62 milli
It takes 1139 iterations.
This is a typical fixed point problem, start from some arbitrary number and keep acting f on it. Several outputs of the series are:
1. It goes to infinity.
2. It goes to some fixed point.
3. It keeps bouncing back and forth(going nowhere).
Two types of fixed points are attractors and opposite attractors. Attractors are attracting nearby points, i.e., if we start from some point "close" enough to the attractor, the series will converge to the attractor. Opposite attractor is just the opposite, the series will go away from the opposite attractor.
In order to do these, we need a few functions:
1. function f:
java 代码
- private long numOfOnes(long x)
- {
- // recursion stops
- if (x <= 0) return 0;
- if (x == 1) return 1;
- int powerk = 0;
- long tenPowers = 1;
- long leadingDigit = x;
- while (leadingDigit >= 10)
- {
- leadingDigit /= 10;
- powerk++;
- tenPowers *= 10;
- }
- long reminder = x - leadingDigit * tenPowers;
- if (leadingDigit == 1)
- {
- return powerk * tenPowers / 10 + 1 + reminder + numOfOnes(reminder);
- }
- else
- {
- return leadingDigit * powerk * tenPowers / 10 + tenPowers + numOfOnes(reminder);
- }
- }
This is basically a direct translate of the formula (A) and (B) in Lemma 4.
2. inverse of f:
Obviously the next one is f inverse. Since f is not single valued, we have to have a better definition on the inverse. We define the inverse of f for a given y as the smallest x such that x < y <= f(x), so we could step as far as possible.
java 代码
- public long inverseFunc(long y)
- {
- // recursion default.
- if (y <= 0) return 0;
- if (y == 1) return 1;
- if (y == 2) return 10;
- // check whether y is in 1's range
- int m = isInOneRange(y);
- if (m != -1)
- {
- long tmp = y - (m + 1) * power(10, m) - 1;
- long inc = findRoot(tmp);
- return power(10, m + 1) + inc;
- }
- else
- {
- int k = numOfDigits(y) - 1;
- long tmp = y - power(10, k);
- long ak = tmp / (k * power(10, k - 1));
- if (ak > 9) ak = 9; // leave the rest to the recursion
- long remainder = tmp - ak * k * power(10, k - 1);
- long xRemainder = inverseFunc(remainder);
- return ak * power(10, k) + xRemainder;
- }
- }
The tricky part here is to figure out the power k. Here in order to know whether we should use formula (A) or (B), we need to check whether the to-be-found x has leading 1. So the helper function is
java 代码
- private int isInOneRange(long y)
- {
- // This is to check whether the func value is between the function
- // values of 10^n and 2*10^n.
- // this can be done faster since it's sorted, but again I am lazy
- int k=-1;
- for (int i=0; i<9; i++)
- {
- if (y <= y2[i])
- {
- k = i;
- break; // first smaller, break out
- }
- }
- if (k==-1) return -1;
- if (y >= y1[k]) return k;
- else return -1;
- }
where we define the following
java 代码
- long[] x1 = new long[9];
- long[] x2 = new long[9];
- long[] y1 = new long[9];
- long[] y2 = new long[9];
- for (int i=1; i<10; i++)
- {
- x1[i-1] = power(10, i);
- x2[i-1] = 2 * x1[i-1] - 1;
- y1[i-1] = numOfOnes(x1[i-1]);
- y2[i-1] = numOfOnes(x2[i-1]);
- }
- If we print out them:
- x range=[10, 19] y range=[2, 12]
- x range=[100, 199] y range=[21, 140]
- x range=[1000, 1999] y range=[301, 1600]
- x range=[10000, 19999] y range=[4001, 18000]
- x range=[100000, 199999] y range=[50001, 200000]
- x range=[1000000, 1999999] y range=[600001, 2200000]
- x range=[10000000, 19999999] y range=[7000001, 24000000]
- x range=[100000000, 199999999] y range=[80000001, 260000000]
- x range=[1000000000, 1999999999] y range=[900000001, 2800000000]
The other missing piece is the function foundRoot(). This is used in formula (A), which can be simplified in the form x + f(x) = y, with unknown x. We need a function to find the root x.
java 代码
- public long findRoot(long y)
- {
- // find a root for x + f(x) = y, where f is the number of one's function
- // in the above.
- // we need a x such that x + f(x)>=y, the largest x.
- // Note that x + f(x) is a mononically increasing function.
- long x0 = 0;
- long x1 = y;
- long x;
- while (x1 - x0 > 1)
- {
- x = x0 + (x1 - x0) / 2;
- long func = numOfOnes(x) + x;
- if (func == y) return x;
- if (func < y)
- {
- x0 = x;
- }
- else
- {
- x1 = x;
- }
- }
- if (x0 + numOfOnes(x0) == y) return x0;
- else return x1;
- }
Two other small functions are:
java 代码
- private static int numOfDigits(long x)
- {
- int i = 0;
- while (x > 0)
- {
- x /= 10;
- i++;
- }
- return i;
- }
which computes the number of 1's in x, and
java 代码
- private static long power(long base, int power)
- {
- long ret = 1;
- for (int i=1; i<=power; i++) ret *= base;
- return ret;
- }
which computes the power for the performance reason. With all of these in places, the only thing left is a "conductor" method:
java 代码
- public void countDigitOne()
- {
- long begin = System.currentTimeMillis();
- long loop = 10000000000L;
- int iterationTimes = 1;
- while (loop > 0 && iterationTimes < ITERATION_LIMIT)
- {
- long func = numOfOnes(loop);
- if (func == loop)
- {
- System.out.println("-----> found a fixed point: x=" + loop);
- // now skip this one and keep going for the next one.
- loop--;
- }
- else
- {
- if (func < loop) // we force this to go to the left.
- {
- loop = func;
- }
- else // func > loop
- {
- func = inverseFunc(loop);
- if (func < loop && numOfOnes(func) >= loop)
- {
- loop = func;
- }
- else
- {
- loop --; // if we can't find one, just decrement it.
- }
- }
- }
- iterationTimes++;
- }
- System.out.println("It takes " + (System.currentTimeMillis() - begin) + " milli");
- System.out.println("It takes " + iterationTimes + " iterations");
- }
The result is:
-----> found a fixed point: x=1111111110
-----> found a fixed point: x=535200001
-----> found a fixed point: x=535200000
-----> found a fixed point: x=535199990
-----> found a fixed point: x=535199989
-----> found a fixed point: x=535199988
-----> found a fixed point: x=535199987
-----> found a fixed point: x=535199986
-----> found a fixed point: x=535199985
-----> found a fixed point: x=535199984
-----> found a fixed point: x=535199983
-----> found a fixed point: x=535199982
-----> found a fixed point: x=535199981
-----> found a fixed point: x=535000001
-----> found a fixed point: x=535000000
-----> found a fixed point: x=513199998
-----> found a fixed point: x=502600001
-----> found a fixed point: x=502600000
-----> found a fixed point: x=501599990
-----> found a fixed point: x=501599989
-----> found a fixed point: x=501599988
-----> found a fixed point: x=501599987
-----> found a fixed point: x=501599986
-----> found a fixed point: x=501599985
-----> found a fixed point: x=501599984
-----> found a fixed point: x=501599983
-----> found a fixed point: x=501599982
-----> found a fixed point: x=501599981
-----> found a fixed point: x=500200001
-----> found a fixed point: x=500200000
-----> found a fixed point: x=500199990
-----> found a fixed point: x=500199989
-----> found a fixed point: x=500199988
-----> found a fixed point: x=500199987
-----> found a fixed point: x=500199986
-----> found a fixed point: x=500199985
-----> found a fixed point: x=500199984
-----> found a fixed point: x=500199983
-----> found a fixed point: x=500199982
-----> found a fixed point: x=500199981
-----> found a fixed point: x=500000001
-----> found a fixed point: x=500000000
-----> found a fixed point: x=117463825
-----> found a fixed point: x=35200001
-----> found a fixed point: x=35200000
-----> found a fixed point: x=35199990
-----> found a fixed point: x=35199989
-----> found a fixed point: x=35199988
-----> found a fixed point: x=35199987
-----> found a fixed point: x=35199986
-----> found a fixed point: x=35199985
-----> found a fixed point: x=35199984
-----> found a fixed point: x=35199983
-----> found a fixed point: x=35199982
-----> found a fixed point: x=35199981
-----> found a fixed point: x=35000001
-----> found a fixed point: x=35000000
-----> found a fixed point: x=13199998
-----> found a fixed point: x=2600001
-----> found a fixed point: x=2600000
-----> found a fixed point: x=1599990
-----> found a fixed point: x=1599989
-----> found a fixed point: x=1599988
-----> found a fixed point: x=1599987
-----> found a fixed point: x=1599986
-----> found a fixed point: x=1599985
-----> found a fixed point: x=1599984
-----> found a fixed point: x=1599983
-----> found a fixed point: x=1599982
-----> found a fixed point: x=1599981
-----> found a fixed point: x=200001
-----> found a fixed point: x=200000
-----> found a fixed point: x=199990
-----> found a fixed point: x=199989
-----> found a fixed point: x=199988
-----> found a fixed point: x=199987
-----> found a fixed point: x=199986
-----> found a fixed point: x=199985
-----> found a fixed point: x=199984
-----> found a fixed point: x=199983
-----> found a fixed point: x=199982
-----> found a fixed point: x=199981
-----> found a fixed point: x=1
It takes 62 milli
It takes 1139 iterations.
This is a typical fixed point problem, start from some arbitrary number and keep acting f on it. Several outputs of the series are:
1. It goes to infinity.
2. It goes to some fixed point.
3. It keeps bouncing back and forth(going nowhere).
Two types of fixed points are attractors and opposite attractors. Attractors are attracting nearby points, i.e., if we start from some point "close" enough to the attractor, the series will converge to the attractor. Opposite attractor is just the opposite, the series will go away from the opposite attractor.
发表评论
-
Revisit 一道应聘智力题的编程求解, Einstein puzzle
2010-03-09 00:36 1366Another brain teaser, titled 一道 ... -
Another Google question - drop glassballs from a building 5
2007-05-13 04:01 1030Here are some results are the t ... -
Another Google question - drop glassballs from a building 4
2007-05-13 03:42 1480The test cases are divided into ... -
Another Google question - drop glassballs from a building 3
2007-05-13 03:33 1039The next step is to find the ac ... -
Another Google question - drop glassballs from a building 2
2007-05-13 03:02 1055Here is the code following the ... -
Another Google question - drop glassballs from a building 1
2007-05-12 04:43 1159Here is the question: 原题: ... -
Given n coins and a pan balance,find the only counterfeit 4
2007-02-27 05:54 1087The Utils class is composed of ... -
Given n coins and a pan balance,find the only counterfeit 3
2007-02-27 05:50 1441In the 1-ball case, if the stat ... -
Given n coins and a pan balance,find the only counterfeit 2
2007-02-27 05:29 1054Now it comes to the Scale class ... -
Given n coins and a pan balance, find the only counterfeit 1
2007-02-27 04:49 1295The problem is: There is one ... -
A Google's Interview Question - GLAT #20 series 4
2007-02-08 02:36 1041The entire class is as follows: ... -
A Google's Interview Question - GLAT #20 series 2
2007-02-08 02:24 1010Now, we can deduct the recursio ... -
A Google's Interview Question - GLAT #20 series 1
2007-02-08 02:22 1106Question: Consider a function ...
评论