POJ Exponentiation解題
36518 ワード
Problem: 1001
User: Quincy
Memory: 260K
Time: 0MS
Language: C++
Result: Accepted Source Code
以前はフォルダの下を巡回していたので、ファイルとフォルダを再帰的に呼び出す方法を採用していました.その後,非再帰的な広さ優先アルゴリズムを用いて実現できることが分かったが,自分のコードよりも優れ,より優雅であると感じた.
私は多くの时に问题を解决してただそれを解决すればいいので、考えを変えることを考えていないので、自分のアルゴリズムの方面の知识を高めることを决めて、自分に异なる解决の考えをあげます.
最初は何度提出しても問題があったが、現実に10.0000を10に表示することに気づいた.10ではないので問題が発生しましたが、主にテスト例が全面的ではありません.
User: Quincy
Memory: 260K
Time: 0MS
Language: C++
Result: Accepted
// ExponentiationDemo.cpp : Defines the entry point for the console application.
//
#include <string.h>
#include <iostream>
using namespace std;
const int DATA_LENGTH=200;
const int INPUT_LENGTH=100;
struct LargeNumber
{
int dotIndex;
int dataLength;
char data[DATA_LENGTH];
};
struct InputNumber
{
LargeNumber number;
int power;
};
void MultiLargeNumber(const LargeNumber* num1, const LargeNumber* num2, LargeNumber* outResult)
{
int nLength1 = num1->dataLength;
int nLength2 = num2->dataLength;
LargeNumber tempValue;
memset(&tempValue, 0, sizeof(tempValue));
int ntempValueIndex = 0;
for (int i=nLength1-1; i >=0; --i, ntempValueIndex++)
{
int nCarryNum = 0;
int index = 0;
for (int j=nLength2-1; j >= 0; --j, ++index)
{
int nData = num1->data[i];
nData = nData * num2->data[j] + nCarryNum + tempValue.data[index+ntempValueIndex];
tempValue.data[index+ntempValueIndex] = nData % 10;
nCarryNum = nData / 10;
}
if (0!=nCarryNum)
{
tempValue.data[index+ntempValueIndex] = nCarryNum;
index++;
}
tempValue.dataLength = index + ntempValueIndex;
}
tempValue.dotIndex = num1->dotIndex + num2->dotIndex;
/// Reserve Result to num1;
memset(outResult, 0, sizeof(LargeNumber));
int nLengthResult = tempValue.dataLength;
for (int i=0; i < nLengthResult; ++i)
{
outResult->data[i] = tempValue.data[nLengthResult-i-1];
}
outResult->dotIndex = tempValue.dotIndex;
outResult->dataLength = tempValue.dataLength;
}
bool ConvertStrToNum(const string& str, LargeNumber* num)
{
int ndataIndex = 0;
bool bZero = true;
for(int i=0; i<str.length(); ++i)
{
char tempValue = str.at(i);
if (tempValue == '.')
{
num->dotIndex = str.length() - i - 1;
continue;
}
if (tempValue < '0' || tempValue > '9')
{
return false;
}
if (tempValue != '0')
{
bZero = false;
}
num->data[ndataIndex++] = tempValue - '0';
}
if (bZero)
{
num->dataLength = 0;
num->dotIndex = 0;
}
else
{
num->dataLength = ndataIndex;
}
return true;
}
void PrintLargeNumber(const LargeNumber* num)
{
char szResult[DATA_LENGTH] = {0};
int nResultIndex = 0;
int nLength = num->dataLength;
for (int i=0; i<nLength; ++i)
{
if (num->dotIndex == nLength-i)
{
szResult[nResultIndex++] = '.';
//strResult.push_back('.');
//cout << "." ;
}
szResult[nResultIndex++] = char(num->data[i]+'0');
//strResult.push_back(char(num->data[i]+'0'));
//cout << char(num->data[i]+'0');
}
/// Remove back zero
for (int i = nResultIndex-1; i >= 0; --i)
{
if (szResult[i] != '0')
{
if (szResult[i] == '.')
{
szResult[i] = 0;
}
break;
}
szResult[i] = 0;
}
/// Remove front zero
int nStartPos = 0;
for (; nStartPos < nResultIndex; ++nStartPos )
{
if (szResult[nStartPos] != '0')
{
break;
}
}
cout << (char*)(szResult+nStartPos) << endl;
}
int main()
{
char s[8];
int n;
//cin.get(s, 7);
//cin >> n;
InputNumber Inputs[INPUT_LENGTH] = {0};
int nInputCount = 0;
while(cin >> s >> n)
{
if (!ConvertStrToNum(s, &Inputs[nInputCount].number))
{
return 0; //continue;
}
Inputs[nInputCount].power = n;
++nInputCount;
}
int index=0;
while (index < nInputCount)
{
LargeNumber Result;
memcpy(&Result, &Inputs[index].number, sizeof(LargeNumber));
for (int i=0; i<Inputs[index].power-1; ++i)
{
MultiLargeNumber(&Inputs[index].number, &Result, &Result);
}
PrintLargeNumber(&Result);
++index;
}
return 0;
}
以前はフォルダの下を巡回していたので、ファイルとフォルダを再帰的に呼び出す方法を採用していました.その後,非再帰的な広さ優先アルゴリズムを用いて実現できることが分かったが,自分のコードよりも優れ,より優雅であると感じた.
私は多くの时に问题を解决してただそれを解决すればいいので、考えを変えることを考えていないので、自分のアルゴリズムの方面の知识を高めることを决めて、自分に异なる解决の考えをあげます.
最初は何度提出しても問題があったが、現実に10.0000を10に表示することに気づいた.10ではないので問題が発生しましたが、主にテスト例が全面的ではありません.