Нахождение максимальной последовательности Коллатца между 1-1000000
Я пытаюсь найти максимум Последовательность Коллатца между 1 и 1000000. Я написал следующий код ниже. Я думаю, это правильно, но это очень медленно. Можете ли вы дать мне несколько советов, чтобы сделать это быстрее? Благодарю.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool myfn(int i, int j) { return i<j; }
int collatz(int x);
int main()
{
vector <int> myvector;
for(int i = 1; i < 1000000; i++)
{
myvector.push_back(collatz(i));
}
cout<<*max_element(myvector.begin(),myvector.end(),myfn);return 0;
}
int collatz(int x)
{
int counter = 1;while(1)
{
if(x == 1)
break;
if(x % 2 == 0)
{
x = x / 2;
counter++;
}
else
{
x = 3 * x + 1;
counter++;
}
}
return counter;
}
Решение
Вот несколько советов:
Инициализируйте вектор в соответствии с вашими возможностями.
Вектор может расширяться, пока вы нажимаете элементы. В худшем случае одно перераспределение на push_back.
Обрабатывать вектор как массив
После того, как вы инициализировали свой вектор до его емкости, вы можете использовать оператор [] для доступа к векторному слоту вместо вызова push_back,
Оптимизировать коллатц
Это, вероятно, ваше узкое место. Попробуйте поместить в отдельный файл и запустить оптимизацию компилятора.
Там может быть более оптимальный алгоритм.
Другие решения
На самом деле, я только что проверил, и ваш код не просто «чрезвычайно медленный», а бесконечно цикличный. Нет, вы не просто опровергли гипотезу Коллатца, но, насколько я понимаю, вы страдаете от целочисленного переполнения.
Более конкретно, во время collatz(113383) int x переменная становится отрицательной из-за переполнения:
551580299 1654740898 827370449 -1812855948 -906427974 -453213987
Вскоре после этого он начинает цикл в следующей последовательности и, следовательно, никогда не выходит из цикла
-37 -110 -55 -164 -82 -41 -122 -61 -182 -91 -272 -136 -68 -34 -17 -50 -25 -74 -37 ...
После того как я изменил int x аргумент long long, программа довольно быстро заканчивается.
Тогда, конечно, остается вопрос: не возникает ли переполнений, которые не вызывают бесконечные циклы и остаются незамеченными, так как тогда вы все равно получите неправильный ответ. Однако после сдачи
if (x < 0) {
cout << "ERROR" << endl;
}
в конце while(1) Я думаю, вы можете быть уверены, что long long достаточно велика для последовательностей Коллатца для чисел от 1 до 1000000 (8 байт на моем компьютере по сравнению с 4 байтами для int, если вам будет интересно).
РЕДАКТИРОВАТЬ:
В качестве примечания: я не вижу смысла сохранять вектор всех результатов, если вам нужен только максимум. Следующий код потребляет меньше памяти:
int maxCollatz = 0;
for(int i = 1; i < 1000000; i++) {
if (i % 10000 == 0)
cout << i << endl;
maxCollatz = max(maxCollatz, collatz(i));
}
И еще одно замечание: на самом деле вы выполняете только циклы от 1 до 999999, поэтому, если последовательность Коллатца для 1000000 будет самой длинной, вы можете пропустить этот …