階調アルゴリズム(1)

Greedyアルゴリズム

「欲張りに」解題
→現在の状況で、今すぐ選べる方法

毎時毎刻ベストに見えるものを選び、今後の影響を考慮しない

グレースケールアルゴリズム標準

質問に対して「最大順」「最小順」などの基準を提示

これらの基準に基づき並べ替えアルゴリズムとペアで出題

金をさがす
質問する
カウンターに500元、100元、50元、10元のコインがあり、制限がない場合
小銭はN元で、コインの個数が一番少ないです.
(ただし、お釣りNは10の倍数)
「大通貨単位から」おつり

最大の単位500元を探して、それから100元、50元、10元の順番で探すことができます.

例:2670元を探しているとしたら

500元:5個

100元:1個

50元:1個

10元:2個

コードの例

import Foundation

func coinCountMin(_ change: Int) {

    var money = change
    let coin_list = [500, 100, 50, 10]
    var coinCount = 0

    for coin in coin_list{
        let count = money / coin
        if count != 0 {
            coinCount += count
            money -= coin * count
        } else { continue }
    }

    print(coinCount)
}

coinCountMin(1260)

コードフィーチャー

for coin in coin_list文から分かるように、通貨の種類のように繰り返し実行する必要があります.

従って、コインの種類がN個である場合、コードの時間的複雑度がO(N)となる.

小銭ではなく、コインの種類だけがアルゴリズムの時間的複雑さに影響することがわかる.

グリディアルゴリズムの合理性

大部分の問題はグリッディアルゴリズムを用いた場合「最適解」が見つからない可能性がある.

グリディアルゴリズムで問題の解法を探す場合,その正しさを検討すべきである.

Griddyアルゴリズムが適用されない例
今、金庫には無数の五百四百元が入っていますが、八百元を探すとコインが一番少ないです.

階調アルゴリズム方式
-500元:1個
-100元:3個

実最適解
-400元:2個

実際の最適解はグリディアルゴリズムの解から半分減少することが分かった.
アルゴリズム適用条件
第1例では、500원, 100원, 50원, 10원これらの単位同士の排水形態で行う.