[问题描述] 一个正整数(非素数)可表示成它的因子(1与其本身除外)的乘积。
例如:12有因子2,3,4,6,所以可表示为:
12=2*2*3=4*3=2*6
给出任一个正整数N,求出它所有的因子乘积的表达式(交换律得出的不同式子算同一种)。
[算法说明] 读入一个整数N,首先求出它的所有的因子以及每个因子可能的次数。
例如:整数48:
因子:2 3 4 6 8 12 16 24
次数:4 1 2 1 1 1 1 1
将上面的结果存入数组A:ARRAY[0..20,1..2]中。其中:A[?,1]表示因子;A[?,2]表示次数。
然后用简单回溯的方法求出所有可能的表示。
数组B[0..20]记录取数情况;C:ARRAY[0..20]工作单元。
[程序清单]
program exp4(input,output);
var a : array[0..20,1..2] of integer;
c,b : array[0..20] of integer;
n,m,I,j,s,k,l : integer;
Begin
WRITELN;readln(n);
for i:=1 to 20 do a[i,1]:=0;
a[0,1]:=1 ; a[0..2]:=1; j:=0;
for i:=2 to n-1 do
begin
s:=0; m:=n;
while(m<>0) and (m mod i=0) do
begin
m:=m div i;
S:=S+1 ;
end;
if S>0 then begin
j:=j+1; a[J,1]:=i ;
a[j,2]:= S ;
end
end;
for i:=0 to j do b[i]:=0;
whil b[0]=0 do
begin
k:=j;
while b[k]:=a[k,2] do k:=k-1;
b[k]:=b[k]+1;
for L:= K+1 TO J do b[L]:=0;
s:=1;
for i:=1 to j do
if b[i]<>0 then for L:=1 to b[i] do
S:=S*a[i,1] ;
if s=n then begin
for i:=1 to j do c[i]:=b[i];
WRITE(‘(‘); M:=1;
for i:=1 to j do
while(c[i]>0) and (M<>N) do
begin
M:=M?A[i.1];
if M=N then write(a[i,j])
else begin
write(A[i,1],’?’);
c[i]:=c[i]-1;
end;
end;
writeln(‘)’);
end
end
End.