Posted on 2008-08-12 21:10
Hero 閱讀(139)
評論(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
?;
}