Euler вопрос проекта 14 (проблема Collatz)
Следующая повторяющаяся последовательность определяется для набора положительных целых чисел:
n-> n/2 (n даже), n-> 3n + 1 (n нечетно),
Используя правило выше и запускающийся с 13, мы генерируем следующую последовательность:
13 40 20 10 5 16 8 4 2 1 Таким образом эта последовательность (запускающийся в 13 и заканчивающийся в 1) содержит 10 условий. Хотя это еще не было доказано (проблема Collatz), считается, что все стартовые числа заканчиваются в 1.
Какое стартовое число, под один миллион, производит самую длинную цепочку?
Примечание: После того как цепочка запускается, условиям позволяют выйти за предел один миллион.
Я пытался кодировать решение этого в C использование метода "в лоб". Однако кажется, что моя программа останавливается при попытке вычислить 113383. Советуйте :)
#include <stdio.h>
#define LIMIT 1000000
int iteration(int value)
{
if(value%2==0)
return (value/2);
else
return (3*value+1);
}
int count_iterations(int value)
{
int count=1;
//printf("%d\n", value);
while(value!=1)
{
value=iteration(value);
//printf("%d\n", value);
count++;
}
return count;
}
int main()
{
int iteration_count=0, max=0;
int i,count;
for (i=1; i<LIMIT; i++)
{
printf("Current iteration : %d\n", i);
iteration_count=count_iterations(i);
if (iteration_count>max)
{
max=iteration_count;
count=i;
}
}
//iteration_count=count_iterations(113383);
printf("Count = %d\ni = %d\n",max,count);
}
5 ответов
Причина задержки в том, что вы проходите через число больше 2 ^ 31-1 (также известное как INT_MAX ); попробуйте использовать unsigned long long вместо int .
Я недавно писал об этом в блоге ; обратите внимание, что в C наивный итерационный метод более чем достаточно быстр. Для динамических языков вам может потребоваться оптимизация с помощью мемоизации, чтобы подчиниться правилу одной минуты (но здесь это не так).
Ой, я сделал это снова (на этот раз изучая дальнейшие возможные оптимизации с использованием C ++).
Обратите внимание, что ваше решение методом грубой силы часто вычисляет одни и те же подзадачи снова и снова. Например, если вы начнете с 10 , вы получите 5 16 8 4 2 1 ; но если вы начнете с 20 , вы получите 20 10 5 16 8 4 2 1 . Если вы кешируете значение 10 после вычисления, вам не придется вычислять его заново.
(Это известно как динамическое программирование .)
Я решил проблему некоторое время назад, и, к счастью, мой код все еще у меня. Не читайте код, если вам не нужен спойлер :
#include <stdio.h>
int lookup[1000000] = { 0 };
unsigned int NextNumber(unsigned int value) {
if ((value % 2) == 0) value >>= 1;
else value = (value * 3) + 1;
return value;
}
int main() {
int i = 0;
int chainlength = 0;
int longest = 0;
int longestchain = 0;
unsigned int value = 0;
for (i = 1; i < 1000000; ++i) {
chainlength = 0;
value = i;
while (value != 1) {
++chainlength;
value = NextNumber(value);
if (value >= 1000000) continue;
if (lookup[value] != 0) {
chainlength += lookup[value];
break;
}
}
lookup[i] = chainlength;
if (longestchain < chainlength) {
longest = i;
longestchain = chainlength;
}
}
printf("\n%d: %d\n", longest, longestchain);
}
time ./a.out
[don't be lazy, run it yourself]: [same here]
real 0m0.106s
user 0m0.094s
sys 0m0.012s
Как было сказано, самый простой способ - получить некоторую память, чтобы избежать повторного вычисления того, что не было вычислено. Возможно, вам будет интересно узнать, что цикла не существует, если вы принадлежите к числу менее миллиона (цикл еще не обнаружен, и люди исследовали гораздо большие числа).
Чтобы перевести это в код, вы можете думать в стиле Python:
MEMOIZER = dict()
def memo(x, func):
global MEMOIZER
if x in MEMOIZER: return MEMOIZER[x]
r = func(x)
MEMOIZER[x] = r
return r
Мемоизация - это очень общая схема.
Что касается гипотезы Коллатце, вы можете оказаться в затруднительном положении, потому что числа действительно могут расти и, следовательно, вы можете взорвать доступную память.
Это традиционно выполняется с помощью кэширования, вы кешируете только последние n результатов (с учетом того, что они занимают заданный объем памяти), и когда у вас уже есть n элементов в кэше и вы хотите добавляешь более новую, старую отбрасываешь.
Для этой гипотезы может быть доступна другая стратегия, хотя ее немного сложнее реализовать. Основная идея состоит в том, что у вас есть только способы достичь заданного числа x :
- из
2 * x - из
(x-1) / 3
Следовательно если вы кешируете результаты 2 * x и (x-1) / 3 , то больше нет смысла в кешировании x >> это никогда не будет вызывать больше (кроме случаев, когда вы хотите напечатать последовательность в конце ... но только один раз).Я предоставляю вам воспользоваться этим преимуществом, чтобы ваш кеш не увеличивался слишком сильно :)
Только что протестировав его в C # кажется, что 113383 - это первое значение, в котором 32-битный тип int становится слишком маленьким для хранения каждого шага в цепочке.
Попробуйте использовать unsigned long при работе с такими большими числами;)