| Subject: Optimal strategy |
Author:
Hjálmtýr
|
[
Next Thread |
Previous Thread |
Next Message |
Previous Message
]
Date Posted: 15:36:59 02/12/04 Thu
Það kom fram spurning eftir fyrirlesturinn í morgun um hegðun "optimal strategy" aðferðarinnar til að spila Nim.
Ég svaraði því ekki alveg rétt, þannig að hér kemur nákvæmara svar.
Segjum að staðan sé sú að þrjár hrúgur sé með 4, 5 og 2 steina hver. Þá er tvíundarútgáfur þessara talna XOR-aðar saman:
4: 0100
5: 0101
2: 0010
--------
útk: 0011
Ef við XOR-um útkomuna við hin gildin þá fáum við hvert nýja gildið í hrúgunni þarf að vera til að XOR-unin á öllum gildunum gæfi 0000. Þetta nýja gildi má auðvitað ekki vera meira en gamla gildið í hrúgunni, því þá þurfum við að BÆTA við steinum, en við megum bara taka burt steina.
Skoðum XOR-un útkomunnar við gildi einstakra hrúga:
Hrúga 1: 0100^0011=0111, nýja gildið er því 7, sem er meira en gamla gildið, sem var 4, svo þetta gengur ekki. Hrúga 2: 0101^0011=0110, nýja gildið er 6, en gamla gildið var 5, svo þetta gengur ekki. Hrúga 3: 0010^0011=0001, nýja gildið er 1, en gamla gildið var 2. Þetta er því í lagi. Ef við tökum einn stein út úr hrúgu 3 þá er XOR-útkoma allra gildanna:
4: 0100
5: 0101
1: 0001
--------
útk: 0000
Við erum því í þessari eftirsóknarverðu stöðu.
Það má rekja sig í gegnum allar hrúgurnar og prófa þetta, en það er reyndar nóg að fara beint í eina af þeim hrúgum sem hafa 1-bita í sama sæti og efsti 1-bitinn er í útkomunni. Hér að ofan var 3ja hrúgan sú eina sem hafði 1-bita í öðru sætinu frá hægri, sem var efsti bitinn í útkomunni.
Ég vona að þetta skiljist, amk. af þeim sem hafa eitthvað spáð í þessa aðferð.
[
Next Thread |
Previous Thread |
Next Message |
Previous Message
]
| |
Feedback: 