Book of tasks on programming. Old version

 

 by Aliaksandr N. Prykhodzka

 

протокол, registr, address, чайник, public, выбор, лекция, goto, сдвиг, директива, system, counter, inline, abstract, public, шестнадцатеричный, самообучение
 

Pascal. Answers. Pc.14. Realization of algorithms. Tasks of Дьюдени



главная страница


Pc.14.1



Pc.14.2


Первая попытка - напишем программу в предположении, что искомое число состоит не более, чем из 9-ти цифр, то есть, помещается в диапазон Longint.

Program E_5_2_2;
uses crt, dos;
label kkk;
var
      S : array[1..9] of 0..2;
      Per : 0..1;
      Pr, Prr : boolean;
      i : integer;
      LL : longint;
      MM : integer;
      Len, Num3, Num7 : integer;
begin
      Pr:=false;
      Prr:=false;

      for Len:=1 to 9 do begin

            for i:=1 to 9 do S[i]:=0;

            repeat
                  Prr:=true;
                  for i:=1 to Len do Prr:=Prr and (S[i]=1);

                  LL:=0;      MM:=0;      Num3:=0;      Num7:=0;
                  for i:=1 to Len do begin
                        LL:=LL*10;
                        if S[i]=0 then begin
                              LL:=LL+3;
                              MM:=MM+3;
                              Num3:=Num3+1
                        end
                        else begin
                              LL:=LL+7;
                              MM:=MM+7;
                              Num7:=Num7+1
                        end;
                  end;
                  Pr:=(LL mod 3=0) and (LL mod 7=0) and
                  (MM mod 3=0) and (MM mod 7=0) and
                  (Num3>0) and (Num7>0);

                  Per:=1;
                  for i:=1 to Len do begin
                        S[i]:=S[i]+Per;      Per:=0;
                        if S[i]=2 then begin
                              Per:=1;      S[i]:=0;
                        end;
                  end;

            until Pr or Prr;

            if Pr then goto kkk;

      end;

      LL:=0;

kkk:
      writeln(LL);
end.

Данная программа не нашла требуемое число. Следовательно, данное число состоит более, чем из 9-ти цифр. Перепишем эту программу с использованием символьной арифметики, в предположении, что искомое число состоит не более, чем из 250-ти цифр. Символьная арифметика описана в решении задачи P.36.1.

Program E_5_2_2A;
uses crt, dos, LargeNumbers;
label kkk;
var
      S : array[1..250] of 0..2;
      Per : 0..1;
      Pr, Prr : boolean;
      i : integer;
      LL, X3, X7, X10, XA, XB, XC, XD : string;
      MM : integer;
      Len, Num3, Num7 : integer;
begin
      Pr:=false;
      Prr:=false;

      X3:=LNAssign(3);
      X7:=LNAssign(7);
      X10:=LNAssign(10);

      for Len:=1 to 250 do begin

            for i:=1 to 250 do S[i]:=0;

            repeat
                  Prr:=true;
                  for i:=1 to Len do Prr:=Prr and (S[i]=1);

                  LL:=LNAssign(0);
                  MM:=0;      Num3:=0;      Num7:=0;

                  for i:=1 to Len do begin
                        LL:=LNMul(LL,X10);
                        if S[i]=0 then begin
                              LL:=LNAdd(LL,X3);
                              MM:=MM+3;
                              Num3:=Num3+1
                        end
                        else begin
                              LL:=LNAdd(LL,X7);
                              MM:=MM+7;
                              Num7:=Num7+1
                        end;
                  end;
                  LNDivMod(LL,X3,XA,XB);
                  LNDivMod(LL,X7,XC,XD);
                  Pr:=LNAskZero(XB) and LNAskZero(XD) and
                  (MM mod 3=0) and (MM mod 7=0) and
                  (Num3>0) and (Num7>0);

                  Per:=1;
                  for i:=1 to Len do begin
                        S[i]:=S[i]+Per;      Per:=0;
                        if S[i]=2 then begin
                              Per:=1; S[i]:=0;
                        end;
                  end;

            until Pr or Prr;

            if Pr then goto kkk;

      end;

      LL:=LNAssign(0);

kkk:
      writeln(LL);
end.

Данная программа нашла требуемое число. Это число есть 7337733333.



Pc.14.3


Поскольку в языке Паскаль нет типов чисел, содержащих большое число цифр, то напишем требуемую программу с использованием символьной арифметики.. Символьная арифметика описана в решении задачи P.36.1. Заметим, что эта программа реализует чисто переборный алгоритм и будет выполняться на компьютере с процессором Pentium несколько часов.

Program E_5_2_3;
uses crt, dos, LargeNumbers;
var
      X10, AA, BB, CC, XX000, R1, R2, XX : string;
      Pr : boolean;
      sh : integer;
begin
      X10:=LNAssign(10);
      AA:=LNAssign(123456789);
      BB:=LNAssign(100000009);
      XX:=LNAssign(987654321);
      XX000:=LNAssign(1000000000);

      sh:=0;
      repeat
            sh:=sh+1;
            CC:=LNMul(AA,BB);
            LNDivMod(CC,XX000,R1,R2);
            Pr:=(R2=XX);
            if not Pr then BB:=LNAdd(BB,X10);
            if sh>999 then begin
                  sh:=0;
                  writeln(BB);
            end;
      until Pr or (length(BB)>9);

      if not Pr then BB:=LNAssign(0);

      writeln('================');
      writeln('================');
      writeln('================');
      writeln(BB);
      writeln('================');
end.



Pc.14.4



Pc.14.5



Pc.14.6



Pc.14.7

 

©   Aliaksandr Prykhodzka    1993 - 2007