帕斯卡高精度乘法和 N 冪問題

它通常是用倒置陣列完成的。

樓上的精度不高。

我會為你寫乙個乘法。

typearr=array[0..10000]of longint;a[0] 是長度。

function cheng(a,b:arr):arr;

vari,j:longint;

beginfillchar(cheng,sizeof(cheng),0);

for i:=1 to a[0] do

for j:=1 to b[0] do begin

cheng[i+j-1]:=cheng[i+j-1]+a[i]*b[j];

cheng[i+j]:=cheng[i+j]+cheng[i+j-1]mod 10;

cheng[i+j]:=cheng[i+j]div 10;

end;if cheng[a[0]+b[0]]>0 then cheng[0]:=a[0]+b[0] else cheng[0]:=a[0]+b[0]-1;

end;

讓我們分解一下：

設字串的長度為 n，乘數符號為 k，如果 n = 50 且 k = 1，則有 （n-1） = 49 個不同的乘法，當 k = 2 時，有 c（2， 50-1） = 1176 個乘法，即 c（k， n-1） 乘法，當 n 和 k 稍大時，窮舉法將不起作用。

設數字字串為 a1a2...。an

當 k=1：可以在 a1a2 中插入乘數符號時。n-1 個位置，因此我們得到 n-1 個子字串的乘積：

a1*a2…an,a1a2*a3…an,a1a2…Fortune Bird A（幸運鳥A）

n-1*an

這相當於一種詳盡的方法）。

此時的最大值 = 最大值

設 f[i，j] 表示 in。

i 數字。

J乘數符號的最大值G[i，j]表示從AI到AJ的數字列，肢源可以得到動態傳遞方程：

f[i,j]

max1<=i<=n,1<=j<=k)

邊界：f[i，0]。

g[1,i]

序列本身）階段：子問題是插入 j-1、j-2 ......新增到子字串中1,0 個乘數符號，因此乘數符號的數量用作階段（j 階段）的劃分。

狀態：隨著相乘序列的變化，每個階段都分為多個狀態。

決策：在每個州的每個階段做出決策。

資料結構：本題對精度要求不高，longint 可用於 pascal）。

intn,k;

n 是數字數，k 是除數*

inti,j,l;

迴圈變數*

charc;

字元以 * 格式讀取

intdata[50]=;

數字陣列*

intg[50][50],f[50][10];

g 是數值列，f 是動態規劃陣列*

初始化：cin

nk;*讀取，n，k*

for(i=1;i<=n;i++)cin

c;*讀入數字*

data[i]=c-'0';

字元轉換為數字*

g[i][i]=data[i];初始化序列*

for(i=1;i<=n-1;i++)

for(j=i+1;j<=n;j++)

g[i][j]=g[i][j-1]*10+data[j];

初始化序列*

for(i=1;i<=n;i++)

f[i][0]=g[1][i];

初始化動態規劃陣列*

動態規劃：for（i=1; i<=n;i++） 方程：f[i，j] 表示將 j * 符號插入前 i 個數字的最佳值。*/

for(j=1;j<=i+1;j++)

for(l=1;l<=i-1;l++)

f[i][j]=max(f[i][j],f[l][j-1]*g[l+1][i]);

輸出 f[n][k]。