SPEZIFIKATION
Messstoffe kontrollieren
einheitlich Staatsexamen 2016
in Informatik und IKT
1. Ernennung von KIM USE
Das Unified State Exam (im Folgenden als USE bezeichnet) ist ein Formular objektive Bewertung die Qualität der Ausbildung von Personen, die gemeistert haben Bildungsprogramme Mitte Allgemeinbildung, mit Aufgaben einer standardisierten Form (Kontrollmessmaterialien).
Die Prüfung erfolgt gem Bundesgesetz vom 29. Dezember 2012 Nr. 273-FZ „Über Bildung in der Russischen Föderation“.
Kontrolle Messmaterialien ermöglichen es Ihnen, das Niveau der Beherrschung der föderalen Komponente durch Absolventen festzulegen staatliche Norm sekundäre (vollständige) allgemeine Bildung in Informatik und IKT, Grund- und Fachniveau.
Die Ergebnisse des Einheitlichen Staatsexamens in Informatik und IKT werden anerkannt Bildungsorganisationen Mitte Berufsausbildung und Bildungseinrichtungen der höheren Berufsbildung als Ergebnisse Aufnahmeprüfungen in Informatik und IKT.
2. Dokumente, die den Inhalt von KIM USE definieren
3. Ansätze zur inhaltlichen Auswahl, Aufbau der Struktur des KIM USE
Inhaltlich werden die Aufgabenstellungen an den Schwerpunktthemen des Informatik- und IKT-Studiums erarbeitet, vereint in folgenden Themenblöcken: „Information und ihre Kodierung“, „Modellierung u Computerexperiment“, „Zahlensysteme“, „Logik und Algorithmen“, „Elemente der Theorie der Algorithmen“, „Programmierung“, „Architektur von Computern und Computernetzwerke", "Behandlung Zahlenangaben“, „Technologien zum Suchen und Speichern von Informationen“.
Der Inhalt der Prüfungsarbeit umfasst die Hauptinhalte des Informatik- und IKT-Kurses, seine wichtigsten Themen, den wichtigsten Stoff darin, der in den meisten Versionen des in der Schule unterrichteten Informatik- und IKT-Kurses eindeutig interpretiert wird.
Die Arbeit enthält sowohl Aufgaben der Basisstufe der Komplexität, die Prüfung der Kenntnisse und Fähigkeiten, die der Standard der Basisstufe vorsieht, als auch
und Aufgaben mit erhöhter und hoher Komplexität, wobei die von der Norm bereitgestellten Kenntnisse und Fähigkeiten geprüft werden Profilebene. Die Anzahl der Aufgaben in der KIM-Variante soll einerseits eine umfassende Einschätzung der über die gesamte Studienzeit im Fach erworbenen Kenntnisse und Fähigkeiten der Absolventinnen und Absolventen ermöglichen und andererseits die Kriterien der Komplexität erfüllen, Stabilität der Ergebnisse und Zuverlässigkeit der Messung. Dazu werden in KIM zwei Arten von Aufgaben verwendet: mit einer kurzen Antwort und einer ausführlichen Antwort. Der Aufbau der Prüfungsarbeit sorgt für eine optimale Aufgabenverteilung verschiedene Typen und Sorten, drei Komplexitätsstufen, Prüfung von Wissen und Fähigkeiten auf drei verschiedene Ebenen: Wiedergabe, Anwendung in Standardsituation, Anwendung in einer neuen Situation. Der Inhalt der Prüfungsarbeit spiegelt einen wesentlichen Teil der Inhalte des Faches wider. All dies gewährleistet die Gültigkeit der Testergebnisse und die Zuverlässigkeit der Messung.
4. Die Struktur 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.
BEI Prüfungsarbeit Folgende Arten von Aufgaben mit Kurzantwort werden angeboten:
- Aufgaben zur Auswahl und Aufzeichnung einer oder mehrerer richtiger Antworten aus der vorgeschlagenen Antwortliste;
- Aufgaben zur Berechnung eines bestimmten Werts;
- Aufgaben, um die richtige Reihenfolge zu ermitteln, die gemäß 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 und Zahlen), geschrieben ohne Leerzeichen und andere Trennzeichen.
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 die 12 Punkte Grundstufe, 10 Aufgaben mit erhöhter Komplexität, 1 Aufgabe - mit hoher Komplexität.
Teil 2 enthält 4 Aufgaben, von denen die erste fortgeschrittenes Level Schwierigkeit, die restlichen 3 Aufgaben hohes Level Schwierigkeiten. Die Aufgaben dieses Teils beinhalten das Schreiben einer ausführlichen Antwort in beliebiger Form.
Einheitliche Staatsexamensentscheidung Informatik
1. Aufgabe. Wie viele Einsen gibt es in Binärschreibweise für die Hexadezimalzahl 12F0 16 ?
Erläuterung.
Lassen Sie uns die Zahl 12F0 übersetzen 16 nach binärem Zahlensystem: 12F0 16 = 1001011110000 2 .
Zählen wir die Anzahl der Einheiten: Es gibt 6 davon.
Antwort: 6.
2. Aufgabe Boolesche Funktion F wird durch den Ausdruck (¬ z ) ∧ x ∨ x ∧ y . Bestimme welche Spalte der Wahrheitstabelle der Funktion F entspricht jeder der Variablen x, y, z.
Variable eines | Variable 2 | Variable 3 | Funktion |
Schreiben Sie die Buchstaben in Ihre Antwort. x, y, z in der Reihenfolge, in der ihre entsprechenden Spalten erscheinen (zuerst der Buchstabe, der der 1. Spalte entspricht; dann der Buchstabe, der der 2. Spalte entspricht; dann der Buchstabe, der der 3. Spalte entspricht). Schreiben Sie die Buchstaben in der Antwort hintereinander, Sie brauchen keine Trennzeichen zwischen die Buchstaben zu setzen. Beispiel. Lassen Sie den Ausdruck x → y , abhängig von zwei Variablen x und y , und die Wahrheitstabelle:
Variable eines | Variable 2 | Funktion |
Dann entspricht die 1. Spalte der Variablen j , und die 2. Spalte entspricht der Variablen x . Schreiben Sie in Ihre Antwort: ja.
Erläuterung.
Dieser Ausdruck ist eine Disjunktion zweier Konjunktionen. Wir können feststellen, dass es in beiden Begriffen einen Faktor gibt x . Das heißt für x = 0 ist die Summe gleich 0. Also für die Variable x nur die dritte Spalte passt.
In der achten Reihe der Tabelle x = 1, und der Wert der Funktion ist 0. Dies ist nur möglich, wenn z = 1, y = 0, also Variable1 − z , und Variable2 − y .
Antwort: zyx
3. Aufgabe In der Abbildung rechts ist die Straßenkarte des N-Sky-Distrikts als Diagramm dargestellt, die Tabelle enthält Informationen über die Länge dieser Straßen (in Kilometern).
Da die Tabelle und das Diagramm unabhängig voneinander gezeichnet wurden, ist die Nummerierung Siedlungen in der Tabelle ist nicht verwandt Briefe auf der Grafik. Bestimmen Sie die Länge der Straße von Punkt B nach Punkt E. Geben Sie in Ihrer Antwort eine ganze Zahl an - wie in der Tabelle angegeben.
Erläuterung.
Punkt B ist der einzige Punkt mit fünf Straßen, also entspricht er P6, und Punkt E ist der einzige mit vier Straßen, also entspricht er P4.
Die Länge der Straße von P6 nach P4 beträgt 20.
Antwort: 20.
4. Aufgabe Das Datenbankfragment liefert Informationen über Familienbeziehungen. Bestimmen Sie anhand der gegebenen Daten, wie viele direkte Nachkommen (d. h. Kinder und Enkel) Pavlenko A.K. sind in Tabelle 1 aufgeführt.
|
|
ODER
Für Stapeloperationen mit Dateien werden Dateinamensmasken verwendet. Die Maske ist eine Folge von Buchstaben, Zahlen und anderen in Dateinamen zulässigen Zeichen, die auch die folgenden Zeichen enthalten kann:
Symbol "?" ( Fragezeichen) bedeutet genau ein beliebiges Zeichen.
Das Symbol "*" (Sternchen) bedeutet eine beliebige Folge von Zeichen beliebiger Länge, wobei "*" auch eine leere Folge angeben kann.
Das Verzeichnis enthält 6 Dateien:
maverick.map
Maverick.mp3
Taverne.mp4
Revolver.mp4
vera.mp3
zveri.mp3
Unten sind acht Masken. Wie viele davon stimmen mit genau vier Dateien aus dem angegebenen Verzeichnis überein?
*ver*.mp* | *?ver?*.mp? | ?*ver*.mp?* | *v*r*?.m?p* |
???*???.mp* | ???*???.m* | *a*.*a* | *a*.*p* |
Erläuterung.
Aus Tabelle 2 sehen wir, dass Pavlenko A.K. (ID 2155) zwei Kinder hat, ihre IDs sind 2302 und 3002.
Pavlenko E. A. (ID 2302) hat drei Kinder und Pavlenko I. A. (ID 3002) hat zwei.
Somit hat Pavlenko A.K. sieben direkte Nachkommen: zwei Kinder und fünf Enkelkinder.
Antwort: 7.
ODER
Betrachten Sie jede Maske:
1. Mit der Maske *ver*.mp* werden fünf Dateien ausgewählt:
Maverick.mp3
Taverne.mp4
Revolver.mp4
vera.mp3
zveri.mp3
2. Per Maske *?ver?*.mp? Es werden drei Dateien ausgewählt:
Maverick.mp3
Taverne.mp4
zveri.mp3
3. Mit mask?*ver*.mp?* werden vier Dateien ausgewählt:
Maverick.mp3
Taverne.mp4
Revolver.mp4
zveri.mp3
4. Mit der Maske *v*r*?.m?p* wird eine Datei ausgewählt:
maverick.map
5. Mit mask???*???.mp* werden drei Dateien ausgewählt:
Maverick.mp3
Taverne.mp4
Revolver.mp4
6. Die Maske ???*???.m* wählt vier Dateien aus:
maverick.map
Maverick.mp3
Taverne.mp4
Revolver.mp4
7. Mit der Maske *a*.*a* wird eine Datei ausgewählt:
maverick.map
8. Mit der Maske *a*.*p* werden vier Dateien ausgewählt:
maverick.map
Maverick.mp3
Taverne.mp4
vera.mp3
Das heißt, drei Masken, die genau vier Dateien aus dem angegebenen Verzeichnis entsprechen.
Antwort: 3.
Antwort: 7|3
5. Aufgabe Nachrichten, die nur vier Buchstaben enthalten, werden über den Kommunikationskanal übertragen: P, O, S, T; zur Übertragung wird ein binärer Code verwendet, der eine eindeutige Dekodierung ermöglicht. Für die Buchstaben T, O, P werden folgende Codewörter verwendet: T: 111, O: 0, P: 100.
Geben Sie das kürzeste Codewort für den Buchstaben C an, bei dem der Code eine eindeutige Decodierung zulässt. Bei mehreren solcher Codes ist der Code mit dem kleinsten Zahlenwert anzugeben.
Erläuterung.
Der Buchstabe C kann nicht als 0 codiert werden, da 0 bereits vergeben ist.
Der Buchstabe C kann nicht als 1 codiert werden, da die Codierung des Buchstabens T mit 1 beginnt.
Der Buchstabe C kann nicht als 10 codiert werden, da die Codierung des Buchstabens P mit 10 beginnt.
Der Buchstabe C kann nicht als 11 codiert werden, da die Codierung des Buchstabens T mit 11 beginnt.
Der Buchstabe C kann als 101 codiert werden - dies ist der kleinste mögliche Bedeutung.
Antwort: 101.
6. Suche Die Eingabe des Algorithmus ist eine natürliche Zahl N. Der Algorithmus baut daraus wie folgt eine neue Zahl R auf.
1. Eine binäre Darstellung der Zahl N wird konstruiert.
2. Diesem Eintrag werden rechts zwei weitere Ziffern nach folgender Regel hinzugefügt:
A) Alle Ziffern der binären Notation werden addiert, und der Rest der Division der Summe durch 2 wird am Ende der Zahl (rechts) hinzugefügt. Beispielsweise wird Eintrag 11100 in Eintrag 111001 umgewandelt;
B) Die gleichen Aktionen werden für diesen Datensatz ausgeführt - der Rest der Division der Ziffernsumme 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 dies an kleinste Zahl N, für die das Ergebnis des Algorithmus größer als 125 ist. Tragen Sie diese Zahl in die Antwort ein Dezimalsystem rechnen.
ODER
Der Performer-Rechner hat zwei Teams, denen Nummern zugeordnet sind:
1. addiere 2,
2. mit 5 multiplizieren.
Bei der ersten Ausführung addiert der Rechner 2 zur Zahl auf dem Bildschirm, bei der zweiten multipliziert er sie mit 5.
Beispielsweise ist Programm 2121 Programm
mit 5 multiplizieren
addiere 2,
mit 5 multiplizieren
addiere 2,
die die Zahl 1 in die Zahl 37 umwandelt.
Schreiben Sie die Reihenfolge der Befehle in ein Programm, das die Zahl 2 in die Zahl 24 umwandelt und nicht mehr als vier Befehle enthält. Geben Sie nur Befehlsnummern an.
Erläuterung.
Dieser Algorithmus weist am Ende der Zahl entweder 10 zu, wenn sie ursprünglich eine ungerade Anzahl von Einsen in ihrer binären Notation hatte, oder 00, wenn sie gerade war.
126 10 = 1111110 2 kann als Ergebnis des Algorithmus aus der Nummer 11111 erhalten werden 2 .
11111 2 = 31 10 .
Antwort: 31.
ODER
Lassen Sie uns das Problem von der Rückseite lösen und dann die empfangenen Befehle von rechts nach links aufschreiben.
Wenn die Zahl nicht durch 5 teilbar ist, wird sie durch Befehl 1 empfangen, wenn sie teilbar ist, dann durch Befehl 2.
22 + 2 = 24 (Mannschaft 1)
20 + 2 = 22 (Mannschaft 1)
4 * 5 = 20 (Team 2)
2 + 2 = 4 (Mannschaft 1)
Antwort: 1211.
Antwort: 31|1211
7. Aufgabe. Fragment gegeben Kalkulationstabelle. Eine Formel wurde aus Zelle E4 in Zelle D3 kopiert. Beim Kopieren der Adressen der Zellen in der Formel wurden diese automatisch geändert. Was ist geworden numerischer Wert Formeln in Zelle D3?
=$B2 * C$3 |
Hinweis: Das $-Zeichen kennzeichnet eine absolute Adressierung.
ODER
Ein Fragment einer Tabelle ist gegeben.
=(A1-3)/(B1-1) | =(A1-3)/(C1-5) | C1/(A1 – 3) |
Welche Ganzzahl muss in Zelle A1 geschrieben werden, damit das Diagramm, das auf den Werten der Zellen im Bereich A2:C2 basiert, mit der Zahl übereinstimmt? Es ist bekannt, dass alle Zellenwerte aus dem betrachteten Bereich nicht negativ sind.
Erläuterung.
Die Formel wurde beim Kopieren in Zelle D3 in =$B1 * B$3 geändert.
B1 * B3 = 4 * 2 = 8.
Antwort: 8.
ODER
Setzen Sie die Werte von B1 und C1 in die Formeln A2:C2 ein:
A2 = (A1-3)/5
B2 = (A1-3)/5
C2 = 10/(A1-3)
Da A2 = B2, dann ist С2 = 2 * A2 = 2 * B2
Ersatz:
10/(A1-3) = 2*(A1-3)/5
A1 - 3 = 5
A1 = 8.
Antwort: 8.
8. Aufgabe Notieren Sie die Zahl, die als Ergebnis des folgenden Programms gedruckt wird. Zu Ihrer Bequemlichkeit wird das Programm in fünf Programmiersprachen präsentiert.
BASIC | Python |
DIM S, N ALS INTEGER S=0 N=0 WÄHREND S S=S+8 N=N+2 WENDE DRUCKEN N | s = 0 n=0 während s s = s + 8 n = n + 2 |
Algorithmische Sprache | Paskal |
alg frühzeitig ganze Zahl n, s n:=0 s:= 0 tschüss s s:= s + 8 n:= n + 2 kts Ausgang n con | var s, n: ganze Zahl; Start s:= 0; n:=0; während s Start s:= s + 8; n:= n + 2 Ende; schreiben(n) Ende. |
Xi |
|
#enthalten int Haupt() (int s = 0, n = 0; während (s printf("%d\n", n); 0 zurückgeben; |
|
Erläuterung.
Die While-Schleife wird ausgeführt, solange die Bedingung s wahr ist
Antwort: 28.
9. Aufgabe. Wie viel Speicherplatz (in KB) muss mindestens reserviert werden, um eine beliebige 64×64-Pixel-Bitmap speichern zu können, vorausgesetzt, 256 können im Bild verwendet werden? verschiedene Farben? Schreiben Sie in die Antwort nur eine ganze Zahl, Sie müssen keine Maßeinheit schreiben.
ODER
Das Musikfragment wurde im Monoformat aufgenommen, digitalisiert und ohne Datenkomprimierung als Datei gespeichert. Die Größe der resultierenden Datei beträgt 24 MB. Anschließend wurde dasselbe Musikstück erneut in Stereo aufgenommen (Zweikanalaufnahme) und mit einer 4-fach höheren Auflösung und einer 1,5-fach niedrigeren Abtastrate als beim ersten Mal digitalisiert. Eine Datenkomprimierung wurde nicht durchgeführt. Geben Sie die Größe der Datei in MB an, die sich aus dem Umschreiben ergibt. Schreiben Sie in die Antwort nur eine ganze Zahl, Sie müssen keine Maßeinheit schreiben.
Erläuterung.
Ein Pixel wird mit 8 Bit Speicher kodiert.
Insgesamt 64 * 64 = 2 12 Pixel.
Die vom Bild belegte Speichermenge 2 12 * 8 = 2 15 Bit = 2 12 Byte = 4 KB.
Antwort: 4.
ODER
Wenn dieselbe Datei im Stereoformat aufgenommen wird, wird ihre Lautstärke um das Zweifache erhöht. 24 * 2 = 48
Wenn die Auflösung um das 4-fache erhöht wird, erhöht sich auch die Lautstärke um das 4-fache. 48 * 4 = 192
Wenn die Abtastrate um das 1,5-fache reduziert wird, wird seine Lautstärke um das 1,5-fache reduziert. 192 / 1,5 = 128.
Antwort: 128.
Antwort: 4|128
10. Aufgabe Igor erstellt eine Tabelle mit Codewörtern für die Nachrichtenübertragung, jede Nachricht hat ihr eigenes Codewort. Igor verwendet 5-Buchstaben-Wörter als Codewörter, in denen es nur die Buchstaben P, I, R gibt und der Buchstabe P genau 1 Mal vorkommt. Jeder der anderen gültigen Buchstaben kann im Codewort beliebig oft oder gar nicht vorkommen. Wie viele verschiedene Codewörter kann Igor verwenden?
Erläuterung.
Igor kann 2 nachholen 4 Wörter, indem Sie den Buchstaben P an die erste Stelle setzen. Ebenso können Sie es auf den zweiten, dritten, vierten und fünften Platz setzen. Wir bekommen 5 * 2 4 = 80 Wörter.
Antwort: 80.
11. Aufgabe Nachfolgend sind zwei rekursive Funktionen (Prozeduren) in fünf Programmiersprachen geschrieben: F und G.
BASIC | Python |
DECLARE SUB F(n) DECLARE SUB G(n) SUB F(n) WENN n > 0 DANN G(n - 1) END SUB SUB G(n) DRUCKEN "*" WENN n > 1 DANN F(n - 3) END SUB | def F(n): Wenn n > 0: G(n - 1) def G(n): Drucken("*") Wenn n > 1: F(n - 3) |
Algorithmische Sprache | Paskal |
alg F(Ganzzahl n) frühzeitig Wenn n > 0 dann G(n - 1) Alle con alg G(Ganzzahl n) frühzeitig Fazit "*" Wenn n > 1 dann F(n - 3) Alle con | Prozedur F(n: ganze Zahl); nach vorne; Prozedur G(n: ganze Zahl); nach vorne; Prozedur F(n: ganze Zahl); Start Wenn n > 0 dann G(n - 1); Ende; Prozedur G(n: ganze Zahl); Start writeln("*"); Wenn n > 1 dann F(n-3); Ende; |
Xi |
|
nichtig F(int n); leere G(int n); nichtig F(int n)( Wenn (n > 0) G(n - 1); ungültig G(int n)( printf("*"); Wenn (n > 1) F(n-3); |
|
Wie viele Sternchen werden beim Aufruf von F(11) auf dem Bildschirm ausgegeben?
Erläuterung.
Lassen Sie uns die Arbeit des Programms simulieren:
F(11)
G(10): *
F(7)
G(6): *
F(3)
G(2): *
F(-1)
Antwort: 3.
12. Suche In der TCP/IP-Netzwerkterminologie ist eine Netzmaske a binäre Zahl, die bestimmt, welcher Teil der IP-Adresse eines Netzwerkhosts sich auf die Netzwerkadresse bezieht und welcher Teil sich auf die Adresse des Hosts selbst in diesem Netzwerk bezieht. Normalerweise wird die Maske nach den gleichen Regeln geschrieben wie die IP-Adresse - in vier Bytes, wobei jedes Byte als geschrieben wird Dezimalzahl. 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 111.81.208.27 lautet die Netzwerkadresse 111.81.192.0. Was ist der kleinstmögliche Wert des dritten Bytes von links der Maske? Schreiben Sie Ihre Antwort als Dezimalzahl.
Erläuterung.
Schreiben wir das dritte Byte der IP-Adresse und Netzwerkadresse in Binärschreibweise:
208 10 = 11010000 2
192 10 = 11000000 2
Wir sehen, dass die ersten beiden Bits der Maske auf der linken Seite Einsen sind, was bedeutet, dass die verbleibenden Bits Null sein müssen, damit der Wert der kleinste ist. Wir erhalten, dass das dritte Byte der Maske von links 11000000 ist 2 = 192 10
Antwort: 192.
13. Aufgabe Bei Anmeldung unter Computersystem Jeder Benutzer erhält ein Passwort, das aus 15 Zeichen besteht und nur Zeichen aus dem 12-Zeichensatz enthält: A, B, C, D, E, F, G, H, K, L, M, N. In der Datenbank zum Speichern Informationen über jeden Benutzer wird die gleiche und die kleinstmögliche ganzzahlige Anzahl von Bytes zugewiesen. 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 400 Bytes, um Informationen über 20 Benutzer zu speichern. Wie viele Bytes werden für die Speicherung zugewiesen zusätzliche Informationüber einen Benutzer? Notieren Sie in der Antwort nur eine Ganzzahl - die Anzahl der Bytes.
Erläuterung.
Je nach Bedingung können 12 Buchstaben in der Nummer verwendet werden. Es ist bekannt, dass mit Hilfe von N Bits 2N codiert werden können Verschiedene Optionen. Seit 2 3 4 , dann werden 4 Bit benötigt, um jedes der 12 Zeichen zu schreiben.
Um alle 15 Zeichen des Passworts zu speichern, benötigen Sie 4 15 = 60 Bits, und da zum Schreiben eine ganzzahlige Anzahl von Bytes verwendet wird, nehmen wir den nächsten nicht geringeren Wert, ein Vielfaches von acht, diese Zahl ist 64 = 8 8 Bits (8 Bytes).
Lassen Sie die Speichermenge, die für zusätzliche Sitzungen zugewiesen wird, sein x, dann:
20 * (8+x) = 400
x=12
Antwort: 12.
14. Suche 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 die 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, kehrt der Befehl zurück boolesch true, andernfalls wird false zurückgegeben. Linie
der Ausführende wird nicht geändert.
Zyklus
Tschüss Bedingung
Befehlsfolge
ENDE AUF WIEDERSEHEN
Wird ausgeführt, solange die Bedingung wahr ist.
Im Aufbau
IF-Bedingung
AN team1
ELSE-Team2
ENDE WENN
Befehl1 (wenn Bedingung wahr ist) oder Befehl2 (wenn Bedingung falsch ist) wird ausgeführt.
Welche Zeichenfolge ergibt sich aus der Anwendung des Folgenden
Programm in eine Zeichenfolge bestehend aus 68 aufeinanderfolgenden Ziffern 8? In Beantwortung
notieren Sie sich die resultierende Zeichenfolge.
ANFANG
NOCH gefunden (222) ODER gefunden (888)
WENN gefunden (222)
zu ersetzen (222, 8)
ELSE ersetzen (888, 2)
ENDE WENN
ENDE AUF WIEDERSEHEN
DAS ENDE
Erläuterung.
In 68 aufeinanderfolgenden Zahlen 8 gibt es 22 Dreier-Achter-Gruppen, die durch 22 Zweier ersetzt werden und zwei Achter bleiben.
68(8) = 22(2) + 2(8)
22(2) + 2(8) = 1(2) + 9(8)
1(2) + 9(8) = 4(2)
4(2) = 1(2) + 1(8) = 28
Antwort: 28.
15. Suche 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 existieren verschiedene Wege von Stadt A nach Stadt M?
Erläuterung.
Beginnen wir mit dem Zählen der Wege vom Ende der Route - von der Stadt M. Lassen Sie N X - die Anzahl der verschiedenen Wege von Stadt A nach Stadt X, N - Gesamtzahl Wege. Stadt M kann von L oder K aus erreicht werden, also N = N M \u003d N L + N K. (*)
Ähnlich:
NK \u003d N Und;
N L \u003d N Und;
N. ich \u003d N. E. + N. W. + N. Z
N K \u003d N E \u003d 1.
Lassen Sie uns weitere Scheitelpunkte hinzufügen:
NB \u003d NB \u003d 1;
N B \u003d N B + N A + N G \u003d 1 + 1 + 1 \u003d 3;
NE \u003d NG \u003d 1;
NG \u003d NA \u003d 1.
Ersetzen Sie in der Formel (*): N = N M = 4 + 4 + 4 + 1 = 13.
Antwort: 13.
Antwort: 56
16. Suche Wert des arithmetischen Ausdrucks: 9 8 + 3 5 - 9 - in Zahlensystemen mit der Basis 3 erfasst. Wie viele Ziffern „2“ sind in diesem Eintrag enthalten?
Erläuterung.
Lassen Sie uns den Ausdruck umwandeln:
(3 2 ) 8 + 3 5 - 3 2
3 16 + 3 5 - 3 2
3 16 + 3 5 = 100...00100000
100...00100000 - 3 2 = 100...00022200
Es gibt drei 2en in der resultierenden Zahl.
Antwort: 3
17. Aufgabe In der Suchsprache der Suchmaschine wird das Symbol "|" verwendet, um die logische Operation "OR" anzuzeigen, und das Symbol "&" wird verwendet, um die logische Operation "AND" anzuzeigen. Die Tabelle zeigt Suchanfragen und die Anzahl der von ihnen gefundenen Seiten für ein bestimmtes Segment des Internets.
Wie viele Seiten (in Tausend) werden für die Abfrage gefundenHomer & Odyssee & Ilias?Es wird angenommen, dass alle Anfragen fast gleichzeitig ausgeführt wurden, sodass sich die Menge der Seiten mit allen gesuchten Wörtern im Laufe der Zeit nicht geändert hat.
Ausführung von Anfragen.
Erläuterung.
Die Anzahl der Anfragen in diesem Bereich wird mit Ni bezeichnet. Unser Ziel ist N5.
Dann finden wir aus der Tabelle Folgendes:
N5 + N6 = 355,
N4 + N5 = 200,
N4 + N5 + N6 = 470.
Aus der ersten und zweiten Gleichung: N4 + 2N5 + N6 = 555.
Aus der letzten Gleichung: N5 = 85.
Antwort: 85
18. Aufgabe Bezeichne mit m&n bitweise Konjunktion von nicht negativen ganzen Zahlen m und n . Also zum Beispiel 14&5 = 1110 2 &0101 2 = 0100 2 = 4.
Was ist die kleinste nicht negative ganze Zahl Und die Formel
x&25 ≠ 0 → (x&17 = 0 → x&A ≠ 0)
ist identisch wahr (d. h. nimmt den Wert 1 für jeden nicht negativen ganzzahligen Wert der Variablen an X )?
Erläuterung.
Wir führen die Notation ein:
(x ∈ EIN) ≡ EIN; (x ∈ P) ≡ P; (x ∈ Q) ≡ Q.
Durch Transformation erhalten wir:
¬P ∨ ¬(Q ∧ ¬A) ∨ ¬P = ¬P ∨ ¬Q ∨ A.
Das logische ODER ist wahr, wenn mindestens eine der Aussagen wahr ist. Zustand ¬P∨ ¬Q = 1 erfüllen die Strahlen (−∞, 40) und (60, ∞). Da der Ausdruck ¬P∨ ¬Q ∨ A muss identisch wahr sein, der Ausdruck A muss auf dem Intervall wahr sein. Seine Länge beträgt 20.
Antwort: 20.
Antwort: 8
19. Suche Das Programm verwendet ein eindimensionales Integer-Array A mit Indizes von 0 bis 9. Die Werte der Elemente sind 4, 7, 3, 8, 5, 0, 1, 2, 9, 6, d.h. A=4, A=7 usw.
Ermitteln Sie den Wert einer Variablen c nachdem Sie das folgende Fragment dieses Programms ausgeführt haben(unten in fünf Programmiersprachen geschrieben).
BASIC | Python |
C=0 FÜR i = 1 BIS 9 WENN A(i) C=c+1 T = A(i) A(i) = A(0) A(0) = t ENDIF WEITER i | C=0 Für i im Bereich (1,10): Wenn A[i] C=c+1 t = A[i] A[i] = A A=t |
Algorithmische Sprache | Paskal |
c:= 0 nc für i von 1 bis 9 wenn A[i] c:= c + 1 t:= A[i] A[i] := A A := t alle kts | c:=0; für i:= 1 bis 9 tun wenn A[i] Start c:= c + 1; t:= A[i]; A[i] := A; A := t; Ende; |
Xi |
|
c = 0; für (i = 1;i wenn (A[i] { c++; t = A[i]; A[i] = A; A=t; } |
|
Erläuterung.
Wenn A[i] ein Array-Element kleiner als A ist, tauscht das Programm sie aus und erhöht den Wert der Variablencdurch 1. Das Programm wird seit 3 zweimal ausgeführt, wobei beim ersten Mal A und A vertauscht werden Mitgleich 2 wird.
Antwort: 2.
20. SucheDer Algorithmus ist unten in fünf Programmiersprachen geschrieben. Nachdem ich eine Nummer erhalten habex, gibt dieser Algorithmus eine Zahl ausM. Es ist bekannt, dassx> 100. Geben Sie die kleinste derartige Zahl (d. h. größer als 100) anx, bei dessen Eingabe der Algorithmus 26 druckt.
BASIC | Python |
DIM X, L, M ALS INTEGER EINGANG X L=X M=65 WENN L MOD 2 = 0 DANN M=52 ENDIF WÄHREND L M WENN L > M DANN L=L-M ANDERS M=M-L ENDIF WENDE DRUCKEN M | x = int(Eingabe()) L=x M=65 wenn L % 2 == 0: M=52 während L != M: wenn L > M: L=L-M anders: M=M-L drucken (M) |
Algorithmische Sprache | Paskal |
alg frühzeitig ganze Zahl x, L, M x eingeben L:= x M:= 65 wenn mod(L,2)=0 dann M:= 52 alle nc während L M wenn L > M dann L:= L - M Andernfalls M:= M - L alle kts Terminal M con | var x, L, M: Ganzzahl; Start readln(x); L:=x; M:= 65; wenn L mod 2 = 0 dann M:= 52; während L M tun wenn L > M dann L:= L - M anders M:= M - L; schreiben(M); Ende. |
Xi |
|
#enthalten void main() { intx, L, M; scanf("%d", &x); L=x; M=65; wenn (L % 2 == 0) M=52; während (L != M)( wenn (L > M) L = L - M; anders M = M – L; } printf("%d", M); } |
|
Erläuterung.
Im Körper der Schleife nehmen die Zahlen M und L ab, bis sie gleich werden. Um am Ende 26 zu drucken, müssen beide Zahlen irgendwann gleich 26 sein. Gehen wir vom Ende zum Anfang: Im vorherigen Schritt war eine Zahl 26, und die andere 26 + 26 = 52. Ein Schritt früher 52 + 26 = 78 und 52. Bis dahin 78 + 52 = 130 und 52. Das heißt, die kleinste mögliche Zahl ist 130. Und da die gefundene Zahl gerade ist, wird M der Wert 52 zugewiesen, was führt zum gewünschten Ergebnis.
Antwort: 130.
21. SucheSchreibe die Antwort hinein kleinster Wert Eingabevariablek, bei der das Programm die gleiche Antwort liefert wie beim Eingabewertk= 10. Zu Ihrer Bequemlichkeit wird das Programm in fünf Programmiersprachen präsentiert.
BASIC | Python |
DIM K, ICH WIE LANG EINGANG K Ich = 1 WÄHREND F(I) Ich = Ich + 1 WENDE DRUCKEN I FUNKTION F(N) F=N*N*N FUNKTION BEENDEN FUNKTION G(N) G = 2*N + 3 FUNKTION BEENDEN | def f(n): gib n*n*n zurück def g(n): gib 2*n+3 zurück k = int(Eingabe()) ich = 1 während f(i) i+=1 drucken (i) |
Algorithmische Sprache | Paskal |
alg frühzeitig ganze Zahl i, k Eingang k i:= 1 nc während f(i) i:= i + 1 kts Ausgang i con Alg ganze Zahl f(int n) frühzeitig Wert:= n * n * n con Alg ganze Zahl g(int n) frühzeitig Wert:= 2*n + 3 con | Var k, i: lange Ganzzahl; Funktion f(n: lange Ganzzahl): lange Ganzzahl; Start f:= n * n * n; Ende; Funktion g(n: lange Ganzzahl): lange Ganzzahl; Start g:= 2*n + 3; Ende; Start readln(k); i:= 1; während f(i) ich:=i+1; schreiben(i) Ende. |
Xi |
|
#enthalten lang f(lang n) ( gib n*n*n zurück; } lang g(lang n) ( gib 2*n + 3 zurück; } int Haupt() { lang k, ich; scanf("%ld", &k); ich = 1; während (f (i) i++; printf("%ld", i); 0 zurückgeben; } |
|
Erläuterung.
Dieses Programm vergleichtundund ergänztichEinheit bis. Und druckt den ersten Wert der Variablenichunter welchen
Bei k = 10 gibt das Programm die Zahl 3 aus.
Schreiben wir die Ungleichung auf:daher erhalten wir den kleinsten Wertk = 3.
Antwort: 3.
22. SucheDarsteller vom 15. Mai wandelt die Zahl auf dem Bildschirm um. Der Darsteller hat zwei Teams, denen Nummern zugewiesen werden:
1. Addiere 1
2. Multipliziere mit 2
Der erste Befehl erhöht die Zahl auf dem Bildschirm um 1, der zweite multipliziert sie mit 2. Das Programm für den May15-Performer ist eine Folge von Befehlen. Wie viele Programme gibt es, bei denen bei der Anfangszahl 2 das Ergebnis die Zahl 29 ist und die Rechenbahn die Zahl 14 enthält und die Zahl 25 nicht enthält?
Die Trajektorie eines Programms ist die Folge von Ergebnissen
Ausführung aller Programmbefehle. Zum Beispiel für Programm 121 mit der Anfangsnummer 7 besteht die Trajektorie aus den Nummern 8, 16, 17.
Erläuterung.
Für die Addition gilt das Kommutativgesetz (Kommutativgesetz), was bedeutet, dass die Reihenfolge der Anweisungen im Programm für das Ergebnis keine Rolle spielt.
Alle Mannschaften steigern sich ursprüngliche Nummer, also kann die Anzahl der Teams (30 − 21) = 9 nicht überschreiten. Außerdem gilt minimale Menge Befehle - 3.
So kann es 3, 4, 5, 6, 7, 8 oder 9 Befehle geben, daher spielt die Reihenfolge der Befehle keine Rolle, jede Anzahl von Befehlen entspricht einem Befehlssatz, der in beliebiger Reihenfolge angeordnet werden kann .
Betrachten Sie alle möglichen Mengen und berechnen Sie die Anzahl der Optionen zum Anordnen von Befehlen in ihnen. Satz 133 hat 3 Optionen Lage. Set 1223 - 12 mögliche Anordnungen: Dies ist die Anzahl der Permutationen mit Wiederholungen (1+2+1)!/(1! 2! 1!). Stellen Sie 12222 - 5 Optionen ein. Set 111222 - 20 mögliche Optionen. Stellen Sie 11123 - 20 Optionen ein. Set 111113 - 6 Optionen, Set 1111122 - 21 Optionen, Set 11111112 - 8 Optionen, Set 111111111 - eine Option.
Insgesamt haben wir 3 + 12 + 5 + 20 + 20 + 6 + 21 + 8 + 1 = 96 Programme.
Antwort: 96.
Antwort: 96.
Antwort: 13
23. SucheWie viele verschiedene Sätze von booleschen Werten gibt es?x1 , x2 , ...x9 , ja1 , ja2 , ... j9 die alle folgenden Bedingungen erfüllen?
(¬ (x1 ≡ j1 )) ≡ (x2 ≡ j2 )
(¬ (x2 ≡ j2 )) ≡ (x3 ≡ j3 )
…
(¬ (x8 ≡ j8 )) ≡ (x9 ≡ j9 )
Die Antwort muss nicht alle verschiedenen Gruppen von Variablenwerten auflistenx1 , x2 , ...x9 , ja1 , ja2 , ... j9 , unter welchen dieses System Gleichheiten. Als Antwort müssen Sie die Anzahl solcher Sätze angeben.
Erläuterung.
Aus der letzten Gleichung sehen wir, dass es drei mögliche Werte von x8 und y8 gibt: 01, 00, 11. Lassen Sie uns einen Optionsbaum für das erste und zweite Wertepaar erstellen.
Somit haben wir 16 Sätze von Variablen.
Optionsbaum für Wertepaar 11:
Wir bekommen 45 Optionen. Somit hat das System 45 + 16 = 61 verschiedene Sätze von Lösungen.
Antwort: 61.
Antwort: 1024
24. SucheEine positive ganze Zahl, die 10 nicht übersteigt, wird verarbeitet.9 . Sie müssen ein Programm schreiben, das die Summe der Ziffern dieser Zahl kleiner als 7 anzeigt.Wenn die Zahl keine Ziffern kleiner als 7 enthält, müssen Sie auf dem Bildschirm 0 anzeigen.Der Programmierer hat das Programm falsch geschrieben. Unten ist dieses Programm für Ihre Bequemlichkeit in fünf Programmiersprachen angegeben.
BASIC | Python |
DIM N, ZIFFER, SUMME WIE LANG EINGANG N SUMME = 0 WÄHREND N > 0 ZIFFER=NMOD 10 WENN ZIFFER SUMME = SUMME + 1 ENDE WENN N=N\10 WENDE ZIFFER DRUCKEN | N = int(Eingabe()) Summe = 0 solange N > 0: Ziffer = N% 10 wenn Ziffer Summe = Summe + 1 N = N // 10 drucken (Ziffer) |
Algorithmische Sprache | Paskal |
alg frühzeitig Ganzzahl N, Ziffer, Summe Eingang N Summe:= 0 nc solange N > 0 Ziffer:= mod(N,10) wenn Ziffer Summe:= Summe + 1 alle N:=div(N,10) kts Digitausgabe con | var N, Ziffer, Summe: lange Ganzzahl; Start readln(N); Summe:= 0; während N > 0 tun Start Ziffer:= N mod 10; wenn Ziffer Summe:= Summe + 1; N:= N div 10; Ende; schreiben(Ziffer) Ende. |
Xi |
|
#enthalten int Haupt() { int N, Ziffer, Summe; scanf("%d", &N); Summe = 0; während (N > 0) { Ziffer = N% 10; wenn (Ziffer Summe = Summe + 1; N = N / 10; } printf("%d",Ziffer); return0; } |
|
Gehen Sie nacheinander wie folgt vor.
1. Schreiben Sie auf, was dieses Programm anzeigt, wenn Sie die Zahl 456 eingeben.
2. Geben Sie ein Beispiel dafür dreistellige Zahl, bei deren Eingabe das Programm die richtige Antwort gibt.
3. Finden Sie alle Fehler in diesem Programm (es können einer oder mehrere sein). 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. bringen Korrekte Option Linien.
Es reicht aus, die Fehler und die Art und Weise, sie zu beheben, für eine Programmiersprache anzugeben. Bitte beachten Sie, dass Sie Fehler in dem vorhandenen Programm finden müssen und keine eigenen schreiben müssen, möglicherweise mit einem anderen Lösungsalgorithmus. Das Korrigieren eines Fehlers sollte nur die Zeile betreffen, die den Fehler enthält.
Erläuterung.
Die Lösung verwendet einen Pascal-Programmeintrag. Sie können das Programm in jeder der vier anderen Sprachen verwenden.
1. Das Programm druckt die Zahl 4.
2. Ein Beispiel für eine Zahl, bei deren Eingabe das Programm die richtige Antwort gibt: 835.
Hinweis für den Rezensenten. Das Programm funktioniert aufgrund einer falsch angezeigten Variable und einer falschen Erhöhung des Betrags nicht richtig. Dementsprechend funktioniert das Programm korrekt, wenn die höchste Ziffer (ganz links) in der Zahl gleich der Summe der Ziffern kleiner als 7 ist.
3. Es gibt zwei Fehler im Programm.
Erster Fehler. Erhöhung des falschen Betrags.
Fehlerzeile:
Summe:= Summe + 1;
Korrekte Lösung:
Summe:= Summe + Ziffer;
Zweiter Fehler. Falsche Anzeige der Antwort auf dem Bildschirm.
Fehlerzeile:
schreiben(Ziffer)
Korrekte Lösung:
schreiben(summe)
25. SucheGegeben sei ein Integer-Array mit 20 Elementen. Array-Elemente können ganzzahlige Werte von -10000 bis einschließlich 10000 annehmen. Beschreiben Sie auf Natürliche Sprache oder in einer der Programmiersprachen ein Algorithmus, mit dem Sie die Anzahl der Paare von Array-Elementen finden und anzeigen können, in denen mindestens eine Zahl durch 3 teilbar ist. Bei diesem Problem bedeutet ein Paar zwei aufeinanderfolgende Array-Elemente. Zum Beispiel für ein Array aus fünf Elementen: 6; 2; 9; -3; 6 - Antwort: 4.
Die Anfangsdaten werden wie unten in Beispielen für einige Programmiersprachen und natürliche Sprache gezeigt deklariert. Es ist verboten, unten nicht beschriebene Variablen zu verwenden, aber es ist erlaubt, einige der beschriebenen Variablen nicht zu verwenden.
BASIC | Python |
KONST N ALS INTEGER = 20 DIM A (1 BIS N) ALS INTEGER DIM I ALS INTEGER, J ALS INTEGER, K ALS INTEGER FÜR I = 1 BIS N EINGANG A(I) NÄCHSTER ICH ... ENDE | # auch erlaubt # zwei verwenden # Integer-Variablen j und k ein = n=20 für i im Bereich (0, n): a.append(int(input())) ... |
Algorithmische Sprache | Paskal |
alg frühzeitig ganze Zahl N = 20 celtab a ganze Zahlen i, j, k nc für i von 1 bis N Eingabe a[i] kts ... con | konst N = 20; Var a: Array von ganzen Zahlen; i, j, k: ganze Zahl; Start für i:= 1 bis N tun readln(a[i]); ... Ende. |
Xi | Natürliche Sprache |
#enthalten #define N 20 int main() ( int a[N]; int i, j, k; für (i = 0; i scanf("%d", &a[i]); ... 0 zurückgeben; } | Wir deklarieren ein Array A mit 20 Elementen. Wir deklarieren die ganzzahligen Variablen I, J, K. In einer Schleife von 1 bis 20 geben wir die Elemente des Arrays A vom 1. bis zum 20. ein. … |
Als Antwort müssen Sie ein Programmfragment (oder eine Beschreibung des Algorithmus in natürlicher Sprache) angeben, das anstelle der Auslassungspunkte stehen sollte. Sie können die Lösung auch in einer anderen Programmiersprache (Name und Version der verwendeten Programmiersprache angeben, z. B. Free Pascal 2.6) oder als Flussdiagramm schreiben. In diesem Fall müssen Sie dieselben Ausgangsdaten und Variablen verwenden, die in der Bedingung vorgeschlagen wurden (z. B. in einem in natürlicher Sprache geschriebenen Beispiel).
k:=k+1
alle
kts
Ausgang k
Paskal
k:= 0;
für i:= 1 bis N-1 tun
if (a[i] mod 3=0) or (a mod 3=0) then
inkl. (k);
schreiben(k);
Xi
k = 0;
für (i = 0; i
wenn (a[i]%3 == 0 || a%3 == 0)
k++;
printf("%d", k);
Natürliche Sprache
Wir schreiben den Anfangswert gleich 0 in die Variable K. In der Schleife vom ersten zum vorletzten Element finden wir den Rest aus der Division des aktuellen und des nächsten Elements des Arrays durch 3. Wenn das erste oder zweite des Ergebnisses Rest 0 ist, erhöhe die Variable K um eins. Nachdem die Schleife abgeschlossen ist, zeigen wir den Wert der Variablen K an
26. SucheZwei 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 verdoppeln. 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), (20, 7), (10, 8), (10, 14). 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 73 erreicht. Der Gewinner ist der Spieler, der den letzten Zug gemacht hat, d.h. der erste, der eine solche Position erreicht, dass insgesamt 73 Steine oder mehr in den Stapeln liegen.
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 muss, der er wann begegnen kann anderes Spiel Feind. Mit den Anfangspositionen (6, 34), (7, 33), (9, 32) hat Petya beispielsweise eine Gewinnstrategie. Um zu gewinnen, muss er nur die Anzahl der Steine im zweiten Stapel verdoppeln.
Übung 1.Geben Sie für jede der Anfangspositionen (6, 33), (8, 32) an, welcher der Spieler eine Gewinnstrategie hat. Beschreiben Sie jeweils die Gewinnstrategie; Erklären Sie, warum diese Strategie zu einem Gewinn führt, und geben Sie an, welche die größte Zahl Es können Züge erforderlich sein, damit der Gewinner mit dieser Strategie gewinnt.
Aufgabe 2.Geben Sie für jede der Anfangspositionen (6, 32), (7, 32), (8, 31) an, welcher der Spieler eine Gewinnstrategie hat. Beschreiben Sie jeweils die Gewinnstrategie; Erklären Sie, warum diese Strategie zu einem Gewinn führt, und geben Sie die maximale Anzahl an Zügen an, die ein Gewinner ausführen kann, um mit dieser Strategie zu gewinnen.
Aufgabe 3.Zum Startposition(7, 31) geben an, welcher der Spieler eine Gewinnstrategie hat. Beschreiben Sie eine Gewinnstrategie; Erklären Sie, warum diese Strategie zu einem Gewinn führt, und geben Sie die maximale Anzahl an Zügen an, die ein Gewinner ausführen kann, um mit dieser Strategie zu gewinnen. Erstellen Sie einen Baum aller Spiele, die mit der von Ihnen angegebenen Gewinnstrategie möglich sind. Präsentieren Sie den Baum in Form eines Bildes oder einer Tabelle.
(7,31)
Insgesamt 38
(7,31+1)=(7,32)
Insgesamt 39
(7+1,32)=(8,32)
Insgesamt 40
(8+1,32)=(9,32)
Insgesamt 41
(9,32*2)=(9,64)
Insgesamt 73
(8,32+1)=(8,33)
Insgesamt 41
(8,33*2)=(8,66)
Insgesamt 74
(8*2,32)=(16,32)
Insgesamt 48
(16,32*2)=(16,64)
Gesamt80
(8,32*2)=(8,64)
Insgesamt 72
(8,64*2)=(8,128)
Insgesamt 136
(7+1,31)=(8,31)
Insgesamt 39
(8,31+1)=(8,32)
Insgesamt 40
(8+1,32)=(9,32)
Insgesamt 41
(9,32*2)=(9,64)
Insgesamt 73
(8,32+1)=(8,33)
Gesamt41
(8,33*2)=(8,66)
Insgesamt 74
(8*2,32)=(16,32)
Insgesamt 48
(16,32*2)=(16,64)
Insgesamt 80
(8,32*2)=(8,64)
Insgesamt 72
(8,64*2)=(8,128)
Insgesamt 136
(7*2,31)=(14,31)
Insgesamt 45
(14,31*2)=(14,62)
Insgesamt 76
(7,31*2)=(7,62)
Insgesamt 69
(7,62*2)=(7,124)
Insgesamt 131
Übung 1.In den Ausgangspositionen (6, 33), (8, 32) hat Wanja eine Gewinnstrategie. Mit der Ausgangsstellung (6, 33) kann nach Petjas erstem Zug eine der folgenden vier Stellungen erreicht werden: (7, 33), (12, 33), (6, 34), (6, 66). Jede dieser Positionen enthält weniger als 73 Steine. Darüber hinaus kann Vanya von jeder dieser Positionen eine Position mit mindestens 73 Steinen erreichen, indem er die Anzahl der Steine im zweiten Stapel verdoppelt. Für Position (8, 32) kann nach Petyas erstem Zug eine der folgenden vier Positionen erreicht werden: (9, 32), (16, 32), (8, 33), (8, 64). Jede dieser Positionen enthält weniger als 73 Steine. Darüber hinaus kann Vanya von jeder dieser Positionen eine Position mit mindestens 73 Steinen erreichen, indem er die Anzahl der Steine im zweiten Stapel verdoppelt. Also, Wanja, für jede Bewegung von Petja
gewinnt mit seinem ersten Zug.
Aufgabe 2.In den Ausgangspositionen (6, 32), (7, 32) und (8, 31) hat Petya eine Gewinnstrategie. Mit der Ausgangsposition (6, 32) muss er sich zunächst bewegen, um die Position (6, 33) von den Ausgangspositionen (7, 32) und (8, 31) zu erhalten. Petya sollte nach dem ersten Zug Position (8, 32) bekommen. Die Positionen (6, 33) und (8, 32) wurden bei der Analyse von Aufgabe 1 berücksichtigt. In diesen Positionen hat der Spieler, der als Zweiter ziehen wird (das ist jetzt Petya), eine Gewinnstrategie. Diese Strategie wurde in der Analyse von Aufgabe 1 beschrieben. Somit gewinnt Petja in jedem Spiel, das Wanja spielt, mit seinem zweiten Zug.
Aufgabe 3.In der Ausgangsposition (7, 31) hat Wanja eine Gewinnstrategie. Nach Petyas erstem Zug kann eine von vier Positionen erscheinen: (8, 31), (7, 32), (14, 31) und (7, 62). In den Positionen (14, 31) und (7, 62) kann Vanya in einem Zug gewinnen, indem er die Anzahl der Steine im zweiten Stapel verdoppelt. Die Stellungen (8, 31) und (7, 32) wurden bei der Analyse von Aufgabe 2 berücksichtigt. In diesen Stellungen hat der Spieler, der einen Zug machen muss (jetzt Wanja), eine Gewinnstrategie. Diese Strategie wurde in der Analyse von Aufgabe 2 beschrieben. Abhängig von Petyas Spiel gewinnt Vanya also im ersten oder zweiten Zug.
27. SucheIm physikalischen Labor wird zur Untersuchung ein Langzeitexperiment durchgeführt Schwerkraftfeld Erde. Jede Minute wird über den Kommunikationskanal eine positive Ganzzahl an das Labor übertragen - der aktuelle Messwert des Sigma 2015-Geräts. Die Anzahl der übertragenen Nummern in der Reihe ist bekannt und überschreitet nicht 10000. Alle Nummern überschreiten nicht 1000. Die Zeit, während der die Übertragung stattfindet, kann vernachlässigt werden.
Es ist notwendig, den "Beta-Wert" einer Reihe von Instrumentenablesungen zu berechnen - das kleinste gleichmäßige Produkt von zwei Ablesungen, zwischen deren Übertragung mindestens 6 Minuten vergangen sind. Wenn ein solches Produkt nicht erhalten werden kann, wird die Antwort als gleich -1 betrachtet.
Zu dieser Aufgabe werden Ihnen zwei Aufgaben angeboten: Aufgabe A und Aufgabe B. Sie können beide Aufgaben oder eine davon nach Ihrer Wahl lösen. Abschlussnote wird als Höchstpunktzahl für die Aufgaben A und B festgelegt. Wenn die Lösung einer der Aufgaben nicht präsentiert wird, dann wird davon ausgegangen, dass die Note für diese Aufgabe 0 Punkte beträgt. Aufgabe B ist eine komplizierte Version von Aufgabe A, die sie enthält Zusätzliche Anforderungen zum Programm.
A. Schreiben Sie ein Programm in einer beliebigen Programmiersprache, um das Problem zu lösen, in dem die Eingabedaten in einem Array gespeichert werden, wonach alle möglichen Elementpaare überprüft werden. Geben Sie die Programmiersprachenversion vor dem Programm an.
Geben Sie an, dass das Programm eine Lösung für AUFGABE A ist.
Die maximale Punktzahl für die Erfüllung von Aufgabe A beträgt 2 Punkte.
B. Schreiben Sie ein Programm zur Lösung des Problems, das sowohl zeit- als auch speichereffizient ist (oder mindestens eine dieser Eigenschaften aufweist).
Ein Programm gilt als zeiteffizient, wenn die Laufzeit
Programm ist proportional zur Anzahl der empfangenen Instrumentenablesungen N, d.h. wenn sich N um k-mal erhöht, sollte die Laufzeit des Programms nicht mehr als k-mal zunehmen.
Ein Programm gilt als speichereffizient, wenn die Größe des im Programm zum Speichern von Daten verwendeten Speichers nicht von der Zahl N abhängt und 1 Kilobyte nicht überschreitet.
Geben Sie vor dem Programm die Version der Programmiersprache an und beschreiben Sie kurz den verwendeten Algorithmus.
Geben Sie an, dass das Programm eine Lösung für AUFGABE B ist.
Die maximale Punktzahl für ein korrektes, zeit- und gedächtniseffizientes Programm beträgt 4 Punkte.
Die maximale Punktzahl für ein korrektes Programm, das zeiteffizient, aber speicherineffizient ist, beträgt 3 Punkte. ERINNERUNG! Vergessen Sie nicht anzugeben, zu welcher Aufgabe jedes der von Ihnen eingereichten Programme gehört.
Die Eingabedaten werden wie folgt dargestellt. Die erste Zeile enthält die Zahl N - die Gesamtzahl der Instrumentenablesungen. Es ist garantiert, dass N > 6 ist. Jede der nächsten N Zeilen enthält eine positive ganze Zahl – die nächste Ablesung des Instruments.
Eingabebeispiel:
11
12
45
5
3
17
23
21
20
19
18
17
Das Programm sollte eine Zahl anzeigen - das in der Bedingung beschriebene Produkt oder -1, wenn ein solches Produkt nicht erhältlich ist.
Beispielausgabe für die obige Beispieleingabe:
54
Erläuterung.
Aufgabe B (die Lösung für Aufgabe A ist unten angegeben, siehe Programm 4). Damit das Produkt gleichmäßig ist, muss mindestens ein Faktor gleichmäßig sein, also beim Suchen passende Werke gerade Messwerte des Geräts können zusammen mit allen anderen und ungerade Messwerte - nur mit geraden - berücksichtigt werden.
Für jede Angabe mit der Nummer k, beginnend mit k = 7, betrachten wir alle unter den Bedingungen des Problems zulässigen Paare, bei denen diese Angabe an zweiter Stelle steht. Das minimale Produkt aller dieser Paare wird erhalten, wenn der minimale geeignete Messwert zuerst in dem Paar unter allen empfangenen vom Beginn des Empfangs bis zu dem Messwert mit der Nummer k – 6 genommen wird. Wenn der nächste Messwert gerade ist, wird der Das Minimum unter den vorherigen kann beliebig sein, wenn es ungerade ist - nur gerade.
Um eine zeiteffiziente Lösung zu erhalten, müssen Sie sich bei der Dateneingabe das absolute Minimum und die minimalen geraden Messwerte für jeden Zeitpunkt merken, jeden neu erhaltenen Messwert mit dem entsprechenden Minimum multiplizieren, das 6 Elemente zuvor verfügbar war, und das Minimum auswählen aller solcher Produkte.
Da jeder aktuelle Tiefstwert nach 6 weiteren Eingaben verwendet wird und danach unnötig wird, reicht es aus, nur die letzten 6 Tiefstwerte zu speichern. Dazu können Sie ein Array aus 6 Elementen verwenden und es durchlaufen, während Sie Daten eingeben. Die Größe dieses Arrays ist unabhängig von gesamt eingegebenen Messwerte, so dass eine solche Lösung nicht nur in Bezug auf die Zeit, sondern auch in Bezug auf das Gedächtnis effektiv ist. Um absolute und sogar Minima zu speichern, müssen Sie zwei solcher Arrays verwenden. Unten ist ein Beispiel für ein solches Programm, das in einer algorithmischen Sprache geschrieben ist.
Beispiel 1. Ein Beispiel für ein korrektes Programm in einer algorithmischen Sprache. Das Programm ist sowohl zeit- als auch speichereffizient.
alg
frühzeitig
ganze Zahl s = 6 | erforderlichen Abstand zwischen den Messungen
ganze Zahl amax = 1001 | mehr als der maximal mögliche Messwert
ganze Zahl N
Eingang N
ganze Zahl a | eine andere Instrumentenablesung
celtab mini | aktuelle Tiefststände der letzten s Elemente
Celtab Minichet | sogar Minima der letzten s-Elemente
Ziel i
| Geben Sie die ersten Messwerte ein, legen Sie die Minima fest
ganze ma; ma:= amax | minimale Lektüre
ganze Hektik; rauschen:= amax | minimaler gleichmäßiger Messwert
nc für i von 1 bis s
Eingabe a
ma:= imin(ma, a)
mini := ma
minichet := Eile
kts
ganze Zahl mp = amax*amax | Mindestwert funktioniert
ganze p
nc für i von s+1 bis N
Eingabe a
wenn mod(a,2)=0
dann n:= a * mini
sonst wenn es eilt
dann n:= a * minieven
sonst n:= amax*amax;
alle
alle
mp:= imin(mp, n)
ma:= imin(ma, a)
if mod(a,2) = 0 then flicker:= imin(flash,a) all
mini := ma
minichet := Eile
kts
wenn mp = amax*amax dann mp:=-1 alle
Ausgabe mp
con
Andere Implementierungen sind ebenfalls möglich. Anstatt beispielsweise ein Array zyklisch zu füllen, können Sie seine Elemente jedes Mal verschieben. Im Beispiel unten werden nicht die Tiefs gespeichert und verschoben, sondern Anfangswerte. Dies erfordert etwas weniger Speicher (ein Array reicht statt zwei), aber die Lösung mit Verschiebungen ist weniger zeiteffizient als mit zyklischem Füllen. Die Laufzeit bleibt jedoch proportional zu N, sodass die maximale Punktzahl für diese Lösung ebenfalls 4 Punkte beträgt.
Programm 2. Ein Beispiel für ein korrektes Pascal-Programm.
Das Programm verwendet Verschiebungen, ist aber zeit- und speichereffizient
Var
N: Ganzzahl
a: Array von ganzen Zahlen; (Speicherung der Instrumentenablesungen)
a_: Ganzzahl; (Eingabe der nächsten Angabe)
p: ganze Zahl;
i, j: ganze Zahl;
Start
readln(N);
(Eingabe der ersten s-Nummern)
for i:=1 to s do readln(a[i]);
(Andere Werte eingeben, Mindestprodukt finden)
ma:= amax; ich:= amax;
mp:=amax*amax;
für i:= s + 1 bis N beginnen
readln(a_);
wenn ein
wenn (a mod 2 = 0) und (a
wenn a_ mod 2 = 0 dann p:= a_ * ma
sonst wenn ich
sonst p:= amax* amax;
wenn P
(Elemente des Hilfsarrays nach links verschieben)
für j:= 1 bis s - 1 tun
a[j] := ein;
a[s] := a_
Ende;
wenn mp = amax*amax dann mp:=-1;
schreiben(mp)
Ende.
Wenn anstelle eines kleinen Arrays fester Größe (zyklisch oder verschoben) alle Originaldaten (oder alle aktuellen Minima) gespeichert werden, bleibt das Programm zeiteffizient, wird aber speicherineffizient, da der erforderliche Speicher proportional zu N wächst. Unten ist ein Beispiel eines solchen Programms in der Sprache Pascal. Ähnliche (und im Wesentlichen ähnliche) Programme werden nicht höher als 3 Punkte bewertet.
Programm 3. Ein Beispiel für ein korrektes Pascal-Programm. Das Programm ist zeiteffizient, aber speicherineffizient
konstant s = 6; (erforderlicher Abstand zwischen den Messwerten)
amax = 1001; (größer als der maximal mögliche Messwert)
Var
N, p, i: ganze Zahl;
ma: ganze Zahl; (Mindestanzahl ohne letzte s)
ich: Ganzzahl; (Minimum gerade Zahl ohne letzten s)
mp: ganze Zahl; (Mindestproduktwert)
Start
readln(N);
(Eingabe aller Instrumentenablesungen)
für i:=1 bis N do readln(a[i]);
ma:= amax;
ich:= amax;
mp:= amax*amax;
für i:= s + 1 bis N tun
Start
wenn ein
wenn (a mod 2 = 0) und (a
ich:= ein;
wenn a[i] mod 2 = 0 dann p:= a[i] * ma
sonst wenn ich
sonst p:= amax * amax;
wenn P
Ende;
wenn mp = amax*amax dann mp:= -1;
schreiben(mp)
Ende.
Möglich ist auch eine Aufzählungslösung, bei der die Produkte aller möglichen Paare gefunden werden und daraus das Minimum ausgewählt wird. Unten (siehe Programm 4) ist ein Beispiel eine solche Entscheidung. Diese (und ähnliche) Lösung ist weder zeit- noch speichereffizient. Es ist eine Lösung für Aufgabe A, aber keine Lösung für Aufgabe B. Die Punktzahl für eine solche Lösung beträgt 2 Punkte.
Programm 4. Ein Beispiel für ein korrektes Pascal-Programm. Das Programm ist weder zeit- noch speichereffizient
konstant s = 6; (erforderlicher Abstand zwischen den Messwerten)
Var
N: Ganzzahl
a: Array von ganzen Zahlen; (alle Instrumentenablesungen)
mp: ganze Zahl; (Mindestproduktwert)
i, j: ganze Zahl;
Start
readln(N);
(Instrumentenwerte eingeben)
für i:=1 bis N tun
readln(a[i]);
mp:= 1000 * 1000 + 1;
für i:= 1 bis N-s beginnen
für j:= i+s bis N beginnen
wenn (a[i]*a[j] mod 2 = 0) und (a[i]*a[j]
dann mp:= a[i]*a[j]
Ende;
Ende;
wenn mp = 1000 * 1000 + 1 dann mp:= -1;
schreiben(mp)
K. Yu. PoljakowVERWENDUNG in der Informatik:
2016 und darüber hinaus …
K. Yu. Poljakow, 2015
http://kpolyakov.spb.ru
Strukturelle Veränderungen 2015-2016
2
Strukturelle Veränderungen 2015-2016
1) Teil A entfernen
2) Verringerung der Anzahl der Aufgaben
3) Verein einfache Aufgaben (4, 6, 7, 9)
Ziel: mehr Zeit für Entscheidungen lassen
komplexe Aufgaben.
4) Python-Sprache
!
K. Yu. Poljakow, 2015
Variabilität!
http://kpolyakov.spb.ru
VERWENDUNG in der Informatik: 2016 und darüber hinaus…
3
Wie viele Einheiten in Binärschreibweise
Hexadezimalzahl 12F016.
1
2
12 102
F
11112
0
1+1+4=6
Geben Sie die kleinste Zahl an, deren binäre Schreibweise
enthält genau drei signifikante Nullen und drei Einsen.
Schreiben Sie Ihre Antwort in Dezimalzahlen
1000112 = 35
K. Yu. Poljakow, 2015
http://kpolyakov.spb.ru
B1: binäres Zahlensystem
VERWENDUNG in der Informatik: 2016 und darüber hinaus…4
B1: binäres Zahlensystem
Zahlen 1025?
1) "auf der Stirn" - übersetzen ...
2) 1025 = 1024 + 1
1024 = 100000000002
1025 = 100000000012
Antwort: 2
511?
511 = 512 - 1
= 10000000002 - 1 = 1111111112
Antwort: 9
K. Yu. Poljakow, 2015
http://kpolyakov.spb.ru
B1: binäres Zahlensystem
VERWENDUNG in der Informatik: 2016 und darüber hinaus…5
B1: binäres Zahlensystem
Wie viele Einheiten gibt es in binärer Schreibweise von Dezimalzahlen
Nummer 999?
1) "auf der Stirn" - übersetzen ...
2) 999 = 1023 – 16 – 8
1023 = 1024 – 1 = 11111111112
minus zwei Einheiten: 8
519?
519 = 512 + 7
512 = 10000000002
7 = 1112
plus drei Einheiten: 4
K. Yu. Poljakow, 2015
http://kpolyakov.spb.ru
B1: Zahlensysteme
VERWENDUNG in der Informatik: 2016 und darüber hinaus…6
B1: Zahlensysteme
Welche der folgenden Zahlen kann hineingeschrieben werden?
binäres Zahlensystem in der Form 1xxx10, wobei x kann
sowohl 0 als auch 1 bedeuten?
1) 74
2) 38
3) 60
4) 47
1) 1000102 = 34 N 1111102 = 62
2) 1xxx10 ist durch 2 teilbar
3) 1xxx10 ist nicht durch 4 teilbar
K. Yu. Poljakow, 2015
http://kpolyakov.spb.ru
B2: Logikfunktionen
VERWENDUNG in der Informatik: 2016 und darüber hinaus…7
B2: logische Funktionen
x1
1
!
x2
0
x3
x4
0
1
x5
x6
x7
x8
1
1
F
0
1
1
Alle Optionen sind einfach UND oder ODER!
1) "auf der Stirn" - in Formeln ersetzen ...
2) wenn alle "OR" eine Null
Überprüfen Sie die Zeile, in der F = 0 ist
x2 ohne Umkehrung, x8 mit Umkehrung
3) wenn alle "Und" eine Einheit
K. Yu. Poljakow, 2015
http://kpolyakov.spb.ru
B2: Logikfunktionen
VERWENDUNG in der Informatik: 2016 und darüber hinaus…8
B2: Logikfunktionen
Funktionstabelle z x x
z
0
0
0
0
1
1
1
1
?y
0
0
1
1
0
0
1
1
K. Yu. Poljakow, 2015
?x
0
1
0
1
0
1
0
1
F
0
1
0
1
0
0
0
1
j.
zxxy
x (z y)
x 0 F 0
x 1
z1
F0
ja 0
Antwort: zyx
http://kpolyakov.spb.ru
B2: Logikfunktionen
VERWENDUNG in der Informatik: 2016 und darüber hinaus…9
B2: Logikfunktionen
Funktionstabelle x y z x
Bestimme, in welchen Spalten x, y und z sind.
z
0
0
0
0
1
1
1
1
?x
0
0
1
1
0
0
1
1
K. Yu. Poljakow, 2015
?y
0
1
0
1
0
1
0
1
F
0
0
1
0
1
1
1
1
ja.
x y z x y z
z 0 F x y
z 1 F x y x y
(x x) (y x) y
y x y 1
z0
x 1 Antwort: zxy
F1
ja 0
http://kpolyakov.spb.ru
B3: Gewichtsmatrizen grafisch darstellen
VERWENDUNG in der Informatik: 2016 und darüber hinaus…10
B3: Gewichtsmatrizen zählt
EIN
EIN
B
C
D
E
F
Z
B
4
C
6
3
D
E
F
11
4
5
7
4
Z
30
27
10
8
2
29
1) asymmetrische Matrix (Digraph)
2) zwei Einbahnstraßen
3) „Wie viele Straßen führen durch N
Punkte?
4) "... nicht weniger als in N Punkten?"
K. Yu. Poljakow, 2015
http://kpolyakov.spb.ru
B3: Gewichtsmatrizen grafisch darstellen
VERWENDUNG in der Informatik: 2016 und darüber hinaus…11
B3: Gewichtsmatrizen grafisch darstellen
1
1
2
2
3
45
4
5
6
6
45
55
3
15 60
2
10 40
15
20 35
4
55
2
55 60 20 55
35
45
45
E
ABER
5
2
Grad
Spitzen
K. Yu. Poljakow, 2015
D
2
40
7
B
7
10
3
4
5
Zu
BEI
Grad 4
Grad 5
G
Antwort: 20
http://kpolyakov.spb.ru
B4-1: Tabellarische Datenbanken
VERWENDUNG in der Informatik: 2016 und darüber hinaus…12
B4-1: Tabellarische Datenbanken
1) Wie viele Nachkommen (Kinder, Enkel, Urenkel...) hat X?
2) Wie viele Vorfahren von X gibt es in der Tabelle?
3) Finden Sie Ihren Großvater mütterlicherseits
23
24
25
K. Yu. Poljakow, 2015
34
57
35
42
http://kpolyakov.spb.ru
VERWENDUNG in der Informatik: 2016 und darüber hinaus…
13
Nachrichten enthalten die Buchstaben P, O, C, T; Gebraucht
Binärcode ermöglicht eindeutig
Dekodierung. Codewörter:
T: 111, O: 0, P: 100.
Geben Sie mit das kürzeste Codewort für den Buchstaben C ein
wobei der Code eine Eindeutigkeit zulässt
Dekodierung. Wenn es mehr als einen solchen Code gibt, bitte angeben
der Code mit dem kleinsten Zahlenwert.
1
0
0x10
0xx
Ö
11
101
P
K. Yu. Poljakow, 2015
0
0
110
1
1
1
0
1
T
http://kpolyakov.spb.ru
B5: Kodierung und Dekodierung
VERWENDUNG in der Informatik: 2016 und darüber hinaus…14
B5: Kodierung und Dekodierung
Nachrichten enthalten drei Vokale: A, E, I - und fünf
Konsonanten: B, C, D, D, K. Buchstaben sind verschlüsselt
Präfix-Code. Es ist bekannt, dass alle Codewörter für
Konsonanten haben die gleiche Länge, und
A-1, E-01, I-001.
Wofür ist die kleinstmögliche Länge von Codewörtern?
Konsonanten?
0
5 Konsonanten 3 Bits 4 Bits 5 Bits
4:1xx
0
1
2:01x
0
1
ABER
1: 001
1
E
verfügbar: 000
000x 000xx
1
2
4
Und
K. Yu. Poljakow, 2015
6 Bit
000xxx
8
http://kpolyakov.spb.ru
B6-1: automatisch
VERWENDUNG in der Informatik: 2016 und darüber hinaus…15
B6-1: automatisch
Parität wiederhergestellt!
Eingabe: natürliche Zahl N.
1. Das Paritätsbit wird am Ende des Binärdatensatzes hinzugefügt
(Quersumme mod 2).
2. Der empfangenen Zeichenfolge wird ein weiteres Paritätsbit hinzugefügt.
Geben Sie die kleinste Zahl an, für die das Ergebnis angezeigt wird
Die Ausführung dieses Algorithmus führt zu einer Zahl
mehr als 125.
!
Schritt 2 addiert 0 2!
Sollte gerade werden = 126 oder 128
Nach Div 2 muss die Parität erhalten bleiben!
126 / 2 = 63 = 1111112: - 6 Einheiten, gerade
Antworten:
K. Yu. Poljakow, 2015
31
http://kpolyakov.spb.ru
B10: Kombinatorik
VERWENDUNG in der Informatik: 2016 und darüber hinaus…16
B10: Kombinatorik
Wie viele Wörter mit 5 Buchstaben gibt es, die nur enthalten
Buchstaben P, I, R, und der Buchstabe P kommt genau einmal vor.
P****
*P***
**P**
***P*
****P
K. Yu. Poljakow, 2015
24 = 16 Wörter
Antwort: 16 5 = 80.
http://kpolyakov.spb.ru
B12: Netzwerkadressierung
VERWENDUNG in der Informatik: 2016 und darüber hinaus…17
B12: Netzwerkadressierung
IP-Adresse 224.128.112.142
Die Netzwerkadresse ist 224.128.64.0.
Was ist das dritte Byte der Maske von links?
nicht vergessen
*.*.112.*
Senioreneinheiten!
*.*.64.0
Maske: 110000002 = 192
192
112 = 011100002
64 = 010000002
!
K. Yu. Poljakow, 2015
Bitweise Konjunktion!
http://kpolyakov.spb.ru
B12: Netzwerkadressierung
VERWENDUNG in der Informatik: 2016 und darüber hinaus…18
B12: Netzwerkadressierung
IP-Adresse 111.81.208.27
Die Netzwerkadresse ist 111.81.192.0.
Was ist der Mindestwert des dritten von links
Maskenbyte?
*.*.208.*
*.*.192.0
208 =
192 =
Maske:
Maske:
110100002
110000002
111000002
110000002
192
K. Yu. Poljakow, 2015
http://kpolyakov.spb.ru
B14: Zeichner
VERWENDUNG in der Informatik: 2016 und darüber hinaus…19
B14: Zeichner
Verschiebung um (–3, –3) 1)
N-MAL WIEDERHOLEN
2)
gehe zu (a, b) 3)
gehe zu (27, 12) 4)
ENDE WIEDERHOLUNG
verschieben um (–22, -7)
3N x 220
3 N j 7 0
kleinstes N > 1
größte n
alle möglichen N
die Summe aller N
N x 25
N und 10
N = gemeinsamer Teiler (25,10)
K. Yu. Poljakow, 2015
http://kpolyakov.spb.ru
B14: Herausgeber
VERWENDUNG in der Informatik: 2016 und darüber hinaus…20
B14: Herausgeber
1) ersetze(v,w)
2) gefunden (v)
NOCH gefunden (222) ODER gefunden (888)
WENN gefunden (222)
zu ersetzen (222, 8)
ELSE ersetzen (888, 2)
Was ist das Ergebnis der Verarbeitung des Strings 88888…8 ?
888888888…8
2 2 2
8
K. Yu. Poljakow, 2015
!
In 4 Schritten
ENTFERNT
8 Achter!
68 - 8 8 = 4
68
8888 28
http://kpolyakov.spb.ru
VERWENDUNG in der Informatik: 2016 und darüber hinaus…
21
Stadt A nach Stadt L, nicht durch B?
D
B
UND
BEI
ABER
G
K. Yu. Poljakow, 2015
Und
E
L
Zu
http://kpolyakov.spb.ru
B15: Anzahl Pfade in Spalten
VERWENDUNG in der Informatik: 2016 und darüber hinaus…22
B15: Anzahl Pfade in Spalten
Wie viele verschiedene Wege gibt es
Stadt A nach Stadt L auf der Durchreise durch D?
D
B
UND
BEI
ABER
G
K. Yu. Poljakow, 2015
Und
E
L
Zu
http://kpolyakov.spb.ru
B16: Zahlensysteme
VERWENDUNG in der Informatik: 2016 und darüber hinaus…23
B16: Zahlensysteme
Wie viele Einheiten sind binär
(ternäre, ...) Schreibweise der Zahl X?
10N = 100…0
10N-1 = 99…9
N
N
2N = 100…02
N
3N = 100…03
N
K. Yu. Poljakow, 2015
2N-1 = 11…1
N
3N-1 = 22…2
N
http://kpolyakov.spb.ru
B16: Zahlensysteme
VERWENDUNG in der Informatik: 2016 und darüber hinaus…24
B16: Zahlensysteme
2N - 2M = 2M (2N-M - 1)
= 100…02 11…12
N-M
M
= 11…100…02
N-M
K. Yu. Poljakow, 2015
M
http://kpolyakov.spb.ru
B16: Zahlensysteme
VERWENDUNG in der Informatik: 2016 und darüber hinaus…25
B16: Zahlensysteme
Nummern (24400–1) (42200+2)?
(24400–1) (42200+2) = (24400–1) (24400+1+1)
= (24400–1) (24400+1) + 24400–1
= 28800 – 1 + 24400–1
= 28800 + 24400 – 21
1
4399
1 + 4399 = 4400
K. Yu. Poljakow, 2015
http://kpolyakov.spb.ru
B16: Zahlensysteme
VERWENDUNG in der Informatik: 2016 und darüber hinaus…27
B16: Zahlensysteme
Wie viele Einheiten gibt es in binärer Schreibweise
Werte der Zahl 8148 - 4123 + 2654 - 17?
8148 = 2444
4123 = 2246
2654
17 = 16 + 1
= 24 + 2 0
2654 + 2444 – 2246 – 24 – 20
444 – 2246 – 24 – 20
2
1
444 – 2
1 + 444 – 2 = 443
K. Yu. Poljakow, 2015
http://kpolyakov.spb.ru
B16: Zahlensysteme
VERWENDUNG in der Informatik: 2016 und darüber hinaus…28
B16: Zahlensysteme
Wie viele Zweien sind in ternärer Schreibweise
Werte der Nummer 9118 + 3123 - 27?
9118 = 3236
27 = 33
K. Yu. Poljakow, 2015
3236 + 3123 – 33
1
120 Zweien
http://kpolyakov.spb.ru
B16: Zahlensysteme
VERWENDUNG in der Informatik: 2016 und darüber hinaus…29
B17: Suchanfragen in Suchmaschinen
Anfrage
USA | Japan | China
Japan | China
(USA & Japan) | (USA & China)
Vereinigte Staaten von Amerika
A=USA
Anfrage
A|B
B
A&B
EIN
Seiten
450
260
50
?
B = Japan | China
Seiten
450
260
50
?
EIN
A&B
B
NA | B = NA + NB - NA & B
NA = 450 - 260 + 50 = 240
K. Yu. Poljakow, 2015
http://kpolyakov.spb.ru
B17: Suchanfragen in Suchmaschinen
VERWENDUNG in der Informatik: 2016 und darüber hinaus…30
P = und Q = . Kleinste angeben
die mögliche Länge eines solchen Segments A, dass der Ausdruck
(x P) (((x Q) (x A)) (x P))
identisch wahr, das heißt gleich 1 für alle
der Wert von x.
P(xP),
Q(xQ),
EIN (x EIN)
P (Q EIN P)
P (Q EIN P)
P Q EIN P P Q EIN
PQ A
P
Q
K. Yu. Poljakow, 2015
P
37
40
60
77
x
20
Q
http://kpolyakov.spb.ru
B18: Logische Operationen, Mengen
VERWENDUNG in der Informatik: 2016 und darüber hinaus…31
Satz A: ganze Zahlen. Ausdruck
(x(2, 4, 6, 8, 10, 12)) → (((x(4, 8, 12, 116))
¬(x A)) → ¬(x (2, 4, 6, 8, 10, 12)))
wahr für jeden Wert von x. Bestimmen
der kleinstmögliche Wert der Summe der Elemente
setzt A.
P x (2, 4, 6, 8, 10, 12),
Q x (4, 8, 12, 116),
A x A
P (Q EIN P)
PQ A
Amin P Q P Q (4, 8, 12)
K. Yu. Poljakow, 2015
= 24
http://kpolyakov.spb.ru
B18: Logische Operationen, Mengen
VERWENDUNG in der Informatik: 2016 und darüber hinaus…32
B18: logische Operationen, setzt
(x & 49<>0) ((x & 33 = 0) (x & A<> 0))
P x & 49 0,
A x & A 0
P(Qualitätssicherung)
Q x & 33 0,
P (Q EIN) P Q EIN
P Q EIN (P Q) EIN
K. Yu. Poljakow, 2015
http://kpolyakov.spb.ru
B18: Logische Operationen, Mengen
VERWENDUNG in der Informatik: 2016 und darüber hinaus…33
B18: Logische Operationen, Mengen
"&" ist eine bitweise Konjunktion (AND). Ausdruck
(x & 49<>0) ((x & 33 = 0) (x & A<> 0))
wahr für jedes natürliche x. Bestimmen
der kleinstmögliche Wert von A.
x&49
Bitnummer
5 4 3 2 1 0
49 = 110001
X = abcdef
X&49=ab000f
x & 49 = 0 alle Bits (5, 4, 0) sind Null
x&49<>
K. Yu. Poljakow, 2015
http://kpolyakov.spb.ru
B18: Logische Operationen, Mengen
VERWENDUNG in der Informatik: 2016 und darüber hinaus…34
B18: Logische Operationen, Mengen
"&" ist eine bitweise Konjunktion (AND). Ausdruck
(x & 49<>0) ((x & 33 = 0) (x & A<> 0))
wahr für jedes natürliche x. Bestimmen
der kleinstmögliche Wert von A.
(PQ)A
P:x & 49<>0-Bits (5, 4, 0) sind ungleich Null
F: x & 33 = 0 alle Bits (5, 0) sind Null
Bitnummer
5 4 3 2 1 0
33 = 100001
!
?
Bit 4 ist ungleich Null!
K. Yu. Poljakow, 2015
Was folgt daraus?
Amin = 24 = 16
http://kpolyakov.spb.ru
B18: Logische Operationen, Mengen
VERWENDUNG in der Informatik: 2016 und darüber hinaus…35
B18: Logische Operationen, Mengen
"&" ist eine bitweise Konjunktion (AND). Ausdruck
(x&A<>0) ((x & 20 = 0) (x & 5<> 0))
wahr für jedes natürliche x. Bestimmen
P x & 20 0,
A x & A 0
A (PQ)
Q x & 5 0,
EIN (PQ) EIN PQ
P Q EIN (P Q) EIN
K. Yu. Poljakow, 2015
http://kpolyakov.spb.ru
B18: Logische Operationen, Mengen
VERWENDUNG in der Informatik: 2016 und darüber hinaus…36
B18: Logische Operationen, Mengen
"&" ist eine bitweise Konjunktion (AND). Ausdruck
(x&A<>0) ((x & 20 = 0) (x & 5<> 0))
wahr für jedes natürliche x. Bestimmen
der größtmögliche Wert von A.
(PQ)A
P: x & 20 = 0 alle Bits (4, 2) sind Null
F: x & 5 = 0 alle Bits (2, 0) sind Null
!
Bits (4, 2, 0) in x sind Null!
Amax = 24 + 22 + 20 = 21
K. Yu. Poljakow, 2015
Sie werden zurückgesetzt
Anzahl Bits
bei &!
http://kpolyakov.spb.ru
B18: Logische Operationen, Mengen
VERWENDUNG in der Informatik: 2016 und darüber hinaus…37
B19: Array-Verarbeitung
c:=0;
für i:= 1 bis 9 tun
wenn ein< A[i] then begin
c:= c + 1;
t:= A[i];
Paarpermutation
A[i]:= A; beim Sortieren
A:= t
Blase
Ende;
K. Yu. Poljakow, 2015
http://kpolyakov.spb.ru
B19: Array-Verarbeitung
VERWENDUNG in der Informatik: 2016 und darüber hinaus…38
B19: Array-Verarbeitung
1)
2)
3)
4)
5)
6)
6
9
9
9
9
9
9
9
6
7
7
7
7
7
7
7
6
6
6
6
6
2
2
2
2
2
2
2
1
1
1
5
5
5
5
5
5
5
1
1
1
1
0
0
0
0
3
3
3
3
3
3
3
0
4
4
4
4
4
4
4
0
8
8
8
8
8
8
8
0
c=6
K. Yu. Poljakow, 2015
http://kpolyakov.spb.ru
B19: Array-Verarbeitung
VERWENDUNG in der Informatik: 2016 und darüber hinaus…39
B19: Array-Verarbeitung
Ein Array mit Indizes von 0 bis 9.
c:=0;
für i:= 1 bis 9 tun
wenn A[i]< A then begin
c:= c + 1;
t:= A[i];
A[i]:= A;
Paarpermutation
A:= t
Ende;
Welchen Wert wird die Variable "c" haben?
4 7 3 8 5 0 1 2 9 6
4 7 3 8 5 0 1 2 9 6
4 7 3 8 5 0 1 2 9 6
K. Yu. Poljakow, 2015
c=2
http://kpolyakov.spb.ru
B19: Array-Verarbeitung
VERWENDUNG in der Informatik: 2016 und darüber hinaus…40
B19: Array-Verarbeitung
s:=0;
n:=10;
für i:=0 bis n-1 beginnen
s:=s+A[i]-A
Ende;
s:=A-A+A-A+A-...
+A-A+A-A+A-A
max = 999 - 100 = 899
K. Yu. Poljakow, 2015
http://kpolyakov.spb.ru
B19: Array-Verarbeitung
VERWENDUNG in der Informatik: 2016 und darüber hinaus…41
B19: Array-Verarbeitung
Ein Array mit Indizes von 0 bis 10.
s:=0;
n:=10;
für i:=0 bis n-2 beginnen
s:=s+A[i]-A
Ende;
Das Array enthielt dreistellige natürliche Zahlen.
Die Höchster Wert kann "s" haben?
s:=A-A+A-A+A-...
+A-A+A-A+A-A
max = 999 + 999 - 100 - 100 = 1798
1798
K. Yu. Poljakow, 2015
http://kpolyakov.spb.ru
B19: Array-Verarbeitung
VERWENDUNG in der Informatik: 2016 und darüber hinaus…42
B20: Schleifen und Bedingungen ("Lerne den Algorithmus")
Geben Sie die kleinste fünfstellige Zahl x an, für die
6 wird zuerst gedruckt und dann 3.
a:=0;
Minimum und Maximum!
b:= 10;
readln(x);
während x > 0 beginnen
y:= x mod 10;
x:= x div 10;
33336
wenn y > a dann a:= y;
wenn ja< b then b:= y;
Ende;
schreiben(a); (Maximalzahl)
schreiben(b); (Mindestzahl)
!
K. Yu. Poljakow, 2015
http://kpolyakov.spb.ru
B20: Schleifen und Bedingungen ("Lerne den Algorithmus")
VERWENDUNG in der Informatik: 2016 und darüber hinaus…43
B20: Zyklen und Bedingungen
Was ist die kleinste Zahl x größer als 100 für die
26 wird gedruckt.
var x, L, M: Ganzzahl;
Start
x ungerade: ggT(x,65) = 26
readln(x);
x gerade: ggT(x,52) = 26
L:=x; M:= 65;
wenn L mod 2 = 0, dann ist x durch 26 teilbar,
M:= 52;
ist nicht durch 52 teilbar!
während L<>M tun
gcd(104,52) = 52
104
wenn L > M dann
L:= L - M
Antwort: 130
anders
M:= M - L;
schreiben(M);
Euklids Algorithmus!
Ende.
!
K. Yu. Poljakow, 2015
http://kpolyakov.spb.ru
B20: Zyklen und Bedingungen
VERWENDUNG in der Informatik: 2016 und darüber hinaus…44
B21: Zyklen und Verfahren
Start
ich
f(ich)
f:= n*(n-1)+10
1
10
Ende;
…
2
12
readln(k);
3
16
ich:= 0;
4
22
während f(i)< k do
5
30
36
ich:= ich + 1;
schreiben(i);
6
40
Halt: k<= f(i)
31 … 40
10
K. Yu. Poljakow, 2015
?
Für k = 30?
23 … 30
8
http://kpolyakov.spb.ru
B21: Zyklen und Verfahren
VERWENDUNG in der Informatik: 2016 und darüber hinaus…45
B21: Zyklen und Verfahren
Finden Sie die Anzahl der verschiedenen Werte von k für die
das Programm gibt die gleiche Antwort wie für k = 36.
Funktion f(n: lange Ganzzahl): lange Ganzzahl;
Start
Halt:
f:= n*(n-1)+10
f(i-1)< k <= f(i)
Ende;
(i-1)*(i-2)+10< k <= i*(i-1)+10
…
i2-3i+12< k <= i2-i+10
readln(k);
ich:= 0;
i=6: 30< k <= 40
während f(i)< k do
31 … 40
ich:= ich + 1;
schreiben(i);
Antwort: 10
K. Yu. Poljakow, 2015
http://kpolyakov.spb.ru
B21: Zyklen und Verfahren
VERWENDUNG in der Informatik: 2016 und darüber hinaus…46
B21: Zyklen und Verfahren
Finden Sie den kleinsten Wert von k, für den
das Programm gibt die gleiche Antwort wie für k = 10.
def f(n):
Halt:
gib n*n*n zurück
f(i-1)< g(k) <= f(i)
def g(n):
(i-1)3< 2k+3 <= i3
gib 2*n+3 zurück
3 < 23 <= i3
k=10:
(i-1)
k = int(Eingabe())
i=3
ich = 1
während f(i)< g(k):
8 < 2k+3 <= 27
i+=1
3 … 12
drucken (i)
Antwort: 3
K. Yu. Poljakow, 2015
http://kpolyakov.spb.ru
B21: Zyklen und Verfahren
VERWENDUNG in der Informatik: 2016 und darüber hinaus…47
B22: Programme für Darsteller
1) addiere 1
2) mit 2 multiplizieren
Wie viele Programme gibt es für welche von 2
die Zahl 29 wird erhalten und gleichzeitig die Flugbahn der Berechnungen
die Zahl 14 enthält und die Zahl 25 nicht enthält?
N ungerade
KN 1
Wiederkehrende Formel: K N
K N 1 K N / 2 N gerade
1
2
3
4
5
6
7
8
9
10
11
12
13
14
1
1
1
2
2
3
3
5
5
7
7
10
10
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
13
13
13
13
13
13
13
13
13
13
13
0
0
0
13
13
Neubeginn
K. Yu. Poljakow, 2015
Du kannst nicht hierher kommen
http://kpolyakov.spb.ru
B22: Programme für Darsteller
VERWENDUNG in der Informatik: 2016 und darüber hinaus…48
C24: Fehlerkorrektur
Eine natürliche Zahl x wird gelesen, die Sie finden müssen
die Anzahl der signifikanten Ziffern in ihrer binären Notation.
readln(x);
c:=0;
während x > 0 beginnen
c:= c + x mod 2;
x:= x div 10
Ende;
schreiben(c)
1)
2)
3)
4)
?
?
Was denkt er?
Wann funktioniert es
Rechts?
Nur für x=1
ungültiger Anfangswert
ungültige Schleifenbedingung
falsche Variablenänderung
falsche Ausgabe
K. Yu. Poljakow, 2015
http://kpolyakov.spb.ru
C24: Fehlerkorrektur
VERWENDUNG in der Informatik: 2016 und darüber hinaus…49
C24: Fehlerkorrektur
Wir müssen ein Programm schreiben, das anzeigt
die maximale Ziffer einer Zahl, die ein Vielfaches von 3 ist. Wenn die Zahl nicht enthält
Stellen, die durch 3 teilbar sind, muss „NEIN“ auf dem Bildschirm angezeigt werden.
-1
readln(N);
maxDigit:= N mod 10;
Wann funktioniert es
während N > 0 beginnen
Rechts?
Ziffer:= N mod 10;
wenn Ziffer mod 3 1)=letzte
0, dann ist die Ziffer durch 3 teilbar
wenn Ziffer > maxDigit
dann
2) zuletzt
Zahl kleiner als
maxDigit:= erwünscht
Ziffer;Ergebnis
N:= N div 10;
-1
Ende;
wenn maxDigit = 0 dann writeln("NO")
sonst writeln(maxDigit);
?
K. Yu. Poljakow, 2015
http://kpolyakov.spb.ru
C24: Fehlerkorrektur
VERWENDUNG in der Informatik: 2016 und darüber hinaus…50
Für eine gegebene Sequenz von nicht-negativ
ganze Zahlen, müssen Sie das Maximum finden
Produkt zweier seiner Elemente, deren Zahlen
unterscheiden sich um mindestens 8. Anzahl der Elemente
Sequenz nicht größer als 10000 ist.
Aufgabe A (2 Punkte). O(N2) in der Zeit, O(N) im Speicher.
Aufgabe B (3 Punkte). O(N) in der Zeit, O(N) im Gedächtnis.
Aufgabe B (4 Punkte). O(N) in der Zeit, O(1) im Speicher.
K. Yu. Poljakow, 2015
http://kpolyakov.spb.ru
VERWENDUNG in der Informatik: 2016 und darüber hinaus…
51
S27: schwierige Aufgabe zum Programmieren
Aufgabe A (2 Punkte). Die Daten werden in einem Array gespeichert.
var N: ganze Zahl;
a: Array von ganzen Zahlen;
i, j, max: ganze Zahl;
Start
readln(N);
für i:=1 bis N do read(a[i]);
max:= -1;
für i:= 9 bis N tun
für j:= 1 bis i-8 tun
wenn (a[j]*a[i] > max) dann
max:= a[j]*a[i];
schreiben(max)
Ende.
K. Yu. Poljakow, 2015
http://kpolyakov.spb.ru
C27: schwieriges Programmierproblem
VERWENDUNG in der Informatik: 2016 und darüber hinaus…52
C27: schwieriges Programmierproblem
Aufgabe B (3 Punkte). Daten im Array, O(N)-Zeit.
i-8
ich
ein [ich]
m
akkumulieren!
max a[ j ] a[i] max a[ j ] a[i]
j
j
max:= 0;
m:= 0;
für i:= 9 bis N beginnen
wenn a > m dann m:= a;
wenn m*a[i] > max dann max:= m*a[i];
Ende;
K. Yu. Poljakow, 2015
http://kpolyakov.spb.ru
C27: schwieriges Programmierproblem
VERWENDUNG in der Informatik: 2016 und darüber hinaus…53
C27: schwieriges Programmierproblem
i-8
ich
in einem Array speichern
var a: Array von Integer;
x
Anfängliches Füllen des Arrays:
für i:=1 bis 8 do read(a[i]);
Förderung:
für i:=1 bis 7 tun
a[i]:=a;
a:=x;
K. Yu. Poljakow, 2015
!
Es ist die Warteschlange!
http://kpolyakov.spb.ru
C27: schwieriges Programmierproblem
VERWENDUNG in der Informatik: 2016 und darüber hinaus…54
C27: schwieriges Programmierproblem
Aufgabe B (4 Punkte). Speicher O(1), Zeit O(N).
a
x
konstant d = 8; (Wechsel)
... ( bereits die ersten d Stücke gelesen )
max:= 0;
m:= 0;
für i:=d+1 bis N beginnen
lesen (x);
wenn a > m dann m:= a;
wenn m*x > max dann max:= m*x;
für j:=1 bis d-1 tun
a[j]:= a;
a[d]:= x;
Ende;
K. Yu. Poljakow, 2015
http://kpolyakov.spb.ru
C27: schwieriges Programmierproblem
VERWENDUNG in der Informatik: 2016 und darüber hinaus…55
C27: schwieriges Programmierproblem
Aufgabe B (4 Punkte). Keine Verschiebung (Warteschlangenring).
ich 0
1
2
3
9
1
5
6
7
k
0
a
4
10
2 11
3 12
4 5
8
9
N-1
10 11 12 13 14 15 16 17 18
7
6
7
8
a:=daten[i];
für i:=0 bis d-1 do read(a[i]);
für i:=d bis N-1 beginnen
lesen (x);
k:= ich mod d;
wenn a[k] > m dann m:= a[k];
wenn m*x > max dann max:= m*x;
a[k]:=x;
Ende;
K. Yu. Poljakow, 2015
http://kpolyakov.spb.ru
C27: schwieriges Programmierproblem
VERWENDUNG in der Informatik: 2016 und darüber hinaus…56
C27: schwieriges Programmierproblem
Berechnen Sie das maximale gerade Produkt von zwei
Angaben, zwischen den Zeitpunkten ihrer Übermittlung
mindestens 8 Minuten sind vergangen.
x
Unterstützung
1) das Maximum von allen
2) maximal gleichmäßig
x
sogar sogar * alle
sogar irgendein * sogar
K. Yu. Poljakow, 2015
in einem Array speichern
(drehen)
http://kpolyakov.spb.ru
C27: schwieriges Programmierproblem
VERWENDUNG in der Informatik: 2016 und darüber hinaus…57
C27: schwieriges Programmierproblem
für i:=d bis N-1 beginnen
lesen (x);
k:= ich mod d;
maximal
eben
wenn a[k] > m dann m:= a[k];
wenn ((a[k] mod 2 = 0) und
(a[k] > mEven)) then mEven:= a[k];
wenn x mod 2 = 1 dann beginne
erhalten
seltsam
wenn mEven*x > max dann
max:= mGerade*x;
Ende
erhalten
eben
anders
wenn m*x > max dann max:= m*x;
a[k]:=x;
Ende;
K. Yu. Poljakow, 2015
http://kpolyakov.spb.ru
C27: schwieriges Programmierproblem
VERWENDUNG in der Informatik: 2016 und darüber hinaus…58
Schlussfolgerungen
!
K. Yu. Poljakow, 2015
Variabilität!
http://kpolyakov.spb.ru
Schlussfolgerungen
VERWENDUNG in der Informatik: 2016 und darüber hinaus…59
Ende des Filmes
POLYAKOW Konstantin Jurjewitsch
Doktor der Technischen Wissenschaften, Lehrer für Informatik
GBOU-Sekundarschule Nr. 163, St. Petersburg
K. Yu. Poljakow, 2015
http://kpolyakov.spb.ru
Für Abiturienten. Es muss von denen genommen werden, die am meisten planen, Universitäten zu besuchen vielversprechende Spezialitäten wie Informationssicherheit, Automatisierung und Kontrolle, Nanotechnologie, Systemanalyse und Steuerung, Flugkörpersysteme und Raumfahrt, Kernphysik und Technologie und viele andere.
Kasse allgemeine Informationenüber die Prüfung und beginnen Sie mit der Vorbereitung. Änderungen Im Vergleich zum Vorjahr gibt es in der neuen Version von KIM USE 2019 praktisch keine. Die einzige Sache ist, dass Fragmente von Programmen, die in der Sprache C geschrieben wurden, aus den Aufgaben verschwunden sind: Sie wurden durch Fragmente ersetzt, die in der Sprache C++ geschrieben wurden. Und aus Aufgabe Nummer 25 entfernten sie die Möglichkeit, als Antwort einen Algorithmus in natürlicher Sprache zu schreiben.
Punktzahl BENUTZEN
Um das Einheitliche Staatsexamen in Informatik zu bestehen, reichten im vergangenen Jahr zumindest für die besten Drei 42 Hauptpunkte. Sie wurden zum Beispiel für die richtig gelösten ersten 9 Aufgaben des Tests vergeben.
Wie es 2019 sein wird, ist noch nicht sicher bekannt: Sie müssen auf eine offizielle Anordnung von Rosobrnadzor über die Einhaltung von Primär- und warten Test Ergebnisse. Höchstwahrscheinlich wird es im Dezember erscheinen. Wenn man bedenkt, dass das Maximum primäre Punktzahl für den gesamten Test gleich geblieben, wird sich höchstwahrscheinlich nicht ändern und Mindestpunktzahl. Werfen wir einen Blick auf diese Tabellen:
Teststruktur VERWENDEN
Informatik ist die längste Prüfung (dasselbe gilt für die Prüfung in Mathematik und Literatur), die Dauer beträgt 4 Stunden.
2019 besteht der Test aus zwei Teilen mit 27 Aufgaben.
- Teil 1: 23 Aufgaben (1-23) mit einer kurzen Antwort, die eine Zahl, eine Buchstabenfolge oder Zahlen ist.
- Teil 2: 4 Aufgaben (24–27) mit ausführlicher Lösung, komplette Lösung Aufgaben werden auf dem Antwortbogen 2 festgehalten.
Alle Aufgaben sind auf die eine oder andere Weise mit einem Computer verbunden, aber es ist nicht erlaubt, ihn zu verwenden, um während der Prüfung ein Programm in Gruppe C-Aufgaben zu schreiben. Außerdem erfordern die Aufgaben keine komplexen mathematischen Berechnungen und auch die Verwendung eines Taschenrechners ist nicht erlaubt.
Vorbereitung auf die Prüfung
- Passieren VERWENDEN Sie Tests online kostenlos ohne Registrierung und SMS. Die vorgestellten Tests sind in ihrer Komplexität und Struktur identisch mit den realen Prüfungen, die in den entsprechenden Jahren abgehalten werden.
- Download Demoversionen der Prüfung in Informatik, wodurch Sie sich besser auf die Prüfung vorbereiten und das Bestehen erleichtern können. Alle vorgeschlagenen Tests sind zur Vorbereitung konzipiert und zugelassen VERWENDEN Bundes Institut Pädagogische Messungen(FIPI). In der gleichen FIPI, alles offiziell USE-Optionen.
Die Aufgaben, die Sie sehen werden, werden höchstwahrscheinlich nicht in der Prüfung zu finden sein, aber es wird Aufgaben geben, die den Demoaufgaben ähneln, zum selben Thema oder einfach mit unterschiedlichen Nummern.
Allgemeine USE-Nummern
| Jahr | Mindest. Punktzahl BENUTZEN | Durchschnittsnote | Anzahl der Bewerber | Nicht bestanden, % | Menge 100 Punkte |
Dauer- Prüfungsdauer, min. |
| 2009 | 36 | |||||
| 2010 | 41 | 62,74 | 62 652 | 7,2 | 90 | 240 |
| 2011 | 40 | 59,74 | 51 180 | 9,8 | 31 | 240 |
| 2012 | 40 | 60,3 | 61 453 | 11,1 | 315 | 240 |
| 2013 | 40 | 63,1 | 58 851 | 8,6 | 563 | 240 |
| 2014 | 40 | 57,1 | 235 | |||
| 2015 | 40 | 53,6 | 235 | |||
| 2016 | 40 | 235 | ||||
| 2017 | 40 | 235 | ||||
| 2018 |
