Analyse av oppgave 26. Demoversjon av eksamen i informatikk 2019 (FIPI):

To spillere, Petya og Vanya, spiller følgende spill. Foran spillerne ligger to steinrøyser. Spillerne bytter på Petya tar det første trekket. I en omgang kan en spiller legge til en av haugene (etter eget valg) én stein eller tredoble antallet steiner i en haug.

La det for eksempel være 10 steiner i en haug og 7 steiner i en annen; Vi vil angi en slik posisjon i spillet med (10, 7). Så i ett trekk kan du få en av fire posisjoner: (11, 7), (30, 7), (10, 8), (10, 21).

For å gjøre trekk har hver spiller et ubegrenset antall steiner.
Spillet avsluttes i det øyeblikket det totale antallet steiner i haugene blir minst 68. Vinneren er spilleren som gjorde det siste trekket, dvs. den første som oppnår en posisjon der haugene inneholder 68 eller flere steiner.
I det første øyeblikket var det seks steiner i den første haugen, S-steiner i den andre haugen; 1 ≤ S ≤ 61.

Vi vil si at en spiller har en vinnende strategi hvis han kan vinne med noen trekk fra motstanderen. Å beskrive en spillers strategi betyr å beskrive hvilket trekk han bør gjøre i enhver situasjon som han kan møte med forskjellige spill fra motstanderen. Beskrivelsen av en vinnende strategi bør ikke inkludere trekk fra en spiller som spiller i henhold til denne strategien som ikke er ubetinget vinnende for ham, dvs. ikke vinne uavhengig av motstanderens spill.

Fullfør følgende oppgaver:

Øvelse 1
EN) Spesifiser alle slike tallverdier S, hvor Petya kan vinne i ett trekk.
b) Det er kjent at Vanya vant med sitt første trekk etter Petits mislykkede første trekk. Angi minimumsverdien S når en slik situasjon er mulig.

Oppgave 2
Spesifiser denne verdien S, der Petya har en vinnende strategi, og to betingelser er oppfylt samtidig:
Petya kan ikke vinne i ett trekk;
Petya kan vinne med sitt andre trekk, uavhengig av hvordan Vanya beveger seg.
For den gitte verdien av S, beskriv Petits vinnerstrategi.

Oppgave 3
Spesifiser verdien av S der to betingelser er oppfylt samtidig:
Vanya har en vinnerstrategi som lar ham vinne med det første eller andre trekket i alle Petyas spill;
Vanya har ikke en strategi som vil tillate ham å være garantert å vinne på sitt første trekk.
For den angitte verdien S beskrive Vanyas vinnerstrategi.

Konstruer et tre med alle mulige spill med denne vinnerstrategien til Vanya (i form av et bilde eller en tabell). I trenoder, angi posisjoner; på kanter anbefales det å indikere bevegelser. Treet skal ikke inneholde spill som er umulige hvis den vinnende spilleren implementerer sin vinnende strategi. For eksempel er ikke hele spilltreet det riktige svaret på denne oppgaven.

Analyse av oppgave 27. Demoversjon av eksamen i informatikk 2019 (FIPI):

Programinngangen mottar en sekvens på N positive heltall, alle tall i sekvensen er forskjellige. Alle par av forskjellige elementer i sekvensen vurderes,
plassert i en avstand på ikke mindre enn 4(forskjellen i indeksene til elementene i paret må være 4 eller mer, rekkefølgen på elementene i paret er uviktig).
Det er nødvendig å bestemme antall slike par for hvilke produktet av elementene er delelig med 29.

Beskrivelse av inn- og utdata:
Den første linjen i inndataene spesifiserer antall tall N ( 4 ≤ N ≤ 1000). Hver av de neste N linjene inneholder ett positivt heltall som ikke overstiger 10 000 .
Som et resultat bør programmet gi ut ett tall: antall par av elementer som ligger i sekvensen i en avstand på minst 4, der produktet av elementene er et multiplum av 29.

Eksempel på inndata:

7 58 2 3 5 4 1 29

Eksempelutgang for eksempelinngangen ovenfor:

Fra 7 gitte elementer, med tanke på de tillatte avstandene mellom dem, kan du lage 6 produkter: 58 4 = 232:29 = 8 58 1 = 58:29 = 2 58 29 = 1682:29 = 58 2 1 = 2 2 29 = 58:29=2 3 29 = 87:29=3

Av disse er 5 verk fordelt på 29.

Det kreves å skrive et tids- og minneeffektivt program for å løse det beskrevne problemet.

-> demoversjon av Unified State Exam 2019

Videregående allmennutdanning

Datavitenskap

Demoversjon av Unified State Exam 2019 i informatikk og IKT

Du kan laste ned demoversjonen av Unified State Examination in data science for kandidater fra 2019 ved å bruke lenken nedenfor:

Les om nyvinninger i eksamensmuligheter i andre fag.

Manualen inneholder oppgaver som er så nærme som mulig de virkelige som brukes på Unified State Exam, men fordelt etter emne i den rekkefølgen de studeres i 10.-11. klassetrinn på videregående. Ved å jobbe med boken kan du konsekvent arbeide gjennom hvert emne, eliminere kunnskapshull og systematisere materialet som studeres. Denne strukturen i boken vil hjelpe deg å forberede deg mer effektivt til Unified State-eksamenen.

Demo-KIM Unified State Exam 2019 i informatikk har ikke gjennomgått noen endringer i strukturen sammenlignet med 2018. Dette forenkler arbeidet til læreren betydelig, og selvfølgelig den allerede bygde (jeg vil gjerne stole på dette) planen for å forberede studenten til eksamen.

I denne artikkelen vil vi vurdere løsningen på det foreslåtte prosjektet (i skrivende stund er denne artikkelen fortsatt et PROSJEKT) KIM Unified State Exam i informatikk.

