3

MIT Open Courseware Introduction to Computer Science and Programming を独学しています。問題セット 2には、チキン ナゲットの箱 (6、9、または 20) の合計を数えることに基づくディオファントス方程式が含まれます。

アルゴリズムの作成について私が考えた方法は、測定値のサイズ (値) がスティックに記録され、別のピースに転送される、(木工所のような) 仮想測定スティックを作成するようなものでした。

数直線上で使用されていると想像すると、初期値が示され、それらのスポットに印を付けてから、最初に遭遇した印にゼロ点を移動して新しい印を付け、繰り返します。それは、常に前進することです。

、x=0、a=x+6、b=x+9、c=x+20それぞれがリストに追加され、次のようになります[6,9,20]。次にやりたいことはx、リスト内の次に大きい値に切り替えて、リストに追加される他の変数の新しい値を作成することです。の次の値xは で6、他の変数を変更すると、次のようなリストになります[6,9,20,12,15,26]。次に、9などです。

私の最初の問題は、重複とリストの順序が無限ループを引き起こすことでした。リストに戻す一連のリストを作成する行を追加することで、それを修正しました。これはほとんど機能しました。

しかし、ここに問題があります。可能なすべての値でリストを埋めるわけではありません。たとえば、明らかに 6 の倍数である 48 はリストに入れません。

私の推測では、私の問題は、常に編集および/または追加されているリストを繰り返し処理しているという事実と関係があると思います。

私は研究を行い、他の人がこの問題の答えをどのようにコーディングしたかを見たので、使用して割り当てを再設計できるアルゴリズムがあることを知っています。問題の解決策。これまでの私のコードは次のとおりです。

## Name some initial variables in diophantine equations
x=0
a, b, c= x+6, x+9, x+20

## Create a list to catch values, aka fish
fish = [a,b,c]
## Here goes
while x <= 60:
    for i in fish:
        x = i
        fish = list(sorted(fish))
        a, b, c= x+6, x+9, x+20
        ## option to see what its doing
        print x,a,b,c
        ## catch the values into the list
        fish.append(a)
        fish.append(b)
        fish.append(c)
        ## get rid of duplicate numbers in the list
        fish = list(set(fish))
        a, b, c= x+6, x+9, x+20


else:
    print fish
## Create new list of values NOT caught by the equation

lastMissingFish = list(set(range(0,50))-set(fish))

## Print the last number not reached by the equation
print lastMissingFish [-1]
4

1 に答える 1