argon bulletin board

Факултети => Факултет по математика и информатика => Темата е започната от: Dobromir в 07.06.2003, 09:21:00

Титла: Zadachka-zakachka
Публикувано от: Dobromir в 07.06.2003, 09:21:00
Даден е едносвързан списък, т.е. всеки елемент има указател към следващия, освен това е даден указател към началото на списъка (към първия елемент); не е известен броят на елементите. Ако списъкът е правилно създаден, указателят на последния елемент трябва да бъде nil (празен, не сочи към нищо). Поради възникнала грешка указателят на последния елемент сочи към някой от предишните. Да се оправи грешката възможно най-бързо и с най-малко количество допълнителна памет.

   Съществува алгоритъм, за който времето е линейна функция на дължината на списъка, а броят на допълнителните променливи е константа.

   Доколкото знам, задачката е от тест на Microsoft.

Титла: Zadachka-zakachka
Публикувано от: gefix в 17.06.2003, 13:42:00
Mnogo zaribitelna zadachka - okolo chas se muchih da razbera az li neshto propuskam, v uslovieto li neshto lipsva, nqkakva shega li e tova? Okaza se che vsichko e tochno i nikude nqma greshka - reshenieto e malko "tarikatsko", no go ima. Ako se predavate i ne vi se misli poveche - mojete da poglednete na
http://info.datacom.bg/gefix/zadachka/reshenie.html (http://info.datacom.bg/gefix/zadachka/reshenie.html)
Makar che az na vashe mqsto bih se pomuchil oshte malko - trudno e no e mnogo got kogato sam se setish za neshto. Ne znam dali reshenieto koeto az otkrih e onova za koeto se spomenava v uslovieto - sushtestvuvat mnogo nachini da se postigne neshto s ednakvi sredstva.
Ako se setite za neshto drugo ili imate vuprosi - kazvaite navreme che skoro idva lqtoto i shte otlitam.
@mail@: mitaka911@gmx.net
Титла: Zadachka-zakachka
Публикувано от: Dobromir в 17.06.2003, 17:28:00
Страхотно решение. И добре оформено.