程序设计竞赛试题选(02)

2.质数竖式
    下面的竖式是一个乘法运算问题，它的每个＊号可以代入一个数字，这个数字属于一个特定的由N个数字组成的集合。假如这个集合是｛2，3，5，7｝，那么这个竖式称作“质数竖式”。
　　　　* * *
     X    * *
     ---------
       * * *
     * * *
   -----------
     * * * *
    写一个程序找出对应于集合｛1，2，3，4，5，6，7，8，9｝的任意一个子集的所有竖式。用集合｛2，3，4，6，8｝和质数集合｛2，3，5，7｝来测试你的程序。
运行举例：
ENTER　A　SET　OF　DIGITS:23468
        2 2 2
     X    2 2
    ----------
        4 4 4      <还有3个竖式未显示>
      4 4 4
    ----------
      4 8 8 4
    The number of unique solutions=4

(1)解题思路
  　此题比较简单,只需对两个乘数进行循环，然后判定竖式中的数是否满足要求，需注重的一点是：乘积可能超出整型的范围　，需要用长整型来计算。
(2)参考程序
Var num:Set Of Byte;                {数字集合}
    n:Word;                         {竖式的数目}
procedure Init;                     {读入数据并初始化}
Var st:String;
    i:Word;
Begin
    Write('Enter a set of digits:');
    Readln(St);                     {以字符串的形式读入}
    Num:=[];
    For i:=1 To Length(st) Do
        include(Num,Ord(St[i]-Ord('0'));
        n:=0;
End;

Function Ok(x:Longint):Booklean;         {判定x的每位数是否都在集合中}
Begin
    Ok:=False;
    While x>0 Do
    Begin
        If Not((x Mod 10)In Num)Then Exit;
        x:=x Div 10;
    End;
    Ok:=True;
End;

Procedure Cacl;        {找出满足条件的竖式}
    Var i,j:Longint;
    Begin
        For i:=111 To 999 Do
            If Ok(i) Then
                For j:=11 To 99 Do          {对两个乘数进行循环}
                    If Ok(j) And Ok(j Mod 10)*i)And Ok((j Div 10)*i)
                        And Ok(i*j) Then
                        Begin
                            Inc(n);
                            Writeln('<',n,'>');
                            Writeln(i:6);
                            Writeln('X',j:4);
                            Writeln('-----------');
                            Writeln((i Mod 10)*i:6);
                            Writeln((j Mod 10)*i:6);
                            Writeln((j Div 10)*i:5);
                            Writeln('------------');
                            Write(i*j:6);
                        End;
              Writeln('The number of unique solutions=',n);
            End;
            Begin
                Init;                     {读入数据并初始化}
                Cacl;                     {找出满足条件的竖式}
            End.

(3)运行结果
    Enter a set of digits:2357
{1}
        7 7 5
     X    3 3
    ----------
      2 3 2 5
    2 3 2 5
   -----------
    2 5 5 7 5
    The number of unique solutions=1