Like Tree1Likes
  • 1 Post By stahta01

Help with Collatz Conjecture program

This is a discussion on Help with Collatz Conjecture program within the C Programming forums, part of the General Programming Boards category; For those who do not know what the Collatz Conjecture is: Collatz conjecture - Wikipedia, the free encyclopedia Ok so ...

  1. #1
    Registered User
    Join Date
    Oct 2011
    Posts
    19

    Help with Collatz Conjecture program

    For those who do not know what the Collatz Conjecture is:
    Collatz conjecture - Wikipedia, the free encyclopedia
    Ok so my program works pretty well. There are 2 menu choices. You can either just see the basic hailstone sequence or you print the cycle lengths between any two numbers. In this menu choice, my program is also supposed to find the minimum cycle length and maximum cycle length between the two numbers and print out the the two numbers, as well as their respective integers. This program uses two doubly linked lists to hold the data (one for each menu choice)
    The problem I'm having is the printing and/or finding the max/min cycle length.

    I think the problem is in this function
    Code:
    //comparecycles: This function is for the 1st linked list. It gets the min and max cycle lengths for the double linked list and prints them
    //input: dummy head and tail
    //output: an integer
    int comparecycles(Node * head, Node * tail)
    {
      Node * cur;
      Node * max;
      Node * min;
      for(cur = head -> next; cur != tail; cur = cur -> next) //running through nodes
        {
          if(cur -> cycle_length > max -> cycle_length) //finding the biggest cycle length
        {
          max = cur;
        }
          else if(cur -> cycle_length < min -> cycle_length && min -> cycle_length != 0) //finding smallest
        {
          min = cur;
        }
          else
        {
          //do nothing
        }
         }
      printf("The min is %d from %d\n", min -> cycle_length, min -> num);
      printf("The max is %d from %d\n", max -> cycle_length, max -> num);
      return 0;
    }
    Here is the whole program if you wish to compile it (it's long)
    Code:
    /* 
    This program utilizes the Collatz conjecture. The program can input any integer and it can also tell you the cycle length as well. Although, this code might look complex at first. It is quite simple. There are two doubly linked lists going on at once. So there is basically two copies of each function for each doubly linked list. For example there is two addtails and two deletes. Everything to do with Case 2 is marked with a 2. Everything to do with Case 1 is just left alone.
    */
    
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct node //my node for the 1st case. Listing cycle lengths
    {
      int cycle_length;
      int num;
      struct node *prev;
      struct node *next;
    } Node;
    
    typedef struct node2 //2nd node. This is for the hailstone sequence
    {
      int num;
      struct node2 *prev;
      struct node2 *next;
    } Node2;
    
    Node * newnode(int number, int cycle); //function prototypes. ill go into details of each below
    Node2 * newnode2(int number);
    Node * addtail(Node * head, Node * tail, Node * new);
    Node2 * addtail2(Node2 * head2, Node2* tail2, Node2 * new);
    Node * delete(Node * head);
    Node2 * delete2(Node2 * head2);
    int case1(int start, int finish, Node * head, Node *tail);
    int case2(int num, Node2 * head2, Node2 * tail2);
    int cycle(int num);
    int comparecycles(Node * head, Node * tail);
    void printtable(Node * head, Node *tail);
    void printnodes(Node2 * head2, Node2 * tail2);
    void printmenu();
    
    int main()
    {
      Node * head;
      Node * tail;
      head = newnode(0,0); //dummy head and tail node for the 1st doubly linked list
      tail = newnode(0,0);
      head -> next = tail; //linking
      tail -> prev = head;
    
      Node2 * head2;
      Node2 * tail2;   //dummy head and tail for 2nd list
      head2 = newnode2(0);
      tail2 = newnode2(0);
      head2 -> next = tail2; //linking
      tail2 -> prev = head2;
    
      int  menu_option = 0;
    
      int i = 0; //variables for where to start and end 1st linked list
      int j = 0;
    
      int k = 0; //variables for the start of the 2nd linked list
      while (menu_option != 3)
        {
          printmenu();
          printf(">>");
          scanf("%d", &menu_option);
          switch(menu_option)
        {
            case 1:
             printf("Enter i\n>>");
             scanf("%d", &i);
             printf("Enter j\n>>");
             scanf("%d", &j);
             case1(i,j,head,tail);  //running the case 1 function
             printtable(head,tail);
             delete(head);
           break;
           
               case 2:
             printf("Enter Number\n>>");
             scanf("%d", &k);
             case2(k, head2, tail2); //running case 2
           break;
           
               case 3:
           
             return 0;
           break;
           
               default:
             printf("Error");
           break;
        }
        }
      return 0; 
    }
    
    //newnode: This function allocates memory and set data members for the 1st linked list
    //input: an integer (the number), a 2nd integer (number of cycles)
    //output: pointer to a node
    Node * newnode(int number, int cycle) //1st list
    {
      Node * new;
      new = malloc(sizeof(Node)); //allocating memory
      new -> num = number;
      new -> cycle_length = cycle;
      new -> prev = NULL;  //linking
      new -> next = NULL;
      return new;
    }
    
    //newnode2: This function allocates memory and sets data members for the 2nd linked list
    //input: an integer (the number)
    //output: pointer to a node
    Node2 * newnode2(int number) //2nd list
    {
      Node2 * new;
      new = malloc(sizeof(Node)); //allocating memory
      new -> num = number;
      new -> prev = NULL; //linking
      new -> next = NULL;
      return new;
    }
    
    //addtail: Adds the new node to the tail of the 1st linked list
    //input: dummy head and tail node. The new node to be added
    //output: the dummy tail node
    Node * addtail(Node * head, Node * tail, Node * new)  //1st
    {
      if(tail -> prev == head) //if list is empty
        {
          head -> next = new;
          new -> prev = head;
          tail -> prev = new;
          new -> next = tail;
          return tail;
        }
      else //if list has nodes
        {
          new -> prev = tail -> prev;
          new -> next = tail;
          tail -> prev -> next = new;
          tail -> prev = new;
          return tail;
        }
      return NULL; //should never reach here
    }
    
    //addtail2: This function add the new node to the tail of the 2nd linked list
    Node2 * addtail2(Node2 * head2, Node2 * tail2, Node2 * new) //2nd
    {
      if(tail2 -> prev == head2) //list is empty
        {
          head2 -> next = new;
          new -> prev = head2;
          tail2 -> prev = new;
          new -> next = tail2;
          return tail2;
        }
      else //not empty
        {
          new -> prev = tail2 -> prev;
          new -> next = tail2;
          tail2 -> prev -> next = new;
          tail2 -> prev = new;
          return tail2;
        }
      return NULL; //just in case
    }
    
    //delete: This function deletes all nodes, then starts over like the first lines of main
    //input: dummy head node
    //output: the current node
    Node * delete(Node * head) //1st list
    {
      Node * cur;
      Node * prev;
      prev = head -> next;
      cur = head -> next -> next;
      while(cur != NULL)
        {
           free(prev);
           prev = cur;
           cur = cur -> next;
        }
      free(prev);
      free(head); //everything is freed
      Node * tail; //dummy tail node
      head = newnode(0,0);
      tail = newnode(0,0);
      head -> next = tail; //linking
      tail -> prev = head;
      return cur;
    }
    
    //delete2: This function deletes all nodes, then starts over
    //input: dummy head node
    //output: the cur node
    Node2 * delete2(Node2 * head2) //2nd list
    {
      Node2 * cur;
      Node2 * prev;
      prev = head2 -> next;
      cur = head2 -> next -> next;
      while(cur != NULL)
        {
           free(prev);
           prev = cur;
           cur = cur -> next;
        }
      free(prev); //freeing everything
      free(head2);
      Node2 * tail2;
      head2 = newnode2(0); //starting over. linking
      tail2 = newnode2(0);
      head2 -> next = tail2;
      tail2 -> prev = head2;
      return cur;
    }
    
    //case1: This function does everything case 1 needs. adds data members. adds them to the tail of the list, prints the table and frees memory
    //input: the start (i), the finish (j), dummy head and tail node
    //output: an integer
    int case1(int start, int finish, Node * head, Node * tail)
    {
      for(start; start <= finish; start++)
        {
          Node * new = newnode(start, cycle(start));
          addtail(head, tail, new);
        }
      return 0;
    }
    
    //case2: This function does a lot. Adds data members. Adds nodes to list. Prints nodes and frees memory
    //input: The number to start with, dummy head and tail node
    //output: An integer
    int case2(int num, Node2 * head2, Node2 * tail2)
    {
      int cycle_length = cycle(num);
      Node2 * new = newnode2(num);
      addtail2(head2, tail2, new);
      while(num !=1)
        {
          if(num != 1 && num % 2 ==1)
        {
          num = 3 * num + 1;
          Node2 * new = newnode2(num);
          addtail2(head2, tail2, new);
        }
          else if(num != 1 && num % 2 == 0)
        {
           num = num/2;
          Node2 * new = newnode2(num);
          addtail2(head2, tail2, new);
        }
         }
      printnodes(head2, tail2);
      printf("The cycle length is %d\n", cycle_length);
      delete2(head2);
      return 0;
    }
    
    //cycle: This function is for the 1st and 2nd list. It gets the number of cycle lengths for a number
    //input: An integer
    //output: the correct cycle length
    int cycle(int num)
    {
      int cycle_length = 0;
      while(num != 1)
        {
          if(num != 1 && num % 2 == 1) //if it is odd
        {
          num = 3 * num + 1;
        }
          else if(num != 1 && num % 2 == 0) //even numbers
        {
          num = num/2;
        }
          cycle_length++; //increment counter
        }
      return cycle_length + 1; //including 1
    }
    
    //comparecycles: This function is for the 1st linked list. It gets the min and max cycle lengths for the double linked list and prints them
    //input: dummy head and tail
    //output: an integer
    int comparecycles(Node * head, Node * tail)
    {
      Node * cur;
      Node * max;
      Node * min;
      for(cur = head -> next; cur != tail; cur = cur -> next) //running through nodes
        {
          if(cur -> cycle_length > max -> cycle_length) //finding the biggest cycle length
        {
          max = cur;
        }
          else if(cur -> cycle_length < min -> cycle_length && min -> cycle_length != 0) //finding smallest
        {
          min = cur;
        }
          else
        {
          //do nothing
        }
         }
      printf("The min is %d from %d\n", min -> cycle_length, min -> num);
      printf("The max is %d from %d\n", max -> cycle_length, max -> num);
      return 0;
    }
    
    //printtable: This prints the table for the 1st linked list
    //input: dummy head and tail
    //output: void function
    void printtable(Node * head, Node * tail)
    {
      Node * cur;
      printf("Number\tCycle Length\n"); //table header
      if(head -> next != tail)
        {
          for(cur = head -> next; cur != tail; cur = cur-> next) //run through nodes
        {
          printf("%d\t%d\n", cur -> num, cur -> cycle_length); //printing data members
        }  
        }
      else //if list is empty
        {
          printf("Empty List");
        }
      comparecycles(head, tail); //printing min and max
    }
    
    //printnodes: This function prints the hailstone sequence for the 2nd list
    //input: dummy head and tail
    //output: void function
    void printnodes(Node2 * head2, Node2 * tail2)
    {
      Node2 * cur;
      if(head2 -> next != tail2)
        {
          for(cur = head2 -> next; cur != tail2; cur = cur -> next) //run through
        {
          printf("%d\n", cur -> num); //prints data
        }
        }
      else //if empty
        {
          printf("Empty List");
        }
    }
    
    //printmenu: This function prints the main menu
    //input: N/A
    //output: void
    void printmenu()
    {
      printf("1) Caculate cycle lengths between i and j\n");
      printf("2) Generate hailstone sequence for any number\n");
      printf("3) Exit the program\n");
    }

  2. #2
    Registered User
    Join Date
    Oct 2011
    Posts
    19
    and yes I am aware of the memory leaks so far in this program. I was going to work on freeing up all the memory after I get this little snag done

  3. #3
    Registered User
    Join Date
    May 2009
    Posts
    2,549
    You never initialize max -> cycle_length to any value; same on min.
    NOTE: You never allocate space for them either.
    NOTE: I suggest turning on your compiler warnings and then pay attention to the warnings.
    Code:
    max -> cycle_length
    Tim S.
    Last edited by stahta01; 11-06-2011 at 01:34 PM.
    StarDrago likes this.

  4. #4
    Registered User
    Join Date
    Oct 2011
    Posts
    19
    Sweet! Everything works! I got all the memory leaks caught too! Thanks a lot!

  5. #5
    Banned
    Join Date
    Nov 2011
    Posts
    3
    Oh! I had the same probem. Thank you for your answer!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Collatz's Conjecture
    By KAUFMANN in forum C Programming
    Replies: 15
    Last Post: 06-29-2011, 07:01 PM
  2. Collatz Conjecture
    By eebank in forum C Programming
    Replies: 1
    Last Post: 10-27-2010, 08:51 PM
  3. Help With Collatz Conjecture
    By Dougal in forum C Programming
    Replies: 3
    Last Post: 10-20-2009, 10:01 PM
  4. Goldbach's conjecture
    By dcwang3 in forum C Programming
    Replies: 10
    Last Post: 10-14-2008, 01:34 AM
  5. Goldbach Conjecture
    By StarOrbs in forum C++ Programming
    Replies: 19
    Last Post: 03-17-2005, 03:42 PM

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