2008年2月4日 星期一

Problem 619 Numerically Speaking,數字與文字轉換處理

題目真的不難,但是卻囉唆的要死。
這其實是一個26進位的系統,從1-26,以a-z來代表,不是0-25。我用了p324中的乘法函數,稍作修改,另外也增加了加、減、除等三個函數,用來處理以short陣列所代表的大型數字之加減乘除。
因為常用到以26為底的指數,所以一開始就先利用乘法函數,將26的1~20次方的數字先儲存起來,後來再計算時就會很快。這題有許多字串轉數字陣列的地方,我想或許有更快的方法,不用轉來轉去。另外,也許有一些處理大數字的函式庫可以呼叫應用,但我想自己寫會快些,反正乘法函數已經有了,其他的就類似,甚至更簡單。
這題有個簡單的地方,就是範例做的出來,上傳應該一次就OK,不像有的題目,完成範例不見得上傳就一定會過。像那種題目就很令人睹爛,也不知道錯在哪裡。
下面列出了乘法與減法的函數。
void multiply(short prod[], short multiplier[], int num)
{
short tempSum[DSIZE];
int digitNum, addOn, temp, i, j;

for (i=0;i<DSIZE;i++)
tempSum[i] = 0;
for (i=0;i<DSIZE;i++)
{
temp = num * multiplier[i];
digitNum = floor(log10(temp)+1);
addOn = 0;
for (j=i;j<i+digitNum;j++)
{
tempSum[j] += temp%10 + addOn;
if (tempSum[j]>9)
{
tempSum[j] %= 10;
addOn = 1;
}
else
addOn = 0;
temp /= 10;
}
if (addOn==1)
tempSum[j]++;
}
for (i=0;i<DSIZE;i++)
prod[i] = tempSum[i];
}
int minus(short diff[], short temp[])
{
int minusOn, len=0, i;
for (i=DSIZE-1;i>=0;i--)
{
if (diff[i]-temp[i]<0)
return 0;
else if (diff[i]-temp[i]>0)
{
len = i+1;
break;
}
}
minusOn = 0;
for (i=0;i<DSIZE;i++)
{
diff[i] = diff[i] - temp[i] + 10 - minusOn;
if (diff[i]>=10)
{
diff[i] %= 10;
minusOn = 0;
}
else
minusOn = 1;
}
return 1;
}

p619題目連結
回ACM題庫目錄
回首頁

沒有留言: