You should solve the problem and write your code in ONE python
file. When you are done, you SHOULD COMPRESS the file into one zip
file and SUBMIT THE COMPRESSED FILE ONLY (for example,
Assignment1.zip). Submission should be made ONLINE through the
PORTAL. NO OTHER FORM OF SUBMISSION will be accepted.
Therefore, if you do not submit online through the portal, you will get ZERO
for this assignment.
Problem: A CONJECTURE
[100 Marks]
Consider the following algorithm:
1. input n
2. print n
3. while n ~= 1
4. if n is odd then n = 3n+1
5. else n = n/2
Given the input 22, the following sequence of numbers will be printed by the above
algorithm:
22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
It is conjectured that the algorithm above will terminate (when a 1 is printed) for any
integral input value. Despite the simplicity of the algorithm, it is unknown whether this
conjecture is true. It has been verified, however, for all integers n such that 0 < n <
1,000,000 (and, in fact, for many more numbers than this.)
Given an input n, it is possible to determine the number of numbers printed (including the
1). For a given n this is called the cyclelength of n. In the example above, the cycle
length of 22 is 16.
For any two numbers i and j you are to determine the maximum cycle length over all
numbers between i and j (inclusive).
INPUT SPECIFICATION
The input will consist of a series of pairs of integers i and j (i may be greater than j and
viceversa). All integers will be less than 1,000,000 and greater than 0.
You should process all pairs of integers and for each pair determine the maximum cycle
length over all integers between and including i and j.
OUTPUT SPECIFICATION
For each pair of input integers i and j you should output the maximum cycle length for
integers between and including i and j. The string to print is as follows:
The Maximum Cycle Length is:
SAMPLE INPUT and OUTPUT
Case 1:
Please Enter the Value for i: 1
Please Enter the Value for j: 10
The Maximum Cycle Length is: 20
Case 2:
Please Enter the Value for i: 100
Please Enter the Value for j: 200
The Maximum Cycle Length is: 125
Case 3:
Please Enter the Value for i: 201
Please Enter the Value for j: 210
The Maximum Cycle Length is: 89
Case 4:
Please Enter the Value for i: 900
Please Enter the Value for j: 1000
The Maximum Cycle Length is: 174
ACKNOWLEDGEMENTS
The original version of this assignment was set as a programming challenge on ACM
(http://acm.uva.es/p/v1/100.html). This is slightly modified in the sense that in the
original problem you have to read from files and you have a time limit within which you
should produce your output.
coding in One python file
Page 1 of 12 Replies  972 Views  Last Post: 08 October 2008  12:07 AM
Replies To: coding in One python file
#2
Re: coding in One python file
Posted 07 October 2008  06:48 AM
Dream.In.Code has a policy by which we prefer to see a good faith effort on your part before providing source code for homework assignments. Please post the code you have written in an effort to resolve the problem, and our members would be happy to provide some guidance. Be sure to include a description of any errors you are encountering as well.
Post your code like this:
Thanks.
Post your code like this:
Thanks.
#3
Re: coding in One python file
Posted 08 October 2008  12:07 AM
This may help get you off to a running start ...
''' Consider the following algorithm: 1. input n 2. print n 3. while n ~= 1 4. if n is odd then n = 3n+1 5. else n = n/2 Given the input 22, the following sequence of numbers will be printed by the above algorithm: 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 Example program input/output ... Please Enter the Value for i: 1 Please Enter the Value for j: 10 The Maximum Cycle Length is: 20 Please Enter the Value for i: 100 Please Enter the Value for j: 200 The Maximum Cycle Length is: 125 Please Enter the Value for i: 201 Please Enter the Value for j: 210 The Maximum Cycle Length is: 89 Please Enter the Value for i: 900 Please Enter the Value for j: 1000 The Maximum Cycle Length is: 174 ''' def maxCycleLen( i, j ): maxLen =0 # initial to a lower than the lowest value of 1 for n in range (i, j+1): series = [] while n != 1: series.append(n) if n % 2 == 0: n = n/2 else: n = 3*n + 1 series.append(1) # last value of n = 1 cycleLen = len(series) if cycleLen > maxLen: maxLen = cycleLen return maxLen def getIJandShowMax(): while 1: # i.e. loop forever ... until break try: # allow only integers > 0 to be accepted for input ... i = input('Enter i : ') j = input('Enter j : ') if i < 1 or j < 1 or type(i) != int or type(j) != int \ or i >=1000000 or j >=1000000: raise # an exception ... break # ok ... since no exception raised, we have good data except: print 'NOT valid input. Enter only integers in the range ' \ '1..999999.' if i > j: # then swap ... j,i = i,j maxLen = maxCycleLen( i, j ) print 'Max cycle length is', maxLen while 1: getIJandShowMax() reply = raw_input( 'More y/n ? ' ) if reply in 'nN' and not reply == '': break
This post has been edited by David W: 08 October 2008  12:46 AM
Page 1 of 1
