dazuiniu's blog

cat /dev/dazuiniu/random

100 – the 3*n + 1 problem

View Comments

任何一个自然数如果它是奇数,那么转化为 3n+1,如果是偶数,那么变成它自己的一半,这个过程直到它成为 1 为止。这个就是著名的角谷猜想。而这道题目不是让我们去证明它,而是计算一个数需要多少次才能变成 1。

这个题目需要注意的是我们不能想当然的认为题目中给定的 i 小于 j。只要注意了这个,应该问题不大。:-)

Written by dazuiniu

June 25th, 2010 at 7:14 pm

Posted in UVa

Tagged with

  • http://glacjay.is-a-geek.org/blog/ GlacJAY

    i 和 j 在哪儿?

  • dazuiniu

    哦。说的不是很清楚。
    对于一个具体的自然数,我们可以知道需要多少此变成1,题目中把这个次数叫做cycle的长度,然后题目给的输入是两个数( i 和 j ),需要我们求:对于 i 和 j 之间的数,哪个数的cycle的长度最长,最长的长度是多少。
    有点绕。
    其实看具体的题目更清楚,URL在这里: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=36

    天啊。URL原来这么长。。。

blog comments powered by Disqus