ebSkola

7. tēma / 7.6

7.6 Noslēguma projekts: "Koda lauzējs: AI Efektivitāte"

Stundas uzdevums: Izveidot spēli, kur dators ar binārās meklēšanas stratēģiju uzmin spēlētāja skaitli, pierāda algoritma efektivitāti un pamana pretrunīgas atbildes.

SR 2.4.10. Atkļūdošana un testēšana SR 2.4.13. Pamatkonstrukcijas un datu tipi SR 2.4.16. Saliktas datu struktūras SR 2.4.19. Algoritmu efektivitāte

70 min plāns: Ievads un kritēriju pārruna (~10 min) · 1. uzdevums (~15 min) - uzraksti datora minēšanas robežas · 2. uzdevums (~25 min) - pabeidz binārās meklēšanas AI · 3. uzdevums (~20 min) - saskaiti minējumus un salīdzini ar lineāro. Papildu uzdevumu sāc tikai tad, ja pārējie trīs ir gatavi.

Pirms sāc: šis ir 7. tēmas noslēguma projekts. Šoreiz mini nevis tu, bet dators - tavs uzdevums ir uzrakstīt tā stratēģiju. Noderēs 7.1 stundas binārā meklēšana.

Teorija: kā dators uzvar ar mazāk minējumiem

Lineārā meklēšana pārbauda variantus pēc kārtas: 1, 2, 3, 4... Binārā meklēšana katrā solī atmet pusi no vēl iespējamā diapazona. Tāpēc 100 skaitļu spēlē datoram vajag nevis līdz 100 minējumiem, bet ne vairāk kā 7, ja spēlētājs atbild godīgi.

apaksa = 1
augsa = 100
minejums = (apaksa + augsa) // 2

if atbilde == "lielāks":
    apaksa = minejums + 1
elif atbilde == "mazāks":
    augsa = minejums - 1
Sākums: 1..100
1. minējums: 50
Pēc atbildes paliek tikai puse no variantiem.

Pretruna rodas tad, ja robežas kļūst neiespējamas, piemēram, apakšējā robeža ir lielāka par augšējo. Tas nozīmē, ka iepriekšējās atbildes nevar visas būt patiesas.

Praktiskie uzdevumi

1. uzdevums -

Uzraksti datora minēšanas robežas

Beigās dators nosauks savu pirmo minējumu - tieši diapazona vidu.

  1. Izveido failu koda_lauzejs.py savā krātuvē.
  2. Ieraksti apaksa = 1 un augsa = 100.
  3. Izrēķini minejums = (apaksa + augsa) // 2.
  4. Izdrukā minējumu ar f-string.
  5. Palaid un pārbaudi, vai pirmais minējums ir 50.
  6. Nomaini augsa uz 1000 un pārbaudi jauno pirmo minējumu.

Gatavs, kad: ar diapazonu 1-100 dators sāk ar 50, bet ar 1-1000 - ar 500.

2. uzdevums -

Pabeidz binārās meklēšanas AI

Beigās dators uzminēs tavu skaitli, uzdodot tikai dažus jautājumus.

  1. Uzraksti ciklu while True:.
  2. Izdrukā ciklā datora minējumu un pajautā atbildi.
  3. Nolasi atbildi: lielaks, mazaks vai pareizi.
  4. Pārbīdi apaksa = minejums + 1, ja atbilde ir lielaks.
  5. Pārbīdi augsa = minejums - 1, ja atbilde ir mazaks.
  6. Pārtrauc ciklu ar break, ja atbilde ir pareizi.
  7. Izspēlē vienu partiju, iedomājoties skaitli 73.

Gatavs, kad: dators uzmin skaitli 73, un tu neesi to nekur ierakstījis kodā.

3. uzdevums -

Saskaiti minējumus un salīdzini ar lineāro

Beigās tu skaitļos pierādīsi, kāpēc binārā stratēģija ir labāka.

  1. Pievieno skaitītāju minejumi = 0 un palielini to katrā ciklā.
  2. Izdrukā pēc uzvaras, cik minējumu vajadzēja.
  3. Izspēlē trīs partijas ar dažādiem skaitļiem un pieraksti rezultātus.
  4. Pieraksti, kāds bija lielākais minējumu skaits.
  5. Izrēķini, cik minējumu vajadzētu lineārai stratēģijai sliktākajā gadījumā.
  6. Veic commit ar ziņu Pievieno koda lauzeju un push.
  7. Iesniedz krātuves saiti skolotājam.

Gatavs, kad: nevienā partijā dators nepārsniedz 7 minējumus, kamēr lineārā stratēģija sliktākajā gadījumā prasītu 100.

Papildu uzdevums - Pamani krāpšanos

Ja pamatdarbs ir gatavs, liec datoram pamanīt pretrunīgas atbildes.

  1. Pievieno pārbaudi if apaksa > augsa:.
  2. Izdrukā paziņojumu, ka atbildes ir bijušas pretrunīgas.
  3. Pārtrauc spēli ar break.
  4. Izspēlē partiju, atbildot apzināti nepareizi.
  5. Pārbaudi, ka dators to pamana, nevis griežas mūžīgi.

Gatavs, kad: atbildot pretrunīgi, dators paziņo par krāpšanos, nevis iestrēgst bezgalīgā ciklā.

Biežākās kļūdas (un kā tās labot)

Nodošanas pierādījumi

Snieguma līmeņa apraksts (SLA)

Kritēriji 4-6 (Turpina apgūt) 7-8 (Apguvis) 9-10 (Padziļināti)
Algoritma loģika Dators min skaitļus haotiski vai neizmanto robežu pārbīdi. Precīzi realizēta Binārā meklēšana (diapazona dalīšana uz pusēm). Algoritms ir optimizēts; realizēta pretrunu (krāpšanās) detektēšana.
Efektivitātes analīze Netiek uzskaitīti gājieni vai nav izpratnes par Big O. Gājieni tiek uzskaitīti; izprot O(log n) efektivitāti. README failā sniegta matemātiska analīze par algoritma robežām.
Koda kvalitāte Kods ir vienā failā; trūkst parametru vai komentāru. Kods sadalīts moduļos. Funkcijas saņem un atgriež datus. Pilnīga modularitāte; profesionāls PEP 8 stils un docstrings.

Koda paraugs: Binārā dzinēja sākums

# Failā engine.py
def aprekinat_minejumu(apaksa, augsa):
    """Aprēķina viduspunktu binārajai meklēšanai."""
    return (apaksa + augsa) // 2

# Failā main.py
from engine import aprekinat_minejumu

min_r, max_r = 1, 100
gajieni = 0

while min_r <= max_r:
    minejums = aprekinat_minejumu(min_r, max_r)
    gajieni += 1
    
    atbilde = input(f"Vai Tavs skaitlis ir {minejums}? (L/M/U): ").lower()
    
    if atbilde == 'u':
        print(f"Uzvara {gajieni} gājienos!")
        break
    # ... tālāk seko robežu pārbīdes loģika
Sistēmas statuss: Kalibrēts
Teorētiskā sarežģītība: O(log n)
Maksimums 100 skaitļiem: 7 mēģinājumi