Aufgabe 2. Demoversion der Einheitlichen Staatsprüfung 2018 Informatik (FIPI):

Boolesche Funktion F durch den Ausdruck gegeben ¬x ∨ y ∨ (¬z ∧ w).
Die Abbildung zeigt ein Fragment der Wahrheitstabelle der Funktion F, die alle Sätze von Argumenten enthält, für die die Funktion F falsch ist. Bestimmen Sie, welche Spalte der Wahrheitstabelle der Funktion F jeder der Variablen w, x, y, z entspricht.

Variable 1	Variable 2	Variable 3	Variable 4	Funktion
???	???	???	???	F
1	0	0	0	0
1	1	0	0	0
1	1	1	0	0

Schreiben Sie die Buchstaben in Ihre Antwort. w, X, j, z in der Reihenfolge, in der die ihnen entsprechenden Spalten gehen (zuerst - der Buchstabe, der der ersten Spalte entspricht; dann - der Buchstabe, der der zweiten Spalte entspricht usw.) Schreiben Sie die Buchstaben in der Antwort hintereinander, Sie müssen es nicht Setzen Sie Trennzeichen zwischen die Buchstaben.

Aufgabe 3. Demoversion der Einheitlichen Staatsprüfung 2018 Informatik (FIPI):
In der Abbildung rechts ist die Straßenkarte des N-Sky-Distrikts als Diagramm dargestellt, die Tabelle enthält Informationen über die Länge jeder dieser Straßen (in Kilometern).

Da die Tabelle und das Diagramm unabhängig voneinander gezeichnet wurden, steht die Nummerierung der Siedlungen in der Tabelle in keinem Zusammenhang mit den Buchstabenbezeichnungen in der Grafik. Bestimmen Sie die Länge der Straße vom Punkt aus A zum Absatz G. Notieren Sie in Ihrer Antwort die ganze Zahl - so wie sie in der Tabelle angegeben ist.

4 Aufgabe. Demoversion der Einheitlichen Staatsprüfung 2018 Informatik (FIPI):
Unten sind zwei Fragmente von Tabellen aus der Datenbank der Einwohner des Mikrobezirks. Jede Zeile von Tabelle 2 enthält Informationen über das Kind und einen seiner Eltern. Die Information wird durch den Wert des ID-Feldes in der entsprechenden Zeile von Tabelle 1 dargestellt. Bestimmen Sie anhand der angegebenen Daten, wie viele Kinder zum Zeitpunkt ihrer Geburt Mütter über 22 Jahre alt waren. Berücksichtigen Sie bei der Berechnung der Antwort nur Informationen von
die gegebenen Fragmente der Tabellen.

5 Aufgabe. Demoversion der Einheitlichen Staatsprüfung 2018 Informatik (FIPI):
Über den Kommunikationskanal werden verschlüsselte Nachrichten mit nur zehn Buchstaben übertragen: A, B, E, I, K, L, R, C, T, U. Zur Übertragung wird ein ungerader Binärcode verwendet. Codewörter werden für neun Buchstaben verwendet.

Geben Sie das kürzeste Codewort für den Buchstaben an B, unter denen der Code die Fano-Bedingung erfüllt. Wenn es mehrere solcher Codes gibt, geben Sie den Code mit an am wenigsten numerischer Wert.

6 Aufgabe. Demoversion der Einheitlichen Staatsprüfung 2018 Informatik (FIPI):
Die Eingabe des Algorithmus ist eine natürliche Zahl N. Der Algorithmus baut darauf basierend eine neue Zahl auf R auf die folgende Weise.

1. Eine binäre Schreibweise einer Zahl wird erstellt N.

2. Diesem Eintrag werden rechts zwei weitere Ziffern nach folgender Regel hinzugefügt:

- Addieren Sie alle Ziffern der binären Schreibweise der Zahl N, und der Rest nach Division der Summe durch 2 wird am Ende der Zahl (rechts) hinzugefügt. Zum Beispiel der Eintrag 11100 in Aufnahme umgewandelt 111001 ;

- die gleichen Aktionen werden für diesen Datensatz ausgeführt - der Rest der Division der Summe seiner Ziffern durch 2 wird rechts hinzugefügt.

Der auf diese Weise erhaltene Datensatz (er enthält zwei Ziffern mehr als der Datensatz der ursprünglichen Zahl N) ist ein binärer Datensatz der erforderlichen Zahl R.
Geben Sie die Mindestanzahl ein R, was die Zahl übersteigt 83 und kann das Ergebnis von sein dieser Algorithmus. Schreiben Sie diese Zahl in Dezimalschreibweise auf.

7 Aufgabe. Demoversion der Einheitlichen Staatsprüfung 2018 Informatik (FIPI):
Ein Fragment einer Tabelle ist gegeben. Von Zelle B3 in eine Zelle A4 Formel wurde kopiert. Beim Kopieren der Adressen der Zellen in der Formel wurden diese automatisch geändert. Was ist der numerische Wert der Formel in der Zelle? A4?

Hinweis: Das $-Zeichen kennzeichnet eine absolute Adressierung.

8 Aufgabe. Demoversion der Einheitlichen Staatsprüfung 2018 Informatik (FIPI):

Notieren Sie die Zahl, die als Ergebnis des folgenden Programms gedruckt wird. Zu Ihrer Bequemlichkeit wird das Programm in fünf Programmiersprachen präsentiert.

1 2 3 4 5 6 7 8 9 10 11

var s, n: ganze Zahl ; beginnen s := 260 ; n := 0 während s > 0 beginne s : = s - 15 ; n := n + 2 writeln (n) end .

var s, n: ganze Zahl; Beginn s:= 260; n:=0; während s > 0 beginne s:= s - 15; n:= n + 2 writeln(n) end.

9 Aufgabe. Demoversion der Einheitlichen Staatsprüfung 2018 Informatik (FIPI):

Automatische Kamera produziert Bitmaps Größe 640 × 480 Pixel. In diesem Fall darf die Größe der Datei mit dem Bild nicht überschritten werden 320 KBytes, Datenpaketierung wird nicht durchgeführt. Welche Höchstbetrag Farben können in der Palette verwendet werden?

10 Aufgabe. Demoversion der Einheitlichen Staatsprüfung 2018 Informatik (FIPI):

Alle 4-Buchstaben-Wörter bestehen aus Buchstaben D, E, ZU, UM, R, werden in alphabetischer Reihenfolge aufgelistet und beginnend mit nummeriert 1 .
Unten ist der Anfang der Liste.

1. DDDD 2. DDDE 3. DDDD 4. DDDO 5. DDDR 6. DDED …

Was ist das erste Wort in der Liste, das mit einem Buchstaben beginnt? K?

11 Aufgabe. Demoversion der Einheitlichen Staatsprüfung 2018 Informatik (FIPI):

Unten ist ein rekursiver Algorithmus in fünf Programmiersprachen geschrieben F.
Paskal:

1 2 3 4 5 6 7 8 9

Prozedur F(n: Ganzzahl ) ; start if n > 0 then begin write(n) ; F(n-3) ; F(n div 3 ) Ende Ende ;

Prozedur F(n: ganze Zahl); start if n > 0 then begin write(n); F(n-3); F(n div 3) Ende Ende;

Notieren Sie in einer Reihe ohne Leerzeichen und Trennzeichen alle Nummern, die bei einem Anruf auf dem Bildschirm gedruckt werden F(9). Die Zahlen müssen in derselben Reihenfolge geschrieben werden, in der sie auf dem Bildschirm angezeigt werden.

12 Aufgabe. Demoversion der Einheitlichen Staatsprüfung 2018 Informatik (FIPI):

In der TCP/IP-Netzwerkterminologie ist eine Netzmaske eine Binärzahl, die festlegt, welcher Teil der IP-Adresse eines Hosts sich auf die Netzwerkadresse und welcher Teil auf die Adresse des Hosts selbst in diesem Netzwerk bezieht. Normalerweise wird die Maske nach denselben Regeln wie die IP-Adresse geschrieben – in Form von vier Bytes, wobei jedes Byte als Dezimalzahl geschrieben wird. Gleichzeitig gibt es in der Maske zuerst (in den höchsten Ziffern) Einsen und dann ab einer bestimmten Ziffer Nullen.
Die Netzwerkadresse wird durch Anwenden einer bitweisen Konjunktion auf die gegebene Host-IP-Adresse und Maske erhalten.

Wenn die Host-IP-Adresse beispielsweise 231.32.255.131 und die Maske 255.255.240.0 lautet, lautet die Netzwerkadresse 231.32.240.0.

Für Host mit IP-Adresse 57.179.208.27 Netzwerkadresse ist 57.179.192.0 . Was ist größte mögliche Zahl Einheiten in den Reihen der Maske?

13 Aufgabe. Demoversion der Einheitlichen Staatsprüfung 2018 Informatik (FIPI):

Bei Anmeldung unter Computersystem Jeder Benutzer erhält ein Passwort bestehend aus 10 Figuren. Als Symbole werden Großbuchstaben des lateinischen Alphabets verwendet, d.h. 26 verschiedene Symbole. In der Datenbank wird jedes Passwort mit der gleichen und der kleinstmöglichen ganzen Zahl gespeichert Byte. Dabei wird eine zeichenweise Codierung von Passwörtern verwendet, alle Zeichen werden mit der gleichen und der geringstmöglichen Anzahl von Bits codiert.

Bestimmen Sie die Menge an Speicher (in Bytes), die zum Speichern von Daten erforderlich ist 50 Benutzer. Notieren Sie in der Antwort nur eine Ganzzahl - die Anzahl der Bytes.

14 Aufgabe. Demoversion der Einheitlichen Staatsprüfung 2018 Informatik (FIPI):

Performer Der Zeichner bewegt sich auf der Koordinatenebene und hinterlässt eine Spur in Form einer Linie. Der Zeichner kann den Befehl ausführen gehe zu (a, b), Wo a, b sind ganze Zahlen. Dieser Befehl bewegt den Painter vom Punkt mit den Koordinaten (x,y) zum Punkt mit den Koordinaten (x + a, y + b).

Dem Zeichner wurde der folgende Algorithmus zur Ausführung gegeben (die Anzahl der Wiederholungen und die Größe des Offsets im ersten der wiederholten Befehle sind unbekannt):

START bewegen um (4, 6) WIEDERHOLEN… EINMAL bewegen um (…, …) bewegen um (4, -6) ENDE WIEDERHOLEN bewegen um (-28, -22) ENDE

Als Ergebnis der Ausführung dieses Algorithmus kann der Zeichner kehrt zum Ausgangspunkt zurück. Welche größte die Anzahl der Wiederholungen könnte in der Konstruktion "REPEAT ... ONCE" angegeben werden?

15 Aufgabe. Demoversion der Einheitlichen Staatsprüfung 2018 Informatik (FIPI):

Die Abbildung zeigt ein Diagramm der Straßen, die die Städte A, B, C, D, D, E, G, H, I, K, L, M verbinden.
Auf jeder Straße können Sie sich nur in eine Richtung bewegen, die durch den Pfeil angezeigt wird.
Wie viele verschiedene Wege gibt es aus der Stadt A in der Stadt M durch die Stadt ziehen UND?

16 Aufgabe. Demoversion der Einheitlichen Staatsprüfung 2018 Informatik (FIPI):

Der Wert des arithmetischen Ausdrucks: 49 10 + 7 30 – 49 - in einem Zahlensystem mit Basis geschrieben 7 . Wie viele Ziffern 6 » in diesem Eintrag enthalten?

17 Aufgabe. Demo USE 2018 Informatik (FIPI):

In der Suchsprache der Suchmaschine, um die logische Operation " ODER» Symbol wird verwendet « | ", und um die logische Operation zu bezeichnen " UND" - Symbol " & ».

Die Tabelle zeigt Suchanfragen und die Anzahl der von ihnen gefundenen Seiten für ein bestimmtes Segment des Internets.

