主题:我儿子的一道题不会做!请高手指点一下!
1980
[专家分:0] 发布于 2006-11-03 09:29:00
设有一个包含N个元素的一维数组A,存放的元素为0~N-1(1< N < =10)之间的整数,且
A[i]≠A[j](i≠j),例如当 N=6时,有A=(4,3,0,5,1,2),对A数组进行编码,编码规则如下:
A[0]的编码为0,
A[i]的编码为:在A[0],A[1],A[2],……,A[i-1]中比A[i]的值小的数的个数,(I=1,2,3,……,N-1)
所以上面数组A的编码为B=(0,0,0,3,1,2)。现在要解决的问题是,当给出元素个数N ( N〈=9 〉和数组A的编码B后,根据B的值求出数组A中的原数据。
例如: 输入6
0 0 0 3 1 2
输出
4 3 0 5 1 2
回复列表 (共15个回复)
11 楼
Matodied [专家分:7560] 发布于 2007-05-07 18:50:00
[quote][quote]楼上的面孔很生啊
是跑来捣乱的吗?
[/quote]
很久没来,看来大家都认不到了,以后争取来勤点,至少也混个面熟。
[/quote]
我这道题也不会做,请Moz讲一下你的算法,我们13号就考试了,快点!!!!!
相信你应该能帮我的,不然我没考好就找你!
12 楼
moz [专家分:37620] 发布于 2007-05-07 19:25:00
找我也没用啊,你考不好我更高兴呢,还有佑慧她妹妹呢,她考好了请我吃饭就行了.
13 楼
Matodied [专家分:7560] 发布于 2007-05-07 20:39:00
moz,求求你就讲一下你的算法嘛!不然万一这题在我的考试里出现了怎么办?
14 楼
moz [专家分:37620] 发布于 2007-05-07 21:38:00
那倒用不着你求,本来就准备给你说的,刚才有点事出去了,没来得及张口.
你要是在我发代码的时候问我,兴许我还能长篇大论的.
现在就只是简单的说说思路,具体理论和实现过程以及代码,就靠你自己去努力了.
题目说的是N个不重复的自然数,其实也就是一个数列,
以结果B列,倒求原始A列.
我告诉你一个方法:
1. 找最后一个0,(其实可以简单的看成从右边找起第一个0) 点1
我称这个点为点1 (我不太懂什么顶点枝叶什么的)
意思是再没有比它小的数了,这个位置放最小的数, 0
2. 从点1往右边找最后一个1, 这个位置放次小的数, 1 点2
3. (同上找最后的2,最后的3,最后的4)
4. 某个数找不到了,或者已经到了右边尽头了,返回上一个点(假如是点2),
从点2往点1方向找第二个1, 这个位置放下一个数,依次类推
结合实例,像题目所说的6个数 B列: 0 0 0 3 1 2
B列 A列
0 0 0 3 1 2 X X X X X X
\
这是最后一个0,这里应该是0 -> X X 0 X X X
先找下一个点1,那里应该放1 -> X X 0 X 1 X
再找下一个点2,那里应该放2 -> X X 0 X 1 2
然后到了尽头,往回最后的1之间找第二个2,没找到,继续
往回最后一个0之间找第二个1,没找到,继续
往回找第二个0,这时放下一个数-> X 3 0 X 1 2
再往右边,在空位里找1,没找到,再继续往左找下一个0
-> 4 3 0 X 1 2
处理完0,再回头找下一个最小数-> 4 3 0 5 1 2
直到处理完毕为止.
15 楼
美味的汽水 [专家分:70] 发布于 2007-05-10 20:55:00
没读懂题
我来回复