Del 1

Svarene på oppgave 1–23 er et tall, en sekvens av bokstaver eller tall som skal skrives i SVARSKJEMA nr. 1 til høyre for nummeret til den tilsvarende oppgaven, med start fra første celle, uten mellomrom, komma eller annet ekstra tegn. Skriv hvert tegn i en egen boks i samsvar med prøvene gitt i skjemaet.

Øvelse 1

Regn ut verdien av uttrykket 9E 16 – 94 16.

I svaret ditt skriver du ned den beregnede verdien i desimalnotasjon.

Løsning

Enkel aritmetikk i heksadesimal:

Det er åpenbart at det heksadesimale sifferet E 16 tilsvarer desimalverdien 14. Forskjellen i de opprinnelige tallene gir verdien A 16. Løsningen er i prinsippet allerede funnet. Etter betingelsen presenterer vi den funnet løsningen i desimaltallsystemet. Vi har: A 16 = 10 10.

Svar: 10.

Oppgave 2

Misha fylte ut sannhetstabellen til funksjonen (¬x /\ ¬y) \/ (y≡z) \/ ¬w, men klarte bare å fylle ut et fragment av tre forskjellige linjer, uten engang å indikere hvilken kolonne i tabellen tilsvarer hver av variablene w, x , y, z.

Bestem hvilken tabellkolonne hver variabel w, x, y, z tilsvarer.

I svaret ditt skriver du bokstavene w, x, y, z i den rekkefølgen de tilsvarende kolonnene vises i (først bokstaven som tilsvarer den første kolonnen, deretter bokstaven som tilsvarer den andre kolonnen osv.). Skriv bokstavene i svaret på rad, det er ikke nødvendig å skille mellom bokstavene.

Eksempel. Hvis funksjonen ble gitt av uttrykket ¬x \/ y, avhengig av to variabler, og tabellfragmentet ville se ut som

da ville den første kolonnen tilsvare variabelen y, og den andre kolonnen ville tilsvare variabelen x. Svaret burde vært skrevet yx.

Svar: ___________________________.

Løsning

La oss merke oss at funksjonen (¬x /\ ¬y) \/ (y≡z) \/ ¬w i hovedsak er en disjunksjon av tre "termer":

La oss huske sannhetstabellen for operasjonen av logisk "addisjon" (disjunksjon): summen er "sann" hvis minst ett begrep er "sant", og "usant" hvis begge ledd er "usant". Dette betyr at vi ut fra betingelsene for oppgaven konkluderer med at hvert av begrepene må være falske. Den tredje termen - (¬w) - må være usann, noe som gir oss vår første ledetråd: den fjerde kolonnen må være variabelen w, siden basert på verdiene til den første, andre og tredje kolonnen, kan ingen av dem være variabelen w.

La oss vurdere det andre leddet i funksjonen - (y≡z), - det skal også være lik 0. Derfor er det nødvendig at kolonnene våre med variablene y og z har forskjellige verdier. Med tanke på det første leddet i funksjonen (¬x /\ ¬y), merker vi at variabelen z tilsvarer den første kolonnen. Det første leddet indikerer også at de tomme cellene i den andre og tredje kolonnen skal inneholde 1. Umiddelbart, med tanke på det andre leddet, vil vi gjøre en annen konklusjon om at den tomme cellen i den første kolonnen er lik 1. Det er denne konklusjonen som lar oss gjøre den endelige konklusjonen at den andre kolonnen tilsvarer variabelen y, og følgelig den tredje til variabelen x.

Svar: zyxw.

Oppgave 3

Figuren til venstre viser et veikart over N-rayon; i tabellen indikerer en stjerne tilstedeværelsen av en vei fra en bygd til en annen. Fraværet av en stjerne betyr at det ikke finnes en slik vei.

Hvert oppgjør på diagrammet tilsvarer sitt nummer i tabellen, men det er ikke kjent hvilket nummer. Bestem hvilke antall bosetninger i tabellen som kan tilsvare oppgjør B og C i diagrammet. I svaret ditt skriver du ned disse to tallene i stigende rekkefølge uten mellomrom eller tegnsetting.

Svar: ___________________________.

Løsning

Diagrammet viser at hvert av punktene B og C er forbundet med tre andre punkter. Dette betyr at vi i tabellen må finne antallet bosetninger overfor som det er tre "stjerner" i radene (eller i kolonnene, med tanke på symmetri). Denne betingelsen tilsvarer linje 2 og 6 (henholdsvis kolonne 2 og 6).

Svar: 26.

Oppgave 4

Nedenfor er to fragmenter av tabeller fra databasen om innbyggere i mikrodistriktet. Hver rad i tabell 2 inneholder informasjon om barnet og en av foreldrene hans. Informasjonen presenteres ved verdien av ID-feltet i den tilsvarende raden i Tabell 1. Basert på dataene som er oppgitt, bestemmer du den største forskjellen mellom fødselsårene til søsknene. Når du beregner svaret, ta kun hensyn til informasjonen fra de gitte fragmentene av tabellene.

Svar: ___________________________.

Løsning

Det første du bør ta hensyn til og ikke bli forvirret er at vi ekskluderer mannlige representanter (mer presist tar vi ikke hensyn til dem når vi teller kvinnelige barn): dette er linjene 64, 67, 70, 75, 77, 86 av Tabell 1.

Når vi går gjennom feltene til tabellene, finner vi par med jentebarn:

Som svar legger vi inn den største av de to verdiene av differansen mellom fødselsårene.

Svar: 6.

Oppgave 5

For å kode en bestemt sekvens som består av bokstavene A, B, C, D, D, E, bestemte vi oss for å bruke en ikke-uniform binær kode som tilfredsstiller Fano-betingelsen. For bokstaven A ble kodeordet 0 brukt; for bokstaven B – kodeord 10. Hva er den minste mulige summen av lengdene på kodeordene for bokstavene B, D, D, E?