Anfrage	Gefundene Seiten (in Hunderttausenden)
Schmetterling	22
Raupe	40
Traktor	24
Traktor \| Schmetterling \| Raupe	66
Traktor & Raupe	12
Traktor & Schmetterling	0

Wie viele Seiten (in Hunderttausenden) werden für die Abfrage gefunden Schmetterling & Raupe?
Es wird davon ausgegangen, dass alle Anfragen fast gleichzeitig ausgeführt wurden, sodass sich die Menge der Seiten mit allen gesuchten Wörtern während der Ausführung der Anfragen nicht geändert hat.

18 Aufgabe. Demoversion der Einheitlichen Staatsprüfung 2018 Informatik (FIPI):

Denn was ist die größte ganze Zahl A Formel

identisch WAHR, das heißt, es nimmt den Wert an 1 für jede ganze Zahl nicht negativ X Und j?

19 Aufgabe. Demoversion der Einheitlichen Staatsprüfung 2018 Informatik (FIPI):

Das Programm verwendet ein eindimensionales Integer-Array A mit Indizes von 0 Vor 9 . Die Elementwerte sind jeweils 3, 0, 4, 6, 5, 1, 8, 2, 9, 7, d.h. A=3, A=0 usw.

Ermitteln Sie den Wert einer Variablen C nach dem Ausführen des folgenden Fragments dieses Programms:

1 2 3 4 5 6 7 8 9

c:=0; for i : = 1 to 9 do if A[ i- 1 ] > A[ i] then begin c : = c + 1 ; t := A[i] ; A[ i] := A[ i- 1 ] ; A[ i- 1 ] := t; Ende ;

c:=0; for i:= 1 to 9 do if A > A[i] then begin c:= c + 1; t:= A[i]; A[i] := A; A := t; Ende;

20 Aufgabe. Demoversion der Einheitlichen Staatsprüfung 2018 Informatik (FIPI):

Der Algorithmus ist unten in fünf Programmiersprachen geschrieben. Nachdem ich eine Nummer erhalten habe X, gibt dieser Algorithmus zwei Zahlen aus: L Und M. Geben Sie die kleinste Zahl ein X, bei deren Eingabe der Algorithmus zuerst druckt 5 , und dann 7 .

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

var x, L, M: Ganzzahl ; start readln(x) ; L:=0; M:=0; while x>0 do begin M : = M + 1 ; wenn x mod 2<>0 dann L : = L + 1 ; x := x div 2 ; Ende ; schreiben(L) ; schreiben(M) ; Ende.

var x, L, M: Ganzzahl; readln(x) beginnen; L:= 0; M:= 0; während x>0 beginne M:= M + 1; wenn x mod 2<>0 dann L:= L + 1; x:=x div 2; Ende; schreiben(L); schreiben(M); Ende.

21 Aufgaben. Demoversion der Einheitlichen Staatsprüfung 2018 Informatik (FIPI):

Schreiben Sie in die Antwort die Zahl, die als Ergebnis des folgenden Algorithmus gedruckt wird.

Paskal:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

var a, b, t, M, R : lange Ganzzahl ; Funktion F(x: lange Ganzzahl ) : lange Ganzzahl ; Beginn F: = 2 * (x* x- 1 ) * (x* x- 1 ) + 27 ; Ende ; Beginn a: =- 20 ; b:=20; M:=a; R: = F(a) ; for t: = a to b do begin if (F(t)<= R) then begin M: = t; R: = F(t) end end ; write (M+ R) end .

var a, b, t, M, R: lange Ganzzahl; Funktion F(x: lange Ganzzahl): lange Ganzzahl; Beginn F:= 2*(x*x-1)*(x*x-1)+27; Ende; Beginn a:=-20; b:=20; M:=a; R:=F(a); für t:= a bis b beginnen, wenn (F(t)<= R) then begin M:=t; R:=F(t) end end; write(M+R) end.

22 Aufgabe. Demo USE 2018 Informatik (FIPI):

Performer M17 konvertiert die auf dem Bildschirm geschriebene Zahl.
Der Darsteller hat drei Teams, denen Nummern zugewiesen sind:
1. 1 hinzufügen
2. 2 hinzufügen
3. mit 3 multiplizieren

Der erste erhöht die Zahl auf dem Bildschirm um 1, der zweite erhöht sie um 2, der dritte multipliziert mit 3. Das Programm für den M17-Performer ist eine Folge von Befehlen.

Wie viele Programme gibt es, die die ursprüngliche Zahl umwandeln? 2 an der Zahl 12 und die Flugbahn der Berechnungen des Programms enthält die Zahlen 8 Und 10 ? Die Trajektorie muss beide angegebenen Zahlen enthalten.

Die Trajektorie von Programmberechnungen ist die Folge von Ergebnissen der Ausführung aller Programmbefehle. Zum Beispiel für Programm 132 mit der Anfangsnummer 7 besteht die Trajektorie aus den Nummern 8, 24, 26.

Lösung 23 USE-Zuweisungen in der Informatik-Demoversion 2018 FIPI:

Wie viele verschiedene Sätze von booleschen Werten gibt es? x1, x2, … x7, y1, y2, … y7 die alle folgenden Bedingungen erfüllen?

(¬x1 ∨ y1) → (¬x2 ∧ y2) = 1
(¬x2 ∨ y2) → (¬x3 ∧ y3) = 1
…
(¬x6 ∨ y6) → (¬x7 ∧ y7) = 1

Als Antwort müssen Sie die Anzahl solcher Sätze angeben.

Lösung 24 Aufgabe der Klausur Informatik Demoversion 2018 FIPI:

Eine natürliche Zahl, die nicht überschreitet 10 9 . Wir müssen ein Programm schreiben, das anzeigt die maximale Ziffer einer Zahl, die ein Vielfaches von 5 ist. Wenn es keine Ziffern in der Zahl gibt, die ein Vielfaches von sind 5 , muss angezeigt werden NEIN. Der Programmierer hat das Programm falsch geschrieben. Unten ist dieses Programm für Ihre Bequemlichkeit in fünf Programmiersprachen angegeben.
Erinnerung: 0 ist durch jede natürliche Zahl teilbar.
Paskal:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

var N, Ziffer, maxDigit: longint ; start readln(N) ; maxDigit := N mod 10 ; während N > 0 beginnen Ziffer : = N mod 10 ; if digit mod 5 = 0 then if digit > maxDigit then maxDigit := digit; N := N div 10 ; Ende ; if maxDigit = 0 then writeln ("NO") else writeln (maxDigit) end .

var N, Ziffer, maxDigit: longint; readln(N) beginnen; maxDigit:= N mod 10; während N > 0 beginne digit:= N mod 10; if digit mod 5 = 0 then if digit > maxDigit then maxDigit:= digit; N:= N div 10; Ende; if maxDigit = 0 then writeln("NO") else writeln(maxDigit) end.

Gehen Sie nacheinander wie folgt vor:
1. Schreiben Sie, was dieses Programm anzeigt, wenn Sie eine Zahl eingeben 132 .
2. Geben Sie bei der Eingabe ein Beispiel für eine solche dreistellige Zahl an
Das Programm gibt die richtige Antwort.
3. Finden Sie alle Fehler in diesem Programm (es kann einen oder mehrere geben). Es ist bekannt, dass jeder Fehler nur eine Zeile betrifft und behoben werden kann, ohne andere Zeilen zu ändern. Für jeden Fehler:
1) schreiben Sie die Zeile aus, in der der Fehler gemacht wurde;
2) Geben Sie an, wie der Fehler behoben werden kann, d. h. Geben Sie die richtige Version der Zeichenfolge an.
Es reicht aus, die Fehler und die Art und Weise, sie zu beheben, für eine Programmiersprache anzugeben.

Lösung 25 der USE-Aufgabe in Informatik Demoversion 2018:

Bei einem Integer-Array von 30 Elemente. Array-Elemente können ganzzahlige Werte annehmen 0 Vor 10000 inklusive. Beschreiben Sie in einer der Programmiersprachen einen Algorithmus, der die Anzahl der Elemente eines Arrays größer als findet 100 und worin Vielfache von 5, und ersetzt dann jedes solche Element durch eine Zahl, die der gefundenen Zahl entspricht. Es ist garantiert, dass mindestens ein solches Element im Array vorhanden ist. Als Ergebnis müssen Sie das geänderte Array anzeigen, jedes Element des Arrays wird in einer neuen Zeile angezeigt.

Zum Beispiel für ein Array aus sechs Elementen: 4 115 7 195 25 106
das Programm sollte die Zahlen ausgeben: 4 2 7 2 25 106

Die Anfangsdaten werden wie unten in Beispielen für einige Programmiersprachen gezeigt deklariert. Es ist verboten, unten nicht beschriebene Variablen zu verwenden, aber es ist erlaubt, einige der beschriebenen Variablen nicht zu verwenden.

Paskal:

1 2 3 4 5 6 7 8 9 10

konstant N = 30 ; var a: array [ 1 .. N ] of longint ; i, j, k: lange Ganzzahl ; begin for i : = 1 bis N do readln (a[ i] ) ; ... Ende .

konstant N = 30; var a: Array von langen Ganzzahlen; i, j, k: lange Ganzzahl; begin for i:= 1 to N do readln(a[i]); ... Ende.

Als Antwort müssen Sie ein Fragment des Programms angeben, das anstelle der Auslassungspunkte stehen sollte. Sie können die Lösung auch in einer anderen Programmiersprache schreiben (Name und Version der verwendeten Programmiersprache angeben, zB Free Pascal 2.6). In diesem Fall müssen Sie dieselben Ausgangsdaten und Variablen verwenden, die in der Bedingung vorgeschlagen wurden.

Analyse der 26. Aufgabe der Demoversion von 2018 (FIPI):
Zwei Spieler, Petya und Vanya, spielen das folgende Spiel. Vor den Spielern liegt ein Steinhaufen. Die Spieler ziehen der Reihe nach, Petya macht den ersten Zug. In einem Zug kann der Spieler zum Stapel hinzufügen eins Stein oder erhöhen Sie die Anzahl der Steine im Haufen zweimal. Wenn Sie beispielsweise einen Stapel mit 15 Steinen haben, können Sie mit einem Zug einen Stapel mit 16 oder 30 Steinen erhalten. Jeder Spieler hat eine unbegrenzte Anzahl von Steinen, um Züge zu machen.

Das Spiel endet, wenn die Anzahl der Steine im Stapel wird mindestens 29. Der Gewinner ist der Spieler, der den letzten Zug gemacht hat, das heißt, der erste, der einen Stapel mit 29 oder mehr Steinen erhält. Im ersten Moment waren S Steine im Haufen, 1 ≤ S ≤ 28.

Wir werden sagen, dass ein Spieler eine Gewinnstrategie hat, wenn er für alle Züge des Gegners gewinnen kann. Die Strategie eines Spielers zu beschreiben bedeutet, zu beschreiben, welchen Zug er in jeder Situation machen sollte, der er mit den Spielzügen verschiedener Gegner begegnen kann. Zur Beschreibung der Gewinnstrategie TU es nicht zählen die Züge des nach dieser Strategie spielenden Spielers, die für ihn nicht unbedingt gewinnend sind, d.h. nicht zu gewinnen, unabhängig vom Spiel des Gegners.

Übung 1
A) Geben Sie solche Werte der Zahl S an, für die Petya in einem Zug gewinnen kann.
B) Geben Sie einen Wert von S an, bei dem Petya nicht in einem Zug gewinnen kann, Vanya jedoch bei jedem Zug von Petya mit seinem ersten Zug gewinnen kann. Beschreibe Wanjas Gewinnstrategie.

Aufgabe 2
Geben Sie zwei solche Werte von S an, für die Petya außerdem eine Gewinnstrategie hat:
- Petya kann nicht in einem Zug gewinnen;
— Petya kann mit seinem zweiten Zug gewinnen, unabhängig davon, wie Vanya sich bewegt.
Beschreiben Sie für die angegebenen Werte von S die Gewinnstrategie von Petya.

