Створіть прості алгоритми

Skip to content

Це машинний переклад, який може містити помилки!

Quote

“Алгоритм”, слово, яке програмісти використовують, коли не хочуть пояснювати, що вони зробили.

Algoritme?

Що таке алгоритм?

Алгоритм — це логічна функція, яка виконує певну операцію. Отже, ви технічно можете назвати функцію, яка додає два числа, «алгоритмом», але найчастіше алгоритм — це дещо більш складне. Часто алгоритми використовуються для прискорення операцій, які займають багато часу.

Algorithm Meme

Чи потрібно використовувати Python у цих завданнях?

Ні! Ви можете використовувати будь-яку мову програмування, яку ви віддаєте перевагу в цих завданнях.

Вбудовані бібліотеки?

Ідея цих завдань полягає в тому, щоб уникати використання вбудованих бібліотек або спеціальних функцій Python. Наприклад, існує простий “one-liner” для реверсування тексту: text[::-1], але тут ми хочемо, щоб ви спробували вирішити такі завдання без використання цього. Це може статися, що ми згадаємо вбудовану функцію, якщо рішення трохи важко знайти. Це буде позначено ❗.

На практиці має бути повністю можливо вирішити всі ці завдання за допомогою if, for, while та звичайних операцій зі списками.

Як “розробити” алгоритм?

Найчастіше алгоритми розробляються ітеративно. Що це означає?

1. ✅ Спочатку розбийте проблему на менші частини.
  • Насамперед подумайте про найважливіше, що вам потрібно для роботи алгоритму
    • Чи повинен він повертати значення? Логічне значення (boolean)? Список?
    • Чи потрібні мені якісь допоміжні функції?

2. ❓ Чи є якісь “крайні випадки”?
  • Що відбувається, якщо ви вставляєте порожній список або текст?

3. ✅ Почніть з того, що просто спробуйте створити рішення

4. ✅ Перевірте, чи алгоритм працює добре за часом виконання
  • Спробуйте більші вхідні дані, чи займає це багато часу?

5. ❓ Подумайте про своє рішення, чи потрібні вам усі кроки, які ви використовували?
  • Чи всі if-перевірки необхідні?
  • Якщо у вас більше одного for-циклу, чи є якісь очевидні способи перетворити це на один for-цикл?
    • Це відрізняється, якщо у вас вкладені цикли або цикли один за одним. Цикли, що йдуть один за одним, часто можна уникнути.

6. ✅ Подумайте про екстремальні сценарії з вхідними даними:
  • Приклад з числами: великі числа, малі числа, від’ємні числа
  • Приклад тексту: багато тексту, багато маленьких слів, додаткові пробіли, великі та малі літери.

7. ❓ Чи корисно використовувати псевдо-код для кращого розуміння логіки?

Easy Завдання 1 - З’ясувати, чи містить список задане число

Створіть алгоритм (функцію), який з’ясовує, чи містить список задане число. Він повинен повертати True або False залежно від того, чи існує число в списку чи ні.

Ось список з тестовими даними:

Test-data for algoritme:
Test-Data Сjekk Svar
[1, 2, 3, 4, 5, 6, 7, 8, 9] 5 True
[1, 2, 3, 4, 5, 6, 7, 8, 9] 10 False
[2, 3, 5, 7, 11, 13, 17, 19, 23] 2 True
[2, 3, 5, 7, 11, 13, 17, 19, 23] 10 False
[-1, 0, 1, -34, 321, 22, 98, -214] -214 True
[-1, 0, 1, -34, 321, 22, 98, -214] 0 True
[-1, 0, 1, -34, 321, 22, 98, -214] 2 False

Tips til framgangsmåte
  1. Прийміть список та значення списку у функцію. У цьому завданні це будуть числа, але може бути текст.
  2. Використовуйте for-цикл для перебору списку.
  3. Якщо число дорівнює перевірочному числу, поверніть True.
  4. Якщо for-цикл завершено і ви не знайшли його, поверніть False.

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

Easy Завдання 2 - Підсумовування

Створіть алгоритм, який підсумовує список чисел.

Test-data for algoritme:
  • [1, 2, 3, 4, 5, 6], дає відповідь 21.
  • [5, 1, 23, 68, 22, 13, 4], дає відповідь 136
  • [3, 3, -3, -3, 3] дає відповідь 3. Можливо, ви можете ігнорувати від’ємні числа та дати відповідь 9.

Tips til framgangsmåte
  1. Прийміть список у функцію
  2. Збережіть тимчасову суму як 0.
  3. Використовуйте for-цикл для перебору списку.
  4. return суму списку.

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

Medium Завдання 3a - Максимальне значення у списку

Створіть алгоритм, який знаходить найбільше значення у списку.

Test-data for algoritme:
  • [1, 2, 3, 4, 5, 6], дає відповідь 6.
  • [6, 17, 227, 1, 23, 42, 12], дає відповідь 227
  • [2, -2, 2, -2, -2, 2] дає відповідь 2.

Tips til framgangsmåte
  1. Прийміть список у функцію
  2. Призначте тимчасове значення першому елементу списку.
  3. Використовуйте for-цикл для перебору списку та порівняння зі значенням, яке ви встановили в пункті 2.
  4. Якщо значення більше, встановіть тимчасове значення на нове значення.
  5. return це тимчасове значення.

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

    return largest

Easy Завдання 3b - Якщо список порожній?

Додайте перевірку, яка тестує, чи містить список елементи. Якщо ні, поверніть None.

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

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

    return largest

Easy Завдання 4 - Підрахунок кількості заданого елемента в списку

Створіть алгоритм, який підраховує кількість заданого елемента в списку.

Test-data for algoritme:
  • ["apple", "banana", "orange", "apple", "apple", "banana"] з apple дає відповідь 3.
  • [1, 4, 5, 2, 4, -3, -4, 4, 2, 4, 221, 3, 1, 1, 4, 1, 12, 33, 4, 4, 2, -4, 1, 4] з 4 дає відповідь 8.
  • ["cat", "dog", "cat", "mouse", "cat", "dog", "dog"] з dog дає відповідь 3.
  • [7, 7, 2, 9, 7, 1, 0, 7, 3, 7, 9] з 7 дає відповідь 5.
  • ["red", "blue", "green", "red", "yellow", "red"] з red дає відповідь 3.
  • [10, -2, -2, -2, 5, 10, 10, -2] з -2 дає відповідь 4.

Tips til framgangsmåte
  1. Прийміть список та перевірочне значення у функцію
  2. Почніть з тимчасової лічильної змінної, встановленої на 0.
  3. Пройдіть по списку за допомогою циклу for.
  4. Якщо елемент дорівнює перевірці, збільште лічильну змінну на 1.
  5. Поверніть лічильну змінну.

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

    return count

Medium Завдання 5 - Розвернути string, текст

Створіть алгоритм, який розвертає заданий string.

Test-data for algoritme:
  • Hello there! стає !ereht olleH.
  • heisann alle sammen стає nemmas ella nnasieh
  • Python стає nohtyP
  • racecar стає racecar
  • 12345abc стає cba54321
  • god morgen стає negrom dog

Tips til framgangsmåte
  1. Прийміть string у функцію
  2. Створіть тимчасову змінну для зберігання порожнього string.
  3. Пройдіть по тексту за допомогою for-циклу з range. Тут можна пройти по списку назад, але можна вирішити цю задачу, рухаючись вперед по списку.
  4. Додайте кожен символ до тимчасової змінної послідовно.
  5. Поверніть тимчасовий текст.

Svaret (i python) 
def reverse(text):
    result = ""
    # Цей рядок трохи складний, але він починається
    # з кінця, йде (включно) до 0 (записуючи
    # -1 як кінець), і рахує вниз на 1 кожного разу
    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)):
       # додати на початок замість цього
       result = text[i] + result
   return result

Medium Завдання 6 - Алгоритм паліндрому

Створіть алгоритм, який перевіряє, чи є задане слово паліндромом. Приклади паліндромів: abba, racecar, regninger.

Tips til framgangsmåte
  1. Створіть функцію, яка приймає текст для перевірки.
  2. Використовуйте for-цикл, щоб перевірити, чи однакові літери з кожного боку тексту.
  3. Поверніть False, якщо літера не збігається, якщо всі збігаються (for-цикл завершується), поверніть True.

Екстра:
Чи бачите ви, як можна зробити алгоритм вдвічі швидшим?

Hint

Вам потрібно перевіряти лише половину!

Відповідь (в python) 
def palindrome(text):
    for i in range(0, len(text)):
        if text[i] != text[len(text) - i - 1]:
            return False
    return True
Швидший алгоритм

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

Medium Завдання 7 - Перевірка, чи відсортований список

Створіть алгоритм, який перевіряє, чи відсортований список. Найпростіший спосіб перевірити це – почати з початку і порівнювати, чи наступний елемент є “більшим”. Якщо елемент не є “більшим”, то список не відсортований.

Test-data for algoritme:
  • [1, 2, 3, 4, 5, 6], дає відповідь True.
  • [6, 17, 227, 1, 23, 42, 12], дає відповідь False
  • [2, -2, 2, -2, -2, 2] дає відповідь False.
  • [2, 2, 3, 4, 4, 6], дає відповідь True.
  • [12, 23, 34, 45, 56, 67], дає відповідь True.

Tips til framgangsmåte
  1. Створіть функцію, яка приймає список
  2. Використовуйте for-цикл, щоб пройти через весь список (використовуйте range до довжини списку, мінус 1 len(list) - 1)
  3. Порівняйте елемент \(n\) з \(n + 1\), тобто поточний елемент з наступним елементом.
  4. Якщо \(n\) менше за \(n + 1\), перейдіть до наступного порівняння.
  5. Якщо це не менше, а більше, то список не відсортований. Поверніть False тут.
  6. Якщо ви досягнете кінця, то список відсортований, поверніть True.

Svaret (i Python) 
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

Medium Завдання 8 - Перемішування

Створіть алгоритм, який перемішує список речей. Існує багато способів це зробити, але один з хороших – це так званий алгоритм перемішування Фішера-Йетса. Ви можете прочитати більше про це тут Wikipedia.

Test Data
  • ["a", "b", "c", "d", "e"] → може стати наприклад ["c", "e", "a", "d", "b"]
  • [1, 2, 3, 4, 5, 6] → може стати наприклад [4, 1, 6, 3, 2, 5]
  • ["apple", "banana", "orange"] → може стати наприклад ["orange", "apple", "banana"]
  • ["x"] → залишається ["x"]
  • [] → залишається []

Вона працює так:

Алгоритм
  1. Створіть функцію, яка приймає список чисел
  2. Створіть новий порожній список, який зберігатиме змішаний результат.
  3. Використовуйте random для вибору випадкового індексу в списку.
  4. Додайте цей елемент до порожнього списку та видаліть його зі старого
  5. Поверніть новий список з функції

Svaret (i Python) 
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

Medium Завдання 9 - Bogo-sort

У цьому завданні вам потрібно створити (практично) жахливий, але надзвичайно простий алгоритм сортування. Він надзвичайно поганий, коли мова йде про великі списки (з більш ніж 12-13 елементами він займе вічність). На Рівні 2 ми створимо кращий алгоритм сортування, bubble-sort.

Test Data
  • [3, 1, 2] → [1, 2, 3]
  • [5, 4, 3, 2, 1] → [1, 2, 3, 4, 5]
  • [10, 7, 8, 2] → [2, 7, 8, 10]
  • [1, 1, 1] → [1, 1, 1]
  • [9, 3, 6, 3, 9] → [3, 3, 6, 9, 9]
  • [0, -1, 4, -2] → [-2, -1, 0, 4]

Алгоритм працює так:

Алгоритм
  1. Створіть функцію, яка приймає список невідсортованих чисел
  2. Перемішайте список випадково (використовуйте shuffle із завдання 8).
  3. Перевірте, чи список відсортовано (використовуйте перевірку, яку ви створили в завданні 7).
  4. Якщо список не відсортовано, повторіть кроки 2 і 3.
  5. Повторюйте, поки список не буде відсортовано, потім поверніть

Просто кажучи: bogo-sort перемішує весь список і сподівається, що він буде відсортовано.

Gru bogo sort meme
Дізнайтеся про Big O нотацію в Рівні 2.

Підказка: За бажанням використовуйте shuffle із завдання 8, щоб створити невпорядкований список для вашого алгоритму.

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

Hard Завдання 10a - Пошук тексту - “підрядок” (Складно!)

Створіть алгоритм, який може знайти ключове слово в тексті. Тобто, якщо у вас є речення, таке як hello there, ви повернете True з ключовим словом hello, False з ключовим словом, таким як hahah. Цей алгоритм повинен працювати з будь-яким вхідним і вихідним значенням.

Використовуйте текстові дані нижче, щоб перевірити, чи працює ваш алгоритм.

Test-data for algoritme:
  • hello there everyone з there = True
  • hello there everyone з ever = True
  • hello there everyone з then = False
  • qwecvyufavsjekkftyergwcery з sjekk = True

Tips til framgangsmåte
  1. Створіть функцію, яка приймає два strings, дані та ключове слово.
  2. Використовуйте for-loop з range для перебору тексту.
  3. Тут важливо подумати, як далеко має йти цикл.
  4. Створіть тимчасову змінну, яка вказує, чи було знайдено ключове слово, встановіть її на True за замовчуванням.
  5. Використовуйте ще один for-loop з range для порівняння того, де ви знаходитесь у тексті, з ключовим словом.
  6. Якщо щось у ключовому слові не збігається з тим, що ви перевіряєте зараз, встановіть тимчасову змінну на True і break з внутрішнього циклу.
  7. Якщо ви дійдете до кінця тексту, не знайшовши нічого, поверніть False.

Svaret (i Python) 
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

Easy Завдання 10b

Додайте також додаткову перевірку, яка слідкує за тим, щоб ключове слово не було довшим за речення.

Tips til framgangsmåte
  • Додайте цю перевірку перед for-циклом.

Svaret (i python) 
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

Hard Завдання 11 - Реверсування слів у реченні (Складно)

Згадайте Завдання 5 про реверсування речення. Переробіть (або почніть спочатку) алгоритм, який реверсує кожне окреме слово в реченні, а потім збирає їх разом.

Test-data for algoritme:
  • hello there everyone стає olleh ereht enoyreve
  • This is the way it goes! стає sihT si eht yaw ti !seog
  • does this racecar go? of course! стає seod siht racecar ?og fo !esruoc

Tips til framgangsmåte
  1. Створіть функцію, яка приймає string.
  2. ❗Розділіть текст, використовуючи .split(" ").
  3. Створіть тимчасову змінну для зберігання кінцевого значення.
  4. Використовуйте for-цикл для перебору кожного слова.
  5. Використовуйте той самий метод для реверсування, як у Завданні 5
  6. Використовуйте результат і додайте його до змінної, яку ви створили на кроці 2.
  7. Поверніть кінцеве значення

Svaret (i Python) 
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

➕Додатково:

Cracked Завдання E1 - Видалення дублікатів зі списку

Припустімо, у вас є список, який містить числа або текст, але ви хочете видалити дублікати. Створіть алгоритм, який видаляє всі дублікати зі списку та містить лише перший з кожного унікального елемента, який існує в списку.

Tips til framgangsmåte
  1. Почніть з функції, яка приймає список
  2. Тут ми будемо використовувати while-цикли замість for. Це полегшує роботу в Python, в інших мовах for з лічильниками працює добре.
  3. Створіть лічильну змінну idx (для індексу, або i)
  4. Використовуйте while-цикл, який повинен пройти до довжини списку
  5. Ми будемо порівнювати елемент на idx з усіма іншими елементами
  6. Створіть лічильну змінну до jdx (або j), яка починається з idx + 1
  7. Порівняйте елемент на idx з елементом на jdx, якщо вони однакові, видаліть jdx за допомогою pop(jdx).
  8. ПАМ’ЯТАЙТЕ! Якщо ви видаляєте елемент, список стає меншим, тому ми повинні повернутися на один крок назад за допомогою jdx -= 1.
  9. Збільште jdx на 1 і перевірте наступний елемент
  10. Після внутрішнього while-циклу збільште idx на 1 і зовнішній while-цикл продовжить роботу
  11. Поверніть у кінці список з видаленими дублікатами

