Kreu simplajn algoritmojn

Kiel “dezajni” algoritmon?

Plej ofte algoritmoj estas desegnitaj iteracie. Kion tio signifas?

1. ✅ Unue disĵetu la problemon en pli malgrandajn partojn.

• Unue pensu pri la plej grava afero, kiun vi bezonas por ke la algoritmo funkciu
  • Ĉu ĝi devas redoni valoron? Ĉu boolean-on? Ĉu liston?
  • Ĉu mi bezonas iujn helpajn funkciojn?

2. ❓ Ĉu ekzistas iuj “ekstremaj kazoj”?

• Kio okazas se vi enmetas malplenan liston aŭ tekston?

3. ✅ Komencu per simple provi krei solvon

4. ✅ Kontrolu ĉu la algoritmo funkcias bone en la ekzekutotempo

• Provu pli grandan eniron, ĉu ĝi daŭras longan tempon?

5. ❓ Konsideru vian solvon, ĉu vi bezonas ĉiujn paŝojn, kiujn vi uzis?

• Ĉu ĉiuj if-kontrolaj estas necesaj?
• Se vi havas pli ol unu for-ciklo, ĉu ekzistas klaraj manieroj fari tion al unu for-ciklo?
  • Tio estas malsama se vi havas nestigitajn ciklojn aŭ ciklojn post unu la alian. Post unu la alian ofte eblas eviti.

6. ✅ Konsideru ekstremajn scenarojn kun eniroj:

• Ekzemplo kun nombroj: grandaj nombroj, malgrandaj nombroj, negativaj nombroj
• Tekstekzemplo: multe da teksto, multaj malgrandaj vortoj, ekstra spacoj, grandaj kaj malgrandaj literoj.

7. ❓ Ĉu estas utile uzi pseŭdo-kodon por pli bone kompreni la logikon?

Tasko 1 - Trovi ĉu listo enhavas donitan numeron

Kreu algoritmon (funkcion) kiu trovas ĉu listo enhavas donitan numeron. Ĝi devas returni True aŭ False bazite ĉu la nombro ekzistas en la listo aŭ ne.

Jen listo kun testaj datumoj:

def exists_in_list(the_list, check):
    for number in the_list:
        if number == check:
            return True
    return False

Tasko 2 - Sumigado

Kreu algoritmon kiu sumigas liston de nombroj.

def sum_list(numbers):
    total = 0
    for num in numbers:
        total += num
    return total

Tasko 3a - Maksimumo en Listo

Kreu algoritmon kiu trovas la plej grandan valoron en listo.

def find_max(numbers):
    largest = numbers[0]
    for num in numbers:
        if num > largest:
            largest = num

    return largest

Tasko 3b - Se la listo estas malplena?

Aldonu kontrolon kiu testas ĉu la listo enhavas elementojn. Se ne, returnu None.

def find_max(numbers):
    if len(numbers) == 0:
        return None

    largest = numbers[0]
    for num in numbers:
        if num > largest:
            largest = num

    return largest

Tasko 4 - Nombri la nombron de donita elemento en listo

Kreu algoritmon kiu nombras la nombron de donita elemento en listo.

def count(the_list, check):
    count = 0
    for element in the_list:
        if element == check:
            count += 1

    return count

Tasko 5 - Inverti string-on, tekston

Kreu algoritmon kiu inversigas donitan string-on.

def reverse(text):
    result = ""
    # Ĉi tiu linio estas iomete komplika, sed ĝi komenciĝas
    # ĉe la fino, iras (inkluzive) ĝis 0 (skribante
    # -1 kiel finon), kaj kalkulas malsupren je 1 ĉiu fojo
    for i in range(len(text) - 1, -1, -1):
        result += text[i]
    return result

def reverse(text):
   result = ""
   for i in range(0, len(text)):
       # aldonu al la komenco anstataŭe
       result = text[i] + result
   return result

Tasko 6 - Palindroma Algoritmo

Kreiu algoritmon kiu kontrolas ĉu donita vorto estas palindromo. Ekzemploj de palindromoj estas abba, racecar, regninger.