Aufgabe 3
Geben Sie den Wert von S an, bei dem:
- Vanya hat eine Gewinnstrategie, die es ihm ermöglicht, in jedem Petya-Spiel im ersten oder zweiten Zug zu gewinnen;
- Vanya hat keine Strategie, die es ihm ermöglicht, mit einer Garantie im ersten Zug zu gewinnen.

Beschreiben Sie für den gegebenen Wert von S Wanjas Gewinnstrategie. Konstruieren Sie einen Baum aller Spiele, die mit dieser Gewinnstrategie möglich sind (in Form einer Figur oder einer Tabelle). Geben Sie an den Rändern des Baums an, wer den Zug macht; in Knoten - die Anzahl der Steine in einer Position

Der Baum sollte keine Spiele enthalten, die für den gewinnenden Spieler unmöglich sind, seine Gewinnstrategie umzusetzen. Beispielsweise ist der vollständige Spielbaum keine gültige Antwort für diese Aufgabe.

Analyse der 27 Aufgaben der Demoversion von 2018 (FIPI):

Die Eingabe des Programms ist eine Folge von N positive ganze Zahlen, alle Zahlen in der Folge sind verschieden. Alle Paare verschiedener Elemente der Folge werden berücksichtigt (die Elemente eines Paares müssen in der Folge nicht nebeneinander liegen, die Reihenfolge der Elemente im Paar ist nicht wichtig). Muss definiert werden die Anzahl der Paare, durch die das Produkt der Elemente teilbar ist 26 .

Beschreibung der Ein- und Ausgabedaten Die erste Zeile der Eingabedaten gibt die Anzahl der Zahlen N an (1 ≤ N ≤ 1000). In jedem der folgenden N Zeilen enthält eine positive ganze Zahl, die nicht größer ist 10 000 .
Als Ergebnis sollte das Programm eine Zahl ausgeben: die Anzahl der Paare, bei denen das Produkt der Elemente ein Vielfaches von 26 ist.

Eingabebeispiel:

4 2 6 13 39

Beispielausgabe für die obige Beispieleingabe:

Aus den vier gegebenen Zahlen kannst du 6 paarweise Produkte bilden: 2 6 = 12 2 13 = 26 2 39 = 78 6 13 = 78 6 39 = 234 13 39 = 507

Davon sind 4 Werke in 26 unterteilt:

2 13=26; 2 39=78; 6 13=78; 6 39=234

Es ist erforderlich, ein zeiteffizientes und speichereffizientes Programm zu schreiben
Lösung des beschriebenen Problems.

-> Demo-USE 2018

Bei KIM USE 2020 gibt es keine Änderungen in Informatik und IKT.

Die Prüfungsarbeit besteht aus zwei Teilen, inkl 27 Aufgaben.

Teil 1 enthält 23 Aufgaben mit einer kurzen Antwort. Die Antworten zu den Aufgaben 1-23 werden als Zahl, Buchstabenfolge oder Zahlen geschrieben.
Teil 2 enthält 4 Aufgaben mit ausführlicher Antwort. Die Aufgaben 24–27 erfordern eine detaillierte Lösung.

Alle USE-Formulare sind mit hellschwarzer Tinte ausgefüllt. Sie können einen Gel- oder Kapillarstift verwenden. Beim Abschließen von Aufgaben können Sie einen Entwurf verwenden. Eintragungen im Entwurf sowie im Text der Kontrollmessmaterialien werden bei der Bewertung der Arbeit nicht berücksichtigt.

3 Stunden 55 Minuten (235 Minuten) stehen für die Bearbeitung der Prüfungsarbeit in Informatik und IKT zur Verfügung.

Die Punkte, die Sie für abgeschlossene Aufgaben erhalten, werden summiert. Versuchen Sie, so viele Aufgaben wie möglich zu erledigen und die meisten Punkte zu erzielen.

Punkte für Aufgaben in der Informatik

1 Punkt - für 1-23 Aufgaben
2 Punkte - 25.
3 Punkte - 24, 26.
4 Punkte - 27.

Insgesamt: 35 Punkte.

Sekundarstufe Allgemeinbildung

Informatik

Demoversion des Einheitlichen Staatsexamens 2019 in Informatik und IKT

Wir machen Sie auf eine Analyse der Demoversion von USE 2019 in Informatik und IKT aufmerksam. Dieses Material enthält Erklärungen und einen detaillierten Lösungsalgorithmus sowie Empfehlungen zur Verwendung von Nachschlagewerken und Handbüchern, die möglicherweise zur Vorbereitung auf die Prüfung benötigt werden.

Die Demoversion der Einheitlichen Staatsprüfung Informatik für Absolventen des Jahres 2019 können Sie unter folgendem Link herunterladen:

Informieren Sie sich über Neuerungen bei den Prüfungsoptionen für andere Fächer in.

Das Handbuch enthält Aufgaben, die so nah wie möglich an den realen in der Prüfung verwendeten liegen, aber nach Themen in der Reihenfolge verteilt sind, in der sie in den Klassen 10-11 der High School behandelt werden. Durch die Arbeit mit dem Buch können Sie jedes Thema konsequent erarbeiten, Wissenslücken schließen und auch den Lernstoff systematisieren. Diese Struktur des Buches hilft, sich effektiver auf die Prüfung vorzubereiten.

Demo-KIM USE 2019 in der Informatik hat sich gegenüber 2018 in seiner Struktur nicht verändert. Dies vereinfacht die Arbeit des Lehrers und natürlich den bereits erstellten (ich möchte mich darauf verlassen) Plan zur Vorbereitung des Schülers auf die Prüfung erheblich.

In diesem Artikel betrachten wir die Lösung des vorgeschlagenen Projekts (zum Zeitpunkt des Schreibens des Artikels ist es noch ein PROJEKT) KIM USE in der Informatik.

Teil 1

Die Antworten auf die Aufgaben 1–23 sind eine Zahl, eine Folge von Buchstaben oder Zahlen, die im ANTWORTFORMULAR Nr. 1 rechts neben der Nummer der entsprechenden Aufgabe, beginnend mit der ersten Zelle, ohne Leerzeichen, Kommas, geschrieben werden sollten und andere zusätzliche Zeichen. Schreiben Sie jedes Zeichen gemäß den im Formular angegebenen Mustern in ein separates Kästchen.

Übung 1

Berechnen Sie den Wert des Ausdrucks 9E 16 - 94 16 .

Notieren Sie in Ihrer Antwort den errechneten Wert in Dezimalschreibweise.

Lösung

Einfache Arithmetik in Hexadezimal:

Offensichtlich entspricht die hexadezimale Ziffer E 16 dem Dezimalwert 14. Die Differenz der ursprünglichen Zahlen ergibt den Wert A 16 . Die Lösung ist bereits gefunden. Im Anschluss an die Bedingung stellen wir die gefundene Lösung im dezimalen Zahlensystem dar. Wir haben: A 16 \u003d 10 10.

Antworten: 10.

Aufgabe 2

Misha füllte die Wahrheitstabelle der Funktion (¬x /\ ¬y) \/ (y≡z) \/ ¬w aus, schaffte es aber nur, ein Fragment ihrer drei verschiedenen Zeilen auszufüllen, ohne auch nur anzugeben, welche Spalte der Tabelle entspricht jeder der Variablen w, x , y, z.

Bestimmen Sie, welche Tabellenspalte jeder der Variablen w, x, y, z entspricht.

Schreiben Sie in Ihrer Antwort die Buchstaben w, x, y, z in der Reihenfolge, in der ihre jeweiligen Spalten erscheinen (zuerst der Buchstabe, der der ersten Spalte entspricht, dann der Buchstabe, der der zweiten Spalte entspricht, und so weiter). Schreiben Sie die Buchstaben in der Antwort hintereinander, Sie brauchen keine Trennzeichen zwischen die Buchstaben zu setzen.

Beispiel. Wenn die Funktion durch den Ausdruck ¬x \/ y, abhängig von zwei Variablen, gegeben wäre, würde das Fragment der Tabelle so aussehen

dann würde die erste Spalte der Variablen y und die zweite Spalte der Variablen x entsprechen. Die Antwort hätte yx lauten sollen.

Antworten: ___________________________.

Lösung

Beachten wir, dass die Funktion (¬x /\ ¬y) \/ (y≡z) \/ ¬w tatsächlich eine Disjunktion von drei "Termen" ist:

Wir erinnern an die Wahrheitstabelle der Operation der logischen „Addition“ (Disjunktion): in der Summe „wahr“, wenn mindestens ein Term „wahr“ ist, und „falsch“, wenn beide Terme „falsch“ sind. Das bedeutet, dass wir aus der Bedingung der Abtretung schließen, dass jede der Bedingungen falsch sein muss. Der dritte Term – (¬w) – muss falsch sein, was uns unseren ersten Hinweis gibt: Die vierte Spalte muss die Variable w sein, da, basierend auf den Werten der ersten, zweiten und dritten Spalte, keine davon vorhanden ist kann die Variable w sein.

Betrachten Sie den zweiten Term der Funktion - (y≡z), - er muss ebenfalls gleich 0 sein. Daher ist es notwendig, dass unsere Spalten der Variablen y und z unterschiedliche Werte haben. Unter Berücksichtigung des ersten Terms der Funktion (¬x /\ ¬y) stellen wir fest, dass die erste Spalte der Variablen z entspricht. Der erste Term zeigt auch an, dass in den leeren Zellen der zweiten und dritten Spalte 1 sein sollte.Unter Berücksichtigung des zweiten Terms werden wir sofort eine weitere Schlussfolgerung ziehen, dass die leere Zelle in der ersten Spalte gleich 1 ist ist diese Schlussfolgerung, die es uns erlaubt, abschließend die Schlussfolgerung zu ziehen, dass die zweite Spalte der Variablen y entspricht und dementsprechend die dritte der Variablen x.

Antworten: zyxw.

Aufgabe 3

Die Abbildung links zeigt eine Straßenkarte des N-Sky-Distrikts, in der Tabelle zeigt ein Sternchen das Vorhandensein einer Straße von einer Siedlung zur anderen an. Das Fehlen eines Sternchens bedeutet, dass es keine solche Straße gibt.

Jede Siedlung auf dem Diagramm entspricht ihrer Nummer in der Tabelle, aber es ist nicht bekannt, welche Nummer. Bestimmen Sie, welche Siedlungsnummern in der Tabelle den Siedlungen B und C im Diagramm entsprechen können. Notieren Sie in Ihrer Antwort diese beiden Zahlen in aufsteigender Reihenfolge ohne Leerzeichen oder Satzzeichen.

Antworten: ___________________________.

Lösung

Das Diagramm zeigt, dass jeder der Punkte B und C mit drei anderen Punkten verbunden ist. Also müssen wir diese Zahlen in der Tabelle finden Siedlungen, denen in Zeilen (oder in Spalten unter Berücksichtigung der Symmetrie) drei "Sternchen" gegenüberstehen. Zeilen 2 und 6 entsprechen dieser Bedingung (Spalten 2 bzw. 6).

Antworten: 26.

Aufgabe 4

Unten sind zwei Fragmente von Tabellen aus der Datenbank der Einwohner des Mikrobezirks. Jede Zeile von Tabelle 2 enthält Informationen über das Kind und einen seiner Eltern. Die Information wird durch den Wert des ID-Felds in der entsprechenden Zeile von Tabelle 1 dargestellt. Ermitteln Sie anhand der bereitgestellten Daten die größte Differenz zwischen den Geburtsjahren der Schwestern. Berücksichtigen Sie bei der Berechnung der Antwort nur die Informationen aus den angegebenen Fragmenten der Tabellen.

Antworten: ___________________________.

Lösung

Das erste, worauf Sie achten sollten und sich nicht verwirren lassen, ist, dass wir männliche Vertreter ausschließen (genauer gesagt, wir berücksichtigen sie nicht, wenn wir weibliche Kinder zählen): Dies sind die Zeilen 64, 67, 70, 75, 77, 86 von Tabelle 1.

