Logička funkcija F dana je izrazom. Logički i istiniti skupovi. Rješenja 1. Logička funkcija f dana je s x

Katalog zadataka.
Broj programa s obveznom fazom

Razvrstavanje Osnovno Prvo jednostavno Prvo složeno Popularnost Prvo novo Prvo staro
Riješite testove na ovim zadacima
Povratak na katalog zadataka
Verzija za ispis i kopiranje u MS Wordu

Izvođač A16 pretvara broj napisan na ekranu.

Izvođač ima tri tima, kojima su dodijeljeni brojevi:

1. Dodajte 1

2. Dodajte 2

3. Pomnožite s 2

Prvi od njih povećava broj na ekranu za 1, drugi ga povećava za 2, treći ga množi s 2.

Program za izvođača A16 je niz naredbi.

Koliko programa postoji koji izvorni broj 3 pretvaraju u broj 12, au isto vrijeme računska putanja programa sadrži broj 10?

Računalna putanja programa slijed je rezultata izvođenja svih programskih naredbi. Na primjer, za program 132 s početnim brojem 7, putanja će se sastojati od brojeva 8, 16, 18.

Riješenje.

Traženi broj programa jednak je umnošku broja programa koji iz broja 3 dobivaju broj 10 i broja programa koji iz broja 10 dobivaju broj 12.

Neka je R(n) broj programa koji pretvaraju broj 3 u broj n, a P(n) broj programa koji pretvaraju broj 10 u broj n.

Za sve n > 5 vrijede sljedeće relacije:

1. Ako n nije djeljiv s 2, tada je R(n) = R(n - 1) + R(n - 2), budući da postoje dva načina da se dobije n - zbrajanjem jedan ili zbrajanjem dva. Slično P(n) = P(n - 1) + P(n - 2)

2. Ako je n djeljiv s 2, tada je R(n) = R(n - 1) + R(n - 2) + R(n / 2). Slično P(n) = P(n - 1) + P(n - 2) + P(n / 2)

Izračunajmo sekvencijalno vrijednosti R(n):

R(5) = R(4) + R(3) = 1 + 1 = 2

R(6) = R(5) + R(4) + R(3) = 2 + 1 + 1 = 4

R(7) = R(6) + R(5) = 4 + 2 = 6

R(8) = R(7) + R(6) + R(4) = 6 + 4 + 1 = 11

R(9) = R(8) + R(7) = 11 + 6 = 17

R(10) = R(9) + R(8) + R(5) = 17 + 11 + 2 = 30

Sada izračunajmo vrijednosti P(n):

P(11) = P(10) = 1

P(12) = P(11) + P(10) = 2

Dakle, broj programa koji zadovoljavaju uvjete problema je 30 · 2 = 60.

Odgovor: 60.

Odgovor: 60

Izvor: Demo verzija Jedinstvenog državnog ispita 2017. iz informatike.

1. Dodajte 1

2. Dodajte 3

Koliko ima programa kod kojih je zadani početni broj 1 rezultat broj 17, au isto vrijeme trajektorija računanja sadrži broj 9? Računalna putanja programa slijed je rezultata izvođenja svih programskih naredbi. Na primjer, za program 121 s početnim brojem 7, putanja će se sastojati od brojeva 8, 11, 12.

Riješenje.

Koristimo metodu dinamičkog programiranja. kreirajmo niz dp, gdje je dp[i] broj načina za dobivanje broja i korištenjem takvih naredbi.

Dinamička baza:

Formula prijelaza:

dp[i]=dp + dp

Ovo ne uzima u obzir vrijednosti za brojeve veće od 9, koje se mogu dobiti iz brojeva manjih od 9 (čime se preskače putanja od 9):

Odgovor: 169.

Odgovor: 169

Izvor: Rad za osposobljavanje iz INFORMATIKE, 11. razred 29. studenog 2016. Opcija IN10203

Performer May17 pretvara broj na ekranu.

Izvođač ima dva tima, kojima su dodijeljeni brojevi:

1. Dodajte 1

2. Dodajte 3

