Экспонирование по квадрату (Project Euler 99) Советы по моему решению - PullRequest
0 голосов
/ 17 августа 2011

Вот проблема, о которой я говорю http://projecteuler.net/index.php?section=problems&id=99

Мой код скомпилируется и будет работать правильно. Я предполагаю, что вычисление - то, где это портит. Это говорит мне о том, что строка № 633 является самой большой (что, по словам Эйлера, неверно).

#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;
}

Ответы [ 2 ]

5 голосов
/ 17 августа 2011

Вы недооцениваете эту проблему.

Вам нужно придумать способ радикального уменьшения этих чисел, чтобы вы могли их сравнить.Другими словами, вы можете захотеть посмотреть, сколько цифр будет в результате.

Подсказка будет log (a ^ b) = b * log (a)

3 голосов
/ 17 августа 2011

32-битный тип int может содержать только 2 ^ 32 значения, и некоторые из них магически становятся отрицательными в какой-то момент ...

...