0

作りたいプログラミング:
ある電子硬貨があるとする。そこで、あなたは明日から一日以上の硬貨の値を予測できるとする。これを踏まえて、最大利益を計算するプログラミングを作る。
ルール: 一日に一回取引が可能。売るか。買うか。何もしないか。ただし、多くても一個の硬貨しか持てない。それ以上は持てないとする。

例:ユーザからこの様なインプットをしてもらう:2 3 5 1 8 9 2  結果を11と表示しなければならない。

私はいろいろ試したが答えにたどり着かなかったです。理由はコードの下に書きます。
私が使った策:
タプルに対してループを掛ける。毎回その日の値を前後の値と比較し、極値か見極める。一定期間内の極大値であって、硬貨が1個であれば硬貨を売る。一定期間内の極小値であって硬貨が0個の時は硬貨を購入。
期間の始まりだけは極小でなくても、上昇するようであれば購入する。最終日に関しては、硬貨を所有してるなら必ず売る。
よって、最初にタプルの頭と尻を切った。コードのコメント参照。↓

def cal_price(prices):
    newlist = prices.copy()
    tuple1 = tuple(newlist)  
    tuple2_1 = tuple(prices)
    tuple2_2 = tuple2_1[1:-1] #最初の日と最終日を切り落とした
    total = 0
    number_coin = 0  #コインは一が上限だから一ループごと足し引きされる。

    if tuple1[0]< tuple1[1]:  #まずは最初の日の処理
        number_coin += 1
        total -= tuple1[0]
    for index_tuple2, val in enumerate(list(tuple2_2)): 
        x = index_tuple2 + 1
        # x is   index_tuple1
        if number_coin==1 and tuple1[x-1]<tuple1[x] and tuple1[x]>tuple1[x+1]: #極大値かつ硬貨一個 
                                                                                 # の場合
            total += val
            number_coin -= 1 
        elif number_coin==0 and tuple1[x-1]>tuple1[x] and tuple1[x]<tuple1[x+1]: #上と逆
            total -= val
            number_coin += 1
    
    if number_coin == 1: #最終日の処理
        total += tuple1[-1]
    return total

この様に関数を作りました。そこでユーザーにインプットしてもらった値をタプルに変えました。しかし、この方法では一日だけの値を与えられた場合、タプルの範囲を超えてエラーが出てきてしまします。
一日の値を入力してもエラーじゃなくて、0 が出るような物を作りたいです。
さらに、値段が変動してない場合に全く対応してません。初心者です。お手柔らかにお願いします。よろしくお願いいたします。。。

そもそも方向性が間違ってる気がするので、それに関するヒントを与えてくれたらありがたいです。

1
  • 「一日の値を入力してもエラーじゃなくて、0 が出るような物」…cal_price() 関数の初っ端に if len(prices) < 2: return 0 とでも書いておけばよいのではないですか。
    – metropolis
    2021年9月23日 11:54

3 件の回答 3

0

なんだかややこしく考えてるようですが、明日値段が上がるなら買う、そうでないなら買わない、これだけのアルゴリズムで利益は最大化できます。

まず、コインの売買に関するルールですが

  • 一日の最初にコインを持っていたらその日の値段で、必ず売る。
  • そのあと、コインを1枚買うかどうか選べる。

こういうルールを考えると

  • コインを売る × コインを買う -> 何もしない
  • コインを売る × コインを買わない -> 売る
  • コインを売らない × コインを買う -> 買う
  • コインを売らない × コインを買わない -> 何もしない

と対応付けることができて、しかもコインを2枚以上同時にもてないというルールを満たすので、今のルールと同等です。
このルールで考えれば、次の日に売ってしまうコインを買うかどうかというのは次の日に値段が上がるかどうかだけ考えればことが明らかなので最初のアルゴリズムで十分だとわかります。

極大かどうかを考えるのは間違った方法ではありませんが、今のコードはその実装としては不十分で、 極値が連続する場合、つまり[1, 2, 2, 1]こういう状況では極値だと判定されないというようなバグがあります。

実は、コインを持っていなくて明日値段が上がるなら買う、コインを持っていて明日値段が下がるなら売るとするとこで、極大・極小値の最終日(上の例でいうと二回目の2の日)に売り買いすることができます。
なぜならコインを持っているということはコインを買ってから値段が下がっていないということを、コインを持っていないということはコインを売ってから値段が上がっていないということを意味し、コインを持ってるかどうかだけで前日以前の値段の動きが十分にわかるからです。
このアルゴリズムだと最終的なコードは同じようなものですし、最初に極値での売り買いを思いついたのであればこちらのほうがわかりやすかもしれません。

1日の入力しか与えられないというようなエッジケースは、個別に処理してもかまわないと思います。

0

ルール: 一日に一回取引が可能。売るか。買うか。何もしないか。ただし、多くても一個の硬貨しか持てない。それ以上は持てないとする。

このルールに従えば、硬貨を持っている場合は「売るか。何もしないか。」
硬貨を持っていない場合は「買うか。何もしないか。」ですから
再帰関数を使用して prices を1つずつ進めるのが良さそうです。

def cal_price(prices, coin=0, profit=0):
    if not prices:
        return profit
    if coin:
        return max(cal_price(prices[1:], coin, profit),   # 何もしない
                   cal_price(prices[1:], 0, profit + prices[0] - coin))  # 売る
    else:
        return max(cal_price(prices[1:], coin, profit),   # 何もしない
                   cal_price(prices[1:], prices[0], profit))   # 買う

prices = [2,3,5,1,8,9,2]
ans = cal_price(prices)
print(ans)  # 11
0

前後の日だけ比べてもそれが最善の売買の選択かは確定しないかと思います。例えば多少損切りをしてもその日に売っておいて、翌日以降に大儲けできる可能性もあるかと思います。
geocentricさんが考えた策はひとまずおいといて、とりあえずの方向性としては愚直に全通り試すのがプログラムらしくていいんじゃないでしょうか。

例えば、2351892の7回の取引では、最初の価格2のときに「売り」「買い」「保留」の3通り選べます。
これが7回あるので3^7=2187全通りの取引を全部試して一番利益が得られるものを見つけるという方法がはじめの一歩としてシンプルな方法かと思います。

2187通りの中には、コインが無い状態での「売り」や、連続した「買い」など実行できないものも含まれますので、そういったものは試行から除外していきます。

2000通りぐらいならこれで瞬時に答えはでますので、まずはこれで答えが出せることをゴールとします。つぎに桁数が増えていくとどんどん組み合わせは増えていくので、そうなったときにどうやって高速化していくかは、また別の質問として聞いてみたら良いと思います。

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。