Prva naredba povećava broj na ekranu za 1, druga ga povećava za 3. Program za izvođača May17 niz je naredbi.

Koliko ima programa kod kojih je zadani početni broj 1 rezultat broj 15, au isto vrijeme trajektorija računanja sadrži broj 8? Računalna putanja programa je slijed rezultata izvođenja svih programskih naredbi. Na primjer, za program 121 s početnim brojem 7, putanja će se sastojati od brojeva 8, 11, 12.

Riješenje.

Koristimo metodu dinamičkog programiranja. Kreirajmo niz dp, gdje je dp[i] broj načina za dobivanje broja i korištenjem takvih naredbi.

Dinamička baza:

Formula prijelaza:

dp[i]=dp + dp

Ali ovo ne uzima u obzir brojeve koji su veći od 8, ali možemo doći do njih od vrijednosti manje od 8. Sljedeće će pokazati vrijednosti u ćelijama dp od 1 do 15: 1 1 1 2 3 4 6 9 9 9 18 27 36 54 81 .

Analiza zadatka 2 Jedinstvenog državnog ispita 2017. iz računarstva iz projekta demo verzije. Ovo je zadatak osnovne razine težine. Približno vrijeme za rješavanje zadatka je 3 minute.

Provjereni elementi sadržaja: sposobnost konstruiranja tablica istinitosti i logičkih sklopova. Elementi sadržaja testirani na Jedinstvenom državnom ispitu: izjave, logičke operacije, kvantifikatori, istinitost izjava.

Zadatak 2:

Logička funkcija F dano je izrazom x /\¬ g /\ (¬ z \/ w).
Slika prikazuje fragment tablice istinitosti funkcije F koji sadrži svi F pravi.
Odredite koji stupac tablice istinitosti funkcije F odgovara svakoj od varijabli w, x, g, z.

Napiši slova u svoj odgovor w, x, y, z redoslijedom kojim se pojavljuju odgovarajući stupci (prvo - slovo koje odgovara prvom stupcu; zatim - slovo koje odgovara drugom stupcu, itd.) Napišite slova u odgovoru u nizu, nema potrebe stavljati separatora između slova.

Primjer. Kad bi funkcija bila dana izrazom ¬ x \/ g, ovisno o dvije varijable: x I g, a dan je i fragment njegove tablice istinitosti, koji sadrži svi skupovi argumenata za koje funkcija F pravi.

Tada bi prvi stupac odgovarao varijabli g, a drugi stupac je varijabla x. Odgovor je trebao pisati: yx.

Odgovor: ________

x /\¬ g /\ (¬ z \/ w)

Konjunkcija (logičko množenje) je istinita ako i samo ako su svi iskazi istiniti. Stoga varijabla x 1 .

Dakle, varijabla x odgovara stupcu s varijablom 3.

Varijabilna ¬y stupac koji sadrži vrijednost mora odgovarati 0 .

Disjunkcija (logičko zbrajanje) dva iskaza je istinita ako i samo ako je barem jedan iskaz istinit.
Disjunkcija ¬z\/w u ovom retku će biti istina samo ako z=0, w=1.

Dakle, varijabla ¬z odgovara stupcu s varijablom 1 (1 stupac), varijabla w odgovara stupcu s varijablom 4 (stupac 4).

Prvo definirajmo što imamo u problemu:

logička funkcija F definirana nekim izrazom. Elementi tablice istinitosti ove funkcije također su prikazani u zadatku u obliku tablice. Stoga, kada zamjenjujete određene vrijednosti x, y, z iz tablice u izraz, rezultat bi se trebao podudarati s onim danim u tablici (pogledajte objašnjenje u nastavku).
Varijable x, y, z i tri stupca koja im odgovaraju. Štoviše, u ovom problemu ne znamo koji stupac odgovara kojoj varijabli. Odnosno u stupcu Varijabla. 1 može biti x, y ili z.
Od nas se traži da odredimo koji stupac odgovara kojoj varijabli.

Pogledajmo primjer.

Riješenje

