Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

A 2001. novemberi informatika feladatok megoldása

A közöltek csak megoldásvázlatok, esetleg csak végeredmények. A maximális pontszám eléréséhez általában ennél részletesebb megoldás szükséges. A részletes megoldásokat a beküldött dolgozatok alapján a KöMaL-ban folyamatosan közöljük.

I. 7. A Faktoriális(N) függvény rendkívül gyorsan növekszik. Míg az 5!=120, addig már a 10!=3 628 800 ábrázolásához 4 byte-os egész számokra van szükség. A 100! pedig már csak speciális matematikai programokkal kezelhető.

Tudjuk azonban, hogy minden természetes számnak elkészíthető a prímtényezős felbontása. Például:

5!=23.3.5      10!=28.34.52.7.

Készítsünk programot, amely beolvassa billentyűzetről N értékét (1leNle10 000), majd kiírja a képernyőre az N! prímtényezős felbontását. (10 pont)

A feladat egy N szám faktoriális függvényének prímtényezős felbontásának elkészítése. Bemenő adat egy N természetes szám, mely legalább egy. A kimenő adat egy sorozat, mely szám-párokat tartalmaz, a prímosztókat, illetve azok multiplicitásait. Az össze prímet N-ig, olyan multiplicitással, hogy az összes szorzata N!-t adja.

Ehhez a feladatértelmezéshez (specifikáció) keresünk algoritmust.

Két megoldást is közlünk, melyeknek eredménye természetesen ugyanaz.

Az első megoldás értelmezése:

Pascal program:

Program faktorialis;
  uses newdelay,crt;
  const maxprim=5000;
  type primfelbontas=record
                       db: integer;
                       elem: array [1..maxprim] of record
                                                     prim,kitevo: integer
                                                   end;
                     end;
  var fakt,akt: primfelbontas;
      i,j,n: integer;

  Procedure Primtenyezok(i: integer;var akt: primfelbontas);
    var j:integer;

    Function prim(j: integer): Boolean;
      var k: integer;
    begin
      k:=2;
      while (k*k<=j) and ((j mod k)>0) do k:=k+1;
      prim:=k*k>j;
    end;

  begin
    j:=2; akt.db:=1; akt.elem[1].prim:=j; akt.elem[1].kitevo:=0;
    while j<=i do
    begin
      if i mod j=0 then
      begin
        akt.elem[akt.db].kitevo:=akt.elem[akt.db].kitevo+1;
        i:=i div j;
      end
      else
      begin
        j:=j+1;
        while (j<=i) and not prim(j) do j:=j+1;
        if j<=i then
        begin
          akt.db:=akt.db+1;
          akt.elem[akt.db].prim:=j; akt.elem[akt.db].kitevo:=0;
        end;
      end;
    end;
    if akt.elem[akt.db].kitevo=0 then akt.db:=akt.db-1;
  end;
begin
  clrscr; writeln('                          Faktoriális számítás'); writeln;
  repeat
    write('Minek a faktoriálisát számoljam ki?'); readln(n);
  until (1<=N) and (n<=10000);
  writeln(n,'! felbontása:'); writeln;
  if n=1 then writeln(1) else
  begin
    fakt.db:=1; fakt.elem[1].prim:=2; fakt.elem[1].kitevo:=1;
    for i:=3 to n do
    begin
      Primtenyezok(i,akt);
      for j:=1 to akt.db do
        fakt.elem[j].kitevo:=fakt.elem[j].kitevo+akt.elem[j].kitevo;
      if fakt.db<akt.db then
      begin
        fakt.db:=fakt.db+1; fakt.elem[fakt.db]:=akt.elem[fakt.db];
      end;
    end;
    for i:=1 to fakt.db do write('prím=',fakt.elem[i].prim,
                                 '  kitevő=',fakt.elem[i].kitevo,' , ');
  end;
  readln;
end.

A második megoldás értelmezése:

