📄 100.html
字号:
<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML 2.0//EN"><!--Converted with LaTeX2HTML 96.1 (Feb 5, 1996) by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds --><HTML><HEAD><TITLE>The 3n + 1 problem</TITLE><META NAME="description" CONTENT="The 3n + 1 problem"><META NAME="keywords" CONTENT="htmlatex"><META NAME="resource-type" CONTENT="document"><META NAME="distribution" CONTENT="global"><LINK REL=STYLESHEET HREF="htmlatex.css"></HEAD><BODY LANG="EN" BGCOLOR=#FFFFFF> <H1><BR CLEAR=ALL><CENTER><TABLE BGCOLOR=#0060F0><TR><TD><B><FONT SIZE=5 COLOR=#C0FFFF> <A NAME="SECTION0001000000000000000000">The 3<I>n</I> + 1 problem</A></FONT> </B></TABLE></CENTER></H1><P><H2><FONT COLOR=#0070E8><A NAME="SECTION0001001000000000000000">Background</A></FONT></H2><P>Problems in Computer Science are often classified as belonging to acertain class of problems (e.g., NP, Unsolvable, Recursive). In thisproblem you will be analyzing a property of an algorithm whoseclassification is not known for all possible inputs.<P><H2><FONT COLOR=#0070E8><A NAME="SECTION0001002000000000000000">The Problem</A></FONT></H2><P>Consider the following algorithm:<PRE><TT> 1. input <I>n</I><P> 2. print <I>n</I><P> 3. if <I>n</I> = 1 then STOP<P> 4. if <I>n</I> is odd then <IMG WIDTH=95 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline44" SRC="100img1.gif" > <P> 5. else <IMG WIDTH=74 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline46" SRC="100img2.gif" > <P> 6. GOTO 2<P></TT></PRE><P>Given the input 22, the following sequence of numbers will be printed22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1<P>It is conjectured that the algorithm above will terminate (when a 1 isprinted) for any integralinput value. Despite the simplicity of the algorithm,it is unknown whether this conjecture is true. It has been verified,however, for all integers <I>n</I> such that 0 < <I>n</I> < 1,000,000 (and, in fact,for many more numbers than this.)<P>Given an input <I>n</I>, it is possible to determinethe number of numbers printed before the 1 is printed. For a given <I>n</I> this iscalled the <EM>cycle-length</EM> of <I>n</I>. In the example above, the cyclelength of 22 is 16.<P>For any two numbers <I>i</I> and <I>j</I> you are to determine the maximum cyclelength over all numbers between <U> <I>i</I> and<I>j</I>.<P></U></U><H2><FONT COLOR=#0070E8><A NAME="SECTION0001003000000000000000">The Input</A></FONT></H2><P>The input will consist of a series of pairs of integers <I>i</I> and <I>j</I>, one pair ofintegers per line. All integers will be less than 10,000 and greaterthan 0.<P>You should process all pairs of integers and for eachpair determine the maximum cycle length over all integers between andincluding <I>i</I> and <I>j</I>.<P><H2><FONT COLOR=#0070E8><A NAME="SECTION0001004000000000000000">The Output</A></FONT></H2><P>For each pair of input integers <I>i</I> and <I>j</I> you should output <I>i</I>, <I>j</I>,and the maximum cycle length for integers between and including<I>i</I> and <I>j</I>. These three numbersshould be separated by at least one space with all three numbers on oneline and with one line of output for each line of input. The integers<I>i</I> and <I>j</I> must appear in the output in the same order in which theyappeared in the input and should befollowed by the maximum cycle length (on the same line).<P><H2><FONT COLOR=#0070E8><A NAME="SECTION0001005000000000000000">Sample Input</A></FONT></H2><P><PRE>1 10100 200201 210900 1000</PRE><P><H2><FONT COLOR=#0070E8><A NAME="SECTION0001006000000000000000">Sample Output</A></FONT></H2><P><PRE>1 10 20100 200 125201 210 89900 1000 174</PRE><P></BODY></HTML>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -