"The Euler Project". Task.

I decided to solve problems from the "Euler Project". I started with the simplest ones, and then there was a snag. Here is the task 14 (http://euler.jakumo.org/problems/view/14.html).
Here is her solution:

#include <iostream>
#include <vector>
#include <ctime>
#include <algorithm>
#include <utility>
#include <map>

using namespace std;

//проверка на чётность числа
bool is_odd(int number)
{
    if (number % 2 == 0)
        return 1;
    return 0;
}

//вычисление самой последовательности Колатца
int cntNumsInCollatz_seq(int first_number)
{
    if ( first_number == 1 )
        return 1;

    if ( is_odd( first_number ) )
        return 1 + cntNumsInCollatz_seq( first_number / 2 );

    if ( !is_odd( first_number ) )
        return 1 + cntNumsInCollatz_seq( 3 * first_number + 1 );
}

int main()
{

    time_t time = clock();

    int length = INT_MIN;
    int number;

    for (int i = 100000; i != 2; i--)
    {

        int tmp_rez = cntNumsInCollatz_seq( i );

        if (tmp_rez > length)
        {
            length = tmp_rez;
            number = i;
        }
    }

    cout << "Time of work: " << double(clock() - time)/CLOCKS_PER_SEC << endl;

    cout << length << endl;
    cout << number << endl;

    return 0;
}

It's just a recursive function, that's all. For numbers 100 000 and less, it works more or less, but as soon as I want to calculate for numbers from 1 000 000 and less, the program crashes, because, apparently, the recursion depth is too large.

I'm trying to optimize it by Меморизации (saving the previously calculated result and then accessing it), so as not to calculate the same thing over 300 times, because, for example, if you calculate the number of steps for 13, then: 

13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1

And if for 7, then: 

7 -> 22 -> 11 -> 34 -> 17 -> 52 -> 26 -> 13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1

But since the number of steps for 13 was calculated at an early stage, for 7 in the sequence starting from 40, you can not continue the calculations, but take the finished result.

I'm trying to implement it.
Works at times faster, but for 10 000 it returns the error vector out of range.

How can I deal with this if the vector size can no longer be increased? Yes, and it is somehow expensive to have a vector of such dimensions. Please help me. We need another option here, I guess.

Here is the modified code:

#include <iostream>
#include <vector>
#include <ctime>
#include <algorithm>
#include <utility>
#include <map>

using namespace std;

//здесь добавил вектор
vector< int > numbers(1000000, 0);

 //проверка на чётность числа
bool is_odd(int number)
{
    if (number % 2 == 0)
        return 1;
    return 0;
}

//вычисление самой последовательности Колатца
int cntNumsInCollatz_seq(int first_number)
{

    //здесь проверка на присутствие элемента в векторе 
    if ( numbers[ first_number ] != 0 )
        return numbers[ first_number ];

    if ( first_number == 1 )
        return 1;

    if ( is_odd( first_number ) )
        return 1 + cntNumsInCollatz_seq( first_number / 2 );

    if ( !is_odd( first_number ) )
        return 1 + cntNumsInCollatz_seq( 3 * first_number + 1 );
}

int main()
{

    time_t time = clock();

    int length = INT_MIN;
    int number;

    for (int i = 10000; i != 2; i--)
    {

        int tmp_rez = cntNumsInCollatz_seq( i );

            //здесь добавление элемента ввектор
        numbers[ i ] = tmp_rez;

        if (tmp_rez > length)
        {
            length = tmp_rez;
            number = i;
        }
    }

    cout << "Time of work: " << double(clock() - time)/CLOCKS_PER_SEC << endl;

    cout << length << endl;
    cout << number << endl;

    return 0;
}
Author: LEQADA, 2014-10-31
Source

1 answers

Apparently, the sequence can grow well beyond a million, so remember all intermediate numbers are probably not the best idea.

Also, odd in English means not even, so it's better to rename your function.

First, let's get rid of unnecessary recursion. Instead of recursion, it is quite possible to use iteration:

int next_Collatz(int current)
{
    if ( is_even( current ) )
        return current / 2;
    else
        return 3 * current + 1;
}

int cntNumsInCollatz_seq(int first_number)
{
    int cnt = 1;
    int current_number = first_number;
    while (current_number != 1)
    {
        current_number = next_Collatz(current_number);
        cnt++;
    }
    return cnt;
}

Thus, we do not overflow the stack if a million occur in the sequence. elements.

Then we can remember the length of the sequence for several initial values of first_number - for example, for a million. :)

It turns out the following:

const int MEMOIZATION_RANGE = 100000; // произвольное значение, чем больше,
                                      // тем лучше, сколько память позволяет
vector<int> CollatzLength(MEMOIZATION_RANGE, -1);

CollatzLength[1] = 1; // важно

int computeNumsInCollatz_seq(int first_number)
{
    int partial_length = 0;
    int current = first_number;
    // цикл до какого-то уже вычисленного значения
    // цикл обязательно закончится, когда мы придём к одному из уже
    // просчитанных чисел (например, к единице).
    while (true)
    {
        if (current < MEMOIZATION_RANGE && CollatzLength[current] != -1)
            break; // нашли!
        // если нет, переходим к следующему
        current = next_Collatz(current);
        partial_length++; // ... увеличивая длину куска
    }
    // это полная длина:
    int length = partial_length + CollatzLength[current];
    // повторяем тот же цикл сначала, записывая данные в таблицу
    partial_length = length;
    current = first_number;
    while (true)
    {
        if (current < MEMOIZATION_RANGE)
        {
            if (CollatzLength[current] != -1)
                break;
            CollatzLength[current] = partial_length;
        }
        current = next_Collatz(current);
        partial_length--;
    }
    return length;
}

It remains only to remember the maximum. You can probably handle it yourself.

 5
Author: VladD, 2014-11-01 11:34:29