间隔排列
【题意描述】
有2N个木块，每个木块标上1到N的自然数中的一个，每个数字会出现在两个木块上。把这些木块排成一排，要求是：标号为i的两个木块之间要间隔i 个其它木块。比如说N=3的情况，下面就是一个可行的排列：3，1，2，1，3，2。编程实现，对给定的N，求出一个可行排列。
【输入格式】
输入只有一行，给出一个数字N,N<=40
【输出格式】
输出一个满足题意的排列，任两个数字间用一个空格隔开，无解则输出”No Solution”
【样例输入】
3
【样例输出】
3 1 2 1 3 2
【问题解析】
对于这个题我们没有什么好的构造的方法，只能进行搜索，但在搜索有两个非常重要的技巧
1：在搜索时，应该先搜索大数字，再搜索小数字，因为大数字它对位置的要求较小数字更为严格，按搜索的原则应该先搜索这样的对象。
2：当程序写完试运行时，我们发现N mod 4=1或2时，发现运行的时间较长，
而其它情况下程序很快就到可行解，我们就应该警觉到N mod4=1或2时，不
存在可行解，下面我们证明N mod 4=1或2时，问题无解。
设问题的一个可行解为a1,a2,……,a n，其中a i为标号为i的数字的位置，
这些数字它们对应数字的位置应该为a 1+1+1,a 2+2+1,……,a n +n+1.这2N 个整数a 1,a 2,……,a n , a 1+1+1,a 2+2+1,……,a n +n+1正是整数1,2,3，……,2N ，因而
a 1+a 2+…+a n +(a 1+1+1)+(a 2+2+1)+…+(a n +n+1)=
∑=n
x k
21
2(a 1+a 2+an)+n(n+1)/2+n=2n(2n+1)/2
2(a 1+a 2+…+a n )=(3n 2-n)/2
4(a 1+a 2+…+a n )=n(3n-1)
可见n(3n-1)应该为4的倍数，当n mod 4=0,1,2,3时，n(3n-1) mod 4分别为0,2,2,0，故n mod 4=1或2时，问题无解
【性能分析】
时间复杂度：不好分析
编程复杂度：简单
【总结】
1：确定好搜索对象至关重要
2：用数学思想排除无解的情况，避免无谓的搜索
【源程序】
var
t:array[-1..100] of Longint;
tot,n:Longint;
procedure find(dep:Longint);
var
j:Longint;
begin
if dep=0 then
begin
for j:=1 to n*2 do
if j<>n*2 then
write(t[j],' ')
else
writeln(t[j]);
halt;
end;
for j:=1 to 2*n-dep-1 do
if (t[j]=0) and (t[j+dep+1]=0) then            begin
t[j]:=dep;
t[j+dep+1]:=dep;
find(dep-1);
t[j]:=0;
t[j+dep+1]:=0;
end;
end;
begin
fillchar(t,sizeof(t),0);
字符串长度排序readln(n);
if (n mod 4=1) or (n mod 4=2) then            writeln(‘No Solution’)
else
find(n);

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。