Merk. Fano-tilstanden betyr at ingen kodeord er begynnelsen på et annet kodeord. Dette gjør det mulig å entydig dekryptere krypterte meldinger.

Svar: ___________________________.

Løsning

For å løse problemet, la oss bygge en graf:

Et kodeord med lengde 2 - 11, eller hvilket som helst av kodeordene med lengde 3, vil uunngåelig bli begynnelsen på et av ordene med lengde 4. Valget av lengde 4 skyldes det faktum at det var behov for å kode fire bokstaver . De resulterende kodeordene gir sammen en lengde på 16.

Svar: 16.

Oppgave 6

Inngangen til algoritmen er et naturlig tall N. Algoritmen konstruerer et nytt tall R fra det som følger.

1. En binær representasjon av tallet N er konstruert.
2. Ytterligere to sifre legges til denne oppføringen til høyre i henhold til følgende regel: hvis N er partall, legges først null og deretter ett til på slutten av tallet (til høyre). Ellers, hvis N er oddetall, legges først en til høyre, og deretter null.

For eksempel vil den binære representasjonen 100 av tallet 4 bli konvertert til 10001, og den binære representasjonen 111 av tallet 7 vil bli konvertert til 11110.

Posten oppnådd på denne måten (den har to sifre mer enn i posten til det opprinnelige tallet N) er en binær registrering av tallet R - resultatet av operasjonen av denne algoritmen.

Spesifiser minimumstallet R som er større enn 102 og kan være resultatet av denne algoritmen. I svaret ditt skriver du dette tallet i desimaltallsystemet.

Svar: ___________________________.

Løsning

La oss representere tallet 102 i binær form: 1100110 2. Vi er interessert i antallet som blir større. Vi flytter "opp" ved å legge til en om gangen:

1100111 2 – 103 10 – binær representasjon samsvarer ikke med algoritmen;

1101000 2 – 104 10 – binær representasjon samsvarer ikke med algoritmen;

1101001 2 – 105 10 – binær representasjon tilsvarer algoritmen.

Svar: 105.

Oppgave 7

Et fragment av et regneark er gitt. Formelen ble kopiert fra celle C3 til celle D4. Ved kopiering endres celleadressene i formelen automatisk. Hva er den numeriske verdien av formelen i celle D4?

Merk. $-tegnet angir absolutt adressering.

Svar: ___________________________.

Løsning

Når vi kopierer formelen i celle D4, får vi: =$B$3+E3. Ved å erstatte verdiene får vi ønsket resultat:

400+700, dvs. 1100.

Svar: 1100.

Oppgave 8

Skriv ned tallet som vil bli skrevet ut som et resultat av følgende program. For enkelhets skyld presenteres programmet på fem programmeringsspråk.

Svar: ___________________________.

Løsning

La oss følge endringene i verdiene til variablene:

s = 0, n = 75 - verdier før syklusen;

s + n (75)< 150, s = s + 15 = 15, n = n – 5 = 70 – значения после первой итерации;

s + n (85)< 150, s = s + 15 = 30, n = n – 5 = 65 – значения после 2 итерации;

s + n (95)< 150, s = s + 15 = 45, n = n – 5 = 60 – значения после 3 итерации;

s + n (105)< 150, s = s + 15 = 60, n = n – 5 = 55 – значения после 4 итерации;

s + n (115)< 150, s = s + 15 = 75, n = n – 5 = 50 – значения после 5 итерации;

s + n (125)< 150, s = s + 15 = 90, n = n – 5 = 45 – значения после 6 итерации;

s + n (135)< 150, s = s + 15 = 105, n = n – 5 = 40 – значения после 7 итерации;

s + n (145)< 150, s = s + 15 = 120, n = n – 5 = 35 – значения после 8 итерации;

sløyfen avbrytes ved neste trinn, viser programmet ønsket verdi.

Svar: 35.

Oppgave 9

Det automatiske kameraet produserer rasterbilder på 200x256 piksler. Det samme antall biter brukes til å kode fargen på hver piksel, og pikselkodene skrives til filen etter hverandre uten mellomrom. Størrelsen på bildefilen kan ikke overstige 65 KB uten å ta hensyn til størrelsen på filoverskriften. Hva er det maksimale antallet farger som kan brukes i en palett?

Svar: ___________________________.

Løsning

La oss starte med noen enkle beregninger:

200 × 256 – antall piksler i rasterbildet;

65 KB = 65 × 2 10 × 2 3 biter – den øvre terskelen for filstørrelse.

Forholdet til vil tillate oss å få fargedybden til pikselen, dvs. antall biter som er allokert til fargekoding for hver piksel.

Og til slutt, den ønskede verdien, som vi bestemmer ved hjelp av den klassiske formelen:

2Jeg = n, 2 10 .

Svar: 1024.

Oppgave 10

Vasya komponerer 5-bokstavsord som bare inneholder bokstavene Z, I, M, A, og hvert ord har nøyaktig en vokalbokstav og den vises nøyaktig 1 gang. Hver av de gyldige konsonantene kan vises i et ord hvor mange ganger eller ikke i det hele tatt. Et ord er en hvilken som helst gyldig sekvens av bokstaver, ikke nødvendigvis meningsfull. Hvor mange ord er det Vasya kan skrive?

Svar: ___________________________.

Løsning

Hvis det ikke var for betingelsen "det er nøyaktig en vokalbokstav og den forekommer nøyaktig 1 gang," ville problemet være løst ganske enkelt. Men det er denne tilstanden, og det er to forskjellige vokaler.

Denne vokalen kan være i en av 5 posisjoner. La oss anta at hun er i første posisjon. Det er nøyaktig 2 mulige vokalalternativer i dette tilfellet.I de resterende fire posisjonene har vi to konsonantalternativer. Totale alternativer for det første tilfellet:

