Collatz Sequence

[m0rf0s]

Am si eu o problema. Task-ul este jos (dupa cod). 

Codul actual: 

#include <stdio.h>
#include <stdlib.h>

    int lengthOfCollatzSequence(int n)
{    
        unsigned i=0;
        while(n!=1);
{
    if(n%2==0) 
        n=n/2;
    else n=3*n+1;
         i++;
} 
    return i;
} 

    int main( int argc, char *argv[])
{
    int a, b, n, length, x;
            x=0;
        scanf("%d %d", &a, &b);
            for(;a <= b; a++)
{
            length=lengthOfCollatzSequence(a);
                if(length >=x)
                x=length; n=a;
                
}
        printf("%d", n);
    return 0;
}

 

Problema aste urmatoarea: cand uploadez, nu primesc nici un output, si din cauza asta primesc eroarea de : time limit exceeded. Codul se compileaza este ok, doar ca nu pot rezolva problema cu time limit exceeded. 

Ma puteti ajuta?

P.S. string/arrays/math.h NU pot fi folosite.

TASK 2: Collatz sequence
This problem involves the Collatz conjecture, also know as the 3n + 1 problem. The conjecture
can be summarized as follows. Take any integer n>1. If n is even, divide it by 2 to get n/2.
If n is odd, multiply it by 3 and add 1 to obtain 3n + 1. The conjecture is that no matter
what number you start with, if the above process is repeatedly applied, then you will always
eventually reach 1. As an example, consider the Collatz sequence that starts with n=11 which
needs 14 steps to reach 1:
11 ! 34 ! 17 ! 52 ! 26 ! 13 ! 40 ! 20 ! 10 ! 5 ! 16 ! 8 ! 4 ! 2 ! 1:
In this problem, we consider only integers n from the interval 1 n 100000. For this
interval the conjecture has been verified to be true. Within this interval, the number n = 77671
produces the greatest intermediate value (1570824736, which easily fits in an int) in the sequence
of visited numbers.
Write a function lengthOfCollatzSequence that has as its argument a positive integer
value n less than 100000. The function should return the number of steps in the Collatz sequence
that starts with n and ends with 1.
Next, write a program that reads from the input two integers a and b, where 2 a b
100000. The output should be the integer n (where a n b), that needs the largest number of
1
steps to reach 1. If several of these integers exist, then the output should be the smallest one. Of
course, the program must make use of the function lengthOfCollatzSequence.
Example 1:
input:
2 10
output:
9
Example 2:
input:
2 100000
output:
77031
Example 3:
input:
1234 5678
output:
3711

[MrGrj]

Nu inteleg nimic din codul asta postat. Pune-l si tu pe bpaste cu indentarea corecta.

 

- ai ; dupa while

- as face functia lengthOfCollatzSequence de tipul long long

- in main() folosesti arg si argv dar nu le folosesti nicaieri

- if(length >=x) -> aici aveai nevoie de acolade (ai doua instructiuni)

 

Problema cu time limit exceeded este din cauza faptului ca programul tau, la un moment dat incearca sa calculeze un nr. mai mare de 2^31 - 1.

Incearca asa:

#include <stdio.h>
#include <stdlib.h>

int lengthOfCollatzSequence(int n) {    
    unsigned i = 0;
    
    while(n != 1) {
        if(n % 2 == 0) 
            n = n / 2;
        else 
            n = 3 * n + 1;
        i++;
    } 
    return i;
} 

int main()
{
    int a, b, length = 0, x = 0;
    scanf("%d %d", &a, &b);
    for(;a <= b; a++) {
        int l = lengthOfCollatzSequence(a);
        if(length < l) {
            length = l; 
            x = a;
        }
    }
    printf("%d", x);
}

PS: Nu mai ai nevoie de return 0. E un subiect discutat foarte mult in ultimul timp. Compilatorul stie sa il puna singur cand intalneste } din main (in C99 cel putin). Pentru mai multe detalii: http://stackoverflow.com/a/4138710/6165050

Edited September 27, 2016 by MrGrj