- 浏览: 80159 次
文章分类
最新评论
-
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 1451Another brain teaser, titled 一道 ... -
Another Google question - drop glassballs from a building 5
2007-05-13 04:01 1080Here are some results are the t ... -
Another Google question - drop glassballs from a building 4
2007-05-13 03:42 1539The test cases are divided into ... -
Another Google question - drop glassballs from a building 3
2007-05-13 03:33 1096The next step is to find the ac ... -
Another Google question - drop glassballs from a building 2
2007-05-13 03:02 1110Here is the code following the ... -
Another Google question - drop glassballs from a building 1
2007-05-12 04:43 1209Here is the question: 原题: ... -
Given n coins and a pan balance,find the only counterfeit 4
2007-02-27 05:54 1120The Utils class is composed of ... -
Given n coins and a pan balance,find the only counterfeit 3
2007-02-27 05:50 1507In the 1-ball case, if the stat ... -
Given n coins and a pan balance,find the only counterfeit 2
2007-02-27 05:29 1110Now it comes to the Scale class ... -
Given n coins and a pan balance, find the only counterfeit 1
2007-02-27 04:49 1340The problem is: There is one ... -
A Google's Interview Question - GLAT #20 series 4
2007-02-08 02:36 1107The entire class is as follows: ... -
A Google's Interview Question - GLAT #20 series 2
2007-02-08 02:24 1076Now, we can deduct the recursio ... -
A Google's Interview Question - GLAT #20 series 1
2007-02-08 02:22 1163Question: Consider a function ...
相关推荐
根据给定的信息,我们可以推断出这是一篇关于Google招聘测试的文章,具体是关于Google实验室能力倾向测试(GLAT)的介绍与解析。虽然提供的内容片段并不完整,但基于现有信息,我们可以对提及的每一道题目进行详细...
- **背景介绍**:2004年10月,Google在几本专业杂志上发布了名为“Google实验室能力倾向测试”(GLAT)的一份特殊招聘试题。这份试题在全球范围内引起了广泛的关注,不仅因为它出自全球领先的科技公司之一Google,还...
依巴谷输入星表集(第2版)是欧洲空间局(ESA)为依巴谷天体测量卫星工作使用的输入星表,该卫星在轨运行四年,从1989年11月到1993年3月间返回了高质量的科学数据。该数据集于1993年对外释放。 在国家科技基础平台...
下载后解开压缩包,里面有五个文件:glut.h,glut.lib,glut32.lib,glut.dll,glut32.dll。 然后把.h文件放到VC的include路径下的GL文件夹下,VC++6.0版本对应的文件夹是安装路径下VC98\Include\GL。...
idl代码与Matlab 辉光 Global airglOW模型,可以从Fortran 2003编译器中独立且轻松地进行访问。 可选提供脚本语言,包括: Python≥3.6 Matlab的 GNU八度≥4.2 IDL ...glat , glon , Q , Echar , Nb
2. **纬度和经度处理**:`input_glat`和`input_glong`函数分别用于获取用户输入的纬度和经度,以度分秒的形式。纬度范围限制在0°至60°之间,经度可以是负值,表示西经。 3. **时间计算**:`t_century`函数将从...
接收 xyz 格式的点云,然后将其转换为具有纬度向量、经度向量、glat/glon 网格(使用 meshgrid)和 az(高度)矩阵的 MATLAB 样式的网格。 然后将这些保存到指定的输出 .mat 文件中。
它的构建允许任何人检查志愿者为数据库中或任何 GLON、GLAT 位置的任何主题(图像)创建的分类。 对于每个图像,您都可以看到原始志愿者绘图、聚类结果和该地区 SIMBAD 上的对象(这一点还没有完全完成)。 例如...