-1

バスケットボールの試合の最終スコアを考えると、最終スコアにつながる可能性のあるスコアリングシーケンスの数をどのように数えることができますか。

各スコアは、訪問チームまたはホームチームのいずれかによる3ポイント、2ポイント、1ポイントのスコアのいずれかになります。例えば：

basketball(3,0)=4

これらは4つの可能なスコアリングシーケンスであるため：

V3
V2, V1
V1, V2
V1, V1, V1

そして：basketball（88,90）= 2207953060635688897371828702457752716253346841271355073695508308144982465636968075

また、グローバル変数を使用せずに再帰的に実行する必要があります（辞書は許可されており、おそらくこれを解決する方法です）。また、関数は引数（basketball（m、n））として結果のみを取得できます。

解決策を求めた人のために：

basketballDic={}
def basketball(n,m):
    count=0;
    if n==0 and m==0:
        return 1;
    if (n,m) in basketballDic:
        return basketballDic[(n,m)]
    if n>=3:
        count+= basketball(n-3,m)
    if n>=2:
        count+= basketball(n-2,m)
    if n>=1:
        count+= basketball(n-1,m)
    if m>=3:
        count+= basketball(n,m-3)
    if m>=2:
        count+= basketball(n,m-2)
    if m>=1:
        count+= basketball(n,m-1)
    basketballDic[(n,m)]=count;
    return count;
4

3 に答える 3

2

再帰アルゴリズムを検討している場合、把握する必要があることが 2 つあります。

  1. 再帰が終了する基本ケースは何ですか。
  2. 再帰的なケースは何ですか。つまり、以前の 1 つ以上の値から 1 つの値をどのように計算できるでしょうか?

バスケットボールの問題の基本ケースは非常に単純です。スコアがない場合、たまたまそこにたどり着いた可能性のあるバスケットのセットが 1 つだけあります (それは空のセットです)。したがってbasketball(0,0)、1 を返す必要があります。

再帰的なケースは、考えるのが少し難しいです。与えられたスコア、たとえば (M,N) を (0,0) になるまで段階的に減らし、途中で各スコアを取得するさまざまな方法を数え上げる必要があります。以前の状態から (M,N) に到達するためにスコアが変更された可能性がある方法は 6 つあります (各チームの 1、2、および 3 ポイント バスケット)。したがって、(M,N) に到達する方法の数は(M-1,N)、(M-2,N)、(M-3,N)、(M,N-1)、(M,N-2)、( M,N-3)。したがって、これらは(おそらくいくつかの境界チェックの後)作成したい再帰呼び出しです。

単純な再帰的な実装では、高いスコアを解決するのに非常に長い時間がかかることがわかります。これは、同じ値を何度も計算するためです (たとえば、(1,0) のスコアを何百回も取得する方法は 1 つしかないと計算する場合があります)。メモ化は、以前に計算された結果を記憶することで、重複作業を防ぐのに役立ちます。問題が対称であることも注目に値します ((N,M) を取得する方法と同じ数の (M,N) のスコアを取得する方法があります)。現在の結果だけでなく、その逆もあります。

于 2012-12-05T00:01:33.177 に答える
1

これを行う方法は 2 つありますが、どちらも指定した出力に近づくことはできません。あまり関係のない方法は、可能な最大得点プレー数を数えることです。バスケットボールの得点は 1 点であるため、これは常に関数への両方の入力の合計に等しくなりbasketball()ます。2 番目の手法は、最小得点プレー数をカウントすることです。これは、次のように再帰を使用して簡単に実行できます。

def team(x):
    if x:
        score = 3

        if x < 3:
            score = 2
        if x < 2:
            score = 1

        return 1 + team(x - score)
    else:
        return 0

def basketball(x, y):
    return team(x) + team(y)

これをもっと簡潔に、さらにエレガントに行うことはできますか? 確かに、しかし、これは、あなたが取り組んでいる種類のステートレスで再帰的なソリューションの適切な出発点を提供するはずです.

于 2012-12-04T21:45:50.160 に答える
0

0 になるまで再帰を使用して、指定された結果 (すべての可能なプレイ - 1,2,3 ポイント) から削減しようとしましたが、そのためにはグローバル変数が必要であり、使用できません。

たぶん、これはあなたが必要なものを明らかにする場所です。必要に応じて、現在のカウントを渡したり、使用済みカウント (または残りのカウント) を返したりすることで、グローバルを回避できます。

あなたの場合、ポイントを再帰関数に渡してカウントを返すだけだと思います。戻り値が追加されるため、再帰が巻き戻されるにつれて最終的な合計がロールアップされます。

編集

正しい結果を生成できる関数を作成しました。この質問は「メモ化」とタグ付けされています。これを使用すると、パフォーマンスが大幅に向上します。これがないと、同じサブシーケンスが何度も処理されます。デコレーターを使用してメモ化を実装しました。

@Maxwell のチームの個別の処理が気に入りましたが、そのアプローチでは、探している数値が生成されません。(おそらく、元の文言がまったく明確ではなかったため、問題の説明を書き直しました)。最終的に、1 つの関数で 6 つのホームとビジターのスコアリングの可能性を処理しました。

数える必要があるのは末期状態に陥った回数だと気付くまで、私の数え方は間違っていました。

解決

他の解決策が投稿されています。これが私の（あまり読みにくい）ワンライナーです：

def bball(vscore, hscore):
    return 1 if vscore == 0 and hscore == 0 else \
        sum([bball(vscore-s, hscore) for s in range(1,4) if s <= vscore]) + \
        sum([bball(vscore, hscore-s) for s in range(1,4) if s <= hscore])

実際、関数定義の直前に次の行もあります。

@memoize

Michele Simionato のdecorator モジュールと memoize サンプルを使用しました。@Blckknght が述べたように、関数は可換であるため、これを利用するために memoize をカスタマイズできます。

一般的なメモ化によって提供される関心の分離が好きですが、次のような方法でキャッシュを初期化することもできます。

cache = {(0, 0): 1}

関数内の 0,0 引数の特殊なケース チェックを削除します。

于 2012-12-04T21:33:20.500 に答える