Cserbák Márton <cm552(a)hszk.bme.hu> writes:
Kedves Péter!
Már majdnem egy hónapja ugyanazon a szinten vagyok elakadva az NLP házimmal.
Az a problémám, hogy egyes teszteseteket gyorsan megold, más megoldásoknál
kiugróan hosszú idõre van szüksége, egyes feladatokat pedig (pl. 23.) több
órán belül sem old meg. Megpróbáltam leadni is a megoldásom, az elsõ három
feladatot megoldotta, a többin, ahogy vártam, túllépte az idõkeretet.
Mellékelten elküldöm a tesztsor futtatásának kimenetét, hogy lásd, melyik
példákkal akadt gondom:
01. pelda, 11x11, 111 adott szam, 1 megoldas, futasi ido = 0.03 sec.
02. pelda, 11x11, 61 adott szam, 1 megoldas, futasi ido = 0.02 sec.
03. pelda, 11x11, 21 adott szam, 6 megoldas, futasi ido = 6.53 sec.
04. pelda, 12x12, 85 adott szam, 1 megoldas, futasi ido = 0.01 sec.
05. pelda, 12x12, 29 adott szam, 2 megoldas, futasi ido = 0.04 sec.
06. pelda, 12x12, 27 adott szam, 2 megoldas, futasi ido = 41.60 sec.
07. pelda, 13x13, 116 adott szam, 1 megoldas, futasi ido = 0.02 sec.
08. pelda, 13x13, 45 adott szam, 1 megoldas, futasi ido = 0.09 sec.
09. pelda, 13x13, 55 adott szam, 1 megoldas, futasi ido = 0.02 sec.
10. pelda, 14x14, 113 adott szam, 1 megoldas, futasi ido = 0.02 sec.
11. pelda, 14x14, 35 adott szam, 12 megoldas, futasi ido = 5.63 sec.
12. pelda, 15x15, 128 adott szam, 1 megoldas, futasi ido = 0.03 sec.
13. pelda, 15x15, 34 adott szam, 1 megoldas, futasi ido = 13.14 sec.
14. pelda, 16x16, 146 adott szam, 1 megoldas, futasi ido = 0.03 sec.
15. pelda, 16x16, 36 adott szam, 1 megoldas, futasi ido = 0.89 sec.
16. pelda, 16x16, 28 adott szam, 4 megoldas, futasi ido = 3.38 sec.
17. pelda, 17x17, 166 adott szam, 1 megoldas, futasi ido = 0.03 sec.
18. pelda, 17x17, 36 adott szam, 24 megoldas, futasi ido = 32.26 sec.
19. pelda, 17x17, 88 adott szam, 1 megoldas, futasi ido = 0.02 sec.
20. pelda, 18x18, 183 adott szam, 1 megoldas, futasi ido = 0.04 sec.
21. pelda, 18x18, 43 adott szam, 3 megoldas, futasi ido = 10.30 sec.
22. pelda, 19x19, 199 adott szam, 1 megoldas, futasi ido = 0.03 sec.
Szeretnélek megkérni, hogy nézd meg melyik feladatoknál van szükség kiugróan
magas idõre, és ha megmondanád, hogy ezek a példák miben különböznek a
többitõl. Rengeteget segítenél ezzel, mert most már teljesen tanácstalan
vagyok, hol keressem a hibát. Segítségedet elõre is köszönöm,
A több mint 1 megoldást adó feladatok általában nem tartalmaznak redundáns
információt, és a (relative) kevés adott számot tartalmazók is. Úgy tûnik
fõleg ezek okozzák a gondot. Gondolkodjál redundáns korlátokon, de fõleg a
BOROTVÁLÁS bevezetését javasolom, szerintem az utóbbi nagyon egyszerû és
szinte biztosan segít.
Péter