2 × 2 × 2 × 2 × 2 = 2 5 = 32

Jeg gjentar, det er nøyaktig 5 alternativer for plasseringen av en vokal i ordet vårt. Totalt:

Svar: 160.

Oppgave 11

Nedenfor er den rekursive algoritmen F skrevet på fem programmeringsspråk.

Skriv ned på rad, uten mellomrom eller skilletegn, alle tallene som vil bli skrevet ut på skjermen når du ringer F(4). Tallene må skrives i samme rekkefølge som de vises på skjermen.

Svar: ___________________________.

Løsning

For klarhetens skyld, la oss bygge et tre:

Når vi beveger oss langs dette rekursjonstreet, får vi verdien som vil være den ønskede løsningen.

Svar: 1231412.

Oppgave 12

I terminologien til TCP/IP-nettverk er en nettverksmaske et binært tall som bestemmer hvilken del av IP-adressen til en nettverksvert som refererer til nettverksadressen, og hvilken del som refererer til adressen til selve verten på dette nettverket. Vanligvis er masken skrevet i henhold til de samme reglene som IP-adressen - i form av fire byte, med hver byte skrevet som et desimaltall. I dette tilfellet inneholder masken først enere (i de høyeste sifrene), og deretter fra et bestemt siffer er det nuller. Nettverksadressen oppnås ved å bruke en bitvis konjunksjon på den gitte verts-IP-adressen og masken.

For eksempel, hvis vertens IP-adresse er 231.32.255.131 og masken er 255.255.240.0, er nettverksadressen 231.32.240.0.

For en node med IP-adressen 117.191.37.84 er nettverksadressen 117.191.37.80. Hva er den minste mulige verdien av den siste (lengst til høyre) byten av masken? Skriv svaret ditt som et desimaltall.

Svar: ___________________________.

Løsning

La oss skrive den ene under den andre den binære representasjonen av den siste høyre byten til IP-adressen, nettverksadressen og masken i samsvar med definisjonen (i den øverste linjen, for enkelhets skyld, er bitene nummerert):

Vi vil flytte fra høyre til venstre, og erstatte bitverdiene i masken. La oss samtidig ta hensyn til at i masken vår "først (i de høyeste sifrene) er det enere, og deretter fra et visst siffer er det nuller."

Fra den 0. biten (fra høyre til venstre), vil vi velge verdiene til nettverksmasken under hensyntagen til den bitvise konjunksjonen:

I den 4. biten er det åpenbart at en nullverdi ikke lenger er egnet, og det bør være en 1 (en). Ved å starte fra denne posisjonen og deretter flytte til venstre, vil vi ha alle enhetene:

Ønsket verdi for byten lengst til høyre er 111100002, som tilsvarer verdien 24010 i desimalnotasjon.

Svar: 240.

Oppgave 13

Ved registrering i et datasystem får hver bruker et passord som består av 7 tegn og inneholder kun tegn fra det 26-tegnssettet med store latinske bokstaver. Databasen tildeler det samme og minst mulige heltall antall byte for å lagre informasjon om hver bruker. I dette tilfellet brukes tegn-for-tegn-koding av passord, alle tegn er kodet med samme og minst mulig antall biter. I tillegg til selve passordet lagres tilleggsinformasjon i systemet for hver bruker, som det er tildelt et heltall av byte for; dette nummeret er det samme for alle brukere.

For å lagre informasjon om 30 brukere var det nødvendig med 600 byte. Hvor mange byte er tildelt for å lagre tilleggsinformasjon om én bruker? I svaret ditt skriver du bare ned et heltall - antall byte.

Svar: ___________________________.

Løsning

Hver brukers informasjon lagres

600 ÷ 30 = 20 byte.

Koding av 26 tegn krever minimum 5 bits minne. Derfor kreves et passord på 7 tegn

5 × 7 = 35 biter.

35 bits krever minimum 5 byte minne.

Det nødvendige antallet byte for å lagre tilleggsinformasjon om én bruker er:

20 byte – 5 byte = 15 byte.

Svar: 15.

Oppgave 14

Executor Editor mottar en rekke tall som input og konverterer den. Redaktøren kan utføre to kommandoer, i begge kommandoene representerer v og w strenger med tall.

A) erstatte (v, w).

Denne kommandoen erstatter den første venstre forekomsten av strengen v med strengen w. For eksempel å kjøre kommandoen

erstatte (111, 27)

konverterer streng 05111150 til streng 0527150.

Hvis det ikke er noen forekomster av v i en streng, endrer ikke strengen å utføre kommandoen replace (v, w).

B) funnet (v).

Denne kommandoen sjekker om strengen v forekommer i executorens linjeredigering. Hvis det oppstår, returnerer kommandoen den boolske verdien "true", ellers returnerer den verdien "false". Eksekutørs linje endres ikke.

BYE tilstand

rekkefølge av kommandoer

AVSLUTT HEI

utføres så lenge betingelsen er sann.

I design

IF tilstand

TIL lag 1

SLUTT OM

kommando1 utføres (hvis betingelsen er sann).

I design

IF tilstand

TIL lag 1

ELSE kommando2

SLUTT OM

kommando1 (hvis betingelsen er sann) eller kommando2 (hvis betingelsen er usann) utføres.

Hvilken streng oppnås ved å bruke følgende program på en streng bestående av 82 påfølgende siffer 1? Skriv ned den resulterende strengen i svaret ditt.

SÅ langt funnet (11111) ELLER funnet (888)

HVIS funnet (11111)

Å erstatte (11111, 88)

HVIS funnet (888)

Å erstatte (888, 8)

SLUTT OM

SLUTT OM

AVSLUTT HEI

Svar: ___________________________.

Løsning

