Застрял в бесконечном цикле? (Может быть)
Я пытаюсь завершить проект Эйлера Задача 14 в с ++ и я честно застрял. Прямо сейчас, когда я запускаю проблему, она застревает на Пока: число с наибольшим количеством: 113370 со счетом 155
Пока что: число с наибольшим количеством, но когда я пытаюсь изменить значение i на более чем 113371, это работает. Что здесь происходит??
Вопрос в том:
Следующая итерационная последовательность определена для множества положительных
целые числа: n → n / 2 (n четное) n → 3n + 1 (n нечетное)Используя приведенное выше правило и начиная с 13, мы генерируем следующее
последовательность:13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 Видно, что это
последовательность (начиная с 13 и заканчивая 1) содержит 10 терминов.
Хотя это еще не доказано (проблема Коллатца), это
думал, что все начальные номера заканчиваются на 1. Какой начальный номер,
до миллиона производит самую длинную цепочку?
#include<stdio.h>
int main() {
int limit = 1000000;
int highNum, number, i;
int highCount = 0;
int count = 0;
for( number = 13; number <= 1000000; number++ )
{
i = number;
while( i != 1 ) {
if (( i % 2 ) != 0 ) {
i = ( i * 3 ) + 1;
count++;
}
else {
count++;
i /= 2;
}
}
count++;
printf( "So Far: the number with the highest count: %d with the count of %d\n",
number, count );
if( highCount < count ) {
highCount = count;
highNum = number;
}
count = 0;
//break;
}
printf( "The number with the highest count: %d with the count of %d\n",
highNum, highCount );
}
Решение
Вы получаете целочисленное переполнение. Обновите свой код следующим образом и убедитесь сами:
if (( i % 2 ) != 0 ) {
int prevI = i;
i = ( i * 3 ) + 1;
if (i < prevI) {
printf("oops, i < prevI: %d\n", i);
return 0;
}
count++;
}
Вы должны изменить тип i в long long или же unsigned long long чтобы предотвратить переполнение.
(И да, кешируем промежуточные результаты)
Другие решения
Запомните все промежуточные результаты (до некоторого подходящего большого числа).
Также используйте достаточно большой тип:
#include <stdio.h>
static int collatz[4000000];
unsigned long long collatzmax;
int comp(unsigned long long i) {
if(i>=sizeof collatz/sizeof*collatz) {
if(i>collatzmax)
collatzmax = i;
return 1 + comp(i&1 ? 3*i+1 : i/2);
}
if(!collatz[i])
collatz[i] = 1 + comp(i&1 ? 3*i+1 : i/2);
return collatz[i];
}
int main() {
collatz[1] = 1;
int highNumber= 1, highCount = 1, c;
for(int i = 2; i < 1000000; i++)
if((c = comp(i)) > highCount) {
highCount = c;
highNumber = i;
}
printf( "The number with the highest count: %d with the count of %d\n",
highNumber, highCount );
printf( "Highest intermediary number: %llu\n", collatzmax);
}
По колиру: http://coliru.stacked-crooked.com/a/773bd8c5f4e7d5a9
Вариант с меньшим временем выполнения: http://coliru.stacked-crooked.com/a/2132cb74e4605d5f
The number with the highest count: 837799 with the count of 525
Highest intermediary number: 56991483520
КСТАТИ: для наивысшего встреченного посредника необходимо 36 бит для представления в качестве числа без знака.
С помощью вашего алгоритма вы вычисляете несколько одинаковых по времени рядов.
Вы можете кэшировать результат для предыдущих чисел и использовать их повторно.
Что-то вроде:
void compute(std::map<std::uint64_t, int>& counts, std::uint64_t i)
{
std::vector<std::uint64_t> series;
while (counts[i] == 0) {
series.push_back(i);
if ((i % 2) != 0) {
i = (i * 3) + 1;
} else {
i /= 2;
}
}
int count = counts[i];
for (auto it = series.rbegin(); it != series.rend(); ++it)
{
counts[*it] = ++count;
}
}
int main()
{
const std::uint64_t limit = 1000000;
std::map<std::uint64_t, int> counts;
counts[1] = 1;
for (std::size_t i = 2; i != limit; ++i) {
compute(counts, i);
}
auto it = std::max_element(counts.begin(), counts.end(),
[](const std::pair<std::uint64_t, int>& lhs, const std::pair<std::uint64_t, int>& rhs)
{
return lhs.second < rhs.second;
});
std::cout << it->first << ":" << it->second << std::endl;
std::cout << limit-1 << ":" << counts[limit-1] << std::endl;
}
демонстрация (10 секунд)
Не пересчитывайте одни и те же промежуточные результаты снова и снова!
Дано
typedef std::uint64_t num; // largest reliable built-in unsigned integer type
num collatz(num x)
{
return (x & 1) ? (3*x + 1) : (x/2);
}
Тогда значение collatz(x) зависит только от x, а не когда вы это называете. (Другими словами, collatz это чистая функция.) Как следствие, вы можете memoize значения collatz(x) для разных значений x, Для этого вы можете использовать std::map<num, num> или std::unordered_map<num, num>,
Для справки, Вот это полное решение.
И вот оно на Coliru, со временем (2,6 с).