A Legendre-formulát kódoljuk, ami a következő. Minden p prímre és N pozitív egészre igaz, hogy N! prímtényezős felbontásában a p kitevője

\(\displaystyle \left[{N\over p}\right]+\left[{N\over p^2}\right]+\left[{N\over p^3}\right]+\dots\).

Természetesen ennek a sornak a tagjai valahonnan kezdve nullák, ugyanis N<pi esetén az egészrész nulla lesz.)

Pascal program:

Program Faktorialis;
  Var
    N,p:LongInt;
  Function kitevo(pp,NN:LongInt):LongInt;
    Var
      k,ppp:LongInt;
  Begin
    k:=0;
    ppp:=pp;
    While ppp<=NN do begin
      k:=k+trunc(nn/ppp);
      ppp:=ppp*pp;
    end;
    kitevo:=k;
  end;
  Procedure KovetkezoPrim(Var p:LongInt);
    Function prim(j: LongInt): Boolean;
      var k: LongInt;
    begin
      k:=2;
      while (k*k<=j) and ((j mod k)>0) do k:=k+1;
      prim:=k*k>j;
    end;
  Begin
    p:=p+2;
    While Not prim(p) do
      p:=p+2;
  end;
Begin
  WriteLn('N faktorialis (N!) primtenyezos felbontasa:');
  WriteLn;
  Write('Add meg N értékét! :');
  ReadLn(N);
  WriteLn;
  WriteLn('A prímtényezős felbontás:');
  WriteLn;
  If N=1
    Then WriteLn(1);
  p:=2;
  If p<=N
    Then Write(p:5,' a ',kitevo(p,N):5,'-n    |');
  p:=3;
  While p<=N do begin
    Write(p:5,' a ',kitevo(p,N):5,'-n    |');
    KovetkezoPrim(p);
  end;
  ReadLn;
End.

I. 8. Egy kutya úgy úszik át a folyón a túlparton álló gazdájához, hogy minden pillanatban a gazdi irányába igyekszik. Ezt a mozgást kell közelítő módszerrel modellezni, és a képernyőre kirajzolnod. Ehhez a következő, valós értékű paramétereket kell beolvasnia a programnak a billentyűzetről:

(a) A folyó szélességét méterben.

(b) A gazda távolságát méterben a kutya kezdőpontjának vetületétől a túlparton (pozitív, ha a folyásiránnyal azonos irányban van, negatív az ellenkező esetben).

(c) A kutya sebességét (m/s, nagysága állandó).

(d) A folyó sebességét (m/s, a folyó minden pontjában állandó nagyságú).

(e) A közelítés pontosságát, azaz annak az időintervallumnak a hosszát másodpercekben, amelyen belül a program egyenes vonalú mozgással számolhat.

A folyó két partját párhuzamos egyeneseknek tekintjük. A modellezés akkor álljon le, amikor a kutya már egy méternél közelebb kerül a túlsó parthoz.

Rajzoljuk ki a két partot jelző vízszintes egyeneseket, a kutya és a gazda kezdőhelyzetét és a kutya útját. (10 pont)

Ennek a szimulációnak az ábrázolásakor egyszerű átszámolási módszert használunk a valós koordinátarendszer és a képernyőn való megjelenítés tengelyei között. Egy méternek egy pixel fog megfelelni, illetve a képernyőn való ábrázolásnak megfelelően az x-tengely értékei jobbra nőnek, az y-tengely értékei pedig (a képernyő címzésének megfelelően, de a fizikában megszokottal ellentétben) a monitor alsó része felé nőnek.

Kódértelmezés:

Pascal program:

Program Uszo_kutya;
  Uses
    Graph;
  Var
    gd,gm:Integer;
    a,b,c,d,e,t:Real;
    szog,gx,gy,kx,ky:Real;
    hiba:Boolean;
  Procedure OpenGraph;
  Begin
    DetectGraph(gd,gm);
    InitGraph(gd,gm,'c:\langs\bp\bgi');
  End;

