3n+1 problem

This is a discussion on 3n+1 problem within the C Programming forums, part of the General Programming Boards category; If you don't know this problem it is here http://acm.uva.es/p/v1/100.html . I don't know why my code is receiving wrong ...

  1. #1
    Registered User linuxdude's Avatar
    Join Date
    Mar 2003
    Location
    Louisiana
    Posts
    926

    3n+1 problem

    If you don't know this problem it is here http://acm.uva.es/p/v1/100.html.
    I don't know why my code is receiving wrong answer. It is right for the selected input. Also, I've done 1 1000000 and it doesn't seg fault on any numbers. Then I thought from the way that they worded it that they could give input out of order (swap function), but that didn't fix it. Why do they say it is wrong.
    Code:
    /*@JUDGE_ID:   110101   100 C "3n+1"*/
    
    #include <stdio.h>
    
    unsigned long int func(unsigned long int num);
    void swap(unsigned long int *tx,unsigned long int *ty);
    
    int main(void){
            unsigned long x,y,z,max=0,temp;
            fflush(stdout);
            while(scanf("&#37;lu %lu", &x,&y)==2){
                    if(x>y) swap(&x,&y);
                    max = 0;
                    for(z=x;z<=y;z++){
                            temp = func(z);
                            if(temp>max) max = temp;
                    }
                    printf("%lu %lu %lu\n",x,y,max);
            }
            return 0;
    }
    void swap(unsigned long int *tx,unsigned long int *ty){
            unsigned long int temp;
            temp = *tx;
            *tx = *ty;
            *ty = temp;
    }
    unsigned long int func(unsigned long int num){
            if(num == 1){
                    return 1;
            }
            else if(num%2==0){
                    return 1 + func(num/2);
                    }
            else{
                    return 1 + func(num*3+1);
            }
    }
    Thanks
    Last edited by linuxdude; 05-27-2007 at 01:47 PM. Reason: changed int temp to unsigned long temp;

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,344
    Maybe it takes too long?
    Maybe it's needlessly massively recursive?
    Maybe your swap function truncates data?
    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
    Registered User linuxdude's Avatar
    Join Date
    Mar 2003
    Location
    Louisiana
    Posts
    926
    It doesn't take too long because the error would be Time Limit Exeeded and not Wrong Answer
    So does that cancel out the first two? Also, how does a pointer swap lose data? I thought since they are dereferencing them as unsigned longs and stored into an unsigned long nothing bad would happen.
    Thanks :-D

  4. #4
    Registered User
    Join Date
    May 2007
    Posts
    58
    Code:
            else if(num&#37;2==0){
                    return 1 + func(num/2);
                    }
            else{
                    return 1 + func(num*3+1);
    Why do you add 1?

    Also, you're not supossed to use recursion.

    Look at this, it's working:

    Code:
    int main()
    {
            int n;
            start: scanf("%d",&n);
            print: printf("%d\n",n);
            if(n==1) goto start;
            if(n%2==1)
                n = 3*n + 1;
            else
                n = n/2;
    
            goto print;
    
            return 0;
    }
    You're swap function is algo wrong, because you assing a long int to an int, maybe in some architectures that'll work fine but it's not portable.
    Last edited by Govalant; 05-27-2007 at 01:23 PM.

  5. #5
    Registered User linuxdude's Avatar
    Join Date
    Mar 2003
    Location
    Louisiana
    Posts
    926
    I add one to keep track of how many times I do each step. The problem is to see which one takes the most steps between an interval [x,y]. Why am I not supposed to use recursion. I know I can do it without recursion, but I wanted to. It is simple and not slow. Sorry, I forgot to make temp an unsigned long. It still was wrong when I changed temp. My algo isn't wrong is it?

  6. #6
    Fear the Reaper...
    Join Date
    Aug 2005
    Location
    Toronto, Ontario, Canada
    Posts
    625
    Currently, I can't see anything wrong with it, but some sample output would be of some assisstance.
    Teacher: "You connect with Internet Explorer, but what is your browser? You know, Yahoo, Webcrawler...?" It's great to see the educational system moving in the right direction

  7. #7
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    The OP's link is a little out of date. The conjecture has been tested up to about 2.88 x 10^18.

    http://en.wikipedia.org/wiki/Collatz_conjecture

  8. #8
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,006
    The integers i and j must appear in the output in the same order in which they appeared in the input
    Consider an input of 1000 900.
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  9. #9
    Registered User linuxdude's Avatar
    Join Date
    Mar 2003
    Location
    Louisiana
    Posts
    926
    thanks Dave_Sinkula when i swapped I didn't print them swapped. it is solved now :-D

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

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