Vratimo se sada rješenju. Pogledajmo pobliže formulu: \((\neg z) \klin x \vee x\klin y\)
Sadrži dvije konstrukcije s veznikom, povezane disjunkcijom. Kao što je poznato, najčešće je disjunkcija istinita (za to je dovoljno da je jedan od članova istinit).
Pogledajmo onda pažljivo retke u kojima je izraz F lažan.
Prva linija nam nije zanimljiva, jer ne određuje gdje je što (sve vrijednosti su iste).
Razmotrimo onda pretposljednji redak, on sadrži većinu 1, ali rezultat je 0.
Može li z biti u trećem stupcu? Ne, jer će u ovom slučaju posvuda u formuli biti 1, i stoga će rezultat biti jednak 1, ali prema tablici istinitosti, vrijednost F u ovom retku je 0. Stoga z ne može biti varijabla . 3.
Slično, za prethodni redak imamo da z ne može biti varijabla. 2.
Stoga, z je varijabla. 1.
Znajući da je z u prvom stupcu, razmotrite treći red. Može li x biti u drugom stupcu? Zamijenimo vrijednosti:
\((\neg z) \klin x \vee x\klin y = \\ = (\neg 0) \klin 1 \vee 1\klin 0 = \\ = 1 \klin 1 \vee 0 = \\ = 1 \vee 0 = 1\)
Međutim, prema tablici istine, rezultat mora biti 0.
Stoga, x ne može biti Per. 2.
Stoga, x je varijabla. 3.
Dakle, metodom eliminacije, y je varijabla. 2.
Dakle, odgovor je sljedeći: zyx (z - varijabla 1, y - varijabla 2, x - varijabla 3).

Izvor posla: Rješenje 2437. Jedinstveni državni ispit 2017. Računalstvo. V.R. Leschiner. 10 opcija.

Zadatak 2. Logička funkcija F dana je izrazom . Odredite koji stupac tablice istinitosti funkcije F odgovara svakoj od varijabli x, y, z.

U svom odgovoru napišite slova x, y, z redom kojim se pojavljuju odgovarajući stupci (prvo - slovo koje odgovara 1. stupcu, zatim - slovo koje odgovara 2. stupcu, zatim - slovo koje odgovara 3. stupac) . Slova u odgovoru upišite redom, nema potrebe stavljati razdjelnike između slova.

Riješenje.

Prepišimo izraz za F uzimajući u obzir prioritete operacija negacije, konjunkcije i disjunkcije:

Razmotrimo 4. redak tablice (1,1,0)=0. Iz ovoga vidimo da treće mjesto mora biti ili varijabla y ili varijabla z, inače će druga zagrada sadržavati 1, što će dovesti do vrijednosti F=1. Sada razmotrite 5. redak tablice (0,0,1)=1. Budući da x mora biti na prvom ili drugom mjestu, prva zagrada će dati 1 samo kada je y na 3. mjestu. S obzirom da je druga zagrada uvijek jednaka 0, tada je F=1 dobiven zbog 1 u prvoj zagradi. Dakle, našli smo da je y na 3. mjestu. Na kraju, razmotrite 7. redak tablice (1,0,1)=0. Ovdje je y=1, a za F=0 potrebno je z=0 i x=1, dakle, x je na 1. mjestu, a z na drugom.

№1

(x /\ y/\z/\¬w)\/ (x /\ y/\¬z/\¬w)\/ (x /\¬ y/\¬z/\¬w).

Riješenje

x /\ y/\z/\¬w – x=1, y=1, z=1, w=0;
x /\ y/\¬z/\¬w – x=1, y=1, z=0, w=0;
x /\¬y/\¬z/\¬w – x=1, y=0, z=0, w=0.
Kao rezultat, dobivamo 6 jedinica.
Odgovor: 6.

№2 Logička funkcija F dana je izrazom

(¬x /\ y/\¬z/\w)\/ (x /\ y/\z/\¬w)\/ (x /\¬ y/\¬z/\w).

Stepan je naveo sve skupove varijabli za koje je ovaj izraz istinit. Koliko je jedinica napisao Stepan? U svoj odgovor upišite samo cijeli broj - broj jedinica.