La oss "visualisere" situasjonen:

82 enheter kan grovt sett representeres som 16 grupper på 5 enheter, samt en gruppe på to enheter. Det første anropet til den betingede operatøren gir oss 16 grupper med par på åttere - det er 32 åttere, eller 10 grupper på tre åttere, pluss et annet gratis par på åttere. Det er klart at de to siste enhetene forblir urørt av utøveren. Og de 12 gjenværende åttetallene, gruppert etter tre, er allerede 4 åttere. En gjentakelse til - 2 åttere og 2 enere gjenstår.

Svar: 8811.

Oppgave 15

Figuren viser et diagram over veier som forbinder byene A, B, C, D, D, E, F, Z, I, K, L, M. På hver vei kan du bare bevege deg i én retning, angitt med pilen.

Hvor mange forskjellige veier er det fra by A til by M, som går gjennom by L?

Svar: ___________________________.

Løsning

La oss se på diagrammet vårt igjen. Denne gangen på diagrammet ser vi merker ordnet i en bestemt rekkefølge.

Til å begynne med legger vi merke til at banene fra punkt I til punkt M - en rett linje og gjennom punkt K - er uthevet i farger. Dette ble gjort fordi, i henhold til betingelsene for problemet, er det nødvendig å bestemme antall stier bare gjennom punkt A.

La oss starte fra startpunkt A - dette er et spesielt punkt, ingen vei fører dit, formelt kan du bare komme dit derfra. La oss anta at antallet veier inn til den er 1.

Det andre punktet B - det er åpenbart at det bare kan nås fra ett punkt og bare en vei. Det tredje punktet kan ikke være verken B eller D - antall veier til punkt B kan ikke bestemmes uten å bestemme antall veier til G, og til G uten å bestemme antall veier til D. D er det tredje punktet på vår vei. Antall stier som fører til det er lik 1. La oss fortsette denne kjeden av slutninger ved å bestemme antall stier som fører til et gitt punkt som summen av antall stier ved tidligere punkter som fører direkte til den nåværende. Punkt I er et kritisk punkt - antall stier som fører til det er lik summen av 5 (E) + 16 (F) + 7 (G) og lik 28. Neste punkt er L, veien fører til det bare gjennom I, er det ingen annen vei, men derfor forblir antallet stier også lik 28. Og til slutt, sluttpunktet - M - i henhold til betingelsene for problemet, fører bare en vei til det, noe som betyr den ønskede verdien vil også forbli lik 28.

Svar: 28.

Oppgave 16

Verdien av det aritmetiske uttrykket 9 7 + 3 21 – 9 er skrevet i tallsystemet med grunntall 3. Hvor mange sifre "2" inneholder denne oppføringen?

Svar: ___________________________.

For å løse problemet, la oss omskrive det opprinnelige uttrykket og også omorganisere begrepene:

3 21 + 3 14 – 3 2 .

La oss huske at i det ternære tallsystemet er selve tallet 3 10 skrevet 10 3. K- 10-potens n essens 1 og K nuller. Og det er også åpenbart at første ledd 3 21 ikke påvirker antall toere på noen måte. Men forskjellen kan ha effekt.

Svar: 12.

Oppgave 17

I søkemotorspråket brukes symbolet "|" for å angi den logiske operasjonen "ELLER", og symbolet "&" brukes for å angi den logiske operasjonen "AND".

Tabellen viser søkene og antall sider funnet for et bestemt segment av Internett.

Hvor mange sider (i hundretusenvis) vil bli funnet for søket? Hals | Skip | Nese? Det antas at alle spørringene ble utført nesten samtidig, slik at settet med sider som inneholder alle de søkte ordene ikke endret seg under utførelsen av spørringene.

Svar: ___________________________.

Løsning

Selvfølgelig indikerer OR-operasjonen operasjonen med å legge til verdiene til sidene som ble funnet for hvert ord separat: 35+35+40. Men for noen søk var det sider som var felles for hvert ordpar - de må ekskluderes, dvs. du må trekke 33 fra den tidligere funnet summen.

Svar: 77.

Oppgave 18

For hva er det største ikke-negative heltall A uttrykket

(48 ≠ y + 2x) \/ (A< x) \/ (A < y)

er identisk sant, dvs. tar verdien 1 for et hvilket som helst ikke-negativt heltall x og y?

Svar: ___________________________.

Løsning

Problemet er rent matematisk...

Uttrykket gitt i oppgavebetingelsen er disjunksjonen av tre ledd. Det andre og tredje leddet avhenger av ønsket parameter:

La oss representere det første leddet annerledes:

Punkter på en linje (graf av en funksjon) med heltallskoordinater er de verdiene til variablene x og y der den slutter å være sann. Derfor må vi finne en A som vil sikre sannheten til eller på disse punktene.

Eller, for forskjellige x og y, som tilhører den rette linjen, vil de vekselvis (noen ganger samtidig) ta på seg den sanne verdien for enhver A i området. i denne forbindelse er det viktig å forstå hvilken parameter A skal være for tilfellet når y = x.

De. vi får systemet:

Løsningen er lett å finne: y=x=16. Og det største heltallet som passer oss for parameter A=15.

Svar: 15.

Oppgave 19

Programmet bruker en endimensjonal heltallsmatrise A med indekser fra 0 til 9. Verdiene til elementene er henholdsvis 2, 4, 3, 6, 3, 7, 8, 2, 9, 1, dvs. A = 2, A = 4 osv. Bestem verdien av en variabel c etter å ha utført følgende fragment av dette programmet, skrevet nedenfor på fem programmeringsspråk.

Svar: ___________________________.

Løsning

Et programfragment utfører en repetisjonssløyfe. Antall iterasjoner er 9. Hver gang betingelsen er oppfylt, vises variabelen Medøker verdien med 1, og bytter også verdiene til to matriseelementer.

Startsekvens: 2, 4, 3, 6, 3, 7, 8, 2, 9, 1. I posten kan du konstruere følgende iterasjonsskjema:

Svar: 7.

Oppgave 20

Algoritmen er skrevet nedenfor på fem programmeringsspråk. Gitt et naturlig desimaltall x som input, skriver denne algoritmen ut to tall: L og M. Spesifiser det største tallet x, når det angis, skriver algoritmen først ut 21 og deretter 3.

Svar: ___________________________.

Løsning

En liten kodeanalyse:

1. Vi må vise verdiene til variablene L og M. Variabelen M, dette kan sees ved å studere koden litt, indikerer antall iterasjoner av løkken, dvs. Hoveddelen av løkken må utføres tre ganger nøyaktig.
2. Verdien av tallet L, som skal skrives ut først, er produktet lik 21. I produktet kan 21 fås fra 7 og 3. Merk også at produktet kun er mulig hvis verdien av variabelen er oddetall x i gjeldende iterasjon.
3. Den betingede operatoren indikerer at én av tre ganger vil verdien av variabelen være partall. De resterende to gangene med en oddeverdi av variabelen x, vi får resten av å dele x med 8 til å være en gang 3 og en annen gang 7.
4. Variabel verdi x reduseres tre ganger med 8 av heltallsdivisjonsoperasjonen.

Ved å kombinere alt som er sagt tidligere, får vi to alternativer:

x 1 = (7 × 8 + ?) × 8 + 3 og x 2 = (3 × 8 + ?) × 8 + 7

I stedet for et spørsmålstegn, må vi velge en verdi som ikke vil være mer enn 8 og vil være jevn. La oss ikke glemme tilstanden i oppgaven - "den største x". Jo større er partall, ikke over 8 – 6. Og fra x1 og x2 er det åpenbart at den første er større. Etter å ha regnet ut, får vi x=499.

Svar: 499.

Oppgave 21

Bestem tallet som vil bli skrevet ut som et resultat av følgende algoritme. For enkelhets skyld presenteres algoritmen på fem programmeringsspråk.

Merk. Abs- og iabs-funksjonene returnerer den absolutte verdien til inngangsparameteren.

Svar: ___________________________.

Løsning

La oss skrive funksjonen vår i vanlig form:

For å gjøre bildet klarere, la oss også plotte denne funksjonen:

Når vi ser nærmere på koden, legger vi merke til følgende åpenbare fakta: inntil det øyeblikket løkken utføres, er variabelen M=-20 og R=26.

Nå selve syklusen: tjueen iterasjoner, hver avhengig av oppfyllelsen (eller ikke-oppfyllelsen) av en betingelse. Det er ikke nødvendig å sjekke alle verdiene - grafen vil hjelpe oss mye her. Når du beveger deg fra venstre til høyre, vil verdiene til variablene M og R endres til det første minimumspunktet er nådd: x=-8. Videre og opp til punktet x=8 gir tilstandskontrollen falske verdier og verdiene til variablene endres ikke. Ved punkt x=8 vil verdiene endres for siste gang. Vi får ønsket resultat M=8, R=2, M+R=10.

Svar: 10.

Oppgave 22

Executor Calculator konverterer tallet skrevet på skjermen. Utøveren har tre lag, som er tildelt nummer:

1. Legg til 2
2. Multipliser med 2
3. Legg til 3

Den første av dem øker tallet på skjermen med 2, den andre multipliserer det med 2, den tredje øker det med 3.

Et kalkulatorprogram er en sekvens av kommandoer.

Hvor mange programmer er det som konverterer det opprinnelige tallet 2 til tallet 22 og samtidig inneholder programmets beregningsbane tallet 11?

Et programs beregningsbane er en sekvens av resultater fra utførelsen av alle programkommandoer. For eksempel, for program 123 med det første tallet 7, vil banen bestå av tallene 9, 18, 21.

Svar: ___________________________.

Løsning

Til å begynne med, la oss løse problemet enkelt, uten å ta hensyn til tilleggsbetingelsen "inneholder tallet 11":

Programmet er kort, og det beregner heller ikke verdien 11 i sin bane. Og her er det verdt å dele opp problemet i to små oppgaver: å bestemme antall stier fra 2 til 11 og fra 11 til 22. Det endelige resultatet, vil åpenbart tilsvare produktet av disse to verdiene. Å konstruere komplekse diagrammer med trær er ikke en rasjonell sløsing med tid på eksamen. Det er ikke mange tall i vårt utvalg, så jeg foreslår at du vurderer følgende algoritme:

La oss skrive ned alle tallene fra startnummeret til det siste inklusive. Under den første vil vi skrive 1. Ved å flytte fra venstre til høyre, vil vi vurdere antall måter å komme til gjeldende posisjon ved å bruke kommandoene gitt til oss.

Du kan umiddelbart fjerne åpenbare posisjoner som ikke påvirker beslutningen: 3 kan krysses ut - det er klart at det ikke kan nås fra startposisjonen ved å bruke en av kommandoene som er tilgjengelige for oss; 10 – gjennom den kan vi ikke på noen måte komme til vår mellomliggende, og viktigst av alt, obligatoriske posisjon 11.

Vi kan komme til 4 ved å bruke to kommandobaner: x2 og +2, dvs. gjennom 4 er det 2 stier. La oss skrive denne verdien under 4. Det er bare én måte å komme til 5 på: +3. La oss skrive verdien 1 under 5. Den eneste måten å komme til 6 på er gjennom 4. Og under den har vi verdien 2. Følgelig er det langs disse to banene at vi ved å passere 4 kommer fra 2 til 6. Vi skriver under 6 verdien 2. I 7 kan du få fra de to foregående posisjonene ved å bruke kommandoene vi har, og for å få antall stier som er tilgjengelige for oss for å komme til 7, legger vi til tallene som ble angitt under disse tidligere posisjonene . De. i 7 får vi 2 (fra under 4) + 1 (fra under 5) = 3 måter. Ved å gå frem i henhold til denne ordningen får vi videre:

