Pirmojo etapo uždavinių sąlygos

8. RASKITE REIKŠMES. Paskalio kalbos funkcija užrašytas šitoks algoritmas:
function f (x: integer): integer;
  var n: integer;
begin
  n := x;
  while x > 2 do
    begin
      x := x - 2;
      n := n * x
    end;
  f := n
end;

Nesinaudodami kompiuteriu, apskaičiuokite šių reiškinių reikšmes:

a) f(4);
b) f(6) – f(5);
c) f(19) mod f(9);
d) f(10) div f(5);

9. H. LEDGARDO UŽDAVINYS. Turime sveikųjų skaičių masyvą, kurio elementai surikiuoti nemažėjančiai. Funkcija daug randa, koks skaičius masyve sutinkamas daugiausia kartų. Jeigu keli skaičiai pakartoti vienodai kartų, tinka bet kuris.

function daug (a: array[m..n : integer] of integer): integer;
  var i,           { elemento indekso numeris }
      r,           { ir elemento reikšmė }
      k,           { kelintas vienodas }
      sk: integer; { vienodų skaičius }
begin
  r := a[m];
  sk := 1; k := 1;
  for i := m + 1 to n do
    if a[i] = a[i-1]
       then begin
              k := k + 1;
              if k > sk
                 then begin
                        r := a[i];
                        sk := k
                      end
            end
       else k := 1;
  daug := r
end;

Sprendimas natūralus, logiškas. Tačiau algoritmą galima patobulinti bei sutrumpinti. Šiek tiek jį pakeitus galima išmesti kintamąjį k ir vieną sąlyginį sakinį. Padarykite tai.

10. KALADĖLIŲ PERDĖLIOJIMAS. Duota 1000 kaladėlių, išdėstytų eile. Ant kiekvienos kaladėlės užrašyta po vieną raidę. Ar galima kaladėles perdėlioti taip, kad nė viena raidė nebūtų toje pačioje vietoje? Reikia rasti bent vieną perdėliotų kaladėlių variantą.

Pagrįskite uždavinio sprendimą ir užrašykite algoritmą.

D = D₁ + D₂ + … + D_n

Buvo sutarta, kad teisingiausia būtų išdalyti taip, kad egzistuotų toks skaičius C ir būtų tenkinamos tokios sąlygos:

jei D_i < C, tai d_i = D_i;
jei D_i > C, tai d_i = C arba d_i = C + 1;
jei D_i <= D_j, tai d_i <= d_j;
d = d₁ + d₂ + … + d_n.

Kaip išdalyti diskelius, kad būtų tenkinamos išvardytos sąlygos?

Aprašykite uždavinio sprendimo idėją. Parašykite diskelių dalijimo algoritmą ir jį pagrįskite.

12. NULIŲ IR VIENETŲ SEKA. Nulių ir vienetų seka generuojama šitaip. Rašomas nulis – tai pirmasis sekos narys. Po to prie sekos prirašoma (pakartojama) jau esanti invertuota seka (t. y. nuliai pakeisti vienetais, o vienetai – nuliais). Taigi su kiekvienu žingsniu seka dvigubai pailgėja.

Žemiau parodyta, kaip formuojama seka:

0
0 1
0 1 1 0
0 1 1 0 1 0 0 1
0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0

Parašykite algoritmą n-ajam sekos nariui rasti.

1) kiekviena grupė būtų sudaryta iš N skaičių;
2) kiekvienas skaičius priklausytų tik vienai grupei;
3) visų grupių skaičių sumos būtų lygios.

14. DU ŽIRGAI. Šachmatų lentoje stovi baltas ir juodas žirgai. Reikia nustatyti, į kuriuos langelius gali eiti baltasis žirgas, kad jo nekirstų juodasis.

Pradiniai duomenys – pirma baltojo, po to juodojo žirgo koordinatės šachmatų lentoje. Horizontaliai (iš kairės į dešinę) – raidės a..h, vertikaliai (iš apačios į viršų) – skaitmenys 1..8.

Rezultatas – baltojo žirgo pozicijos, išvardytos laikrodžio rodyklės kryptimi pradedant nuo viršaus.

15. PASKALIO TRIKAMPIS. Paskalio trikampis atrodo šitaip:
    1
   1 1
  1 2 1
 1 3 3 1
1 4 6 4 1
. . . . .

Kiekvienos eilutės pirmasis ir paskutinis nariai lygūs 1, o kiti nariai lygūs virš jų esančių dviejų gretimų skaičių sumai.

Turime N degtukų, kuriuos reikia išdėlioti į krūveles pagal Paskalio trikampio skaičius. Parašykite algoritmą, kuris rastų, kokį didžiausią Paskalio trikampį galima sudėlioti iš degtukų krūvelės. Trikampio dydį reikia nurodyti jį sudarančių pilnų eilučių skaičiumi.

Tarkime, kad N = 13. Tuomet rezultatas turi būti 3 (trim eilutėms bus sunaudoti 7 degtukai, o likusiųjų 6 degtukų ketvirtajai eilutei nebeužtenka).