[help] 3n+1 problem

This is a discussion on [help] 3n+1 problem within the C++ Programming forums, part of the General Programming Boards category; Salam to Muslims, Hi there guys, I need some help with this problem. I have written code and it does ...

  1. #1
    K12
    K12 is offline
    Registered User
    Join Date
    Oct 2009
    Posts
    8

    [help] 3n+1 problem

    Salam to Muslims,

    Hi there guys,
    I need some help with this problem. I have written code and it does work as far as I can tell but one of the online judges does not accept it.

    Please suggest any amendments to make the code better:
    Code:
    #include <iostream>
    
    using namespace std;
    
    int CycleLength(int x);
    
    int main(){
        while(1){
        int unsigned i,j,k,l,max=0;
        cin>>i>>j;
        k=i;
        l=j;
    
        if ((i==0)&&(j==0)) break;
    
        if(i==j){max=CycleLength(i);}
        else
        if(i>j){for(i;i>j;i--){
            if (CycleLength(i)>max)
            max=CycleLength(i);
                      }
            }
        {
        for(i;i<j;i++){
            if (CycleLength(i)>max)
            max=CycleLength(i);
                      }
            }
        cout<<k<<" "<<l<<" "<<max<<endl;}
    
    }
    
    int CycleLength(int x){
            int count=1;
    
            while(x>1){
                if (x%2==!0)
                    x=3*x+1;
                else x=x/2;
    
            count++;
                    }
    
            return count;
            }
    Thanks.

  2. #2
    Password:
    Join Date
    Dec 2009
    Location
    NC
    Posts
    587
    Maybe they didn't like your style. That code isn't very easy to read. Fix the indentation, and don't do
    Code:
    if(cond)expr;
    do
    Code:
    if(cond)
         expr;

  3. #3
    Registered User
    Join Date
    May 2009
    Posts
    2,612
    Quote Originally Posted by User Name: View Post
    Fix the indentation
    The indentation by itself is enough for me to consider you code as bad code.

    Some of programmers on this site say using "using namespace std;" is bad thing to use.

    Many programmers say to declare only one variable per line.

    How you did it.
    Code:
    int unsigned i,j,k,l,max=0;
    Preferred
    Code:
    int unsigned i; /* Comment saying what this Variable does */ 
    int unsigned j;
    int unsigned k;
    int unsigned l;
    max=0;

    Tim S.
    Last edited by stahta01; 12-12-2010 at 02:24 PM.

  4. #4
    a_capitalist_story
    Join Date
    Dec 2007
    Posts
    2,651
    Salam to Muslims
    [strike]So, are only Muslims worthy of salutation?[/strike]

    Sorry, I missed the second salutation... :sheepish grin:
    Last edited by rags_to_riches; 12-13-2010 at 05:18 AM. Reason: Shouldn't overreact when feeling cranky!

  5. #5
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Quote Originally Posted by User Name: View Post
    Maybe they didn't like your style.
    I lol'ed. I don't know if it was deliberate or not, but those "online judges" are automated machines that test if the output provided is correct ;-).

    Though I'm not going to bother find out what's wrong if the code is so dreadfully formatted.

    Edit: actually, I did spot the two problems. Well, not just two, I expect you'll get a time limit exceeded as well, unless they're extremely friendly.
    Last edited by EVOEx; 12-12-2010 at 03:20 PM.

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,307
    Quote Originally Posted by stahta01 View Post
    Preferred
    Code:
    int unsigned i; /* Comment saying what this Variable does */ 
    int unsigned j;
    int unsigned k;
    int unsigned l;
    max=0;
    Never!
    If you ever have to provide a comment to say what a variable is for then chances are that your variable names simply suck.
    There's nothing wrong with declaring multiple variables on one line. Clearly if all those variables are meant to be the same type then it's easier to change one line later rather than five, which leads me on to my next point... You broke it by no longer declaring 'max' (which incidentally is also a bad variable name).

    Quote Originally Posted by rags_to_riches View Post
    So, are only Muslims worthy of salutation?
    I would try not to be offended. To the rest of us who don't know what that word means, K12 did say "Hi" to us.

    K12:
    It seriously took me about 3 minutes to properly match the brakets up when reading that mess. It should not even take 3 seconds for code that long!
    If you want others to help you then you need to do a lot better.
    Also, whitespace is your friend.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  7. #7
    The larch
    Join Date
    May 2006
    Posts
    3,573
    It would help if you told us why this is not accepted.

    E.g if the Judge treats warnings as errors, then you have comparisons between signed and unsigned integers.

    If it is too slow, then you should be able to tell immediately that you are calling CycleLength twice as often as needed.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  8. #8
    K12
    K12 is offline
    Registered User
    Join Date
    Oct 2009
    Posts
    8
    Some of programmers on this site say using "using namespace std;" is bad thing to use.
    Why? What are the pros and cons?

    Alright, I took your advice of indentation and did my best to fix the current code in terms of indentation. Please check it and spot the problem if the indentation is satisfactory, if not, then please tell me how to improve my indentation. Thanks a lot for the help so far guys.

    Here is the indented code:
    Code:
    #include <iostream>
    
    using namespace std;
    
    int CycleLength(int x);
    
    int main()
    {
        while(1)
        {
        int unsigned i,j,k,l,max_cycle=0;
        //i,j are user inputs of the two numbers. k,l store initial values of i and j respectively to be printed out later.
    
    
        cin>>i>>j;
    
        k=i;
        l=j;
    
        if ((i==0)&&(j==0)) break;
    
        if(i==j)
            max_cycle=CycleLength(i);
        else
        if(i>j)
            {
                for(i;i>j;i--)
                {
                    if (CycleLength(i)>max_cycle)
                    max_cycle=CycleLength(i);
                }
            }
    
        for(i;i<j;i++)
        {
            if (CycleLength(i)>max_cycle)
                max_cycle=CycleLength(i);
        }
    
        cout<<k<<" "<<l<<" "<<max_cycle<<endl;
        }
    }
    
    int CycleLength(int x)
    {
            int count=1;
    
            while(x>1)
            {
                if (x%2==!0)
                        x=3*x+1;
                else
                        x=x/2;
            count++;
            }
            return count;
    }
    I tried my best to satisfy everyone, but I did not understand why it was better to declare each variable in their own line and I also changed the variable 'max' to 'max_cycle'.

  9. #9
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,307
    Well that's much better!

    Here's a relevant xkcd image, by the way.

    Is there a problem description somewhere that we can read to see if this does what was asked?
    It may be that the problem is integer overflow inside CycleLength.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  10. #10
    K12
    K12 is offline
    Registered User
    Join Date
    Oct 2009
    Posts
    8
    Thanks, the image was hilarious.

    You can check out the description here:
    Code:
    http://online-judge.uva.es/p/v1/100.html
    EDIT: Judges keep on giving a wrong answer for this.
    Last edited by K12; 12-13-2010 at 09:24 PM.

  11. #11
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Your for loops stop one too soon (you need to compute the cycle length for j, too).

  12. #12
    K12
    K12 is offline
    Registered User
    Join Date
    Oct 2009
    Posts
    8
    Attempted a fix:
    Code:
    if(i>j)
            {
                for(i;i>j-1;i--)
                {
                    if (CycleLength(i)>max_cycle)
                    max_cycle=CycleLength(i);
                }
            }
    
        for(i;i<j+1;i++)
        {
            if (CycleLength(i)>max_cycle)
                max_cycle=CycleLength(i);
        }

  13. #13
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Also, your "hey I'm done now" check is extremely brittle -- as in, I don't see how it can work. There's not a 0 0 pair at the end of the input, and i and j don't end up at 0 along the way. If there's no data, then i and j don't get changed to 0 somehow -- the read fails, which is what you should be checking for.

  14. #14
    K12
    K12 is offline
    Registered User
    Join Date
    Oct 2009
    Posts
    8
    The problem description does not mention how the input should stop. I just assumed a 0 0 input would end it. If you have any experience with questions like this, please tell me how to get it right.

  15. #15
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    The input stops, that's how you know it's done. You can check whether an input stream is still "good" (i.e., if every read so far has succeeded) or if it has "failed". You should do that.

    Hint: istream - C++ Reference

Page 1 of 2 12 LastLast
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, 10: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

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