La oss gå til høyre halvdel av det betingede senteret - 11. Først nå i beregningen vil vi bare ta hensyn til de stiene som går gjennom dette senteret.

Svar: 100.

Oppgave 23

Hvor mange forskjellige sett med verdier av de logiske variablene x1, x2, ... x7, y1, y2, ... y7 er det som tilfredsstiller alle betingelsene som er oppført nedenfor?

(y1 → (y2 /\ x1)) /\ ​​​​(x1 → x2) = 1

(y2 → (y3 /\ x2)) /\ ​​​​(x2 → x3) = 1

(y6 → (y7 /\ x6)) /\ ​​​​(x6 → x7) = 1

Svaret trenger ikke å liste opp alle de forskjellige settene med verdier av variablene x1, x2, ... x7, y1, y2, ... y7 som dette likhetssystemet er oppfylt for. Som svar må du angi antall slike sett.

Svar: ___________________________.

Løsning

En ganske detaljert analyse av denne kategorien problemer ble publisert på en gang i artikkelen "Systems of logical equations: solution using bit chains."

Og for videre diskusjon husker vi (for klarhets skyld skriver vi ned) noen definisjoner og egenskaper:

La oss nå se på systemet vårt igjen. Vær oppmerksom på at den kan skrives om litt annerledes. For å gjøre dette må du først og fremst merke deg at hver av de valgte faktorene i de første seks ligningene, så vel som deres gjensidige produkt, er lik 1.

La oss jobbe litt med de første faktorene til likningene i systemet:

Når vi tar hensyn til de ovennevnte betraktningene, får vi ytterligere to ligninger, og det opprinnelige ligningssystemet vil ha formen:

I denne formen er det opprinnelige systemet redusert til standardoppgavene som er omtalt i den tidligere nevnte artikkelen.

Hvis vi vurderer den første og andre ligningen til det nye systemet separat, tilsvarer settene dem (la oss legge igjen en detaljert analyse av denne konklusjonen for leseren):

Disse argumentene ville føre oss til mulige 8 × 8 = 64 løsninger hvis ikke for den tredje ligningen. I den tredje ligningen kan vi umiddelbart begrense oss til å vurdere bare de variantene av settene som passer for de to første ligningene. Hvis vi erstatter det første settet i den tredje ligningen y 1…y 7, som kun består av 1, så er det åpenbart at bare ett sett vil tilsvare det x 1…x 7, som også består av kun 1. Ethvert annet sett som inneholder minst én 0, passer ikke for oss. Tenk på det andre settet y1…y7 – 0111111. For x 1, er begge mulige verdier akseptable - 0 og 1. De gjenværende verdiene, som i forrige tilfelle, kan ikke være lik 0. Vi har to sett som oppfyller denne betingelsen. Det tredje settet y1…y7 – 011111 vil matche de tre første settene x 1…x 7. Osv. Ved å argumentere på en lignende måte finner vi at det nødvendige antallet sett er lik

1 + 2 + … + 7 + 8 = 36.

Svar: 36.

Del 2

For å registrere svar på oppgaver i denne delen (24–27), bruk SVARSKJEMA nr. 2. Skriv først ned oppgavenummeret (24, 25 osv.), og deretter den fullstendige løsningen. Skriv ned svarene dine tydelig og leselig.

Videre ser vi ikke behovet for å komme opp med noe annet enn det offisielle innholdet i KIM-demoversjonen. Dette dokumentet inneholder allerede "innholdet i riktig svar og instruksjoner for vurdering", samt "instruksjoner for vurdering" og noen "merknader til assessor". Dette materialet er gitt nedenfor.

Oppgave 24

Et naturlig tall som ikke overstiger 109 mottas for behandling. Du må skrive et program som viser minimum partall av dette tallet. Hvis det ikke er partall i nummeret, må du vise "NO" på skjermen. Programmereren skrev programmet feil. Nedenfor presenteres dette programmet på fem programmeringsspråk for enkelhets skyld.

Gjør følgende i rekkefølge.

1. Skriv hva dette programmet vil sende ut når du skriver inn tallet 231.

2. Gi et eksempel på et tresifret tall, når det legges inn, gir programmet ovenfor, til tross for feil, riktig svar.

3. Finn feilene programmereren har gjort og rett dem. Feilrettingen skal kun påvirke linjen der feilen er lokalisert. For hver feil:

1. skriv ned linjen der feilen ble gjort;
2. angi hvordan feilen skal rettes, dvs. gi riktig versjon av linjen.

Det er kjent at nøyaktig to linjer i programteksten kan rettes slik at den begynner å fungere riktig.

Det er nok å indikere feilene og hvordan du retter dem for ett programmeringsspråk.

Vær oppmerksom på at du må finne feil i et eksisterende program, og ikke skrive dine egne, eventuelt ved hjelp av en annen løsningsalgoritme.

Oppgave 25

Gitt en heltallsmatrise på 30 elementer. Array-elementer kan ta naturverdier fra 1 til 10 000 inkludert. Beskriv en algoritme i et av programmeringsspråkene som finner minimum blant elementene i en matrise som ikke er delelig med 6, og erstatter deretter hvert element som ikke er delbart med 6 med et tall som er lik det funnet minimum. Det er garantert at det er minst ett slikt element i matrisen. Som et resultat er det nødvendig å vise den endrede matrisen, hvert element vises på en ny linje.

For eksempel, for en innledende matrise med seks elementer:

programmet skal sende ut følgende array

