2007-01-18 01:04
by Vasil KolevОтидох на ИББ, не бях ходил от доста време … Оказа се забавно, въпреки че повечето хора закъсняха, и Бобсън като най-съвестен беше ни чакал 40 минути :). Видях се Лора (за която просто не мога да измисля достатъчно добър комплимент), с която простяхме леко и уплашихме хората, накрая Велин се опита да ме изгори с цигара и аз го залях с бира заедно със съседа му :). После Антон написа накратко едно greedy, което да решава задачата за обхождане на цялата шахматна дъска с ход на коня, та го тествахме, и се оказа, че се дъни при дъска 4×4 (за която не се сещам дали има решение), за 35×35 и после за още няколко случая (тествахме до 49×49).
(Ако Антон се навие, ще кача source някъде, така и така мисля да занимая няколко болни човека с тоя алгоритъм :) )
Иначе деня беше стабилно весел, почна се с едно кафе за събуждане, една бира за успокояване и после още 5 валериана (което пак не помогна особено, та на ИББ изпих още няколко бири). Обаче на принципа “Още може!” ще продължавам напред, па да видим кога организма ще реши, че няма да ме трае повече :)
Tags: ИББ
January 21st, 2007 at 21:10
Да, за 4×4 има решение, дори, доколкото си спомням, поне три различни (с точност до ротации и отражения, разбира се). Хммм… greedy? точно за тази задача? как? :) дайте да видим :)
January 22nd, 2007 at 14:15
Брех, с това грийде в историята, че влезете :)
April 20th, 2007 at 19:57
Има greedy-алгоритъм, решаващ задачата за доста дъски. Проблемът е, че може да забие и трябва всъщност да се напише backtrack, който за дъска с 3-цифрени размери влиза в сила 2-3 пъти максимум. Оптимизацията е да обхождате първо тези квадратчета, които могат да бъдат достигнати от най-малко места.
April 20th, 2007 at 22:29
Уф, аз така и така не го публикувах – а е точно това решението, и се дъни някъде на около 49×49 дъска. Имах аз чуството, че е известно :)