一道数列的题 (NOIP)，help

ShiChao · 发表于 2004-6-19 22:32:39

[code:1]
program t1;
var n:integer;
function count(n:integer):integer;
  begin
if n=1 then count:=0 else
   if n mod 2=0 then count:=count(n div 2)+1 else
   count:=count(n*3+1)+1;
  end;
begin
  readln(n);
  writeln(count(n));
end.

输入99
输出:_______
[/code:1]

抽象为
[code:1]
         0                (n == 1)
f(n) = f(n/2)+1       (偶)
         f(3n + 1) + 1 (奇)

f(99) = ?
[/code:1]

lanche · 发表于 2004-6-19 22:37:02

用pascal编译运行不就知道结果了么?

lanche · 发表于 2004-6-19 22:50:16

没有pascal编译器，我翻译成c运行了一下，结果是 25 。

ShiChao · 发表于 2004-6-19 22:52:57

.......
这是读程序题

lanche · 发表于 2004-6-19 22:59:26

那就用笔在纸上算，应该可以在半分钟以内完成。

ShiChao · 发表于 2004-6-19 23:15:28

果然可以直接算出来

但是这到题有没有更好的方法
f(99) 需要递归25次，每次都加1
hehe

lanche · 发表于 2004-6-19 23:28:22

应该可以将公式变换以便更快地算出答案，但我还没看出来，可能是数学太差的缘故^_^

ShiChao · 发表于 2004-6-19 23:38:26

我也这样想，但是只推出了
对于n = 2^k (k数与自然数)
f ( n ) = k

用上这个规律，只是最后少了两三步地归，还是没有用

application · 发表于 2004-6-20 01:05:37

很简单的,一看就可以看出来了

ShiChao · 发表于 2004-6-20 18:23:41

看了，没看出

		自动登录	找回密码
密码			注册