Kildedataene er deklarert som vist nedenfor i eksempler for noen programmeringsspråk. Det er forbudt å bruke variabler som ikke er beskrevet nedenfor, men det er tillatt å ikke bruke noen av de beskrevne variablene.

Som et svar må du gi et fragment av programmet, som skal være plassert på stedet for ellipsen. Du kan også skrive løsningen på et annet programmeringsspråk (angi navn og versjon av programmeringsspråket som brukes, for eksempel Free Pascal 2.6). I dette tilfellet må du bruke de samme inndataene og variablene som ble foreslått i betingelsen (for eksempel i en prøve skrevet på algoritmisk språk).

Oppgave 26

To spillere, Petya og Vanya, spiller følgende spill. Foran spillerne ligger to hauger med steiner. Spillerne bytter på, Petya gjør det første trekket. I en omgang kan en spiller legge til én stein til en av haugene (etter eget valg) eller øke antall steiner i haugen tre ganger. La det for eksempel være 10 steiner i en haug og 7 steiner i en annen; Vi vil angi en slik posisjon i spillet med (10, 7). Så i ett trekk kan du få en av fire posisjoner:

(11, 7), (30, 7), (10, 8), (10, 21).

For å gjøre trekk har hver spiller et ubegrenset antall steiner.

Spillet avsluttes når det totale antallet steiner i haugene blir minst 68. Vinneren er spilleren som gjorde det siste trekket, dvs. den første som oppnår en posisjon der haugene inneholder 68 eller flere steiner.

I det første øyeblikket var det seks steiner i den første haugen, S-steiner i den andre haugen; 1 ≤ S ≤ 61.

Vi vil si at en spiller har en vinnende strategi hvis han kan vinne med noen trekk fra motstanderen. Å beskrive en spillers strategi betyr å beskrive hvilket trekk han bør gjøre i enhver situasjon som han kan møte med forskjellige spill fra motstanderen. Beskrivelsen av en vinnende strategi bør ikke inkludere trekk fra en spiller som spiller i henhold til denne strategien som ikke er ubetinget vinnende for ham, dvs. ikke vinne uavhengig av motstanderens spill.

Fullfør følgende oppgaver.

Øvelse 1

c) Angi alle slike verdier av tallet S som Petya kan vinne for i ett trekk.

d) Det er kjent at Vanya vant med sitt første trekk etter Petyas mislykkede første trekk. Spesifiser minimumsverdien for S når denne situasjonen er mulig.

Oppgave 2

Spesifiser en verdi på S der Petya har en vinnende strategi, og to betingelser er oppfylt samtidig:

• Petya kan ikke vinne i ett trekk;
• Petya kan vinne med sitt andre trekk, uavhengig av hvordan Vanya beveger seg.

For den gitte verdien av S, beskriv Petits vinnerstrategi.

Oppgave 3

Spesifiser verdien av S der to betingelser er oppfylt samtidig:

• Vanya har en vinnerstrategi som lar ham vinne med det første eller andre trekket i alle Petyas spill;
• Vanya har ikke en strategi som vil tillate ham å være garantert å vinne på sitt første trekk.

For den gitte verdien av S, beskriv Vanyas vinnende strategi.

Konstruer et tre med alle mulige spill med denne vinnerstrategien til Vanya (i form av et bilde eller en tabell).

I trenoder, angi posisjoner; på kanter anbefales det å indikere bevegelser. Treet skal ikke inneholde spill som er umulige hvis den vinnende spilleren implementerer sin vinnende strategi. For eksempel er ikke hele spilltreet det riktige svaret på denne oppgaven.

Oppgave 27

Programinngangen er en sekvens av N positive heltall, alle tall i sekvensen er forskjellige. Alle par av forskjellige elementer i sekvensen som ligger i en avstand på minst 4, vurderes (forskjellen i indeksene til elementene i paret må være 4 eller mer, rekkefølgen på elementene i paret er uviktig). Det er nødvendig å bestemme antall slike par der produktet av elementer er delelig med 29.

Beskrivelse av inn- og utdata

Den første linjen i inndataene spesifiserer antall tall N (4 ≤ N ≤ 1000). Hver av de neste N linjene inneholder ett positivt heltall som ikke overstiger 10 000.

Som et resultat bør programmet gi ut ett tall: antall par av elementer som ligger i sekvensen i en avstand på minst 4, der produktet av elementene er et multiplum av 29.

Eksempel på inndata:

Eksempelutgang for eksempelinngangen ovenfor:

Forklaring. Fra 7 gitte elementer, med tanke på de tillatte avstandene mellom dem, kan du lage 6 produkter: 58 4, 58 1, 58 29, 2 1, 2 29, 3 29. Av disse er 5 verk fordelt på 29.

Det kreves å skrive et tids- og minneeffektivt program for å løse det beskrevne problemet.

Et program betraktes som tidseffektivt hvis, med en økning i antall innledende tall N med en faktor på k, kjøretiden til programmet øker med ikke mer enn k ganger.

Et program anses som minneeffektivt hvis minnet som kreves for å lagre alle programvariabler ikke overstiger 1 kilobyte og ikke øker med N.

Maksimal poengsum for et korrekt (som ikke inneholder syntaksfeil og gir riktig svar for alle gyldige inndata) program som er tids- og minneeffektivt er 4 poeng.

Maksimal poengsum for et riktig program som bare er effektiv i tid er 3 poeng.

Maksimal poengsum for et riktig program som ikke oppfyller effektivitetskravene er 2 poeng.

Du kan ta ett program eller to problemløsningsprogrammer (for eksempel kan ett av programmene være mindre effektive). Hvis du tar to programmer vil hvert av dem bli karakterisert uavhengig av det andre, og sluttkarakteren blir den høyeste av de to karakterene.

Før du skriver programteksten, sørg for å kort beskrive løsningsalgoritmen. Vennligst oppgi programmeringsspråket som brukes og versjonen.