Почему эта программа, которая находит наименьшее число треугольников с & gt; 500 факторами, дает сбой?
Ниже я написал программу для решения Project Euler 12, которая включает в себя поиск наименьшего числа треугольника с более чем 500 факторами.
Я не думаю, что есть серьезные ошибки. Я подозреваю, что оптимизация памяти может быть проблемой. При этом, однако, мне нужно длинное int без знака для большого числа треугольника, которое в конечном итоге будет ответом. Я начинаю свою последовательность натуральных чисел с triangleNumbers [0] = 10 000 000 000. Я знаю, что в 9 000 000 000 примерно 300 факторов, поэтому 10 000 000 000 были «наилучшим предположением». Однако, как говорится, я предполагаю, что 10 000 000 000 — это «первое натуральное число», и продолжаю добавлять последующие натуральные числа, чтобы получить «второе» натуральное число и далее (поэтому triangleNumbers [1] = 10 000 000 000 + 2, triangleNumbers [2] = 10 000 000 000 +3 и т. д.).
Любые предложения и советы будут оценены. Спасибо, что помогаете новичку совершенствоваться.
#include <iostream>
#include <vector>
#include <math.h>
using namespace std;
bool keepRunning=true;
unsigned long long int naturalNumberCount=0;
unsigned long long int j=4;
unsigned long long int sum=0;
vector <unsigned long long int> triangleNumbers(0);
unsigned long long int totalFactors=0;
unsigned long long int trialDivisors=1;
unsigned long long int storer=0;
int main()
{
triangleNumbers[0]=10000000000;
triangleNumbers[1]=10000000002;
triangleNumbers[2]=10000000005;
triangleNumbers[3]=10000000009;
triangleNumbers[4]=10000000014;
//listed first few prime numbers above. j is set at 4 for this reason
naturalNumberCount=5;
//10000000014 is the 5th triangle number, and 5 is the 5th natural num
//need this for recursive relation
//5th triangle number = 4th triangle num + 5 (num + naturalNumberCount
while(keepRunning)
{
for(trialDivisors;trialDivisors<=(unsigned long long int)(sqrt(triangleNumbers[j]));trialDivisors++)
{
if(triangleNumbers[j]%trialDivisors==0)
{
totalFactors++;
if(totalFactors>499)//499 because the number itself will be a divisor of itself, so no need to check
{
keepRunning=false;
break;
}
else
{
keepRunning=true;
}
}
else
{
keepRunning=true;
}
}
//need the below to generate and store the next triangle number (as next element of array)
naturalNumberCount++;//for recursive relation
storer=triangleNumbers[j];//store the (j+1)'th triangle number, since we are changing j itself
j++;//raise j, we gonna add the next value
triangleNumbers[j]=(storer+naturalNumberCount);//the new value (last triangle number + current natural)
totalFactors=0;//reset total factors to preclude any carry-over
}cout<<triangleNumbers[j]<<flush;
return 0;
}
Решение
TL;DR
#include <vector>
std::vector <unsigned long long int> triangleNumbers(0);
int main()
{
triangleNumbers[0]=10000000000;
}
У вас есть пустой вектор и самая первая строка в main приводит к неопределенному поведению, так как вы пытаетесь получить доступ к элементу 0 (такого пункта нет).
Живой пример с использованием оператора []
Живой пример, показывающий, что делает vector :: at ()
Обратите внимание, что вторая ссылка демонстрирует, что вы получаете доступ к элементу за пределами, используя at() вместо [ ] чтобы получить доступ к первому пункту.
Чтобы добавить элементы в std::vector, используйте один из методов, предназначенных для этого, а именно vector::push_back(), vector::insert(), vector::emplace_back(), vector::resize()или построить std::vector с необходимым количеством записей.
Самый простой из всех этих вариантов — создать вектор с использованием списка инициализаторов:
std::vector<unsigned long long int> triangleNumbers =
{10000000000, 10000000002, 10000000005, 10000000009, 10000000014};
Как только вы правильно настроите вектор, вам нужно посмотреть на остальную часть вашего кода, чтобы увидеть, где вы можете получить доступ к индексу за пределами допустимого. Особенно взглянуть на j в вашем цикле, и как вы используете его в качестве индекса. vector::at() Функция немедленно сообщит вам, если j выходит за пределы.
РЕДАКТИРОВАТЬ: Если вы действительно хотите синтаксис, который будет имитировать «автоматически расширяемый» массив, самое близкое к этому можно было бы использовать std::unordered_map<int, unsigned long long> как видно по этот пример.
Возможно map решение будет заменой — вам придется протестировать его.
Другие решения
Других решений пока нет …