Posted on 2006-12-05 22:30
TPC2005 阅读(235)
评论(0) 编辑 收藏 引用 所属分类:
UVA 题目讨论
Pro_100 解题思想：
根据题意，输入22,得到的数列：22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
这样我们在计算22的cycle length时，顺便得到了这一数列成员的所有cycle length
22的cycle length为16，11的cycle length为15，依次类推。
把所有计算过cycle length的数保存，以后就不必重复计算。
具体实现方法，建立长度为100000的数据数组，以及长度为500左右的临时数组。
通过他人的程序，事先可以知道的是：1-1000000的最长cycle length为525，
因而数据数组可定义为2字节的short int，临时数组500左右足矣。
例如计算22，可得到22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1的cycle length
然后再计算9，可得到9 28 14 7 22，同时写入临时数组，
当计算到22时查数组可得22的cycle length为16，
那么7的cycle length即为22的cycle length+1=17，依次逆向类推。
9 28 14的cycle length分别为20 19 18，保存到数据数组。
p.s.细节问题：
1.输入的i,j,可能存在i>j的情况，特殊处理。特别指出，先原样输出i,j，再交换。
2.在1-1000000中存在"最大飞行高度"超过2^32的数(若不清楚"最大飞行高度"请看附件介绍)，但是题目保证中间过程没有超过2^32的数，所以不必定义64位整型。
源代码下载
3N+1相关资料下载
1
/**/
/*
***********************************
*/
2
/**/
/*
Pro_100 The 3n + 1 problem
*/
3
/**/
/*
CPU Time 0:00.068 Memory Minimum
*/
4
/**/
/*
Ranklist 288 Programmed By Wingy
*/
5
/**/
/*
***********************************
*/
6
7
#define
MAX 1000000
8
#include
<
stdio.h
>
9
10
int
main()
11
{
12
short
cir[MAX]
=
{
0
,
1
,
2
}
,len,j,tp,lst;
13
unsigned n,i,tm,stk[
500
]
=
{
0
}
,x,y;
14
while
(scanf(
"
%u%u
"
,
&
x,
&
y)
!=
EOF)
15
{
16
lst
=
0
;
17
printf(
"
%u %u
"
,x,y);
18
if
(x
>
y) tm
=
x,x
=
y,y
=
tm;
19
for
(i
=
x;i
<=
y;i
++
)
20
{
21
if
(cir[i]
==
0
)
22
{
23
n
=
i;
24
len
=
0
;
25
while
(
1
)
26
{
27
stk[len
++
]
=
n;
28
if
(n
&
1
) n
=
1
+
n
+
(n
<<
1
);
29
else
n
>>=
1
;
30
if
(n
<
MAX
&&
cir[n])
break
;
31
}
32
tp
=
len
+
cir[n];
33
for
(j
=
0
;j
<
len;j
++
)
34
{
35
tm
=
stk[j];
36
if
(tm
<
MAX) cir[tm]
=
tp;
37
tp
--
;
38
}
39
}
40
if
(cir[i]
>
lst) lst
=
cir[i];
41
}
42
printf(
"
%d\n
"
,lst);
43
}
44
return
0
;
45
}