2

I've tried to solve "The 3n+1" problem. When I debug my code it stuck at line 12, calculation function. "According to Collatz conjecture, j should converge to 1."

Main file

    #include "input_output.h"
    #include <stdlib.h>
    int main() {
        int i=0, j=0;`
        int *num;
        int maxCycle;
        int length;
        input(&i, &j);
        length = j - i + 1;
        num = (int*)malloc(sizeof(int)*(j - i+1));

here is the problem code

        while (i <= j) {            
            calculate(j, num);//<- it stuck at here when i dubug it.
            j--;                    
            num++;                  
        }

        maxCycle = findMax(length, num);
        output(maxCycle);
        return 0;
    }

source file

    #include <stdio.h>
    #include "input_output.h"
    #pragma warning (disable:4996)
    void input(int *i, int *j) {
        scanf("%d %d", i,j);    
    }

    void calculate(int j, int* num) {

        while (j > 1) {     
            if (j % 2 == 0) {   
                j = j / 2;
                *num++;         
            }

            if (j % 2 == 1) {   
                j = j * 3 + 1;  
                *num++;         
            }
        }
    }

    int findMax(int length, int * num){
        int max = 0;
        int idx = 0;
        while (idx < length) {
            if (*num > max) max = *num;
            idx++;
            num++;
        }
        return max;

    }

    void output(int maxout) {
        printf("%d", maxout);
    }

Header

    #ifndef __input_output_H__
    #define __input_output_H__

    void input(int *i, int *j);         
    void calculate(int j,int *num); 
    int findMax(int length, int* num);
    void output(int maxout);



    #endif __input_output_H__

I think header seems no problem and also main file. is there any problem with my source file? I wonder why debugger stuck at there...

Jonathan Leffler
  • 730,956
  • 141
  • 904
  • 1,278
BoHyunK
  • 59
  • 6
  • If your `calculate()` function is supposed to return the number of iterations to reach `1`, maybe the function return type should be `int` (or `size_t`, or `unsigned long long`) instead of passing a pointer to the function and have the return type be `void`. Also, the repeated `(*num)++` is slower than incrementing a local variable – maybe not all that much slower, but probably measurably slower. And, of course, you need to add the parentheses — you're currently accessing unknown locations as you increment a pointer instead of incrementing what the pointer points at. – Jonathan Leffler Feb 19 '19 at 07:39
  • Note that you should not, in general, create function, variable, tag or macro names that start with an underscore. Part of [C11 §7.1.3 Reserved identifiers](https://port70.net/~nsz/c/c11/n1570.html#7.1.3) says: — _All identifiers that begin with an underscore and either an uppercase letter or another underscore are always reserved for any use._ — _All identifiers that begin with an underscore are always reserved for use as identifiers with file scope in both the ordinary and tag name spaces._ See also [What does double underscore (`__const`) mean in C?](https://stackoverflow.com/a/1449301) – Jonathan Leffler Feb 19 '19 at 07:40
  • You have problems because you allocate the array pointed at by `num` in the main function, and then increment that pointer repeatedly, so you lose track of where the start of the array is. But you really don't need an array; you just need the number of cycles for the current integer, and the maximum length found so far. You leak the array because you don't call `free()` — though given that you've lost the value returned by `malloc()`, at the moment, that's a good thing! – Jonathan Leffler Feb 19 '19 at 07:44
  • See [Definitive C Book Guide and List](https://stackoverflow.com/questions/562303/the-definitive-c-book-guide-and-list). I'd suggest K.N.King's book. – Jonathan Leffler Feb 19 '19 at 08:22
  • Thank you for criticized my code very detailly. By the way, if it's not an excuse, could you recommend a book for studying C? I'm trying to choose a book between C Programming : A Modern Approach written by K.N.King and The C Programming Language written by Dennis Ritchie.Or is there any better book for me? – BoHyunK Feb 19 '19 at 08:26

2 Answers2

0

Your loop never ends: you reach j == 1, yet you continue to apply 3n + 1, which makes you go back to 4, and therefore you are in a loop forever:

1 -> 4 -> 2 -> 1 -> ...

By the way, this:

*num++;

is not doing what you think it is doing. You are incrementing the pointer, and then accessing the value (which is not used). So it is as if you had written:

num++;

You should have written (*num)++.

Jonathan Leffler
  • 730,956
  • 141
  • 904
  • 1,278
Acorn
  • 24,970
  • 5
  • 40
  • 69
-1

The problem is at j = j * 3 + 1;, 'j' keeps on increasing if 'j' is greater than 1 and odd. So it hangs at calculate(int j,int *num) as the while loop inside it runs infinitely (j value will reset after a while).

Edit:

I have accumulated all the corrections and have added the code:

main.c :

#include "input_output.h"
#include <stdlib.h>

int main()
{
        int i=0, j=0;
        int *num,*ori;                  //New pointer required to remember the start position of num
        int maxCycle;
        int length;
        input(&i, &j);
        length = j - i + 1;
        num = (int*)calloc((size_t)(j-i+1),sizeof(int));
        ori=num;
        while (i <= j)
        {
                calculate(j, num);
                j--;
                num++;
        }
        num=ori;
        maxCycle = findMax(length, num);
        num=ori;
        output(maxCycle);
        return 0;
}

input_output.h :

#ifndef INPUT_OUTPUT_H
#define INPUT_OUTPUT_H

void input(int *i, int *j);
void calculate(int j,int *num);
int findMax(int length, int* num);
void output(int maxout);

#endif

input_output.c :

#include <stdio.h>
#include "input_output.h"
void input(int *i, int *j) {
        printf("Enter the i & j:\n");
        scanf("%d%d",i,j); 
        printf("Values entered:\ni: %d\nj: %d",*i,*j);
}

void calculate(int j, int* num) {

        while (j > 1) {     
                if (j==1)
                        break;
                if (j % 2 == 0) {   
                        j = j / 2;
                        (*num)++;         
                }
                else{   
                        j = j * 3 + 1;  
                        (*num)++;         
                }
        }

        printf("\nLength Value: %d\n",*num);
}

int findMax(int length, int * num){
        int max = 0;
        int idx = 0;
        printf("\nLength Values:\n");
        while (idx < length) {
                printf("%d ",*num);
                if (*num > max) 
                        max = *num;
                idx++;
                num++;
        }
        return max;

}

void output(int maxout) {
        printf("\nResult: %d", maxout);
}

Compile in linux using: gcc input_output.c main.c -Wall -Wextra -pedantic -Wconversion -std=gnu11 -o collatz

For further clarification please comment.

M. Knight
  • 89
  • 5