Posted on 2008-08-12 21:10
Hero 阅读(126)
评论(0) 编辑 收藏 引用 所属分类:
代码如诗－－ACM
/*
ID: wangzha4
LANG: C++
TASK: shuttle
*/
/*
Test 1: TEST OK [0.000 secs, 2716 KB]
Test 2: TEST OK [0.011 secs, 2712 KB]
Test 3: TEST OK [0.000 secs, 2712 KB]
Test 4: TEST OK [0.000 secs, 2712 KB]
Test 5: TEST OK [0.022 secs, 2716 KB]
Test 6: TEST OK [0.000 secs, 2716 KB]
Test 7: TEST OK [0.000 secs, 2712 KB]
Test 8: TEST OK [0.000 secs, 2716 KB]
Test 9: TEST OK [0.022 secs, 2716 KB]
Test 10: TEST OK [0.000 secs, 2712 KB]
*/
//
*******************************************************
//
题目用构造法解决--第一次了解这种方法
//
以“空白”的位置为关心点
//
4 3 5 6 4 2 1 3 5 7 6 4 2 3 5 4
//
-1 +2 +1 -2 -2 -1 +2 +2 +2 -1 -2 -2 -2 +1 +2 -1
//
第一个“-1”之后有 1 -- 2
//
第二个“1”之后有 2 -- -2
//
第三个“-1”之后有 3 -- 2 -- 达到inn==3的最高点然后开始衰减
//
第四个“-1”之后有 2 -- -2
//
第五个“1”之后有 1 -- 2
//
第六个“-1”之后什么都没有
//
细节注意 :
//
1. 不能定义stime,那是标准的函数，定义sntime
//
2. int sntime ；
/*
******************************************************
另一种解法 : -- 以每次移动的棋子个数为参考点
1． 无论移动什么棋子，以每一次换颜色为界，每次移动数目为1,2,3……n,n,n……,3,2,1
2． 第一次移动白色棋子，最后一次也是的。
例如当n=4时
1． 将一颗白子右移
2． 将两颗黑子依次左移
3． 将三颗白子依次右移
4． 将四颗黑子依次左移
5． 将四颗白子依次右移
6． 将四颗黑子依次左移
……
2*n+1 将最后一颗白子右移
******************************************************
*/
#include
<
cstdio
>
#include
<
iostream
>
#include
<
cstring
>
#include
<
ctime
>
using
namespace
std ;
#define
NDEBUG
int
sntime, entime ;
const
int
size
=
10000
;
int
inn ;
int
count ;
//
记录输出的第几个数
int
posi ;
//
记录空位置
void
printout()
{
printf(
"
%d
"
, posi ) ;
count
++
;
if
(
0
==
count
%
20
) printf(
"
\n
"
) ;
else
printf(
"
"
) ;
}
int
main()
{
freopen(
"
shuttle.in
"
,
"
r
"
, stdin ) ;
freopen(
"
shuttle.out
"
,
"
w
"
,stdout ) ;
while
( cin
>>
inn )
{
sntime
=
clock() ;
posi
=
inn
+
1
;
//
空格的位置
int
change
=
-
1
;
count
=
0
;
for
(
int
i
=
1
; i
<=
inn; i
++
)
{
posi
=
posi
+
change ;
printout() ;
for
(
int
j
=
1
; j
<=
i; j
++
)
{
posi
+=
change
*
(
-
2
) ;
printout() ;
}
change
=
-
change ;
}
change
=
-
change ;
for
(
int
i
=
inn
-
1
; i
>=
1
; i
--
)
{
posi
+=
change ;
printout() ;
for
(
int
j
=
i; j
>=
1
; j
--
)
{
posi
+=
change
*
2
;
printout() ;
}
change
=
-
change ;
}
printf(
"
%d\n
"
, posi
+
change ) ;
entime
=
clock() ;
#ifndef NDEBUG
printf(
"
runtime == %ld\n
"
, entime
-
sntime ) ;
#endif
}
//
while
return
0
;
}