主题：请高手指点一下!竞赛题目
yubinsf
[专家分：0] 发布于 2006-10-09 14:47:00
有2N个盒子，盒子上从1到N自然数进行标号，每个数字会出现在两个盒子上。下面将盒子排成一排，要求是：标号1的两个盒子之间隔1个盒子；标号2的两个盒子之间隔2隔盒子……标号N的两个盒子之间隔N个盒子。如N＝3，可能的排列是2 3 1 2 1 3。编程实现，对给定的N（3≤N≤40），求出一种可行排列。如没有可行排列，输出“No answer”。
回复列表 （共9个回复）
沙发
老大徒伤悲 [专家分：29120] 发布于 2006-10-11 20:05:00
有意思的题目，我估计使用递归方法。
但是目前我没有具体思路。
共同关注。
板凳
maxumi [专家分：2200] 发布于 2006-10-12 09:58:00
当n mod 4 = 0或n mod 4 = 1时, 无解.
数据范围是40, 不是很BT(这题有另一个版本n<=15000, 寒), 回溯就可以了.
3 楼
moz [专家分：37620] 发布于 2006-10-15 00:23:00
这题我想过,
但我只懂单纯的穷举及抽选,
时间消耗很大,
估计需要数学方法及理论.我不懂.
4 楼
moz [专家分：37620] 发布于 2006-10-15 00:23:00
[quote]当n mod 4 = 1或n mod 4 = 2时, 无解.[/quote]
我曾经以为然,但事实好像并不如是.
5 楼
maxumi [专家分：2200] 发布于 2006-10-16 15:09:00
[quote][quote]当n mod 4 = 0或n mod 4 = 1时, 无解.[/quote]
我曾经以为然,但事实并不如是.
[/quote]
orz......写错了, 是n mod 4 = 1或n mod 4 = 2.
6 楼
yubinsf [专家分：0] 发布于 2006-10-20 10:01:00
各位高手,竟然没有一个会做这道题的呀!
7 楼
moz [专家分：37620] 发布于 2006-10-20 11:49:00
我不是高手,我忍你.
8 楼
mickeyice [专家分：200] 发布于 2006-10-23 23:16:00
单纯只要 一种可行方案 应该是回溯 我去~~~~
复习复习
9 楼
moz [专家分：37620] 发布于 2006-10-25 12:24:00
1.我假设 N mod 4 = 1 和 N mod 4 = 2 时无解,
因为我无法验证,时间太长了得不到结果,
就算 N=13, 我的电脑验证时间超过一个小时
2.36之后,开始有部份数的时间也太长了,无法计算,
例如36,39,47,48,51,56,59,60等等,超过15秒,我不够耐心,
相反的,其他数的时间少于一秒.
3.字符串程序:
declare function a312132% (n%)
defint a-z
dim shared i2, s$
cls
for i = 3 to 35
if i mod 4 = 1 then i = i + 2
i2 = i * 2
s$ = space$(i2)
if a312132(i) = 0 then
print i; "no answer"
else
for j = 1 to i2
print asc(mid$(s$, j, 1)) - 48;
next
print
endif
next
function a312132 (n)
do
x = instr(x + 1, s$, " ")
if x = 0 then exit do
y = x + n + 1
if y > i2 then exit do
if mid$(s$, y, 1) = " " then
mid$(s$, x, 1) = chr$(48 + n)
mid$(s$, y, 1) = chr$(48 + n)
if n <= 1 or a312132(n - 1) then
a312132 = -1
exit do
end if
mid$(s$, x, 1) = " "
mid$(s$, y, 1) = " "
end if
loop
'locate , 1: print s$;
if inkey$ = chr$(27) then system
end function
4.数组程序:
declare function a312132% (n%)
defint a-z
dim shared i2, s$
cls
for i = 3 to 35
if i mod 4 = 1 then i = i + 2
i2 = i * 2
redim shared s(i2)
if a312132(i) = 0 then
print i; "no answer"
else
for j = 1 to i2
print s(j);
next
print
endif
next
function a312132 (n)
do
for x = x + 1 to i2
if s(x) = 0 then exit for
next
if x > i2 then exit do
y = x + n + 1
if y > i2 then exit do
if s(y) = 0 then
s(x) = n
s(y) = n
if n <= 1 or a312132(n - 1) then
a312132 = -1
exit do
end if
s(x) = 0
s(y) = 0
end if
loop
if inkey$ = chr$(27) then system
end function
5.也许其中还有什么玄机而我还没有参透,有识之士请指点一二.
用递归的缺点就是堆栈溢出,其实有办法用数组代替解决的.
我来回复
您所在位置：