排序三种石头的阵列 [英] sorting an array of three kinds of stones
问题描述
有三种宝石：红色，绿色和蓝色。
数组中的每个单元格都包含一块石头。
数组需要进行排序，以便所有红色的
宝石将首先出现，然后是蓝色宝石和
然后是绿色宝石。
有N个宝石，数量为数组中的单元格。
开关（i，j） - 在第j个地方切换石头，在第j个地方用
切换一个地方。
颜色（i） - 显示第i个地方的石头颜色。
这些功能只能使用N次。 br />
请帮助我，我试图找到一个合适的解决方案但是
没有成功。
There are three kinds of stones: red,green and blue.
Each cell of the array contains one stone.
The array needs to be sorted so that all the red
stones will come first, then the blue ones and
then all the green ones.
There are N stones, as the number of cells in the array.
switch(i,j)- switch the stone in the i-th place with the
one in the j-th place.
color(i)- reveals the color of the stone in the i-th place.
These functions can be used only N times.
please help me,I tried to reach a proper solution but with
no success.
推荐答案
meital写道：
有三种宝石：红色，绿色和蓝色。
阵列的每个单元格都包含一块石头。阵列需要进行排序，以便所有的红色石头先出现，然后出现蓝色的石头所有绿色的。
有N个宝石，就像阵列中的细胞数量一样。
开关（i，j） - 在第i个地方切换石头
一个在第j个地方。
颜色（i） - 在第i个地方显示石头的颜色。
这些功能只能使用N次。
请帮助我，我试图找到一个合适的解决方案但是没有成功。
There are three kinds of stones: red,green and blue.
Each cell of the array contains one stone.
The array needs to be sorted so that all the red
stones will come first, then the blue ones and
then all the green ones.
There are N stones, as the number of cells in the array.
switch(i,j)- switch the stone in the i-th place with the
one in the j-th place.
color(i)- reveals the color of the stone in the i-th place.
These functions can be used only N times.
please help me,I tried to reach a proper solution but with
no success.
如果做家庭作业的话在C中完成，然后
你的导师给了你一个技巧问题。
正确答案不是试图实施解决方案，而是通过解释原因来证明你对C的了解
无法解决问题。提示：关于你应该使用的功能的名称有什么奇怪的吗？
这个技巧问题有很长的传统，可以追溯到/>
至少与苏格拉底相当，甚至可能更远。
是对驾驶执照的检查，其中提出了
问题你正在接近一个四向交叉路口
每英里四十英里卡车从
右边拉出来的时间;你做了什么？正确的答案不是刹车时的步骤
。或向左转向或向左转向。但是当我接近十字路口时，我不会以每小时四十英里的速度行驶
。
你的导师显然是这种狂热者
教学技术;也许他也是一位禅宗大师。
你要羡慕你接受的教育质量 - 而且，似乎忽略了......
-
Er ******** *@sun.com
我的导师不是给了我
的问题。这个问题在我上次的采访中给了我
，所以我认为
必须有一个合适的解决方案。
我原本应该给出答案，使用C，
，但也可以提供书面算法。
It wasn''t my instructor who gave me the
question. This question was given to me
in my last interview, so I figured that
there must be an appropriate solution.
I was supposed to give the answer, using C,
but it was also possible to give a written algorithm.
[这个谜题更适合comp.programming和/或
rec.puzzles;相应地设置了xposted和followup。]
2004年10月28日星期四，meital写道：
[This puzzle is better suited to comp.programming and/or
rec.puzzles; xposted and followups set accordingly.]
On Thu, 28 Oct 2004, meital wrote:
有三种宝石：红色，绿色和蓝色。
阵列中的每个单元格都包含一块石头。
阵列需要进行排序，以便所有红色石头先出现，然后出现蓝色石头和
然后是所有绿色的。
有N个宝石，就像阵列中的细胞数量一样。
开关（i，j） - 在第i个地方切换石头
一个在第j个地方。
颜色（i） - 在第i个地方显示石头的颜色。
这些功能只能使用N次。
There are three kinds of stones: red,green and blue.
Each cell of the array contains one stone.
The array needs to be sorted so that all the red
stones will come first, then the blue ones and
then all the green ones.
There are N stones, as the number of cells in the array.
switch(i,j)- switch the stone in the i-th place with the
one in the j-th place.
color(i)- reveals the color of the stone in the i-th place.
These functions can be used only N times.
你的意思是，你可以称''颜色''N次，然后叫''切换''
N次？然后问题是微不足道的（虽然完整的工作
解决方案可能需要一些考虑）。
如果你的意思是你只能进行N个函数调用，
''color''和''switch''组合在一起，然后我认为没有
解决方案可能。
红利谜题：解决方案所需的临时
存储的最小位数是多少？如果你可以调用每个函数
N次？
在最小的情况下，您需要多少次切换电话？
最快的
解决方案的最小期望值是多少？
（我确定所有三个谜题已经在某个地方解决了
TAOCP中的
...;）
-Arthur
You mean, you can call ''color'' N times, and then call ''switch''
N times? Then the problem is trivial (though a complete working
solution may require some thought).
If you mean that you can only make N function calls in total,
to both ''color'' and ''switch'' combined, then I think there is no
solution possible.
Bonus puzzle: What is the minimum number of bits of temporary
storage you need for a solution, if you can call each function
N times?
How many calls to ''switch'' do you need, in the minimum case?
What is the minimum big-Oh expecting running time of the fastest
solution?
(I''m sure all three puzzles have been solved already somewhere
in TAOCP...;)
-Arthur
这篇关于排序三种石头的阵列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
