ingångKonceptet med algoritmens exekutor av algoritmen är exekutorns språk. B6
Konceptet med en algoritm. Algoritmexekutorer. Algoritmegenskaper
Begreppet en algoritm är lika grundläggande för datavetenskap som begreppet information. Det finns många olika definitioner av en algoritm, eftersom detta begrepp är ganska brett och används inom olika områden inom vetenskap, teknik och vardagsliv.
Algoritm är en begriplig och exakt sekvens av åtgärder som beskriver processen att omvandla ett objekt från ett initialt tillstånd till ett slutligt tillstånd.
En algoritm är en exakt beskrivning av en sekvens av åtgärder som syftar till att lösa ett givet problem, avsedd för en specifik utförare.
Artist Algoritmen kan vara antingen en person (recept, olika instruktioner, algoritmer för matematiska beräkningar) eller en teknisk anordning. Olika maskiner (datorer, industrirobotar, moderna hushållsapparater). formella artister algoritmer. Den formella exekutorn behöver inte förstå kärnan i problemet som ska lösas, men den exakta exekveringen av sekvensen av kommandon krävs.
Algoritmen kan skrivas olika sätt(verbal beskrivning, grafisk beskrivning - blockschema, program på något av programmeringsspråken etc.). Ett program är en algoritm inskriven iprogrammeringsspråk .
För att skapa en algoritm (program) behöver du veta:
en komplett uppsättning initiala data om problemet (objektets initiala tillstånd);
syftet med att skapa algoritmen (objektets slutliga tillstånd);
utförarens kommandosystem (det vill säga en uppsättning kommandon som utföraren förstår och kan utföra).
Den resulterande algoritmen (programmet) måste ha följande uppsättning egenskaper:
diskrethet (algoritmen är uppdelad i separata steg - kommandon);
entydighet (varje lag bestämmer den enda möjlig åtgärd artist);
begriplighet (alla kommandon i algoritmen ingår i utförarens kommandosystem);
effektivitet (utövaren måste lösa problemet i ett begränsat antal steg).
De flesta av algoritmerna har också egenskapen masskaraktär (med samma algoritm kan många liknande problem lösas).
Metoder för att beskriva algoritmer
Det noterades ovan att samma algoritm kan skrivas på olika sätt. Algoritm kan skrivas naturligt språk. Som sådan använder vi recept, instruktioner etc. För inspelningsalgoritmer avsedda för formella artister, special programmeringsspråk... Vilken algoritm som helst kan beskrivas grafiskt i form av ett blockschema... För detta har ett speciellt notationssystem utvecklats:
|
Beteckning |
Beskrivning |
Anteckningar (redigera) |
|
Algoritm start och slut | ||
|
|
Datainmatning och -utgång. |
Datautmatning hänvisas ibland till på olika sätt:
|
|
|
Handling |
I beräkningsalgoritmer är detta uppdraget |
|
|
Gaffel |
Gaffel - en komponent som krävs för att implementera grenar och slingor |
|
|
Cykelstart med parameter | |
|
|
Typisk process |
I programmering, procedurer eller subrutiner |
|
|
Övergångar mellan block |
Låt oss ge ett exempel på att beskriva en algoritm för att summera två kvantiteter i form av ett blockdiagram:
Detta sätt att beskriva algoritmen är det mest grafiska och begripliga för människor. Därför algoritmerna formella artister vanligtvis utvecklas de först i form av ett blockschema, och först sedan skapar de ett program på en av deprogrammeringsspråk .
Typiska algoritmiska strukturer
Programmeraren har förmågan att designa och använda atypiska algoritmiska strukturer, men detta är inte nödvändigt. Vilken godtyckligt komplex algoritm som helst kan utvecklas på basis av tre typiska strukturer: succession, förgrening och upprepning. I detta fall kan strukturerna arrangeras sekventiellt efter varandra eller kapslade in i varandra.
Linjär struktur (följ)
Den enklaste algoritmiska strukturen är linjär. I den utförs alla operationer en gång i den ordning som de är skrivna.
Förgrening
V full förgrening det finns två alternativ för utförarens handlingar, beroende på värdet av det logiska uttrycket (villkoret). Om villkoret är sant, kommer endast den första grenen att exekveras, annars kommer endast den andra grenen att exekveras.
Den andra grenen kan vara tom. Denna struktur kallas ofullständig förgrening eller traversering.
Från flera grenar är det möjligt att konstruera strukturen " val"(Multiple branching), som inte kommer att välja mellan två, utan från ett större antal alternativ för utförarens handlingar, beroende på flera villkor. Det är viktigt att endast en gren utförs - i en sådan struktur blir ordningen på villkoren viktig: om flera villkor är uppfyllda, kommer bara en av dem att fungera - den första från ovan.
Cykel (upprepning)
Cykellåter dig organisera flera upprepningar av samma sekvens av kommandon- det kallas cykelns kropp. I olika typer av looping-algoritmer kan antalet repetitioner bero på värdet av ett logiskt uttryck (villkor) eller kan hårdkodas i själva strukturen. Det finns cykler: " innan», « medan», cyklar med en räknare. I loopar "före" och "medan" kan ett logiskt uttryck (villkor) föregå slingans kropp ( förutsättningsslinga) eller avsluta loopen ( aftercondition loop).
Cyklar« innan"- upprepning av cykelkroppen tills villkoret är uppfyllt:
Cyklar « medan"- upprepning av cykelkroppen medan villkoret är uppfyllt(Sann):
Motslingor(med parameter)- upprepning av slingkroppen ett givet antal gånger:
Hjälpalgoritm (subrutin, procedur)
Hjälpalgoritm är en modul som kan nås flera gånger från huvudalgoritmen. Användningen av hjälpalgoritmer kan avsevärt minska storleken på algoritmen och förenkla dess utveckling.
Metoder för att utveckla komplexa algoritmer
Det finns två metoder för att utveckla komplexa algoritmer:
Metod för sekventiell uppgiftsbeskrivning("Top-down") är att det ursprungliga komplexa problemet är uppdelat i deluppgifter. Vart och ett av delproblemen beaktas och löses separat. Om någon av deluppgifterna är svåra, delas de också upp i deluppgifter. Processen fortsätter tills deluppgifterna reduceras till elementära. Lösningarna av individuella delproblem samlas sedan i en enda algoritm för att lösa det ursprungliga problemet. Metoden används flitigt eftersom den tillåter flera programmerare att samtidigt utveckla en generell algoritm som löser lokala deluppgifter. Detta är en förutsättning för snabb utveckling av mjukvaruprodukter.
Monteringsmetod("Bottom-up") är att skapa en uppsättning programvarumoduler som implementerar lösningen av typiska uppgifter. När man löser ett komplext problem kan programmeraren använda de utvecklade modulerna som hjälpalgoritmer (procedurer). I många programmeringssystem Det finns redan liknande uppsättningar av moduler, vilket avsevärt förenklar och påskyndar skapandet av en komplex algoritm.
Styralgoritmer och processer
Kontrollera - målmedveten interaktion av objekt, varav några är kontroll, andra är kontrollerade.
I det enklaste fallet finns det två sådana objekt:
Ur datavetenskaplig synvinkel kontrollåtgärder kan betraktas som kontrollinformation. Information kan överföras i form av kommandon. Sekvensen av kommandon för att kontrollera objektet, som leder till ett förutbestämt mål, kallas kontrollalgoritm... Följaktligen kan kontrollobjektet kallas exekutor för kontrollalgoritmen. I exemplet ovan fungerar kontrollobjektet "utan att titta" på vad som händer med kontrollobjektet ( kontroll utan respons öppen... Ett annat kontrollschema kan ta hänsyn till information om processerna som sker i kontrollobjektet:
I det här fallet måste kontrollalgoritmen vara tillräckligt flexibel för att analysera denna information och fatta beslut om dess ytterligare åtgärder beroende på kontrollobjektets tillstånd ( återkopplingskontroll). Detta kontrollschema kallas stängd.
Mer i detalj studeras styrprocesserna. cybernetik... Denna vetenskap hävdar att de mest olika förvaltningsprocesserna i samhället, naturen och tekniken sker på ett liknande sätt, lyder samma principer.
Till början av ämnet
Stäng av AdBlock på den här webbplatsen.
I den här lektionen kommer vi att analysera några av de teoretiska begrepp som formaliserar begreppet programmering. Samtidigt kommer vi att mer exakt formulera huvuduppgiften för din träning.
Till att börja med föreslår jag att du leker lite med följande barnleksak. Gör de första fem uppgifterna, gå tillbaka och fortsätt läsa lektionen.
Fig. 1 Skärmbild av spelplanen på code.org
Hoppas du lyckas. Nu, med hjälp av detta exempel, kommer vi att beskriva flera grundläggande begrepp:
- testamentsexekutor;
- system av exekveringskommandon;
- algoritm.
I leksaken styr vi en röd fågel. Uppgiften för varje steg: att få fågeln till grisen. Fågeln kan utföra vissa kommandon, till exempel: gå framåt, sväng vänster, sväng höger, etc.
En person, maskin eller enhet som kan utföra vissa kommandon kallas en exekutor. I den här leksaken är uppenbarligen artisten en fågel. Den uppsättning kommandon som utföraren förstår och vet hur man utför kallas utförarens kommandosystem.
Sekvensen av kommandon som executorn måste utföra för att lösa problemet kallas en algoritm.
Det är nödvändigt att fokusera på flera punkter.
Utövaren kan endast utföra de kommandon som ingår i hans kommandosystem.
Det betyder till exempel att du inte kan skriva till fågelartist: "Gå till grisen!" Mer exakt kan du skriva ner, men ingenting kommer att hända, tk. utföraren av sådana kommandon vet inte.
Du kan skriva de befintliga kommandona i vilken ordning du tycker är korrekt. Din uppgift som programmerare är att dela upp en stor komplex uppgift i små separata steg, som vart och ett kommer att vara tydligt för utföraren. Dela och härska fungerar igen.
Utövaren gör exakt vad algoritmen instruerar honom att göra.
Fågelartisten är mycket förtroendefull. Det ifrågasätter inte vad du skriver i programmet. Om du till exempel glömmer att vika ut fågeln kommer den att krascha in i väggen. Därför måste du sköta allt själv.
Dina framtida program kommer ofta inte att fungera som du tänkt dig. Misstag händer alla. Det är viktigt att förstå att detta inte är en dåre av datorn, men du gjorde ett misstag i algoritmen. Var inte som dåliga programmerare som alltid har programmet att skylla på.
Låt oss nu, från ett illustrativt exempel, gå vidare till datorverkligheten. Vi skriver program för en dator, vilket innebär att datorn i vårt fall är en exekutör. Kommandosystem - standardfunktioner och konstruktioner av C-språket.
Vilken är huvuduppgiften för din undervisning i grunderna i programmering? Bemästra skickligheten i algoritmiskt tänkande. Det vill säga, lär dig hur du skriver ner lösningen på olika problem i form av en algoritm för en specifik utförare (i vårt fall en dator).
Så, för att sammanfatta:
Datorprogram- en algoritm för att lösa ett problem, skriven på ett programmeringsspråk.
Algoritm - en exakt beskrivning av ordningen på åtgärder som måste utföras av utföraren för att lösa problemet.
Executor - en person eller någon enhet som kan förstå och utföra en viss uppsättning kommandon.
Teoretisk bakgrund
Algoritm - en beskrivning av en sekvens av åtgärder (plan), vars strikta genomförande leder till lösningen av problemet i ett begränsat antal steg.
Algoritmegenskaper:
1. Diskrethet (algoritmen bör bestå av specifika åtgärder som följer i en specifik ordning);
2. Determinism (alla åtgärder måste vara strikt och otvetydigt definierade i varje enskilt fall);
3. Finitet (varje åtgärd och algoritmen som helhet måste kunna slutföras);
4. Massivitet (samma algoritm kan användas med olika indata);
5. Effektivitet (inga fel, algoritmen bör leda till rätt resultat för alla giltiga ingångsvärden).
Algoritmtyper:
1. Linjär algoritm (beskrivning av åtgärder som utförs en gång i en given ordning);
2. Cyklisk algoritm (beskrivning av åtgärder som måste upprepas ett visst antal gånger eller tills uppgiften är slutförd);
3. En grenalgoritm (en algoritm där, beroende på tillståndet, antingen den ena eller den andra sekvensen av åtgärder utförs)
Exempel på problemlösning
Konstnär Ritaren rör sig på koordinatplanet och lämnar ett spår i form av en linje. Ritaren kan utföra kommandot Flytta till (a, b)(där a, b är heltal), vilket flyttar ritaren från punkten med koordinater (x, y) till punkten med koordinater (x + a, y + b). Om siffrorna a, b är positiva, ökas värdet på motsvarande koordinat; om det är negativt minskar det.
Till exempel, om ritaren är vid punkten med koordinaterna (9, 5), då kommandot Byta till
(1, -2) kommer att flytta föredraganden till punkt (10, 3).
Upprepa k gånger
Lag1 Lag2 Lag3
Slutet
betyder att sekvensen av kommandon Lag1 Lag2 Lag3 kommer att upprepas k gånger. Ritaren fick följande algoritm för utförande:
Upprepa 3 gånger
Flytta med (-2, -3) Flytta med (3, 2) Flytta med (-4, 0)
Slutet
Vilket kommando kan denna algoritm ersättas med så att ritaren är på samma punkt som efter exekveringen av algoritmen?
1) Flytta med (-9, -3)
2) Flytta med (-3, 9)
3) Flytta med (-3, -1)
4) Flytta till (9, 3)
Lösning:
Denna uppgift görs bäst sekventiellt.
I en slinga utför ritaren en sekvens av kommandon
- Flytta med (-2, -3)
- Flytta förbi (3, 2)
- Flytta med (-4, 0),
som kan ersättas med ett kommando Flytta med (-2 + 3-4, -3 + 2 + 0), d.v.s. Flytta förbi (-3, -1).
Eftersom cykeln upprepas 3 gånger kommer det mottagna kommandot Flytta med (-3, -1) att utföras 3 gånger. Detta innebär att cykeln kan ersättas med kommandot Flytta till (-3 * 3, -1 * 3), d.v.s. Flytta förbi (-9, -3). Således får vi kommandot Move by (-9, -3) som du kan byta ut hela algoritmen till.
Utbildningsuppgifter
1. Konstnär Ritaren rör sig på koordinatplanet och lämnar ett spår i form av en linje. Ritaren kan utföra kommandot Flytta till (a, b)(där a, b är heltal) flyttar ritaren från punkten med koordinaterna (x, y) till punkten med koordinaterna (x + a, y + b). Om siffrorna a, b är positiva, ökas värdet på motsvarande koordinat; om negativ, minskar.
Till exempel, om ritaren är vid en punkt med koordinater (4, 2), kommer kommandot Flytta med (2, −3) att flytta ritaren till punkten (6, −1).
Upprepa k gånger
Lag1 Lag2 Lag3
Slutet
betyder att sekvensen av kommandon Lag1 Lag2 Lag3 kommer att upprepas k en gång.
Ritaren fick följande algoritm för utförande:
Upprepa 2 gånger
Flytta med (−6, −4)
Efter att ha kört denna algoritm återvände ritaren till startpunkten. Vilket kommando ska sättas istället för kommandot Lag 1?
1) Flytta med (−2, −1)
2) Flytta till (1, 1)
3) Flytta med (−4, −2)
4) Flytta till (2, 1)
2. Flytta till (a, b)
Till exempel, om ritaren är vid en punkt med koordinater (4, 2), kommer kommandot Flytta med (2, −3) att flytta ritaren till punkten (6, −1).
Upprepa k gånger
Lag1 Lag2 Lag3
Slutet
Lag1 Lag2 Lag3 kommer att upprepas k en gång.
Upprepa 4 gånger
Kommando1 Flytta med (3, 3) Flytta med (1, −2) Avsluta
Flytta förbi (−8, 12)
Lag 1?
1) Flytta med (−2, −4)
2) Flytta med (4, −13)
3) Flytta till (2, 4)
4) Flytta med (−8, −16)
3. Konstnär Ritaren rör sig på koordinatplanet och lämnar ett spår i form av en linje. Ritaren kan utföra kommandot Flytta till (a, b)(där a, b är heltal) flyttar ritaren från punkten med koordinaterna (x, y) till punkten med koordinaterna (x + a, y + b). Om siffrorna a, b är positiva, ökas värdet på motsvarande koordinat; om negativ, minskar.
Upprepa k gånger
Lag1 Lag2 Lag3
Slutet
betyder att sekvensen av kommandon Lag1 Lag2 Lag3 kommer att upprepas k en gång.
Ritaren fick följande algoritm för utförande:
Upprepa 3 gånger
Flytta förbi (3, 9)
Efter att ha kört denna algoritm återvände ritaren till startpunkten. Vilket kommando ska sättas istället för kommandot Lag 1?
1) Flytta till (3, 4)
2) Flytta med (−5, −10)
3) Flytta med (−9, −12)
4) Flytta med (−3, −4)
4. Konstnär Ritaren rör sig på koordinatplanet och lämnar ett spår i form av en linje. Ritaren kan utföra kommandot Flytta till (a, b)(där a, b är heltal) flyttar ritaren från punkten med koordinaterna (x, y) till punkten med koordinaterna (x + a, y + b). Om siffrorna a, b är positiva, ökas värdet på motsvarande koordinat; om negativ, minskar.
Till exempel, om ritaren är vid en punkt med koordinater (4, 2), kommer kommandot Flytta med (2, −3) att flytta ritaren till punkten (6, −1).
Upprepa k gånger
Lag1 Lag2 Lag3
Slutet
betyder att sekvensen av kommandon Lag1 Lag2 Lag3 kommer att upprepas k en gång.
Ritaren fick följande algoritm för utförande:
Upprepa 3 gånger
Kommando1 Flytta till (3, 2) Flytta till (2, 1) Avsluta
Flytta med (−9, −6)
Efter att ha kört denna algoritm återvände ritaren till startpunkten. Vilket kommando ska sättas istället för kommandot Lag 1?
1) Flytta med (−6, −3)
2) Flytta till (4, 3)
3) Flytta med (−2, −1)
4) Flytta till (2, 1)
5. Konstnär Ritaren rör sig på koordinatplanet och lämnar ett spår i form av en linje. Ritaren kan utföra kommandot Flytta till (a, b)(där a, b är heltal) flyttar ritaren från punkten med koordinaterna (x, y) till punkten med koordinaterna (x + a, y + b). Om siffrorna a, b är positiva, ökas värdet på motsvarande koordinat; om negativ, minskar.
Upprepa k gånger
Lag1 Lag2 Lag3
Slutet
betyder att sekvensen av kommandon Lag1 Lag2 Lag3 kommer att upprepas k en gång.
Ritaren fick följande algoritm för utförande:
Upprepa 2 gånger
Kommando1 Flytta med (3, 3) Flytta med (1, −2) Avsluta
Flytta med (4, −6)
Efter att ha kört denna algoritm återvände ritaren till startpunkten. Vilket kommando ska sättas istället för kommandot Lag 1?
1) Flytta med (6, −2)
2) Flytta med (−8, 5)
3) Flytta med (−12, 4)
4) Flytta med (−6, 2)
6. Konstnär Ritaren rör sig på koordinatplanet och lämnar ett spår i form av en linje. Ritaren kan utföra kommandot Flytta till (a, b)(där a, b är heltal) flyttar ritaren från punkten med koordinaterna (x, y) till punkten med koordinaterna (x + a, y + b). Om siffrorna a, b är positiva, ökas värdet på motsvarande koordinat; om negativ, minskar.
Till exempel, om ritaren är vid en punkt med koordinater (4, 2), kommer kommandot Flytta med (2, −3) att flytta ritaren till punkten (6, −1).
Upprepa k gånger
Lag1 Lag2 Lag3
Slutet
betyder att sekvensen av kommandon Lag1 Lag2 Lag3 kommer att upprepas k en gång.
Ritaren fick följande algoritm för utförande:
Upprepa 4 gånger
Kommando1 Flytta med (1, 3) Flytta med (1, −2) Avsluta
Flytta med (−4, −12)
Efter att ha kört denna algoritm återvände ritaren till startpunkten. Vilket kommando ska sättas istället för kommandot Lag 1?
1) Flytta med (1, −2)
2) Flytta till (12, 4)
3) Flytta till (2, 11)
4) Flytta med (−1, 2)
7. Konstnär Ritaren rör sig på koordinatplanet och lämnar ett spår i form av en linje. Ritaren kan utföra kommandot Flytta till (a, b)(där a, b är heltal) flyttar ritaren från punkten med koordinaterna (x, y) till punkten med koordinaterna (x + a, y + b). Om siffrorna a, b är positiva, ökas värdet på motsvarande koordinat; om negativ, minskar.
Till exempel, om ritaren är vid en punkt med koordinater (4, 2), kommer kommandot Flytta med (2, −3) att flytta ritaren till punkten (6, −1).
Upprepa k gånger
Lag1 Lag2 Lag3
Slutet
betyder att sekvensen av kommandon Lag1 Lag2 Lag3 kommer att upprepas k en gång.
Ritaren fick följande algoritm för utförande:
Upprepa 4 gånger
Kommando1 Flytta till (3, 2) Flytta till (2, 1) Avsluta
Flytta med (−12, −8)
Efter att ha kört denna algoritm återvände ritaren till startpunkten. Vilket kommando ska sättas istället för kommandot Lag 1?
1) Flytta med (−8, −4)
2) Flytta med (−2, −1)
3) Flytta till (7, 5)
4) Flytta till (2, 1)
8. Framåt n Rätt m
Upprepa 9 [framåt 50 höger 60]
1) vanlig hexagon
2) vanlig triangel
3) öppen polylinje
4) vanlig hexagon
9. Artist En sköldpadda rör sig på datorskärmen och lämnar ett spår i form av en linje. Vid varje givet ögonblick är artistens position och riktningen för hans rörelse kända. Exekutorn har två kommandon: Framåt n(där n är ett heltal) som får sköldpaddan att röra sig n steg i rörelseriktningen; Rätt m(där m är ett heltal), vilket orsakar en förändring av rörelseriktningen med m grader medurs. Inspelning Upprepa k [Kommando1 Kommando2 Kommando3] betyder att sekvensen av kommandon inom parentes kommer att upprepas k gånger.
Sköldpaddan fick följande algoritm för utförande: Upprepa 7 [framåt 70 höger 120]... Vilken form kommer att visas på skärmen?
1) vanlig hexagon
2) öppen polylinje
3) vanlig heptagon
4) vanlig triangel
10. Artist En sköldpadda rör sig på datorskärmen och lämnar ett spår i form av en linje. Vid varje givet ögonblick är artistens position och riktningen för hans rörelse kända. Exekutorn har två kommandon: Framåt n(där n är ett heltal) som får sköldpaddan att röra sig n steg i rörelseriktningen; Rätt m(där m är ett heltal), vilket orsakar en förändring av rörelseriktningen med m grader medurs. Inspelning Upprepa k [Kommando1 Kommando2 Kommando3] betyder att sekvensen av kommandon inom parentes kommer att upprepas k gånger.
Sköldpaddan fick följande algoritm för utförande: Upprepa 9 [framåt 70 höger 90]... Vilken form kommer att visas på skärmen?
2) vanlig hexagon
3) vanlig oktagon
4) regelbunden fyrhörning
11. Artist En sköldpadda rör sig på datorskärmen och lämnar ett spår i form av en linje. Vid varje givet ögonblick är artistens position och riktningen för hans rörelse kända. Exekutorn har två kommandon: Framåt n(där n är ett heltal) som får sköldpaddan att röra sig n steg i rörelseriktningen; Rätt m(där m är ett heltal), vilket orsakar en förändring av rörelseriktningen med m grader medurs. Inspelning Upprepa k [Kommando1 Kommando2 Kommando3] betyder att sekvensen av kommandon inom parentes kommer att upprepas k gånger.
Sköldpaddan fick följande algoritm för utförande: Upprepa 5 [framåt 80 höger 60]... Vilken form kommer att visas på skärmen?
1) vanlig femkant
2) vanlig triangel
3) vanlig hexagon
4) öppen polylinje
12. Artist En sköldpadda rör sig på datorskärmen och lämnar ett spår i form av en linje. Vid varje givet ögonblick är artistens position och riktningen för hans rörelse kända. Exekutorn har två kommandon: Framåt n(där n är ett heltal) som får sköldpaddan att röra sig n steg i rörelseriktningen; Rätt m(där m är ett heltal), vilket orsakar en förändring av rörelseriktningen med m grader medurs. Inspelning Upprepa k [Kommando1 Kommando2 Kommando3] betyder att sekvensen av kommandon inom parentes kommer att upprepas k gånger.
Sköldpaddan fick följande algoritm för utförande: Upprepa 5 [framåt 80 höger 90]... Vilken form kommer att visas på skärmen?
1) öppen polylinje
2) vanlig hexagon
3) vanlig femhörning
4) regelbunden fyrhörning
Teoretisk bakgrund
Exempel på problemlösning
Utbildningsuppgifter
Teoretisk bakgrund
Exempel på problemlösning
Utbildningsuppgifter
Teoretisk bakgrund
Exempel på problemlösning
Utbildningsuppgifter
Teoretisk bakgrund
Exempel på problemlösning
Utbildningsuppgifter
Teoretisk bakgrund
Exempel på problemlösning
Utbildningsuppgifter
Teoretisk bakgrund
Exempel på problemlösning
Utbildningsuppgifter
Teoretisk bakgrund
Exempel på problemlösning
Utbildningsuppgifter
Teoretisk bakgrund
Exempel på problemlösning
Utbildningsuppgifter
Teoretisk bakgrund
Exempel på problemlösning
Utbildningsuppgifter
>> Algoritmtyper
I algoritmer skrivs kommandon efter varandra i en viss ordning. De exekveras inte nödvändigtvis i den inspelade sekvensen: beroende på i vilken ordning kommandona exekveras kan tre typer av algoritmer särskiljas:
Linjära algoritmer;
grenalgoritmer;
algoritmer med upprepningar.
Linjära algoritmer
I vilka kommandon som exekveras i den ordning de skrivs, det vill säga sekventiellt efter varandra, kallas linjär.
Till exempel är följande trädplanteringsalgoritm linjär:
1) gräva ett hål i marken;
2) sänk ner plantan i hålet;
3) fyll hålet med plantan med jord;
4) vattna plantan med vatten.
Med hjälp av ett blockschema kan denna algoritm avbildas enligt följande:
Förgreningsalgoritmer
Situationer där sekvensen av nödvändiga åtgärder är känd i förväg är extremt sällsynta. I livet måste man ofta ta ett beslut beroende på den rådande situationen. Om det regnar tar vi ett paraply och tar på oss en regnrock; om det är varmt, bär lätta kläder. Det finns också mer komplexa urvalsvillkor. I vissa fall beror en persons öde på det valda beslutet.
Beslutslogiken kan beskrivas på följande sätt:
OM<условие>SEDAN<действия 1>ANNAT<действия 2>
Exempel:
Om du vill vara friska, DÅ humör, ANNARS ligga på soffan hela dagen;
OM svalorna flyger lågt, DÅ kommer det att regna, ANNARS kommer det inte att regna;
OM lärdomarna är lärda, gå DÅ ut på en promenad, ANNARS lär du dig.
I vissa fall<действия 2>kan vara frånvarande;
OM<условие>SEDAN<действия 1>
Exempel:
OM han kallade sig en last, så klättra in i ryggen.
En form av organisering av handlingar där, beroende på uppfyllandet av ett visst villkor, det ena eller det andra utförs efterföljande steg kallas förgrening.
Låt oss i form av ett flödesschema skildra handlingssekvensen för en elev i 6:e klass Vasya Mukhin, som han föreställer sig enligt följande: "Om Pavlik är hemma kommer vi att lösa matematiska problem. Annars bör vi ringa Marina och förbereda en biologirapport tillsammans. Om Marina inte är hemma, då måste du sätta dig ner och skriva."
Och så, med hjälp av blockdiagrammet, kan du mycket tydligt representera resonemanget när du löser följande problem.
Av tre mynt av samma valör är ett falskt (lättare). Hur hittar man det med en vägning på en våg utan vikter?
Upprepningsalgoritmer
I praktiken finns det ofta uppgifter där en eller flera handlingar behöver upprepas flera gånger, samtidigt som ett visst förutbestämt villkor är uppfyllt.
Algoritm som innehåller cykler, kallas en round robin eller repetitiv algoritm.
En situation där exekveringen av en loop aldrig tar slut kallas en ändlös loop. Algoritmer bör utvecklas för att undvika sådana situationer.
Låt oss titta på ett exempel från matematik.
Ett naturligt tal kallas primtal om det bara har två delare: en och själva talet1.
2, 3, 5, 7 - primtal; 4, 6, 8 - nej. På 300-talet f.Kr. föreslog den grekiske matematikern Eratosthenes följande algoritm för att hitta alla primtal mindre än ett givet tal n:
1) skriv ut alla naturliga tal från 1 till n;
2) ta bort 1;
3) stryk under det minsta av de omarkerade siffrorna;
4) stryk över alla tal som är multipler av de understrukna i föregående steg;
5) om listan innehåller omarkerade nummer, gå till steg 3, annars är alla understrukna tal primtal.
Detta är en cyklisk algoritm. När den är utförd upprepas steg 3-5 tills det finns omarkerade nummer i den ursprungliga listan.
Så här ser ett flödesschema över en skolbarns handlingar ut, som bör göras innan en kvällspromenad läxa matematik:
Kom ihåg att talet 1 varken är ett sammansatt tal (som har fler än två delare) eller ett primtal.
Det viktigaste
Tre typer av algoritmer kan särskiljas beroende på ordningen för utförande av kommandot:
> linjära algoritmer;
> grenalgoritmer;
> upprepningsalgoritmer.
En algoritm där kommandon exekveras i den ordning de skrivs, det vill säga sekventiellt efter varandra, kallas linjär.
Den form av organiserande åtgärder, där, beroende på uppfyllandet av ett visst villkor, den ena eller andra sekvensen av steg utförs kallas förgrening.
Den form av organiserande åtgärder där exekveringen av samma sekvens av kommandon upprepas så länge som något förutbestämt villkor är uppfyllt kallas en cykel (upprepning).
Frågor och uppgifter
1. Vilka algoritmer kallas linjära?
2. Ge ett exempel på en linjär algoritm,
3. Utföraren "Calculator" kan endast utföra två kommandon: multiplicera med 2 och addera. Kom på den kortaste planen för att få talet 50 av O.
4. Vilken form av organisation av aktioner kallas förgrening?
5. Vilka villkor måste hjältinnan i berättelsen "Gäss-svanar" uppfylla?
6. Ge ett exempel på en algoritm som innehåller förgrening "
7. Läs ett utdrag ur dikten av J. Rodari "Vad luktar hantverket?":
Varje fodral har en speciell lukt:
Bageriet luktar deg och bakverk.
Du går förbi snickeriet -
Luktar spån och fräsch bräda.
Målaren luktar terpentin och färg.
Glasmästaren luktar fönsterspackel.
Chaufförens jacka luktar bensin
Arbetarblus - maskinolja.
Omformuleraom yrken som använder orden "OM ... DÅ" /
8. Kom ihåg vilka hjältar ryska folksagor gör val som avgör deras öde.
9. Av 9 mynt av samma valör är ett falskt (lättare). Hur många vägningar på en våg utan vikter kan du bestämma?
10. Vilken form av organisering av handlingar kallas upprepning?
11. Ge ett exempel på en algoritm som innehåller upprepning.
12. I vilka litterära verk som du känner till äger en cyklisk form av organisering av handlingar rum?
13. Var kommer artisten som fullbordade nästa grupp av lag 16 gånger i rad?
gå 10 meter framåt
rotera 90° medurs
14. Vilken grupp av åtgärder och hur många gånger bör upprepas när man löser nästa problem?
Fyrtio soldater närmade sig floden, längs vilken två pojkar åker i en båt. Hur kan soldaterna gå över till andra sidan, om båten bara kan ta emot en soldat eller två pojkar, men soldaten och pojken inte längre kan ta emot?
15. Kom ihåg problemet med en miniräknare som bara kan multiplicera med 2 och lägga till 1. Det blir mycket lättare att utveckla rationella algoritmer för det om du använder följande blockdiagram:
Använd detta flödesschema och utveckla rationella algoritmer för att erhålla siffrorna 1024 och 500 från siffran 0.
Bosova L. L. Informatik: Lärobok för årskurs 6 / L. L. Bosova. - 3:e uppl., Rev. och lägg till. - M .: BINOM. Kunskapslaboratoriet, 2005. - 208 s .: ill.
Lektionens innehåll lektionsöversikt och stödram lektionspresentation interaktiva tekniker accelerativa undervisningsmetoder Öva tester, testuppgifter online och övningar läxworkshops och träningsfrågor för klassdiskussion Illustrationer video- och ljudmaterial foton, bilder, grafik, tabeller, diagram serier, liknelser, talesätt, korsord, anekdoter, skämt, citat Kosttillskott abstracts cheat sheets chips för de nyfikna artiklarna (MAN) litteratur grundläggande och ytterligare ordförråd av termer Förbättra läroböcker och lektioner korrigering av fel i läroboken, ersättning av föråldrade kunskaper med nya Endast för lärare kalenderplaner lärande program riktlinjer