CSES - Tehtävät

Pallot

Arvioi ensin 1-säteisen ympyrän pinta-alaa hylkäysotannalla. Tuloksen pitäisi olla suunnilleen 3.1413.141.

Entä 1-säteisen pallon tilavuus? Tai nn-ulotteisen hyperpallon?

Epäjärjestykset

Taulukon 1,2,,n1, 2, \dots, n järjestys on epäjärjestys, jos mikään luku ei ole alkuperäisellä paikallaan. Arvioi epäjärjestysten määrää hylkäysotannalla.

Sulkulausekkeet

Kelvollisessa sulkulausekkeessa on yhtä monta alku- ja loppusulkua ja kullakin sululla on pari lausekkeessa. Esimerkiksi seuraava on kelvollinen sulkulauseke:

()(())

Voitko hylkäysotannalla tuottaa satunnaisia kelvollisia lausekkeita? Entä arvioida niiden määrää?

Kokonaisluvut

Pussissa on k\lceil\sqrt{k}\,\rceil kappaletta lukua kk, kullekin k=1,2,,nk = 1, 2, \dots, n. Nosta pussista satunnaisia lukuja nopeasti hylkäysotantaa hyödyntäen.

Sarja

Arvioi sarjan n=11n2\sum_{n=1}^{\infty} \frac{1}{n^2} arvoa hylkäysotantaa hyödyntäen.

Vinkki: vagrtebv k:a xääagrvfyhiha aryvö (rot13)

DNF-SAT

Annetaan nn muuttujan ja mm klausuulin SAT-kaava (ks. KKKK luku 17.2.) muotoa C1C2Cm,C_1 \lor C_2 \lor \dots C_m, jossa jokainen klausuuli CiC_i on muotoa ai1ai2ai,ia_{i1} \land a_{i2} \land \dots \land a_{i,\ell_i} ja jokainen aija_{ij} on jokin muuttuja tai sen negaatio. Esimerkkikaava: (x1¬x2)(¬x1x3x4).(x_1 \land \lnot x_2) \lor (\lnot x_1 \land x_3 \land x_4).

Kehitä algortmi, joka arvioi kelvollisten muuttujavalintojen määrää.