Wenn wir durch die Felder der Tische gehen, finden wir Paare von Kindermädchen:

Geburtsjahr	Geburtsjahr	Unterschied zwischen den Geburtsjahren

Als Antwort geben wir den größten der beiden Werte der Differenz zwischen den Geburtsjahren ein.

Antworten: 6.

Aufgabe 5

Um eine bestimmte Folge bestehend aus den Buchstaben A, B, C, D, D, E zu codieren, haben wir uns entschieden, einen uneinheitlichen Binärcode zu verwenden, der die Fano-Bedingung erfüllt. Für den Buchstaben A wurde das Codewort 0 verwendet; für den Buchstaben B - Codewort 10. Wie groß ist die kleinstmögliche Summe der Codewortlängen für die Buchstaben C, D, D, E?

Notiz. Die Fano-Bedingung bedeutet, dass kein Codewort der Anfang eines anderen Codeworts ist. Dies ermöglicht eine eindeutige Entschlüsselung verschlüsselter Nachrichten.

Antworten: ___________________________.

Lösung

Um das Problem zu lösen, erstellen wir ein Diagramm:

Ein Codewort der Länge 2–11 oder eines der Codewörter der Länge 3 wird unweigerlich der Beginn eines der Wörter der Länge 4. Die Wahl der Länge 4 beruht auf der Tatsache, dass eine Codierung erforderlich war vier Buchstaben. Die resultierenden Codewörter ergeben zusammen eine Länge von 16.

Antworten: 16.

Aufgabe 6

Die Eingabe des Algorithmus ist eine natürliche Zahl N. Der Algorithmus baut daraus wie folgt eine neue Zahl R auf.

Eine binäre Darstellung der Zahl N wird konstruiert.
Diesem Eintrag werden rechts zwei weitere Ziffern nach folgender Regel hinzugefügt: Wenn N gerade ist, wird zuerst eine Null an das Ende der Zahl (rechts) angehängt, dann eine Eins. Andernfalls, wenn N ungerade ist, wird zuerst rechts eins addiert und dann null.

Beispielsweise würde die binäre Schreibweise 100 für die Zahl 4 in 10001 umgewandelt werden, und die binäre Schreibweise 111 für die Zahl 7 würde in 11110 umgewandelt werden.

Der auf diese Weise erhaltene Datensatz (er enthält zwei Ziffern mehr als der Datensatz der ursprünglichen Zahl N) ist ein binärer Datensatz der Zahl R - das Ergebnis dieses Algorithmus.

Geben Sie die Mindestzahl R an, die größer als 102 ist und das Ergebnis dieses Algorithmus sein kann. Schreiben Sie diese Zahl in Dezimalschreibweise auf.

Antworten: ___________________________.

Lösung

Stellen wir die Zahl 102 in binärer Form dar: 1100110 2 . Wir sind an der Zahl interessiert, die größer sein wird. Wir werden nach oben gehen und nacheinander hinzufügen:

1100111 2 - 103 10 - binäre Darstellung passt nicht zum Algorithmus;

1101000 2 - 104 10 - binäre Darstellung passt nicht zum Algorithmus;

1101001 2 – 105 10 – binäre Darstellung entspricht dem Algorithmus.

Antworten: 105.

Aufgabe 7

Ein Fragment einer Tabelle ist gegeben. Eine Formel wurde von Zelle C3 in Zelle D4 kopiert. Beim Kopieren der Adressen der Zellen in der Formel wurden diese automatisch geändert. Wie lautet der numerische Wert der Formel in Zelle D4?

Notiz. Das $-Zeichen kennzeichnet die absolute Adressierung.

Antworten: ___________________________.

Lösung

Beim Kopieren der Formel in Zelle D4 erhalten wir: =$B$3+E3. Durch Ersetzen der Werte erhalten wir das gewünschte Ergebnis:

400+700 d.h. 1100.

Antworten: 1100.

Aufgabe 8

Notieren Sie die Zahl, die als Ergebnis des folgenden Programms gedruckt wird. Zu Ihrer Bequemlichkeit wird das Programm in fünf Programmiersprachen präsentiert.

Antworten: ___________________________.

Lösung

Verfolgen wir die Änderungen in den Werten der Variablen:

s = 0, n = 75 – Werte vor dem Zyklus;

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

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

n + 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 итерации;

n + 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 итерации;

die Schleife beim nächsten Schritt wird unterbrochen, das Programm zeigt den gewünschten Wert an.

Antworten: 35.

Aufgabe 9

Die automatische Kamera erzeugt Bitmaps mit 200 × 256 Pixeln. Die gleiche Anzahl von Bits wird verwendet, um die Farbe jedes Pixels zu codieren, die Pixelcodes werden lückenlos nacheinander in die Datei geschrieben. Die Größe der Bilddatei darf 65 KB nicht überschreiten, ohne die Größe des Dateikopfs. Was ist die maximale Anzahl von Farben, die in einer Palette verwendet werden können?

Antworten: ___________________________.

Lösung

Beginnen wir mit einigen einfachen Berechnungen:

200 × 256 ist die Anzahl der Pixel in einer Bitmap;

65 KB = 65 × 2 10 × 2 3 Bit – die Obergrenze der Dateigröße.

Die Beziehung zu ermöglicht es uns, die Farbtiefe eines Pixels zu erhalten, d.h. die Anzahl der Bits, die für die Farbcodierung für jedes Pixel zugewiesen sind.

Und schließlich der gewünschte Wert, den wir nach der klassischen Formel ermitteln:

2ich = N, 2 10 .

Antworten: 1024.

Aufgabe 10

Vasya bildet 5-Buchstaben-Wörter, in denen es nur die Buchstaben Z, I, M, A gibt, und in jedem Wort gibt es genau einen Vokal, und er kommt genau 1 Mal vor. Jeder der erlaubten Konsonanten kann in einem Wort beliebig oft oder gar nicht vorkommen. Ein Wort ist jede gültige Folge von Buchstaben, die nicht unbedingt bedeutungsvoll ist. Wie viele Wörter kann Vasya schreiben?

Antworten: ___________________________.

Lösung

Wäre da nicht die Bedingung „es gibt genau einen Vokal und er kommt genau 1 mal vor“, wäre das Problem ganz einfach gelöst. Aber es gibt diese Bedingung, und es gibt zwei verschiedene Vokale.

Dieser Vokal kann in einer von 5 Positionen stehen. Nehmen wir an, sie ist in der ersten Position. In diesem Fall gibt es an dieser Position genau 2 mögliche Vokaloptionen, an den restlichen vier Positionen haben wir zwei Konsonantenoptionen. Summe aller Optionen für den ersten Fall:

2 x 2 x 2 x 2 x 2 = 2 5 = 32

Insgesamt gibt es genau 5 Möglichkeiten für die Position des Vokals in unserem Wort.

Antworten: 160.

Aufgabe 11

Der rekursive Algorithmus F ist im Folgenden in fünf Programmiersprachen geschrieben.

Schreiben Sie in einer Reihe, ohne Leerzeichen oder Trennzeichen, alle Zahlen, die auf dem Bildschirm ausgegeben werden, wenn Sie F(4) aufrufen. Die Zahlen müssen in derselben Reihenfolge geschrieben werden, in der sie auf dem Bildschirm angezeigt werden.

Antworten: ___________________________.

Lösung

Lassen Sie uns zur Verdeutlichung einen Baum erstellen:

Wenn wir uns entlang dieses Rekursionsbaums bewegen, erhalten wir den Wert, der die gewünschte Lösung sein wird.

Antworten: 1231412.

Aufgabe 12

In der TCP/IP-Netzwerkterminologie ist eine Netzmaske eine Binärzahl, die festlegt, welcher Teil der IP-Adresse eines Hosts sich auf die Netzwerkadresse und welcher Teil auf die Adresse des Hosts selbst in diesem Netzwerk bezieht. Normalerweise wird die Maske nach denselben Regeln wie die IP-Adresse geschrieben – in Form von vier Bytes, wobei jedes Byte als Dezimalzahl geschrieben wird. Gleichzeitig gibt es in der Maske zuerst (in den höchsten Ziffern) Einsen und dann ab einer bestimmten Ziffer Nullen. Die Netzwerkadresse wird durch Anwenden einer bitweisen Konjunktion auf die gegebene Host-IP-Adresse und Maske erhalten.

Wenn die Host-IP-Adresse beispielsweise 231.32.255.131 und die Maske 255.255.240.0 lautet, lautet die Netzwerkadresse 231.32.240.0.

Für einen Host mit der IP-Adresse 117.191.37.84 lautet die Netzwerkadresse 117.191.37.80. Was ist der kleinstmögliche Wert des letzten (ganz rechten) Bytes der Maske? Schreiben Sie Ihre Antwort als Dezimalzahl.

Antworten: ___________________________.

Lösung

Lassen Sie uns die binäre Darstellung des letzten rechten Bytes der IP-Adresse, Netzwerkadresse und Maske gemäß der Definition untereinander schreiben (in der oberen Zeile sind der Einfachheit halber die Bits nummeriert):



Maske - ?
Netzwerkadresse

Wir bewegen uns von rechts nach links und ersetzen die Werte der Bits in der Maske. Gleichzeitig berücksichtigen wir, dass es in unserer Maske „zuerst (in den höchsten Ziffern) Einsen und dann ab einer bestimmten Ziffer Nullen gibt“.

Beginnend mit dem 0. Bit (von rechts nach links) wählen wir die Werte der Netzwerkmaske unter Berücksichtigung der bitweisen Konjunktion aus:



Maske - ?
Netzwerkadresse

Im 4. Bit ist offensichtlich, dass der Wert Null nicht mehr passt und dort 1 (Eins) stehen sollte. Ausgehend von dieser Position und weiter nach links haben wir alle Einheiten:



Maske - ?
Netzwerkadresse

Das ganz rechts nachzuschlagende Byte ist 111100002, was dezimal 24010 entspricht.

Antworten: 240.

Aufgabe 13

Bei der Registrierung in einem Computersystem erhält jeder Benutzer ein Passwort, das aus 7 Zeichen besteht und nur Zeichen aus dem 26-Zeichen-Satz lateinischer Großbuchstaben enthält. Die Datenbank speichert Informationen über jeden Benutzer mit der gleichen und der kleinstmöglichen ganzzahligen Anzahl von Bytes. Dabei wird eine zeichenweise Codierung von Passwörtern verwendet, alle Zeichen werden mit der gleichen und der geringstmöglichen Anzahl von Bits codiert. Neben dem Passwort selbst werden für jeden Benutzer zusätzliche Informationen im System gespeichert, denen eine ganzzahlige Anzahl von Bytes zugeordnet ist; diese Nummer ist für alle Benutzer gleich.

Es dauerte 600 Bytes, um Informationen über 30 Benutzer zu speichern. Wie viele Bytes werden für die Speicherung zugewiesen Weitere Informationenüber einen Benutzer? Notieren Sie in der Antwort nur eine Ganzzahl - die Anzahl der Bytes.

Antworten: ___________________________.

Lösung

Die Informationen jedes Benutzers werden gespeichert

600 ÷ 30 = 20 Byte.

Für die Codierung von 26 Zeichen sind mindestens 5 Bit Speicher erforderlich. Daher wird ein Passwort mit 7 Zeichen benötigt

5 × 7 = 35 Bit.

35 Bit erfordern mindestens 5 Byte Speicher.

Die gewünschte Anzahl von Bytes zum Speichern zusätzlicher Informationen über einen Benutzer beträgt:

20 Bytes - 5 Bytes = 15 Bytes.

Antworten: 15.

Aufgabe 14

Executor Editor empfängt eine Zahlenfolge als Eingabe und konvertiert sie. Der Editor kann zwei Befehle ausführen, wobei v und w in beiden Befehlen für Zahlenfolgen stehen.

A) ersetze (v, w).