def palindrome(text):
    for i in range(0, len(text)):
        if text[i] != text[len(text) - i - 1]:
            return False
    return True

Tasko 7 - Kontroli ĉu listo estas ordigita

Kreu algoritmon kiu kontrolas ĉu listo estas ordigita. La plej facila maniero kontroli tion estas komenci de la komenco kaj kompreni ĉu la sekva elemento estas “pli granda”. Se elemento ne estas “pli granda”, la listo ne estas ordigita.

def is_sorted(the_list):
    for i in range(len(the_list) - 1):
        if the_list[i] > the_list[i + 1]:
            return False
    return True

Tasko 8 - Miksado

Kreiu algoritmon kiu miksas liston de aĵoj. Ekzistas multaj manieroj fari tion, sed bona maniero estas tio, kio estas nomata Fisher-Yates miksada algoritmo. Vi povas legi pli pri tio ĉi tie Wikipedia.

Ĝi funkcias jene:

import random

def shuffle(the_list):
    shuffled = []

    while len(the_list) > 0:
        i = random.randrange(0, len(the_list))
        shuffled.append(the_list[i])
        the_list.pop(i)

    return shuffled

Tasko 9 - Bogo-sort

En ĉi tiu tasko vi devas krei (praktike) terura, sed ekstrema simple sorteran algoritmon. Ĝi estas ekstrema malbona kiam temas pri grandaj listoj (ĝi prenos eternumon kun pli ol 12-13 aĵoj). En Nivelo 2 ni kreos pli bonan sorteran algoritmon, bubble-sort.

La algoritmo funkcias jene:

Legu pri Big O-notacio en Nivelo 2.

Indico: Eble uzu shuffle el tasko 8 por krei netriceitan liston por via algoritmo.

def bogo_sort(the_list):
    while not is_sorted(the_list):
        the_list = shuffle(the_list)
    return the_list

Tasko 10a - Serĉu tekston - “subŝtringo” (Malfacila!)

Kreu algoritmon kiu povas trovi serĉvorton en teksto. Do, se vi havas frazon kiel hello there vi volus redoni True kun la serĉvorto hello, False kun serĉvorto kiel hahah. Ĉi tiu algoritmo devas funkcii sendepende de la eniro kaj eliro.

Uzu la tekstdatenojn sube por kontroli ĉu via algoritmo funkcias.

def search(data, word): 
    for i in range(0, len(data) - len(word) + 1):
        found = True
        for j in range (0, len(word)):
            if data[i + j] != word[j]:
                found = False
                break
        if found:
            return True

    return False

Tasko 10b

Aldonu ankaŭ plian kontrolon, kiu certigas, ke la serĉvorto ne estas pli longa ol la frazo.

def search(data, word): 
    if len(word) > len(data):
        return False

    for i in range(0, len(data) - len(word) + 1):
        found = True
        for j in range (0, len(word)):
            if data[i + j] != word[j]:
                found = False
                break
        if found:
            return True

    return False

Tasko 11 - Invertigo de vortoj en frazo (Malfacila)

Memoru reen al Tasko 5 pri la invertigo de frazo. Modifu (aŭ komencu denove) por krei algoritmon kiu inversigas ĉiun apartan vorton en frazo, kaj poste kunigas ilin denove.

def reverse_words(words):
    sentence = words.split(" ")
    output = ""

    for word in sentence:
        reversed_word = ""
        for i in range(0, len(word)):
            reversed_word = word[i] + reversed_word
        output += reversed_word + " "

    return output

➕Ekstra:

Kio estas “kiel” en programado?

En programado, “kiel” (angle mock) estas objekto, kiu imitas la konduton de vera objekto. Ĝi estas uzata por testi kodon, sen dependi de la vera objekto. Tiel, oni povas testi specifan funkcion aŭ metodon, sen ke la vera objekto estu disponebla aŭ funkcia.

Ekzemple, se vi volas testi funkcion, kiu alvokas datbazon, vi povas uzi “kiel”-objekton, kiu imitas la datbazon. Tiel, vi povas testi la funkcion, sen ke vi fakte konektu al la vera datbazo.