Begin
  WriteLn('Kutya úszik a folyón.');
  Write('Add meg a folyó szélességét! :');
{  a:=200;{}
  ReadLn(a);
  Write('Add meg a gazdi távolságát a partra vetítve! :');
{  b:=100;{}
  ReadLn(b);
  Write('Add meg a kutya sebességét! :');
{  c:=5;{}
  ReadLn(c);
  Write('Add meg a folyó sebességét! :');
{  d:=6;{}
  ReadLn(d);
  Write('Add meg az időlépés nagyságát! :');
{  e:=1;{}
  ReadLn(e);
  OpenGraph;
  Line(10,10,GetMaxX-10,10);
  Line(10,trunc(a+10),GetMaxX-10,trunc(a+10));
  Circle(20,trunc(a+10),2);
  Circle(trunc(20+b),10,2);
  Circle(trunc(20+b),10,4);
  hiba:=FALSE;
  If c=0
    Then hiba:=True
    else begin
      kx:=20;
      ky:=a+10;
      gx:=20+b;
      gy:=10;
      t:=0;
      SetColor(Red);
      MoveTo(trunc(kx),trunc(ky));
      While ky-gy>1 do begin
        If gx-kx<>0
          Then szog:=arctan((gy-ky)/(gx-kx))
          Else szog:=pi/2;
        If szog>0
          Then szog:=szog+pi;
        SetColor(Blue);
        Line(trunc(kx),trunc(ky),trunc(kx+10*c*cos(szog)),trunc(ky+10*c*sin(szog)));
        SetColor(Red);
        kx:=kx+(c*cos(szog)+d)*e;
        ky:=ky+c*sin(szog)*e;
        LineTo(trunc(kx),trunc(ky));
        t:=t+e;
    {    ReadLn;{}
      end;
      ReadLn;
    End;
  CloseGraph;
  If hiba
    Then WriteLn('Ha nem úszik, nem ér oda.')
    else WriteLn(t:15:2,(kx-20-b):15:2);
  ReadLn;
End.{_Uszo_kutya}

I. 9. A binomiális együtthatók szokásos elrendezése (Pascal háromszög) az ábrán látható alakú lehet. A szélső elemek kivételével mindegyikre igaz, hogy a fölötte levő és az attól eggyel balra levő elem összege.

Készítsünk Excel táblázatot, amely ilyen módon képes megadni a Pascal háromszög első N+1 sorát! Az első sor hetedik cellájába lehessen beírni N értékét (1leNle20), és a táblázat minden esetben pontosan N+1 sorból álljon! (10 pont)

1     N=6
11      
121     
1331    
14641   
15101051  
1615201561 

A megoldás nagyon egyszerű, hiszen a Pascal háromszögről ismeretes, hogy egy elemét úgy kapjuk, hogy a két fölötte elhelyezkedőt összeadjuk. Most a táblázatunkban kicsit "megbillent" a háromszög, így a fölötte levő elemet és az amellettit kell összeadni.

Tehát a megoldás:

Az A oszlopban: =HA(SOR()<=$H$1+1;1;""), mindenhol vagy egyes szerepel, vagy semmi. Annak megfelelően, hogy N+1 sort kell kiírni, vagyis attól függően, hogy a sor sorszáma mennyi.

A többi helyre beírt képlet a következő: =HA(SOR()<=$H$1+1;C5+D5;""), hiszen itt is csak azokat a sorokat kell kiírni, ahol a sor sorszáma maximum N+1 ($H$1 helyen van N értéke), itt a példában a D6-os cellába beírt képlet szerint a a D5-ös és C5-ös cellák értékét kell összeadni.

Egyszerű a kitöltés is, hiszen automatikusan növeli az Excel a kitöltéskor a cellák sor- és oszlopazonosítóit. Arra kell csak vigyázni, hogy a második sorban ne legyen semmi a hatodik cellától kezdve, különben hibás lesz az egész háromszög, hiszen egy karakterrel nem tudunk összeadást végezni.

A megoldás letölthető innen.