Dieser Befehl ersetzt das erste Vorkommen von v links in einer Zeichenfolge durch w. Beispielsweise das Ausführen des Befehls

ersetzen (111, 27)

wandelt die Zeichenfolge 05111150 in die Zeichenfolge 0527150 um.

Wenn eine Zeichenfolge kein Vorkommen der Zeichenfolge v enthält, ändert die Ausführung des Befehls replace (v, w) die Zeichenfolge nicht.

B) gefunden (v).

Dieser Befehl prüft, ob der String v in der Zeile des Executor-Editors vorkommt. Wenn es auftritt, gibt der Befehl den logischen Wert "true" zurück, andernfalls den Wert "false". Der Executor-String wird nicht geändert.

Tschüss Bedingung

Befehlsfolge

ENDE AUF WIEDERSEHEN

ausgeführt, solange die Bedingung wahr ist.

Im Aufbau

IF-Bedingung

AN team1

ENDE WENN

command1 wird ausgeführt (wenn Bedingung wahr ist).

Im Aufbau

IF-Bedingung

AN team1

ELSE-Team2

ENDE WENN

command1 (wenn die Bedingung wahr ist) oder command2 (wenn die Bedingung falsch ist) wird ausgeführt.

Welche Zeichenfolge erhält man, wenn man das folgende Programm auf eine Zeichenfolge aus 82 aufeinanderfolgenden Einsen anwendet? Notieren Sie den empfangenen String in der Antwort.

NOCH gefunden (11111) ODER gefunden (888)

WENN gefunden (11111)

zu ersetzen (11111, 88)

WENN gefunden (888)

zu ersetzen (888, 8)

ENDE WENN

ENDE AUF WIEDERSEHEN

Antworten: ___________________________.

Lösung

Stellen wir uns die Situation vor:

82 Einheiten können bedingt als 16 Gruppen von 5 Einheiten sowie eine Gruppe von zwei Einheiten dargestellt werden. Der erste Aufruf des Bedingungsoperators liefert uns 16 Achtergruppen – das sind 32 Achter oder 10 Dreierachtergruppen, sowie ein weiteres freies Achterpaar. Es liegt auf der Hand, dass die letzten beiden Einheiten vom Performer unbeeinflusst bleiben. Und die 12 verbleibenden Achter, zu dritt gruppiert, sind bereits 4 Achter. Eine weitere Iteration - es gibt 2 Achten und 2 Einsen.

Antworten: 8811.

Aufgabe 15

Die Abbildung zeigt ein Diagramm der Straßen, die die Städte A, B, C, D, E, F, G, Z, I, K, L, M verbinden. Sie können sich auf jeder Straße nur in eine Richtung bewegen, die durch den Pfeil angezeigt wird .

Wie viele verschiedene Wege gibt es von Stadt A nach Stadt M, die durch Stadt L führen?

Antworten: ___________________________.

Lösung

Betrachten Sie unser Schema noch einmal. Dieses Mal sehen wir auf dem Diagramm die Beschriftungen in einer bestimmten Reihenfolge angeordnet.

Zunächst stellen wir fest, dass die Pfade vom Punkt And zum Punkt M - eine gerade Linie und durch den Punkt K - farbig hervorgehoben sind. Dies geschieht, weil es je nach Problemstellung erforderlich ist, die Anzahl der Wege nur durch den Punkt A zu bestimmen.

Beginnen wir beim Startpunkt A – das ist ein besonderer Punkt, dort führt keine Straße hin, formal kommt man nur von ihm selbst dorthin. Nehmen wir an, dass die Anzahl der Pfade zu ihm 1 ist.

Der zweite Punkt B - es ist offensichtlich, dass er nur von einem Punkt und nur auf einem Weg erreicht werden kann. Der dritte Punkt kann weder C noch D sein – die Anzahl der Pfade zu Punkt C kann nicht bestimmt werden, ohne die Anzahl der Pfade in D zu bestimmen, und in D – ohne die Anzahl der Pfade in D zu bestimmen. D ist der dritte Punkt auf unserem Pfad . Die Anzahl der Pfade, die dorthin führen, ist 1. Lassen Sie uns diese Folgerungskette fortsetzen, indem wir die Anzahl der Pfade, die zu einem bestimmten Punkt führen, als die Summe der Anzahl der Pfade in vorherigen Punkten definieren, die direkt zum aktuellen Punkt führen. Punkt I - ein kritischer Punkt - die Anzahl der dorthin führenden Wege entspricht der Summe von 5 (E) + 16 (W) + 7 (Z) und ist gleich 28. Der nächste Punkt ist L, zu dem die Straße führt Es geht nur durch I, es gibt keinen anderen Weg, und daher bleibt die Anzahl der Wege auch gleich 28. Und schließlich, zum Zielpunkt - M - führt je nach Problemstellung nur eine Straße dorthin, die bedeutet, dass der gewünschte Wert auch gleich 28 bleibt.

Antworten: 28.

Aufgabe 16

Der Wert des arithmetischen Ausdrucks 9 7 + 3 21 - 9 wurde im Zahlensystem mit der Basis 3 geschrieben. Wie viele Ziffern „2“ sind in diesem Eintrag enthalten?

Antworten: ___________________________.

Um das Problem zu lösen, schreiben wir den ursprünglichen Ausdruck um und führen auch Permutationen der Terme durch:

3 21 + 3 14 – 3 2 .

Denken Sie daran, dass im ternären Zahlensystem die Zahl 3 10 selbst als 10 3 geschrieben wird. K-te Potenz von 10 N Essenz 1 und K Nullen. Und es ist auch offensichtlich, dass das erste Glied 3 21 die Anzahl der Zweien in keiner Weise beeinflusst. Aber der Unterschied kann sich auswirken.

Antworten: 12.

Aufgabe 17

In der Suchmaschinen-Abfragesprache wird das Symbol "|" verwendet, um die logische Operation "ODER" zu bezeichnen, und das Symbol "&" wird verwendet, um die logische Operation "UND" zu bezeichnen.

Die Tabelle zeigt Suchanfragen und die Anzahl der von ihnen gefundenen Seiten für ein bestimmtes Segment des Internets.

Wie viele Seiten (in Hunderttausenden) werden für die Abfrage gefunden Kehle | Schiff | Nase? Es wird davon ausgegangen, dass alle Anfragen fast gleichzeitig ausgeführt wurden, sodass sich die Menge der Seiten mit allen gesuchten Wörtern während der Ausführung der Anfragen nicht geändert hat.

Antworten: ___________________________.

Lösung

Natürlich gibt die OR-Operation die Operation an, die Werte der gefundenen Seiten für jedes Wort separat zu addieren: 35+35+40. Aber bei einigen Abfragen gab es Seiten, die für jedes der Wortpaare gemeinsam waren - sie müssen ausgeschlossen werden, d.h. Es ist notwendig, 33 von der zuvor gefundenen Summe abzuziehen.

Antworten: 77.

Aufgabe 18

Für was ist die größte nicht negative ganze Zahl A der Ausdruck

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

identisch wahr, d.h. den Wert 1 für jede nicht negative ganze Zahl x und y annimmt?

Antworten: ___________________________.

Lösung

Das Problem ist rein mathematisch...

Der in der Zuordnungsbedingung angegebene Ausdruck ist die Disjunktion dreier Terme. Der zweite und dritte Term sind abhängig vom gewünschten Parameter:

Stellen wir den ersten Term anders dar:

j = –2X+ 48

Punkte einer Geraden (Graph der Funktion) mit ganzzahligen Koordinaten sind diejenigen Werte der Variablen x und y, bei denen sie aufhört zu gelten. Daher müssen wir ein A finden, das an diesen Stellen die Wahrheit oder sicherstellt.

Oder für verschiedene x und y, die zu der Linie gehören, nehmen sie abwechselnd (manchmal gleichzeitig) den wahren Wert für jedes A im Bereich an. In diesem Zusammenhang ist es wichtig zu verstehen, was der Parameter A für den Fall wann sein sollte j = X.

Diese. Wir bekommen das System:

Die Lösung ist leicht zu finden: y=x=16. Und die größte ganze Zahl, die für den Parameter A=15 zu uns passt.

Antworten: 15.

Aufgabe 19

Das Programm verwendet ein eindimensionales Integer-Array A mit Indizes von 0 bis 9. Die Werte der Elemente sind 2, 4, 3, 6, 3, 7, 8, 2, 9, 1, d.h. A=2, A=4 usw. Ermitteln Sie den Wert einer Variablen C nach dem Ausführen des folgenden Fragments dieses Programms, das unten in fünf Programmiersprachen geschrieben ist.

Antworten: ___________________________.

Lösung

Das Programmfragment führt eine Wiederholungsschleife aus. Die Anzahl der Iterationen beträgt 9. Jedes Mal, wenn die Bedingung erfüllt ist, wird die Variable Mit erhöht seinen Wert um 1 und vertauscht außerdem die Werte zweier Array-Elemente.

Anfangsfolge: 2, 4, 3, 6, 3, 7, 8, 2, 9, 1. Das folgende Iterationsschema kann in den Datensatz eingebaut werden:

Iterationsschritt:	Zustandsprüfung	Nach Austausch	Variable Mit






	2<2 – НЕТ

	2<1 – НЕТ

Antworten: 7.

Aufgabe 20

Der Algorithmus ist unten in fünf Programmiersprachen geschrieben. Nachdem dieser Algorithmus eine natürliche Dezimalzahl x als Eingabe erhalten hat, gibt er zwei Zahlen aus: L und M. Geben Sie die größte Zahl x an, bei deren Eingabe der Algorithmus zuerst 21 und dann 3 druckt.

Antworten: ___________________________.

Lösung

Etwas Codeanalyse:

Wir müssen die Werte der Variablen L und M anzeigen. Die Variable M, dies ist aus einer kleinen Studie des Codes ersichtlich, gibt die Anzahl der Iterationen der Schleife an, d.h. der Rumpf der Schleife muss genau dreimal ausgeführt werden.
Der Wert der Zahl L, die zuerst angezeigt werden soll, ist das Produkt gleich 21. Sie können 21 im Produkt aus 7 und 3 erhalten. Beachten Sie auch, dass das Produkt nur möglich ist, wenn der Wert der Variablen ungerade ist X in der aktuellen Iteration.
Der Bedingungsoperator gibt an, dass der Wert der Variablen in einem von drei Fällen gerade ist. In den verbleibenden zwei Zeiten mit einem ungeraden Wert der Variablen X, Wir erhalten, dass der Rest der Division von x durch 8 einmal 3 und das andere Mal 7 ist.
Variabler Wert X wird durch eine ganzzahlige Divisionsoperation um den Faktor 8 reduziert.

Wenn wir alle oben genannten Punkte kombinieren, erhalten wir zwei Optionen:

X 1 = (7 × 8 + ?) × 8 + 3 und X 2 = (3 × 8 + ?) × 8 + 7

Anstelle eines Fragezeichens müssen wir einen Wert wählen, der nicht größer als 8 und gerade ist. Vergessen wir nicht die Bedingung in der Aufgabe - "größtes x". Der größere ist gerade und überschreitet nicht 8 - 6. Und von x1 und x2 ist es offensichtlich, dass der erste größer ist. Beim Rechnen erhalten wir x=499.

Antworten: 499.

Aufgabe 21

Bestimmen Sie die Zahl, die als Ergebnis des folgenden Algorithmus gedruckt wird. Der Einfachheit halber wird der Algorithmus in fünf Programmiersprachen präsentiert.

Notiz. Die Funktionen abs und iabs geben den absoluten Wert ihres Eingabeparameters zurück.

Antworten: ___________________________.

Lösung

Schreiben wir unsere Funktion in der üblichen Form:

Zur Verdeutlichung des Bildes werden wir auch einen Graphen dieser Funktion erstellen:

Wenn wir uns den Code genau ansehen, stellen wir die folgenden offensichtlichen Tatsachen fest: Bis zu dem Moment, in dem die Schleife ausgeführt wird, ist die Variable M=-20 und R=26.