Kiam uzi “kiel”-objektojn?

“Kiel”-objektojn oni uzas, kiam:

• Vi volas testi kodon, kiu dependas de eksteraj faktoroj, kiel datbazoj aŭ API-oj.
• Vi volas izoli la kodon, kiun vi testas, de la resto de la sistemo.
• Vi volas simuli erarajn situaciojn, por vidi, kiel la kodo reagadas.
• Vi volas plibonigi la rapidecon de la testoj.

Kiel krei “kiel”-objekton?

Ekzistas diversaj manieroj por krei “kiel”-objekton. Unu maniero estas uzi bibliotekon aŭ kadron, kiu subtenas “kiel”-objektojn. Alia maniero estas krei la “kiel”-objekton mem, per programado.

Ekzemple, en Python, oni povas uzi la bibliotekon unittest.mock por krei “kiel”-objektojn. En Java, oni povas uzi la bibliotekon Mockito.

Avantaĝoj de uzo de “kiel”-objektoj

• Pli rapida testado: “Kiel”-objektoj estas pli rapidaj ol la vera objekto, do testoj finiĝas pli rapide.
• Izolita testado: “Kiel”-objektoj izolas la testatan kodon, do testoj estas pli fidindaj.
• Simulado de eraroj: “Kiel”-objektoj permesas simuli erarajn situaciojn, do oni povas testi, kiel la kodo reagadas.
• Pli bona kodelego: Uzo de “kiel”-objektoj povas plibonigi la kodelegon, ĉar ĝi klarigas la dependecojn de la kodo.

Tasko E1 - Forigi duplikatojn el listo

Diru ke vi havas liston kiu enhavas nombrojn, aŭ tekston, sed ni volas forigi la duplikatojn. Kreu algoritmon kiu forigas ĉiujn duplikatojn el listo kaj enhavas nur la unuan de ĉiu unika elemento kiu ekzistas en la listo.

def delete_duplicates(the_list):
    idx = 0

    while idx < len(the_list):
        jdx = idx + 1

        while jdx < len(the_list):
            if the_list[idx] == the_list[jdx]:
                the_list.pop(jdx)
                jdx -= 1
            jdx += 1
        idx += 1

    return the_list

Task E2 - Counting Sort

Counting sort estas unu el la malmultaj sortaj algoritmoj kiuj funkcias en tio, kion ni nomas \(O(n)\) tempo. Tio estas, ĝi ne prenas multe pli da tempo ol la nombro da elementoj en la listo. Legu pli pri Big O-notacio en Nivelo 2.

Ĝi iomete dependas de kiom granda la intervalo de elementoj estas. Se la plej malgranda estas 0 kaj la plej granda estas 100000, ĝi povas preni iom da tempo, do ĉi tiu povas esti uzata se la intervalo de valoroj estas malgranda. Ĝi ankaŭ ne funkcias por negativaj nombroj, sed estas eble modifi la algoritmon por funkcii kun negativaj nombroj.

La algoritmo funkcias tiel:

• Trovu kiom granda la plej granda elemento estas, konservu la valoron de ĉi tiu elemento kiel \(k\).
• Kreu liston kiu enhavas \(k + 1\) elementojn, count.
• Trairu la netritan liston kaj uzu la valoron de la nombro kiel indekso. Tio estas, se la elemento havas la valoron 47, tiam vi iras al count[47] kaj pligrandigas ĝin je 1.
• Trairu la count liston kaj metu la nombron da nombroj kiel la indekso estas. Ekzemple: Se estas 3 ĉe indekso 1, tiam vi aldonas tri 1-nombrojn.

def counting_sort(input_list):
    output = []

    max_val = input_list[0]

    for n in input_list:
        if n > max_val:
            max_val = n

    # tio kreas amason da nuloj
    count = [0] * (max_val + 1)

    for n in input_list:
        count[n] += 1

    for i in range(len(count)):
        # uzu _ por ignori valoron
        for _ in range(count[i]):
            output.append(i)

    return output