Like Tree4Likes

Can you find the error?

This is a discussion on Can you find the error? within the C++ Programming forums, part of the General Programming Boards category; This is the Problem Statement: The 3n + 1 Problem Consider the following algorithm to generate a sequence of numbers. ...

  1. #1
    Registered User
    Join Date
    Apr 2013
    Posts
    10

    Can you find the error?

    This is the Problem Statement:
    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.
    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

    I had written the following C++ code for it:
    Code:
    //110101 The 3n + 1 Problem
    # include <iostream>
    using namespace std;
    int main()
    {
        int i,j,k,x,n1,n,m=909,mmax; /*m= a random number that i expect will never appear in the program. just so that the program keeps repeating and exits only on <ctr+c> */
    
    
        do
            {
            cin>> i>>j;
            n=j-i;int  counter[n+1];//n is the size for this counter array
            if ((i<1000000) && (i>0) && (j<1000000) && (j>0))
                {
                for (x=0;x<=n;x++)
                    counter[x]=1;
                x=0;
                for (k=i;k<=j;k++)
                    {
                    n1=k;
                    while (n1!=1)
                        {if ((n1%2)==0)
                            {n1= n1/2; counter[x]=counter[x]+1;}
                        else
                            {n1= n1*3; n1++;  counter[x]=counter[x]+1;}
                        }
                    x++;
                    }
                mmax=counter[0];
                for (x=1;x<=n;x++)
                    if (counter[x]>mmax)
                        mmax=counter[x];
                cout <<i<<" "<<j<<" "<<mmax<<"\n";
                }
            else cout<<"invalid input!";
            } while (m==909);
    }


    I submit this code on the website which had asked for it, but it says "Wrong Answer". I am not able to find any mistake in this. Can anyone please check and let me know what my mistake is? It is not a presentation error. Thanks a lot. Would be of great help.

  2. #2
    Registered User
    Join Date
    Apr 2011
    Posts
    62
    I can't find any thing wrong (thought your indentation,variable naming and organization doesn't exactly help looking). If its a website with an automatic checker it may no be expecting an infinite loop and outputs wrong answer cause as far as it is concerned the program failed to terminate.

  3. #3
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    20,968
    Note that variable length arrays are not part of standard C++, so if the compiler for the automatic checker does not allow for such a language extension, your code will not even compile.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  4. #4
    Registered User
    Join Date
    Apr 2013
    Posts
    10
    @laserlight
    The site provides for a separate section/ count for compilation errors. There are 0 compilation errors.

    @killme
    Yes I am sorry I haven't presented a neat code here. And regarding the infinite loop, yes that could be a possible reason. But in that case, what do you suggest I should do? The i/p and o/p format provided in the question is not flexible enough to let me ask the user if he wants to have another round of this play. In that case, how can I improve the code?

  5. #5
    Registered User
    Join Date
    Apr 2011
    Posts
    62
    Well, I'm assuming whoever runs the website wrote a small script that automaticly calls all answers submitted several times in order to test (that is usually the case). So you can just remove the loop and make the program a "one-off", the website itself will run it as often as it was designed for.

    You are trying to increase flexibility which is great for human users... automated ones are usually "less impressed".

  6. #6
    Registered User
    Join Date
    Apr 2013
    Posts
    10
    Thanks, but I already tried the single-run program. Didn't work

  7. #7
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    20,968
    Does your test output using the given sample input match the sample output exactly? Sometimes tiny formatting differences can cause problems for automated checkers.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  8. #8
    Registered User
    Join Date
    Apr 2013
    Posts
    10
    Yes it does. And there is a separate section/ count for "presentation errors" on their site, which is 0.

    There probably is some input for which I may not be getting the right output, just maybe..

  9. #9
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    20,968
    Okay, post your current program. Use a common indent style and have each statement on its own line.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  10. #10
    Registered User
    Join Date
    Apr 2013
    Posts
    10
    Here it is:
    Code:
    //110101 The 3n + 1 Problem
    # include <iostream>
    using namespace std;
    int main()
    {
        int i,j,k,x,n1,n,m=909,maxcount; //x=index of counter, n=no fo elements in counter, maxcount is the max element from the counter
        cin>> i>>j;
        n=j-i;
        int  counter[n+1];
        if ((i<1000000) && (i>0) && (j<1000000) && (j>0))
        {
            for (x=0;x<=n;x++)
                counter[x]=1;
            x=0;
            for (k=i;k<=j;k++)
            {
                n1=k;
                while (n1!=1)
                {
                    if ((n1%2)==0)
                    {
                        n1= n1/2;
                        counter[x]=counter[x]+1;
                    }
                    else
                    {
                        n1= n1*3; n1++;
                        counter[x]=counter[x]+1;
                    }
                }
                x++;
                }
            maxcount=counter[0];
            for (x=1;x<=n;x++)
                if (counter[x]>maxcount)
                    maxcount=counter[x];
            cout <<i<<" "<<j<<" "<<maxcount<<"\n";
        }
        else cout<<"invalid input!";
        return (0);
    }
    Last edited by neeha_khan; 04-10-2013 at 04:58 AM.

  11. #11
    Registered User
    Join Date
    Apr 2013
    Posts
    10
    The above program is only for 1 set of input.

    The catch is here... "The input will consist of a series of pairs of integers i and j, one pair of integers per line."
    But now how do I know when to stop accepting inputs?

  12. #12
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    20,968
    When the EOF condition has been reached.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  13. #13
    Registered User
    Join Date
    Apr 2013
    Posts
    10
    I made some modifications and wrote this now:


    Code:
    //110101 The 3n + 1 Problem
    # include <iostream>
    # include <fstream>
    using namespace std;
    int main()
    {
        int i,j,k,x,n1,n,maxcount,temp=0; /*x=index of counter, n=no fo elements in counter, maxcount is the max element from the counter*/
        while (cin>> i>>j)
        {
            if ((i<1000000) && (i>0) && (j<1000000) && (j>0))
            {
                if(i > j)
                    {temp=i;i=j;j=temp;}
                n=j-i;
                int  counter[n+1];
                for (x=0;x<=n;x++)
                    counter[x]=1;
                x=0;
                for (k=i;k<=j;k++)
                {
                    n1=k;
                    while (n1!=1)
                    {
                        if ((n1%2)==0)
                        {
                            n1= n1/2;
                            counter[x]=counter[x]+1;
                            //x++;
                        }
                        else
                        {
                            n1= n1*3; n1++;
                            counter[x]=counter[x]+1;
                            //x++;
                        }
                    }
                    x++;
                }
                maxcount=counter[0];
                for (x=1;x<=n;x++)
                    if (counter[x]>maxcount)
                        maxcount=counter[x];
                cout <<i<<" "<<j<<" "<<maxcount<<"\n";
            }
            else cout<<"invalid input!";
        }
        return (0);
    }
    But it still shows "Wrong answer". However, I have got my hands on a program (that I found online) that gives the correct result.

    Code:
    #include <iostream>
    using namespace std;
    int length(int n)
    {
    	int i = 1;
    	while(n != 1)
        {
            if(n % 2 == 0)
            {
                n /= 2;
            }
            else
            {
    			n *= 3;
    			n += 1;
            }
    		i++;
    	}
    	return i;
    }
    int main()
    {
    	int a, b, low, high;
    	while(cin>>a>>b)
        {
    		if(a < b)
    		{
    			low = a;
    			high = b;
    		}
            else
            {
    			low = b;
    			high = a;
    		}
    		int max = length(low);
    		for(int i = low + 1; i <= high; i++) {
    			int l = length(i);
    			if(l > max) {
    				max = l;
    			}
    		}
    		cout<<a<<" "<<b<<" "<<max<<endl;
    	}
    	return 0;
    }
    But I still cannot find the mistake in my program
    Last edited by neeha_khan; 04-14-2013 at 12:10 AM.

  14. #14
    Registered User
    Join Date
    Mar 2013
    Location
    Portugal, Porto.
    Posts
    105
    I haven't managed to compile any of your codes posted here (but the one you looked up online) nor do I understand why they should work.

    -Arrays must have a constant size. You may not change it throughout your program.

    >int counter[n+1]
    This is wrong.

    I'd say use vectors instead of arrays.

    Also, the usage of magic numbers isn't healthy programming. You should avoid them, even though I see you fixed it on your latest version.

    As for the problem itself I don't really undertand why are there 2 inputs. Shouldn't it be just 1 so it would give the cycle length from that number until 1?
    stahta01 and Elysia like this.

  15. #15
    Registered User
    Join Date
    May 2009
    Posts
    2,372
    Quote Originally Posted by Khabz View Post
    As for the problem itself I don't really undertand why are there 2 inputs. Shouldn't it be just 1 so it would give the cycle length from that number until 1?
    Based on the good posted solution the answer is to be the largest run of values between the two numbers (including the starting and ending numbers).

    Note: I do NOT know of any C++ Compiler that supports Variable Length Arrays (VLA)[Part of recent C Standards]; but, if one exists the code might compile with it.
    [I am a C programmer, so I use few C++ Compilers.]

    To OP: I would write a function that does the same as "int length(int n)" does in the good solution.
    Then, write a second function that calls that function using the logic you are trying to use to solve the problem.
    This is a case where functions make the problem much easier to solve and understand the solution.

    Tim S.
    Last edited by stahta01; 04-14-2013 at 09:14 AM.
    "Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the universe trying to produce bigger and better idiots. So far, the Universe is winning." Rick Cook

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Cannot find my error
    By Genxi in forum C Programming
    Replies: 5
    Last Post: 09-24-2012, 02:32 AM
  2. Can't seem to find the error here.
    By DavidP in forum C++ Programming
    Replies: 5
    Last Post: 12-30-2008, 12:26 PM
  3. one error....can't find it
    By ammanbesaw in forum C++ Programming
    Replies: 4
    Last Post: 12-13-2007, 09:36 AM
  4. STL find error with STL map
    By VirtualAce in forum C++ Programming
    Replies: 3
    Last Post: 08-20-2007, 01:23 PM
  5. can't find the error
    By noor_mirza in forum C++ Programming
    Replies: 2
    Last Post: 11-02-2002, 11:58 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