Nun die Schleife selbst: Einundzwanzig Iterationen, jede abhängig von der Erfüllung (oder dem Fehlschlagen) der Bedingung. Es ist nicht nötig, alle Werte zu überprüfen - die Grafik wird uns hier sehr helfen. Von links nach rechts ändern sich die Werte der Variablen M und R, bis der erste Minimalpunkt erreicht ist: x=-8. Weiter und bis zum Punkt x=8 liefert die Bedingungsprüfung falsche Werte und die Werte der Variablen ändern sich nicht. An der Stelle x=8 ändern sich die Werte zum letzten Mal. Wir erhalten das gewünschte Ergebnis M=8, R=2, M+R=10.

Antworten: 10.

Aufgabe 22

Performer Calculator konvertiert die auf dem Bildschirm geschriebene Zahl. Der Darsteller hat drei Teams, denen Nummern zugewiesen sind:

2 hinzufügen
mit 2 multiplizieren
3 hinzufügen

Der erste erhöht die Zahl auf dem Bildschirm um 2, der zweite multipliziert sie mit 2, der dritte erhöht sie um 3.

Das Programm für den Rechner ist eine Folge von Befehlen.

Wie viele Programme gibt es, die die ursprüngliche Zahl 2 in die Zahl 22 umwandeln und der Rechenpfad des Programms die Zahl 11 enthält?

Die Trajektorie von Programmberechnungen ist die Folge von Ergebnissen der Ausführung aller Programmbefehle. Zum Beispiel für Programm 123 mit der Anfangsnummer 7 besteht die Trajektorie aus den Nummern 9, 18, 21.

Antworten: ___________________________.

Lösung

Zunächst lösen wir das Problem einfach, ohne die zusätzliche Bedingung „enthält die Zahl 11“ zu berücksichtigen:

Das Programm ist kurz und gibt in seiner Flugbahn auch nicht den Wert 11. Und hier lohnt es sich, die Aufgabe in zwei kleine Aufgaben aufzuteilen: Bestimmen Sie die Anzahl der Pfade von 2 bis 11 und von 11 bis 22. Das Endergebnis, offensichtlich dem Produkt dieser beiden Werte entsprechen. Das Erstellen komplexer Schemata mit Bäumen ist keine rationale Zeitverschwendung für die Prüfung. Es gibt nicht so viele Zahlen in unserem Bereich, daher schlage ich vor, den folgenden Algorithmus in Betracht zu ziehen:

Wir schreiben alle Zahlen vom Anfang bis zum letzten inklusive aus. Unter dem ersten Schreiben 1. Berücksichtigen Sie von links nach rechts die Anzahl der Möglichkeiten, um mit den uns gegebenen Befehlen zur aktuellen Position zu gelangen.

Sie können offensichtliche Positionen, die die Entscheidung nicht beeinflussen, sofort entfernen: 3 kann durchgestrichen werden - es ist klar, dass sie von der Ausgangsposition aus nicht mit einem der uns zur Verfügung stehenden Befehle erreicht werden kann; 10 - dadurch können wir nicht in unsere Zwischen- und vor allem Pflichtposition 11 gelangen.

Wir können auf zwei Arten zu 4 kommen – Teams: x2 und +2, d.h. 2 Wege führen durch 4. Schreiben wir diesen Wert unter 4. Es gibt nur einen Weg, um auf 5 zu kommen: +3. Schreiben wir den Wert 1 unter 5. Sie können auf 6 nur durch 4 gelangen. Und darunter haben wir den Wert 2. Dementsprechend gelangen wir auf diesen beiden Wegen, wenn wir 4 passieren, von 2 nach 6 Wir schreiben unter 6 den Wert 2. In 7 können Sie mit den Befehlen, die wir haben, von den beiden vorherigen Positionen kommen, und um die Anzahl der Pfade zu erhalten, die uns zur Verfügung stehen, um 7 zu treffen, werden wir die Zahlen addieren, die wir haben unter diesen vorherigen Positionen angegeben. Diese. bei 7 erhalten wir 2 (unter 4) + 1 (unter 5) = 3 Wege. Nach diesem Schema und weiter erhalten wir:

Gehen wir zur rechten Hälfte des bedingten Zentrums - 11. Erst jetzt werden wir bei der Berechnung nur die Pfade berücksichtigen, die durch dieses Zentrum verlaufen.

Antworten: 100.

Aufgabe 23

Wie viele verschiedene Wertesätze von booleschen Variablen x1, x2, ... x7, y1, y2, ... y7 gibt es, die alle folgenden Bedingungen erfüllen?

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

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

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

Die Antwort muss nicht alle verschiedenen Wertesätze der Variablen x1, x2, ... x7, y1, y2, ... y7 auflisten, unter denen das gegebene Gleichheitssystem erfüllt ist. Als Antwort müssen Sie die Anzahl solcher Sätze angeben.

Antworten: ___________________________.

Lösung

Eine ziemlich detaillierte Analyse dieser Kategorie von Problemen wurde einmal im Artikel "Systeme logischer Gleichungen: Lösung mit Bitketten" veröffentlicht.

Und für weitere Überlegungen erinnern wir uns an einige Definitionen und Eigenschaften (zur Verdeutlichung schreiben wir sie aus):

Schauen wir uns noch einmal unser System an. Beachten Sie, dass es etwas anders umgeschrieben werden kann. Dazu stellen wir zunächst fest, dass jeder der ausgewählten Faktoren in den ersten sechs Gleichungen sowie ihr gemeinsames Produkt gleich 1 sind.

Arbeiten wir ein wenig an den ersten Faktoren der Gleichungen im System:

Unter Berücksichtigung der obigen Überlegungen erhalten wir zwei weitere Gleichungen, und das ursprüngliche Gleichungssystem nimmt die Form an:

In dieser Form wird das ursprüngliche System auf die im vorherigen Artikel besprochenen typischen Aufgaben reduziert.

Wenn wir die erste und die zweite Gleichung des neuen Systems getrennt betrachten, dann entsprechen ihnen die Mengen (lassen Sie mich eine detaillierte Analyse dieser Schlussfolgerung für den Leser geben):

Diese Argumentation WÜRDE uns zu den möglichen 8 × 8 = 64 möglichen Lösungen führen, wenn nicht die dritte Gleichung. Bei der dritten Gleichung können wir uns gleich darauf beschränken, nur solche Varianten von Mengen zu betrachten, die für die ersten beiden Gleichungen geeignet sind. Wenn wir den ersten Satz in die dritte Gleichung einsetzen j 1…j 7, die nur aus 1 besteht, dann ist es offensichtlich, dass ihr nur ein Satz entspricht X 1…X 7, die ebenfalls nur aus 1 besteht. Jede andere Menge, die mindestens eine 0 enthält, ist für uns nicht geeignet. Betrachten Sie den zweiten Satz y1…y7 – 0111111. Für X 1, beide möglichen Werte sind erlaubt - 0 und 1. Die verbleibenden Werte können wie im vorherigen Fall nicht gleich 0 sein. Wir haben zwei Sätze, die dieser Bedingung entsprechen. Der dritte Satz y1…y7 - 011111 stimmt mit den ersten drei Sätzen überein X 1…X 7. usw. Wenn wir ähnlich argumentieren, erhalten wir, dass die gewünschte Anzahl von Sätzen gleich ist

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

Antworten: 36.

Teil 2

Notieren Sie die Antworten zu den Aufgaben in diesem Teil (24–27) auf dem ANTWORTFORMULAR Nr. 2. Notieren Sie zuerst die Aufgabennummer (24, 25 usw.) und dann die vollständige Lösung. Schreiben Sie Ihre Antworten klar und leserlich.

Darüber hinaus sehen wir keine Notwendigkeit, etwas anderes als den offiziellen Inhalt der KIM-Demo zu entwickeln. Dieses Dokument enthält bereits „den Inhalt der richtigen Antwort und Hinweise zur Bewertung“, sowie „Hinweise zur Bewertung“ und einige „Hinweise für den Prüfer“. Dieses Material wird im Folgenden vorgestellt.

Aufgabe 24

Zur Verarbeitung wird eine natürliche Zahl empfangen, die nicht größer als 109 ist. Sie müssen ein Programm schreiben, das die kleinste gerade Ziffer dieser Zahl anzeigt. Wenn die Nummer keine geraden Ziffern enthält, zeigen Sie „NEIN“ auf dem Bildschirm an. Der Programmierer hat das Programm falsch geschrieben. Unten ist dieses Programm für Ihre Bequemlichkeit in fünf Programmiersprachen angegeben.

Gehen Sie nacheinander wie folgt vor.

1. Schreiben Sie auf, was dieses Programm anzeigt, wenn Sie die Zahl 231 eingeben.

2. Geben Sie ein Beispiel für eine solche dreistellige Zahl, bei deren Eingabe das angegebene Programm trotz Fehlern die richtige Antwort gibt.

3. Finde die Fehler des Programmierers und korrigiere sie. Das Korrigieren eines Fehlers sollte nur die Zeile betreffen, die den Fehler enthält. Für jeden Fehler:

schreiben Sie die Zeile aus, in der der Fehler gemacht wurde;
Geben Sie an, wie der Fehler behoben werden kann, d. h. Geben Sie die richtige Version der Zeichenfolge an.

Es ist bekannt, dass genau zwei Zeilen im Text des Programms korrigiert werden können, damit es richtig funktioniert.

Es reicht aus, die Fehler und die Art und Weise, sie zu beheben, für eine Programmiersprache anzugeben.

Bitte beachten Sie, dass Sie Fehler im vorhandenen Programm finden müssen und nicht eigene schreiben müssen, möglicherweise mit einem anderen Lösungsalgorithmus.

Die Lösung verwendet einen Pascal-Programmeintrag. Sie können das Programm in jeder der vier anderen Programmiersprachen verwenden.

1. Das Programm druckt die Zahl 1.

2. Das Programm gibt beispielsweise für die Zahl 132 die richtige Antwort.

Hinweis für den Rezensenten. Das Programm arbeitet nicht korrekt aufgrund einer fehlerhaften Erstinitialisierung und einer fehlerhaften Prüfung auf das Fehlen gerader Ziffern. Dementsprechend gibt das Programm die richtige Antwort, wenn die eingegebene Zahl keine 0 enthält, mindestens eine gerade Ziffer enthält und die kleinste gerade Ziffer der Zahl nicht größer ist als die niedrigstwertige (ganz rechts) Ziffer der Zahl (oder einfach steht zuletzt).

3. Es gibt zwei Fehler im Programm.

Erster Fehler: falsche Initialisierung der Antwort (Variable minDigit).

Fehlerzeile:

minDigit:= N mod 10;

Korrekte Lösung:

Anstelle von 10 kann jede ganze Zahl größer als 8 verwendet werden.

Zweiter Fehler: Falsche Prüfung auf das Fehlen gerader Ziffern.

Fehlerzeile:

wenn minDigit = 0 dann

Korrekte Lösung:

wenn minDigit = 10 dann

Anstelle von 10 kann es eine andere Zahl größer als 8 geben, die in minDigit eingegeben wurde, als der erste Fehler behoben wurde, oder prüfen, ob minDigit > 8 ist

