我正在处理欧拉计划的第8个问题,我被要求“找出这个1000位数中乘积最大的13个相邻数字,这个乘积的值是多少?”
这是我的C++代码。由于某种原因,它总是给我错误的答案,我强烈怀疑这与我使用错误的数据类型有关。任何帮助都将不胜感激。
{
int n = 0;
unsigned long long x, y;
signed char num[] = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450";
while(n <= 1000)
{
x = (num[n] - 48) * (num[n + 1] - 48) * (num[n + 2] - 48) * (num[n + 3] - 48) * (num[n + 4] - 48) * (num[n + 5] - 48) * (num[n + 6] - 48) * (num[n + 7] - 48) * (num[n + 8] - 48) * (num[n + 9] - 48) * (num[n + 10] - 48) * (num[n + 11] - 48) * (num[n + 12] - 48);
std::cout << "x" << x << std::endl;
if(x > y)
{
y = x;
}
n = n + 1;
}
std::cout << "y" << y << std::endl;
std::cout << "n" << n << std::endl;
}
4条答案
按热度按时间eaf3rand1#
首先,你没有像其他人在评论中说的那样初始化y。
第二,这个表达式
(num[n] - 48) * (num[n + 1] - 48) * (num[n + 2] - 48) * ...
将以int
精度完成,因为小于int的类型将在执行算术运算之前提升为int改成
以便以
unsigned long long
精度计算表达式。使用“0”而不是48,因为它更清楚地表达了意图,并且无论'0'
的值如何,它都将工作当n〉= 1000-12时,您还可以进行越界访问。请改用
for
如果您认识到在每次迭代中计算乘积时存在一些重叠,则可以进一步改进它
gojuced72#
One major problem as pointed in the other answer, is that your result will be taken as
int
, exceeding the maximum value ofInt32
leading to the wrong answer.Your while will iterate 1 extra index too.The line where you calculatex
can be done much better currently it's hard to follow what's going on and it's hard to maintain.I recommend first creating a constant integer which will have the value of the desired adjacent digits in your case 13.
This should do the job now you should also fix the
while
loop :Here we use the const we declared earlier so if we want the code to work for a different amount of adjacent digits we can simply just change the variable responsive for that.
You should give a starting value to
y
Now going into the while loop we see the long line I spoke of earlier. We can easily edit this to something like :
This is much easier to read and it will remove the use of casting. Now one problem with your current set up your variable 'x' is declared in the outer scope (outside of the loop), and here rather than just setting the variable value we are multiplying it which means we need to reset the variable back to 0 once we are done multiplying. There are 2 ways that you can do this you can either set it to zero at the end of the loop or simply declare it in the while loop which I prefer. It's also important to put the value of
x
to 1 instead of 0..After this we simply keep your original check that determines whether we have found a new number.
At the end we just print
y
Here's the full code :
You might also want to use a little bit more reasonable names
x
andy
sound a little bit like variables that are used in a grid.. For example You can simply changey
tomaxNumber
andy
totempNumber
.kgsdhlau3#
我想我应该分享我的解决方案,以及一个要求其他Scala解决方案的答案。我不是说这在任何方面更好,只是一个稍微不同的方法。而且,我认为
String.substring()
很慢(线性时间复杂度),所以我决定不使用它。还包括一个小的优化与零的处理,没有讨论其他答案:如果在接下来的(13)个数字中存在0,则可以跳过所有这些数字,因为0也将被包括在它们的范围中。
fivyi3re4#
我用Golang解决了这个问题,实际上我所做的是从左右两侧(字符串的开始和结束)阅读系列,以获得一点性能: