簡単なアルゴリズムを作成する

Skip to content

これは機械翻訳されたテキストであり、誤りを含む可能性があります！

Quote

「アルゴリズム」とは、プログラマーが自分が何をしたか説明したくないときに使う言葉です。

Algoritme?

*アルゴリズム*とは何ですか？

アルゴリズムは、特定の操作を実行する論理的な関数です。 つまり、2つの数字を足し合わせる関数を技術的には「アルゴリズム」と呼ぶことができますが、通常、アルゴリズムはそれよりも少し複雑なものです。 アルゴリズムは、時間のかかる操作をより迅速に行うために使用されることがよくあります。

Algorithm Meme

Må jeg bruke Python i disse oppgavene?

いいえ！これらの課題では、お好みのプログラミング言語を使用できます。

組み込みライブラリは？

これらの課題の意図は、組み込みライブラリや特別なPython関数を使用することを*避ける*ことです。たとえば、テキストを反転させる簡単な「ワンライナー」は、text[::-1]ですが、ここではそのような課題をこの方法を使わずに解決しようとすることを期待します。解決策を見つけるのが少し難しい場合は、組み込み関数に言及する*可能性*があります。これは❗でマークされます。

実用上、これらの課題はすべてif、for、while、および通常のリスト操作で完全に解決できるはずです。

アルゴリズムを「設計」するには？

多くの場合、アルゴリズムは 反復的 に設計されます。これはどういう意味でしょうか？

1. ✅ まず問題をより小さな部分に分解します。
  • まず、アルゴリズムが機能するために最も重要なことを考えます。
    • 値を返す必要がありますか？ boolean？ リスト？
    • ヘルパー関数が必要ですか？

2. ❓ エッジケースはありますか？
  • 空のリストやテキストを入力した場合、どうなりますか？

3. ✅ まずは、試して 解決策を作成することから始めましょう。

4. ✅ アルゴリズムが実行時に問題なく機能するか確認
  • より大きな入力で試してみて、時間がかかりすぎませんか？

5. ❓ 解決策について考えます。すべてのステップが必要ですか？
  • すべての if チェックは必要ですか？
  • 1つ以上の for ループがある場合、これを 1つ の for ループにできる明確な方法はありませんか？
    • これは、ネストされた ループと連続したループでは異なります。連続したループは、多くの場合、回避できます。

6. ✅ 入力に関する極端なシナリオを検討してください：
  • 数値の例：大きな数値、小さな数値、負の数値
  • テキストの例：多くのテキスト、多くの短い単語、余分なスペース、大文字と小文字。

7. ❓ ロジックをより良く理解するために 疑似 コードを使用することは役立ちますか？

Easy 課題 1 - リストに特定の数値が含まれているかを確認する

リストに特定の数値が含まれているかどうかを判断するアルゴリズム（関数）を作成します。数値がリストに存在するかどうかによって、True または False を返すようにします。

以下にテストデータの一覧を示します。

Test-data for algoritme:
Test-Data Sjekk 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

この関数は、リスト内に特定の要素が存在するかどうかを確認します。

リスト the_list と確認したい要素 check を引数として受け取ります。

リスト内の各要素を順番に確認し、check と一致する要素が見つかった場合は True を返します。

一致する要素が見つからない場合は 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"] med 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] med 4 は 8 を返します。
  • ["cat", "dog", "cat", "mouse", "cat", "dog", "dog"] med dog は 3 を返します。
  • [7, 7, 2, 9, 7, 1, 0, 7, 3, 7, 9] med 7 は 5 を返します。
  • ["red", "blue", "green", "red", "yellow", "red"] med red は 3 を返します。
  • [10, -2, -2, -2, 5, 10, 10, -2] med -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

このコードは、リスト内の特定の要素の出現回数を数えるPython関数を定義しています。

関数countは、リストthe_listと確認する要素checkを引数として受け取ります。

リストを反復処理し、各要素がcheckと等しいかどうかを確認します。等しい場合は、カウンターcountをインクリメントします。

最後に、カウンター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を返します。

Ekstra:
アルゴリズムを2倍速くできるかどうか分かりましたか？

Hint

半分だけチェックすればいいのです！

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

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ループを使用して、リスト全体を反復処理します（リストの長さから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

この関数は、リストがソートされているかどうかを確認します。リスト内の各要素を順番に調べ、前の要素が次の要素よりも大きい場合、リストはソートされていないと判断し、Falseを返します。すべての要素を調べてもそのような要素が見つからなければ、リストはソートされていると判断し、Trueを返します。

Medium 課題 8 - シャッフル

リスト内の項目をシャッフルするアルゴリズムを作成してください。これを行う方法はたくさんありますが、Fisher-Yates shuffle algorithmと呼ばれるものが良い方法です。このアルゴリズムの詳細については、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"] のままです。
  • [] → まだ [] のままです。

その仕組みは次のとおりです：

Algoritmen
  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]

アルゴリズムは次のように機能します：

Algoritmen
  1. 未整列の数値のリストを入力として受け取る関数を作成します。
  2. リストをランダムにシャッフルします（課題8のshuffleを使用）。
  3. リストがソートされているか確認します（課題7で作成したチェックを使用）。
  4. リストがソートされていない場合は、ステップ2と3を繰り返します。
  5. リストがソートされるまで繰り返し、その後リターンします。

簡単に説明すると: bogo-sortはリスト全体をシャッフルし、ソートされていることを願います。

Gru bogo sort meme
レベル2でBig O表記について学びましょう。

ヒント: タスク8のshuffleを使って、アルゴリズム用にソートされていないリストを作成してください。

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

Hard 課題10a - テキストの検索 - “substring” (難しい!)

テキスト内のキーワードを検索するアルゴリズムを作成してください。例えば、文が hello there の場合、キーワードが hello であれば True を、hahah であれば False を返します。このアルゴリズムは、入力と出力に関係なく機能する必要があります。

以下のテキストデータを使用して、アルゴリズムが機能するかどうかを確認してください。

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. 文字列データと*キーワード*を入力として受け取る関数を作成します。
  2. range を使った for ループを使ってテキストを反復処理します。
  3. ここで、ループがどこまで進むかを考えることが重要です。
  4. キーワードが見つかったかどうかを示す一時変数を、デフォルトで True に設定して作成します。
  5. さらに range を使った for ループを使って、テキスト内の現在位置とキーワードを比較します。
  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

この関数は、与えられた単語のリストを逆順にして、文を生成します。

各単語を反転させ、スペースで区切って結合することで、逆順の文を作成します。

例えば、入力が “hello world” の場合、出力は “olleh dlrow” となります。

➕追加:

Cracked 課題 E1 - リストから重複を削除する

数値やテキストを含むリストがあるとします。重複を削除したいとします。リストからすべての重複を削除し、リストに存在する各一意の要素の最初の要素のみを含むアルゴリズムを作成してください。

Tips til framgangsmåte
  1. まずは、リストを入力として受け取る関数から始めましょう。
  2. ここでは、forの代わりにwhileループを使用します。Pythonではこれが簡単になります。他の言語では、forループでカウンター変数を使用しても問題ありません。
  3. インデックス用のカウンター変数idx（またはi）を作成します。
  4. リストの長さまで実行されるwhileループを使用します。
  5. idxの要素を他のすべての要素と比較します。
  6. idx + 1から始まるカウンター変数jdx（またはj）を作成します。
  7. idxの要素とjdxの要素を比較し、同じであれば、pop(jdx)を使用してjdxを削除します。
  8. HUSK! 要素を削除するとリストが短くなるため、jdx -= 1で1ステップ戻る必要があります。
  9. jdxを1増やして次の要素をテストします。
  10. 内側のwhileループの後、idxを1増やして外側のwhileループを続行します。
  11. 最後に、削除された重複を含むリストを返します。

Test Data
  • [1, 2, 2, 3, 1, 4, 3] → は [1, 2, 3, 4] になります
  • ["a", "b", "a", "c", "b", "d"] → は ["a", "b", "c", "d"] になります
  • [5, 5, 5, 5] → は [5] になります
  • ["x", "y", "z", "x", "y", "x"] → は ["x", "y", "z"] になります
  • [10, -1, 10, -1, 0, 0, 10] → は [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)\) 時間で動作する、数少ないソートアルゴリズムの 1 つです。 つまり、リスト内の要素数よりも大幅に時間がかからないということです。Big O 表記については Level 2 で詳しく説明します。

要素の範囲によって多少異なります。最小値が 0 で最大値が 100000 の場合、少し時間がかかる可能性があります。そのため、値の範囲が小さい場合にこのアルゴリズムを使用できます。負の数には対応していませんが、アルゴリズムを修正して負の数でも動作するようにすることができます。

アルゴリズムは次のように機能します。

  • 最大の要素を調べて、その要素の値を \(k\) として保存します。
  • \(k + 1\) 個の要素を含むリスト count を作成します。
  • ソートされていないリストを反復処理し、数値の値をインデックスとして使用します。たとえば、要素の値が 47 の場合、count[47] に移動して 1 増やします。
  • count リストを反復処理し、インデックスが数値の数になるように配置します。例：インデックス 1 に 3 がある場合、1 の数値を 3 つ追加します。

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