Test Data
  • [1, 2, 2, 3, 1, 4, 3] → blir [1, 2, 3, 4]
  • ["a", "b", "a", "c", "b", "d"] → blir ["a", "b", "c", "d"]
  • [5, 5, 5, 5] → blir [5]
  • ["x", "y", "z", "x", "y", "x"] → blir ["x", "y", "z"]
  • [10, -1, 10, -1, 0, 0, 10] → blir [10, -1, 0]
  • ["apple", "apple', "banana", "orange", "apple", "orange", "pear", "apple"]
    • Має дати: ["apple", "banana", "orange", "pear"]

Svaret (i Python) 
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

Cracked Завдання E2 - Counting Sort

Counting sort є одним з небагатьох алгоритмів сортування, які працюють за час \(O(n)\). Тобто, він не займає набагато більше часу, ніж кількість елементів у списку. Дізнайтеся більше про Big O нотацію в Level 2.

Трохи залежить від того, наскільки великий діапазон елементів. Якщо найменше число 0, а найбільше 100000, це може зайняти трохи часу, тому його можна використовувати, якщо діапазон значень невеликий. Він також не працює з від’ємними числами, але алгоритм можна модифікувати, щоб він працював з від’ємними числами.

Алгоритм працює так:

  • З’ясуйте, яке найбільше число, збережіть значення цього числа як \(k\).
  • Створіть список, який містить \(k + 1\) елементів, count.
  • Пройдіть по невпорядкованому списку та використовуйте значення числа як індекс. Тобто, якщо елемент має значення 47, перейдіть до count[47] і збільште його на 1.
  • Пройдіть по списку count і розмістіть кількість чисел, яка є індексом. Наприклад: якщо на індексі 1 стоїть 3, додайте три 1 числа.

Testdata
Несортовані Дані Відсортовані Дані
[7, 3, 9, 1, 4, 3, 0, 6, 8, 6, 2, 1, 9, 0, 5, 4] [0, 0, 1, 1, 2, 3, 3, 4, 4, 5, 6, 6, 7, 8, 9, 9]
[12, 13, 15, 0, 8, 15, 8, 5, 16, 8, 0, 20, 4, 9, 17, 16, 1, 3, 6, 15, 5, 2, 3, 1, 19, 13, 17, 5, 3, 10] [0, 0, 1, 1, 2, 3, 3, 3, 4, 5, 5, 5, 6, 8, 8, 8, 9, 10, 12, 13, 13, 15, 15, 15, 16, 16, 17, 17, 19, 20]

Tips til framgangsmåte
  1. Почніть зі створення функції, яка приймає список як вхідні дані
  2. Створіть порожній список output
  3. Використовуйте for-цикл, щоб пройти весь список
  4. Відстежуйте максимальне значення в змінній перед for-циклом
  5. Оновіть максимальне значення, якщо ви знайдете щось більше
  6. Створіть список, який містить цю кількість нулів + 1. Приклад: найбільше значення 47, тоді створіть список з 48 нулів. Це можна зробити за допомогою [0] * (maks + 1), або for циклу. Назвіть його count.
  7. Пройдіть список ще раз за допомогою for-циклу
  8. Використовуйте значення елемента як індекс і збільшуйте на 1. count[value] += 1
  9. Використовуйте for-цикл, щоб пройти список count.
  10. Використовуйте значення на кожному індексі, щоб додати цю кількість чисел
  11. Поверніть відсортований список

Svaret (i Python) 
def counting_sort(input_list):
    output = []

    max_val = input_list[0]

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

    # це створить купу нулів
    count = [0] * (max_val + 1)

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

    for i in range(len(count)):
        # використовуйте _ щоб проігнорувати значення
        for _ in range(count[i]):
            output.append(i)

    return output