Bewertungsrichtlinien	Punkte
Beachten Sie! Die Aufgabe erforderte vier Schritte: 1) angeben, was das Programm für eine bestimmte Eingabenummer ausgeben wird; 2) Geben Sie ein Beispiel für die Eingabenummer an, bei der das Programm die richtige Antwort gibt. 3) den ersten Fehler beheben; 4) behebe den zweiten Fehler. Um die Korrektheit der Ausführung von Punkt 2) zu überprüfen, ist es notwendig, das ursprüngliche (fehlerhafte) Programm mit den vom Prüfling angegebenen Eingabedaten formal auszuführen und sicherzustellen, dass das vom Programm ausgegebene Ergebnis das gleiche ist wie für das richtiges Programm. Für die Maßnahmen 3) und 4) gilt der Fehler als behoben, wenn beide der folgenden Bedingungen erfüllt sind: a) die Zeile mit dem Fehler richtig angegeben ist; b) eine neue Version des Strings wird spezifiziert, so dass, wenn ein weiterer Fehler korrigiert wird, das korrekte Programm erhalten wird
Alle vier erforderlichen Schritte wurden ausgeführt, und es wird keine korrekte Zeile als Fehler aufgeführt
Die Bedingungen, die es Ihnen ermöglichen, 3 Punkte zu setzen, sind nicht erfüllt. Eine der folgenden Situationen tritt ein: a) drei der vier erforderlichen Aktionen abgeschlossen sind. Keine korrekte Zeile wird als Fehler aufgeführt; b) alle vier notwendigen Schritte abgeschlossen sind. Nicht mehr als eine richtige Zeile wird als fehlerhaft angezeigt
Die Bedingungen, die es Ihnen ermöglichen, 2 oder 3 Punkte zu setzen, sind nicht erfüllt. Zwei der vier erforderlichen Aktionen abgeschlossen
Bedingungen, die es Ihnen ermöglichen, 1, 2 oder 3 Punkte zu setzen, sind nicht erfüllt

Aufgabe 25

Gegeben sei ein Integer-Array mit 30 Elementen. Array-Elemente können natürliche Werte von 1 bis einschließlich 10.000 annehmen. Beschreiben Sie in einer der Programmiersprachen einen Algorithmus, der das Minimum unter den Elementen eines Arrays findet, die nicht durch 6 teilbar sind, und dann jedes Element, das nicht durch 6 teilbar ist, durch eine Zahl ersetzt, die dem gefundenen Minimum entspricht. Es ist garantiert, dass mindestens ein solches Element im Array vorhanden ist. Als Ergebnis müssen Sie das geänderte Array anzeigen, jedes Element wird in einer neuen Zeile angezeigt.

Zum Beispiel für ein anfängliches Array aus sechs Elementen:

Das Programm sollte das folgende Array ausgeben

Bei Paskal

Bei Python

im BASIC

In C++

In algorithmischer Sprache

Bewertungsrichtlinien	Punkte
Allgemeine Anweisungen. 1. In einem in einer Programmiersprache geschriebenen Algorithmus ist das Vorhandensein einzelner syntaktischer Fehler erlaubt, die die Absicht des Autors des Programms nicht verzerren. 2. Die Effizienz des Algorithmus spielt keine Rolle und wird nicht bewertet. 3. Es ist erlaubt, den Algorithmus in einer anderen Programmiersprache als den in der Bedingung angegebenen Sprachen zu schreiben. In diesem Fall sollten ähnliche Variablen wie in der Bedingung beschrieben verwendet werden. Wenn eine Programmiersprache typisierte Variablen verwendet, müssen Variablendeklarationen den Variablendeklarationen in der Algorithmic Language ähneln. Die Verwendung von nicht typisierten oder nicht deklarierten Variablen ist nur möglich, wenn die Programmiersprache dies zulässt; gleichzeitig muss die Anzahl der Variablen und ihrer Bezeichner der Problemstellung entsprechen. 4. Ein anderes Array-Ausgabeformat als das angegebene ist erlaubt, zB in einer Zeile
Es wurde ein korrekter Algorithmus vorgeschlagen, der das ursprüngliche Array modifiziert und als Ergebnis das modifizierte Array ausgibt
Die Bedingungen sind erfüllt, so dass 2 Punkte gesetzt werden können. Gleichzeitig wird eine allgemein richtige Lösung vorgeschlagen, die nicht mehr als einen der folgenden Fehler enthält: 1) die Schleife geht über die Array-Grenze hinaus; 2) das Minimum ist nicht initialisiert oder falsch initialisiert; 3) die Überprüfung der Teilbarkeit durch 6 wird falsch durchgeführt; 4) die Teilbarkeit durch 6 wird nicht vom Array-Element, sondern von seinem Index geprüft; 5) im Vergleich zum Minimum werden die Zeichen "größer" und "kleiner" verwechselt; 6) Vergleich mit dem Minimum wird für den Index des Array-Elements durchgeführt und nicht für seinen Wert; 7) die logische Bedingung ist falsch zusammengesetzt (zum Beispiel, oder wird anstelle von und verwendet); 8) das ursprüngliche Array ändert sich nicht; 9) nicht alle erforderlichen Elemente werden geändert (z. B. nur das erste oder letzte von ihnen); 10) die Antwort wird nicht ausgegeben oder die Antwort wird nicht vollständig angezeigt (z. B. nur ein Element des Arrays aufgrund des übersprungenen Zyklus der Ausgabe von Elementen oder Operatorklammern); 11) es wird eine Variable verwendet, die nicht im Variablendeklarationsabschnitt deklariert ist; 12) die Bedingung für das Beenden des Zyklus ist nicht oder falsch angegeben;
Es gibt zwei oder mehr Fehler, die in den Absätzen 1–13 aufgeführt sind, oder der Algorithmus ist falsch formuliert (einschließlich des Fehlens eines expliziten oder impliziten Suchzyklus für das gewünschte Element).
Höchste Punktzahl

Aufgabe 26

Zwei Spieler, Petya und Vanya, spielen das folgende Spiel. Vor den Spielern liegen zwei Steinhaufen. Die Spieler ziehen der Reihe nach, Petya macht den ersten Zug. In einem Zug kann der Spieler einen Stein auf einen der Stapel legen (seiner Wahl) oder die Anzahl der Steine im Stapel verdreifachen. Lassen Sie zum Beispiel 10 Steine in einem Stapel und 7 Steine in einem anderen liegen; eine solche Position im Spiel wird mit (10, 7) bezeichnet. Dann können Sie in einem Zug jede der vier Positionen erreichen:

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

Um Züge zu machen, hat jeder Spieler eine unbegrenzte Anzahl von Steinen.

Das Spiel endet in dem Moment, in dem die Gesamtzahl der Steine in den Stapeln mindestens 68 erreicht. Der Gewinner ist der Spieler, der den letzten Zug gemacht hat, d.h. der erste, der eine solche Position erreicht, in der 68 oder mehr Steine in den Stapeln liegen.

Im ersten Moment waren sechs Steine im ersten Haufen und S Steine im zweiten Haufen; 1 ≤ S ≤ 61.

Wir werden sagen, dass ein Spieler eine Gewinnstrategie hat, wenn er für alle Züge des Gegners gewinnen kann. Die Strategie eines Spielers zu beschreiben bedeutet, zu beschreiben, welchen Zug er in jeder Situation machen sollte, der er mit den Spielzügen verschiedener Gegner begegnen kann. Die Beschreibung einer Gewinnstrategie sollte nicht die Züge des nach dieser Strategie spielenden Spielers umfassen, die für ihn nicht unbedingt gewinnend sind, d.h. nicht zu gewinnen, unabhängig vom Spiel des Gegners.

Erledige die folgenden Aufgaben.

Übung 1

c) Geben Sie alle diese Werte der Zahl S an, für die Petya in einem Zug gewinnen kann.

d) Es ist bekannt, dass Vanya mit seinem ersten Zug nach Petyas erfolglosem ersten Zug gewann. Geben Sie den Mindestwert von S an, wenn eine solche Situation möglich ist.

Aufgabe 2

Geben Sie den Wert von S an, für den Petya eine Gewinnstrategie hat und zwei Bedingungen gleichzeitig erfüllt sind:

Petya kann nicht in einem Zug gewinnen;
Petya kann mit seinem zweiten Zug gewinnen, unabhängig davon, wie Vanya sich bewegt.

Beschreiben Sie für den gegebenen Wert von S Petyas Gewinnstrategie.

Aufgabe 3

Geben Sie den Wert von S an, bei dem zwei Bedingungen gleichzeitig erfüllt sind:

Vanya hat eine Gewinnstrategie, die es ihm ermöglicht, im ersten oder zweiten Zug in jedem Spiel von Petya zu gewinnen.
Vanya hat keine Strategie, die es ihm ermöglicht, im ersten Zug zu gewinnen.

Beschreiben Sie für den gegebenen Wert von S Wanjas Gewinnstrategie.

Erstelle einen Baum aller Spiele, die mit Wanjas Gewinnstrategie möglich sind (in Form einer Figur oder einer Tabelle).

Geben Sie Positionen in den Knoten des Baums an, es wird empfohlen, Bewegungen an den Kanten anzuzeigen. Der Baum sollte keine Spiele enthalten, die für den gewinnenden Spieler unmöglich sind, seine Gewinnstrategie umzusetzen. Beispielsweise ist der vollständige Spielbaum keine gültige Antwort für diese Aufgabe.

Übung 1

a) Petya kann mit 21 ≤ S ≤ 61 gewinnen.

Aufgabe 2

Möglicher Wert von S: 20. In diesem Fall kann Petya natürlich nicht mit dem ersten Zug gewinnen. Er kann jedoch Position (7, 20) erreichen. Nach Vanyas Zug kann eine von vier Positionen erscheinen: (8, 20), (21, 20), (7, 21), (7, 60). In jeder dieser Stellungen kann Petya in einem Zug gewinnen, indem sie die Anzahl der Steine im zweiten Stapel verdreifacht.

Hinweis für den Rezensenten. Ein weiterer möglicher Wert von S für diese Aufgabe ist die Zahl 13. In diesem Fall besteht Petyas erster Schritt darin, die Anzahl der Steine im kleineren Stapel zu verdreifachen und die Position (6 * 3, 13) = (18, 13) zu erhalten. Mit dieser Position kann Wanja beim ersten Zug nicht gewinnen, und nach jedem Zug von Wanja kann Petja gewinnen, indem sie die Anzahl der Steine im größeren Stapel verdreifacht. Es reicht aus, einen Wert von S anzugeben und eine Gewinnstrategie dafür zu beschreiben.

Aufgabe 3

Möglicher Wert von S: 19. Nach Petyas erstem Zug sind Stellungen möglich:
(7, 19), (18, 19), (6, 20), (6, 57). In den Positionen (18, 19) und (6, 57) kann Wanja mit dem ersten Zug gewinnen und die Anzahl der Steine im zweiten Stapel verdreifachen. Von den Positionen (7, 19) und (6, 20) kann Vanya die Position (7, 20) erreichen. Diese Stellung wird in Absatz 2 analysiert. Der Spieler, der sie erhalten hat (jetzt Wanja), gewinnt mit seinem zweiten Zug.

Die Tabelle zeigt den Baum der möglichen Spiele (und nur diese) für Wanjas beschriebene Strategie. Die Endstellungen (Vanya gewinnt sie) sind fett gedruckt. In der Abbildung ist derselbe Baum grafisch dargestellt (beide Arten der Darstellung des Baums sind akzeptabel).

Hinweis für den Fachmann. Der Baum aller Parteien kann auch als gerichteter Graph, wie in der Abbildung gezeigt, oder auf andere Weise dargestellt werden. Es ist wichtig, dass die Menge der vollständigen Pfade in der Grafik in einer Eins-zu-Eins-Übereinstimmung mit der Menge der Spiele steht, die mit der in der Lösung beschriebenen Strategie möglich sind.

Reis. 1. Der Baum aller Spiele, die nach Wanjas Strategie möglich sind. Petyas Bewegungen sind in gepunkteten Linien dargestellt; Vanyas Bewegungen sind mit durchgezogenen Linien markiert. Das Rechteck markiert die Positionen, an denen das Spiel endet.

Hinweis für den Rezensenten. Es ist kein Fehler, in einer Situation, in der er mehr als einen Gewinnzug hat, nur einen letzten Zug des gewinnenden Spielers anzugeben

