Thread: 3n+1 problem

  1. #1
    Registered User
    Join Date
    Oct 2010
    Posts
    11

    3n+1 problem

    I am posting my solution for the 3n+1 problem on the online judge webpage. The judge seems to give the verdict of "wrong answer" even though the program works for the test cases given in the problem statement.
    http://uva.onlinejudge.org/index.php...lem&problem=36
    I would be glad if anyone would point out the errors.
    Code:
    #include <stdio.h>
    int cycle_length(int n, int i)
    {  int a;
        if (n == 1)
           return i;
        if(n%2 == 0)
           {a = cycle_length(n/2, ++i); return a;}
        else
           {a = cycle_length((3*n+1), ++i); return a;}
    }
    
    int main()
    {
        int a, b, i, max, min;
        scanf("%d", &a);
        scanf("%d", &b);
        if (a >= b)
           {max = a; min = b;}
        else
            {max = b; min = a;}
        int c[max - min +1];
        
        for(i = 0; i < (max-min+1); i++)
        {
              c[i] = cycle_length((min+i), 1);
        }
        
        for (i=1; i <(max-min+1); i++)
        {
            if (c[i] >= c[0])
               {int t = c[0]; c[0] = c[i]; c[i] = t;}
    }
    printf("%d %d %d", a, b, c[0]);
    return 0;
    }

  2. #2
    Registered User
    Join Date
    Sep 2007
    Posts
    1,012
    Your program will only compute the max cycle length for one pair of numbers. The assignment clearly states that “[t]he input will consist of a series of pairs of integers i and j, one pair of integers per line.”

  3. #3
    Registered User
    Join Date
    Oct 2010
    Posts
    11
    Quote Originally Posted by cas View Post
    Your program will only compute the max cycle length for one pair of numbers. The assignment clearly states that “[t]he input will consist of a series of pairs of integers i and j, one pair of integers per line.”
    I realised that but the problem statement does not state how many series of pairs of integers are to be input nor does it give a condition as to when will the input stop (ie after such or such key is pressed). So how does one design a program to satisfy the judge?

  4. #4
    Registered User Swarvy's Avatar
    Join Date
    Apr 2008
    Location
    United Kingdom
    Posts
    195
    My understanding of the problem is that given a pair of integers you have to design a program which finds the length of each chain for all the numbers in between the integers specified and then return the greatest chain length it found.

    E.g. If you put in start = 20 and finish = 10, then you get a maximum chain length of 21 on the number 18. You could try and verify that by hand if you wanted to.
    I.e. 18, 9, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1

    The answer is 21 in that case because that is the number of numbers in that chain and that is the longest chain between 10 and 20. Now do something similar for the numbers between 1,000,000 and 1.

    Edit: I know the answer to this problem (with source code) but you wouldn't learn anything just by being given the solution.
    Last edited by Swarvy; 10-13-2010 at 09:34 AM.

  5. #5
    Registered User
    Join Date
    Sep 2007
    Posts
    1,012
    Quote Originally Posted by Prestige View Post
    I realised that but the problem statement does not state how many series of pairs of integers are to be input nor does it give a condition as to when will the input stop (ie after such or such key is pressed). So how does one design a program to satisfy the judge?
    You can loop and read as many integers as you want.

    scanf() returns a value that will likely be very helpful in determining when the user is done entering a list.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need help understanding a problem
    By dnguyen1022 in forum C++ Programming
    Replies: 2
    Last Post: 04-29-2009, 04:21 PM
  2. Memory problem with Borland C 3.1
    By AZ1699 in forum C Programming
    Replies: 16
    Last Post: 11-16-2007, 11:22 AM
  3. Someone having same problem with Code Block?
    By ofayto in forum C++ Programming
    Replies: 1
    Last Post: 07-12-2007, 08:38 AM
  4. A question related to strcmp
    By meili100 in forum C++ Programming
    Replies: 6
    Last Post: 07-07-2007, 02:51 PM
  5. WS_POPUP, continuation of old problem
    By blurrymadness in forum Windows Programming
    Replies: 1
    Last Post: 04-20-2007, 06:54 PM