Help a noob. :(

This is a discussion on Help a noob. :( within the C Programming forums, part of the General Programming Boards category; The 3n + 1 Problem Consider the following algorithm to generate a sequence of numbers. Start with an integer n. ...

  1. #1
    Registered User
    Join Date
    Jul 2011
    Posts
    8

    Angry Help a noob. :(

    The 3n + 1 Problem

    Consider the following algorithm to generate a sequence of numbers. Start with an
    integer n. If n is even, divide by 2. If n is odd, multiply by 3 and add 1. Repeat this
    process with the new value of n, terminating when n = 1. For example, the following
    sequence of numbers will be generated for n = 22:
    22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
    It is conjectured (but not yet proven) that this algorithm will terminate at n = 1 for
    every integer n. Still, the conjecture holds for all integers up to at least 1, 000, 000.
    For an input n, the cycle-length of n is the number of numbers generated up to and
    including the 1. In the example above, the cycle length of 22 is 16. Given any two
    numbers i and j, you are to determine the maximum cycle length over all numbers
    between i and j, including both endpoints.[/SIZE]

    I just need help with understanding the problem. What does "maximum cycle length over all numbers between i and j, including both endpoints" mean? X_X

    Input
    The input will consist of a series of pairs of integers i and j, one pair of integers per
    line. All integers will be less than 1,000,000 and greater than 0.

    Output
    For each pair of input integers i and j, output i, j in the same order in which they
    appeared in the input and then the maximum cycle length for integers between and
    including i and j. These three numbers should be separated by one space, with all three
    numbers on one line and with one line of output for each line of input.

    Sample Input
    1 10
    100 200
    201 210
    900 1000

    Sample Output
    1 10 20
    100 200 125
    201 210 89
    900 1000 174

    What's with the output?
    Last edited by jadumonium; 08-19-2011 at 06:32 AM.

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,532
    It means you do
    for ( loop = i ; loop <= j ; loop++ )

    Then for each value of loop, you count how many iterations it takes for 3n+1 to reach 1

    You keep the maximum, and print it out at the end.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Quote Originally Posted by jadumonium View Post
    The 3n + 1 Problem

    Consider the following algorithm to generate a sequence of numbers. Start with an
    integer n. If n is even, divide by 2. If n is odd, multiply by 3 and add 1. Repeat this
    process with the new value of n, terminating when n = 1. For example, the following
    sequence of numbers will be generated for n = 22:
    22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
    It is conjectured (but not yet proven) that this algorithm will terminate at n = 1 for
    every integer n. Still, the conjecture holds for all integers up to at least 1, 000, 000.
    For an input n, the cycle-length of n is the number of numbers generated up to and
    including the 1. In the example above, the cycle length of 22 is 16. Given any two
    numbers i and j, you are to determine the maximum cycle length over all numbers
    between i and j, including both endpoints.[/SIZE]

    I just need help with understanding the problem. What does "maximum cycle length over all numbers between i and j, including both endpoints" mean? X_X
    Take a range of n from i to j (eg, 21 to 123) work the "if even divide by 2 or if odd multiply by 3 and add 1 until n=1" for each and keep a counter to tell you how many numbers are generated for each sequence.

    It's a fairly simple exercise... but an interesting challenge for a beginner...

  4. #4
    Registered User
    Join Date
    Jul 2011
    Posts
    8
    Actually, I've already done that. But here's the continuation of the problem which I'm having problems with.

    Input
    The input will consist of a series of pairs of integers i and j, one pair of integers per
    line. All integers will be less than 1,000,000 and greater than 0.

    Output
    For each pair of input integers i and j, output i, j in the same order in which they
    appeared in the input and then the maximum cycle length for integers between and
    including i and j. These three numbers should be separated by one space, with all three
    numbers on one line and with one line of output for each line of input.

    Sample Input
    1 10
    100 200
    201 210
    900 1000

    Sample Output
    1 10 20
    100 200 125
    201 210 89
    900 1000 174

  5. #5
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Ok... post your code... lets see what you've got...

  6. #6
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,532
    So if you've got the code to do it once, in main, then make a function out of it where you specify the endpoints as parameters.
    A development process

    Then add another bit of code to main to loop reading from a file/stdin to get more end points.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  7. #7
    Registered User
    Join Date
    Jul 2011
    Posts
    8
    Quote Originally Posted by CommonTater View Post
    Ok... post your code... lets see what you've got...
    Code:
    int get_int()
    {
    	int x;
    	scanf("%d", &x);
    	return x;
    }
    
    int even(num)
    {
    	num = num/2;
    	return num;
    }
    
    int  odd(num)
    {
    	num = (3*num) + 1;
    	return num;
    }
    
    int cycle(i, j, count)
    {
    	if(i==j)
    		return count;
    	else if(j%2==0)
    		return cycle(i, even(j), count + 1);
    	else
    		return cycle(i, odd(j), count + 1);
    }
    
    main()
    {
    	int i = get_int();
    	int j = get_int();
    	int x = cycle(i, j, 1);
    	printf("%d %d %d", i, j, x);
    }
    The output I receive doesn't match the output in the examples. When I input 1 and 10, I get 7. But when I input 1 and 22, I get 16, which is truly the cycle of 22. Now I reckon "maximum cycle length for integers between andincluding i and j" must mean another thing. But when I try getting the maximum cycle length of the numbers between i and j, I get a very big number which doesn't match the examples either. What must I do?
    Last edited by jadumonium; 08-19-2011 at 07:13 PM.

  8. #8
    Registered User TheBigH's Avatar
    Join Date
    May 2010
    Location
    Melbourne, Australia
    Posts
    426
    Firstly, the basic shell for a C program is
    Code:
    int main( void ) {
       /* your code goes here */
       return 0;
    }
    because main has to be a function that returns an integer. See this explanation.

    Now, you've solved the problem for one integer. What you need to do now is to loop through all the integers in the range and solve for all of them in turn.
    Code:
    while(!asleep) {
       sheep++;
    }

  9. #9
    Registered User TheBigH's Avatar
    Join Date
    May 2010
    Location
    Melbourne, Australia
    Posts
    426
    The output I receive doesn't match the output in the examples. When I input 1 and 10, I get 7. But when I input 1 and 22, I get 16, which is truly the cycle of 22. Now I reckon "maximum cycle length for integers between andincluding i and j" must mean another thing. But when I try getting the maximum cycle length of the numbers between i and j, I get a very big number which doesn't match the examples either. What must I do?
    Ah, I see where you're going wrong. You've misunderstood the question.

    Let's say you do the 3n+1 process just on the number 7. You'll go 7 - 22 - 11 - 34 - 17 - 52 - 26 - 13 - 40 - 20 - 10 - 5 - 16 - 8 - 4 - 2 - 1. That's a cycle length of 17. What you want to know is, if you do the 3n + 1 problem for all the numbers between 1 and 10 in turn, which of those numbers gives you the longest cycle length. Those should be your "i" and "j" variables. You need to loop from 1 to 10 (or whatever your i and j will be), calculate the cycle length for all of those and keep track of the longest.
    Code:
    while(!asleep) {
       sheep++;
    }

  10. #10
    Registered User
    Join Date
    Jul 2011
    Posts
    8
    Quote Originally Posted by TheBigH View Post
    Ah, I see where you're going wrong. You've misunderstood the question.

    Let's say you do the 3n+1 process just on the number 7. You'll go 7 - 22 - 11 - 34 - 17 - 52 - 26 - 13 - 40 - 20 - 10 - 5 - 16 - 8 - 4 - 2 - 1. That's a cycle length of 17. What you want to know is, if you do the 3n + 1 problem for all the numbers between 1 and 10 in turn, which of those numbers gives you the longest cycle length. Those should be your "i" and "j" variables. You need to loop from 1 to 10 (or whatever your i and j will be), calculate the cycle length for all of those and keep track of the longest.
    This explanation is exactly what I needed. Thanks!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. A noob need help
    By ticktoc09 in forum C Programming
    Replies: 5
    Last Post: 02-26-2011, 01:37 AM
  2. Noob Help :)
    By hcted in forum C++ Programming
    Replies: 7
    Last Post: 02-06-2011, 05:08 PM
  3. noob to C need a little help!!!
    By sk8harddiefast in forum C Programming
    Replies: 8
    Last Post: 02-27-2010, 01:47 PM
  4. Need help...I'm a noob
    By viciousv322 in forum C++ Programming
    Replies: 8
    Last Post: 05-24-2007, 11:52 AM
  5. im a noob not rod
    By cerin in forum C++ Programming
    Replies: 10
    Last Post: 12-29-2004, 07:57 PM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21