Bewertungsrichtlinien	Punkte
Die Aufgabe erfordert drei Aufgaben, die abgeschlossen werden müssen. Ihre Schwierigkeit steigt. Die Anzahl der Punkte entspricht in der Regel der Anzahl der erledigten Aufgaben (näheres siehe unten). Ein Fehler in der Lösung, der die Hauptidee nicht verfälscht und nicht zu einer falschen Antwort führt, beispielsweise ein Rechenfehler bei der Berechnung der Anzahl der Steine in der Endposition, wird bei der Bewertung der Lösung nicht berücksichtigt. Aufgabe 1 ist erledigt, wenn beide Punkte a) und b) erfüllt sind, d.h. für Punkt a) werden alle Werte von S aufgelistet, die die Bedingung erfüllen (und nur sie), für Punkt b) wird der korrekte Wert von S angegeben (und nur er). Aufgabe 2 ist erledigt, wenn die für Petya gewinnbringende Position korrekt angegeben und die entsprechende Strategie von Petya beschrieben ist - wie im Lösungsbeispiel oder auf andere Weise, beispielsweise anhand eines Baums aller möglichen Spiele für Petyas gewählte Strategie (und nur sie). Aufgabe 3 ist abgeschlossen, wenn die für Wanja gewinnende Position korrekt angegeben ist und ein Baum aller möglichen Spiele unter Wanjas Strategie (und nur ihnen) erstellt wurde. In allen Fällen können die Strategien wie im Lösungsbeispiel oder anders beschrieben werden.
Aufgaben 1, 2 und 3 erledigt
Die Bedingungen für die Erzielung von 3 Punkten sind nicht erfüllt und eine der folgenden Bedingungen ist erfüllt. 1. Aufgabe 3 abgeschlossen. 2. Aufgaben 1 und 2 abgeschlossen
Die Bedingungen für die Erzielung von 3 oder 2 Punkten sind nicht erfüllt und eine der folgenden Bedingungen ist erfüllt. 1. Aufgabe 1 abgeschlossen. 2. Aufgabe 2 abgeschlossen
Keine der Bedingungen, die es Ihnen ermöglichen, 3, 2 oder 1 Punkte zu setzen, ist erfüllt

Aufgabe 27

Die Eingabe des Programms ist eine Folge von N positiven ganzen Zahlen, alle Zahlen in der Folge sind unterschiedlich. Es werden alle Paare verschiedener Elemente der Sequenz berücksichtigt, die sich in einem Abstand von mindestens 4 befinden (der Unterschied in den Indizes der Elemente des Paares muss 4 oder mehr betragen, die Reihenfolge der Elemente im Paar ist unwichtig). Es ist notwendig, die Anzahl solcher Paare zu bestimmen, für die das Produkt der Elemente durch 29 teilbar ist.

Beschreibung der Ein- und Ausgangsdaten

Die erste Zeile der Eingabe enthält die Anzahl der Zahlen N (4 ≤ N ≤ 1000). Jede der folgenden N Zeilen enthält eine positive ganze Zahl, die 10.000 nicht überschreitet.

Als Ergebnis sollte das Programm eine einzelne Zahl ausgeben: die Anzahl der Elementepaare, die in der Folge mindestens 4 voneinander entfernt sind, wobei das Produkt der Elemente ein Vielfaches von 29 ist.

Eingabebeispiel:

Beispielausgabe für die obige Beispieleingabe:

Erläuterung. Aus 7 gegebenen Elementen können unter Berücksichtigung der zulässigen Abstände zwischen ihnen 6 Produkte hergestellt werden: 58 4, 58 1, 58 29, 2 1, 2 29, 3 29. Davon sind 5 Werke in 29 geteilt.

Es ist erforderlich, ein zeit- und speichereffizientes Programm zu schreiben, um das beschriebene Problem zu lösen.

Ein Programm gilt als zeiteffizient, wenn bei einer Erhöhung der Anzahl der Anfangszahlen N um k-mal die Laufzeit des Programms um nicht mehr als k-mal zunimmt.

Ein Programm gilt als speichereffizient, wenn der zum Speichern aller Programmvariablen benötigte Speicherplatz 1 Kilobyte nicht überschreitet und nicht mit N zunimmt.

Die maximale Punktzahl für ein korrektes (ohne Syntaxfehler und richtige Antwort für gültige Eingabedaten gebendes) zeit- und speichereffizientes Programm beträgt 4 Punkte.

Die maximale Punktzahl für ein korrektes Programm, das nur auf Zeit wirkt, beträgt 3 Punkte.

Die maximale Punktzahl für ein korrektes Programm, das die Leistungsanforderungen nicht erfüllt, beträgt 2 Punkte.

Sie können ein Programm oder zwei Problemlösungsprogramme absolvieren (z. B. kann eines der Programme weniger effektiv sein). Wenn Sie zwei Programme bestehen, wird jedes von ihnen unabhängig voneinander bewertet, die letzte ist die größere der beiden Bewertungen.

Achten Sie darauf, den Lösungsalgorithmus vor dem Programmtext kurz zu beschreiben. Geben Sie die verwendete Programmiersprache und deren Version an.

Das Produkt zweier Zahlen ist durch 29 teilbar, wenn mindestens einer der Faktoren durch 29 teilbar ist.

Bei der Eingabe von Zahlen können Sie die Anzahl der Vielfachen von 29 zählen, ohne die letzten vier zu zählen. Nennen wir sie n29.

Hinweis für Gutachter. Die Nummern selbst, mit Ausnahme der letzten vier, können nicht gespeichert werden.

Die nächste gelesene Zahl wird als mögliches rechtes Element des gewünschten Paares betrachtet.

Wenn die nächste gelesene Zahl durch 29 teilbar ist, sollte die Anzahl der Zahlen davor zur Antwort hinzugefügt werden, wobei die letzten vier (einschließlich der gelesenen) nicht mitgezählt werden.

Wenn die nächste gelesene Zahl nicht durch 29 teilbar ist, sollte n29 zur Antwort hinzugefügt werden.

Um ein speichereffizientes Programm zu erstellen, beachten Sie, dass es ausreicht, nur die letzten vier Elemente oder Informationen über sie zu speichern, da die Verarbeitung des nächsten Eingabeelements Werte verwendet, die vier Elemente früher sind.

Unten ist ein Pascal-Programm, das den beschriebenen Algorithmus implementiert (PascalABC-Version wird verwendet)

Beispiel 1. Pascal-Programm. Das Programm ist zeit- und speichereffizient

konstant s = 4; (erforderlicher Abstand zwischen den Elementen)

a: Array von langen Ganzzahlen; (Letzte Werte speichern)

a_: lange Ganzzahl; (nächster Wert)

n29: lange Ganzzahl; (die Zahl, die durch 29 Elemente teilbar ist, die letzten s nicht mitgerechnet)

cnt: lange Ganzzahl; (Anzahl der gesuchten Paare)

(Eingabe der ersten s-Nummern)

for i:=1 to s do readln(a[i]);

(Eingabe anderer Werte, Zählen der gesuchten Paare)

für i:= s + 1 bis n tun

wenn a mod 29 = 0 dann n29:= n29 + 1;

wenn a_ mod 29 = 0 dann cnt:= cnt + i - s

cnt:= cnt + n29;

(Elemente des Hilfsarrays nach links verschieben)

for j:= 1 to s - 1 do a[j] := a;

a[s] := a_ (aktuelles Element an das Ende des Arrays schreiben)

Ende August wurden Demoversionen des KIM USE 2019 auf der offiziellen Website des FIPI veröffentlicht (darunter die Demoversion des USE in Informatics).

Für Absolventen von großem Interesse sind die Dokumente, die den Aufbau und Inhalt von KIM regeln – der Kodifikator und die Spezifikation.

USE in Informatics 2019 - Demo mit Antworten und Kriterien von FIPI

USE 2019 in der Informatik-Demoversion	Demo 2019 + Antworten herunterladen
Spezifikation	Demovariante informatika ege
Kodifikator	Kodifikator

Änderungen in KIM 2019 gegenüber KIM 2018.

Das KIM-Modell von 2019 wird sich gegenüber 2018 nicht ändern. Die Anzahl der Aufgaben, ihre Schwierigkeitsgrade, die zu testenden Inhaltselemente und Fähigkeiten sowie die Höchstpunktzahl für das Absolvieren der Aufgaben bleiben gleich wie in den Jahren 2015–2018.

Aufbau von KIM USE

Jede Version der Prüfungsarbeit besteht aus zwei Teilen und umfasst 27 Aufgaben, die sich in Form und Schwierigkeitsgrad unterscheiden.

Teil 1 enthält 23 kurze Antwortaufgaben. In der Prüfungsarbeit werden folgende Arten von Aufgaben mit Kurzantwort vorgeschlagen: - Aufgaben zur Berechnung eines bestimmten Wertes; - Aufgaben zur Ermittlung der richtigen Reihenfolge, die nach einem bestimmten Algorithmus als Zeichenkette dargestellt wird.

Die Antwort auf die Aufgaben von Teil 1 erfolgt durch die entsprechende Eingabe in Form einer natürlichen Zahl oder einer Zeichenfolge (Buchstaben oder Zahlen) ohne Leerzeichen und andere Trennzeichen geschrieben. Teil 2 enthält 4 Aufgaben mit einer ausführlichen Antwort.

Teil 1 enthält 23 Aufgaben in den Schwierigkeitsgraden Basic, Advanced und High. Dieser Teil enthält Aufgaben mit einer kurzen Antwort, was eine eigenständige Formulierung und Aufzeichnung der Antwort in Form einer Zahl oder Zeichenfolge impliziert. Aufgaben überprüfen das Material aller Themenblöcke. In Teil 1 beziehen sich 12 Aufgaben auf die Grundstufe, 10 Aufgaben - auf einen erhöhten Schwierigkeitsgrad, 1 Aufgabe - auf einen hohen Komplexitätsgrad.

Teil 2 enthält 4 Aufgaben, von denen die erste eine erhöhte Komplexität hat, die restlichen 3 Aufgaben eine hohe Komplexität haben. Die Aufgaben dieses Teils beinhalten das Schreiben einer ausführlichen Antwort in beliebiger Form.

Die Aufgaben von Teil 2 zielen darauf ab, die Herausbildung der wichtigsten Fähigkeiten zur Erfassung und Analyse von Algorithmen zu erproben. Diese Fähigkeiten werden auf fortgeschrittenen und hohen Schwierigkeitsstufen getestet. Außerdem werden auf einem hohen Schwierigkeitsgrad Kenntnisse zum Thema „Programmiertechnik“ geprüft.

Die Dauer der Prüfung in Informatik und IKT

Für die Bearbeitung der Prüfungsarbeit stehen 3 Stunden 55 Minuten (235 Minuten) zur Verfügung. Es wird empfohlen, sich 1,5 Stunden (90 Minuten) Zeit zu nehmen, um die Aufgaben von Teil 1 zu erledigen. Es wird empfohlen, den Rest der Zeit den Aufgaben von Teil 2 zu widmen.

Bei KIM USE 2020 gibt es keine Änderungen in Informatik und IKT.

Die Prüfungsarbeit besteht aus zwei Teilen, inkl 27 Aufgaben.

Teil 1 enthält 23 Aufgaben mit einer kurzen Antwort. Die Antworten zu den Aufgaben 1-23 werden als Zahl, Buchstabenfolge oder Zahlen geschrieben.
Teil 2 enthält 4 Aufgaben mit ausführlicher Antwort. Die Aufgaben 24–27 erfordern eine detaillierte Lösung.

3 Stunden 55 Minuten (235 Minuten) stehen für die Bearbeitung der Prüfungsarbeit in Informatik und IKT zur Verfügung.

Die Punkte, die Sie für abgeschlossene Aufgaben erhalten, werden summiert. Versuchen Sie, so viele Aufgaben wie möglich zu erledigen und die meisten Punkte zu erzielen.

Punkte für Aufgaben in der Informatik

1 Punkt - für 1-23 Aufgaben
2 Punkte - 25.
3 Punkte - 24, 26.
4 Punkte - 27.

Insgesamt: 35 Punkte.