Exponentiation by Squaring (Project Euler 99) Tips on my solution
Here is the problem I am talking about http://projecteuler.net/index.php?section=problems&id=99
My code will compile and run correctly. I am guessing the computation is where it is messing up. It is telling me that line number 633 is the largest (which project euler says is incorrect).
#include <iostream>
#include <string>
#include <fstream>
using namespace std;
int poww(int base, int exp);
int main()
{
//ignore messy/unused variables. I am desperate
int lineNumber = 0;
string line;
int answerLine = 0;
int max =0;
int lineNum = 0;
int answer =0;
ifstream inFile;
size_t location;
string temp1,temp2;
int tempMax = 0;
int base,exp = 0;
inFile.open("C:\\Users\\myYser\\Desktop\\base_exp.txt");
while(getline(inFile,line))
{
lineNumber++;
location = line.find(",");
temp1 = line.substr(0,(int(location)));
temp2 = line.substr((int(location)+1),line.length());
//cout << temp1 << " " << temp2 << endl;
base = atoi(temp1.c_str());
exp = atoi(temp2.c_str());
tempMax= poww(base,exp);
if (tempMax > max){
max = tempMax;
answer = base;
answerLine = lineNumber;
}
}
cout << answer << " " << answerLine;
cin.get();
return 0;
}
int poww(int base, int exp)
{
int result = 1;
while (exp)
{
if (exp & 1)
开发者_开发技巧 result *= base;
exp >>= 1;
base *= base;
}
return result;
}
You're under-thinking this problem.
You need to come up with a way to scale down these numbers drastically so you can still compare them. In other words, you may want to look into a way of comparing how many digits the result will be.
A hint would be log(a^b) = b * log(a)
A 32-bit int can only hold 2^32 values, and some of those magically turn negative at some point...
精彩评论