[Homework] C# Basics - Conditional Statements - Problem {13} - Софтуерен университет

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

p.mitov 6 Точки

[Homework] C# Basics - Conditional Statements - Problem {13}

Колеги,

При решаването на задача 13. Triangle от домашното за Условни конструкции срещнах една неочаквана трудност. При изчислението на страните на триъгълника се получава закръгление (15-16 знак при double), в следствие на което за определени входни данни се получава некоректен резултат.

Тествах и авторското решение, качено в judge - също връща грешен отговор в някои случаи.

Всеки може да го тества с точки A(0,0), B(2,2) и C(6,6) - това е само един от множеството примери, които дават грешка. Тези три точки са на една линия и не могат да образуват триъгълник. Но програмата казва, че могат. С включването на дебъгера лесно се вижда защо се получава така - от закръгление едното от неравенствата на триъгълника става вярно.

Опитах да го избегна чрез работа с decimal, но Math.Sqrt си иска double, което оттам насетне обезсмисля работата с decimal.

И тъй като всичко това се случва преди да го кача в judge, пробвах няколко други варианта като с още малко геометрия в крайна сметка стана (без да се ползват неравенствата на триъгълника). Не гледайте, че имам качени няколко грешни решения в judge - на друго се дължат.

В коментарите към домашното ми е препоръчано (и съвсем основателно) да ползвам неравенствата на триъгълника, както ни съветва самото условие на задачата. Надявам се това да не се е отразило на оценката, макар и да не смятам, че се е отразило. По никакъв начин не искам да дискредитирам оценката на домашното, колегата е дал добри препоръки и забележката не е насочена към неговата работа.

Но, това, което ме притеснява повече, е следното - възможно ли е в judge системата да не се тестват достатъчно изчерпателно решенията и в крайна сметка да може да се признае невярно решение. Под невярно имам предвид даващо грешен резултат, а не грешно като концепция. Защото тук е точно такъв случаят - аз изгубих около час да се боря със заобикаляне на закръгленията, а се оказва, че това изобщо не е било необходимо. Допускам, че judge системата проверява дали каченото решение дава същите отговори, както авторското, и затова дава 100 точки.

Надявам се някой да вземе предвид този проблем и да се избегнат подобни случаи занапред.

Поздрави,

Пламен Митов

P.S. Ако някой има решение само с неравенствата на триъгълника, което да дава верен отговор с цитираните по-горе входни данни, нека да покаже как го е постигнал.

Тагове:

12/07/2014 23:15:53 Programming Basics

Anonymous:

Има вече отворена тема за домашно Conditional Statements: https://softuni.bg/forum/questions/details/321

Bi0GaMe Trainer 389 Точки

Заповядай моето решение на задачата.

http://pastebin.com/Wsnrq8Kv

Judge системата има записани тестове, които ги рънва през програмата ти. Има определени инпути и след като ги въведе, judge-а проверява дали аутпута е същия, като този който той има записан. Т.е. не се проверява аутпута по авторското решение, а си има записани тестове.

13/07/2014 00:42:57

Bi0GaMe Trainer 389 Точки

Отне ми 1 час, но успях да намеря метод за корен квадратен, който не дава голяма грешка. Ето го кода, който минава всички тестове + някои който сам тествах.

http://pastebin.com/pgRUtnvk

13/07/2014 01:25:28

p.mitov 6 Точки

Много благодаря за кода. Колкото и да ми е странно, мисля, че нещо подобно бях сътворил, ама нещо не сработи. Не съм си запазил работния код като опитвах да го направя decimal - явно някъде или съм пропуснал нещо или съм прекалил с конвертирането (може би някъде съм направил decimal към double и после обратно). Поне разбрах, че може да се конвертира в decimal без загуба. Мислех, че след като Math.Sqrt работи с double, закръглението става още преди да се конвертира в decimal. Пробвах, не стана и реших, че не може, но очевидно съм го сбъркал. За Judge - ок. Само че пуска и грешни, т.е. не се тестват всички принципни варианти.

13/07/2014 02:44:45

Bi0GaMe Trainer 389 Точки

То се оказва, че този код който използва decimal пропуска грешки, но този, който не използва math.sqrt върши перфектна работа.

13/07/2014 08:24:17

Filkolev 4482 Точки

Аз ползвах double и неравенствата на триъгълника и нямах проблеми. Проверих няколко домашни в които решението беше подобно, и никъде нямаше проблем с Judge. Мисля, че на този лаптоп го нямам моето решение, ще проверя и ще сложа линк впоследствие; а и Pastebin в момента е блокиран. Предполагам по форума ще може да намериш решение, например в общата тема за домашните. Ще погледна междувременно и авторското да видя дали наистина дава грешка; аз като успея сам да се преборя с дадена задача рядко гледам авторското решение.

Между другото напълно е възможно аз да съм ти проверявал домашното, звучи като коментар, който аз бих дал. В този случай може да си спокоен, за задачи със звезда не отнемам точки ако нещо не е наред, а в твоя случай коментарът вероятно е бил по-скоро за ефикасност, а не толкова че кодът е грешен. Имам предвид, че за обемен/неефективен/странен алгоритъм точки не вземам, ако работи. Нали, важното е да работи, а човек се учи и след време ще разбере по-добър начин, или пък ще го посоча в коментарите направо.

Интересно ми е това, което казваш - "от закръгление едното от неравенствата на триъгълника става вярно". За да е триъгълник, трябва и трите неравенства да са верни едновременно, не може 1-2 да са верни и да приемем фигурата за триъгълник. Ако алгоритъмът ти действително проверява неравенствата с логическо "или" от там идва проблемът, трябва да се замени с "и".

По последният ти въпрос - не е възможно Judge да даде точки за грешен отговор. Има определен брой тестове, входните и изходните данни са зададени (и може да ги видиш от секцията на мартенския курс, най-долу, трябва да избереш архивния файл на съответния изпит - в случая е вариант 5). Възможно е обаче решението на дадена задача да не е съвсем коректно, но въпреки това да даде 100/100 - това е в случай, че тестовете не са направени изчерпателни, т.е. авторите не са се досетили да проверят някои случаи. Но това не ни ощетява откъм оценка, напротив, но може да ни даде излишно самочувствие, че сме решили дадена задача, а тя реално да не е 100% вярна.

Едит: Прав си, авторското решение дава грешен отговор при посочените от теб координати (понеже не виждам някаква особена разлика между моето и авторското, без да имам своя код мога да кажа, че и моето ще даде същия отговор).

В случая важното е, че алгоритъмът е абсолютно верен като концепция, а че поради особеностите на закръглянето на дробни числа в изчислителната техника получаваме някои странности, това не е толкова съществено. Възможно е авторът на задачата всъщност да е наясно с проблема, но да не го счита за важен. При 100/100 приемаш, че си постигнал това, което се е искало от теб, а това, че си успял да намериш пробойна някъде, е супер. Ако успееш и да я заобиколиш, още по-добре. Но недей да отделяш твърде много време на този проблем. На изпит се бориш за точки, дори алгоритъмът ти да не е идеален. А имаше и случай, в който авторското решение не отговаряше на условието (между текстовото условие и дадените примери към задачата имаше разминаване) и се наложи да си коригирам формулата. Т.е. безгрешни хора няма.

13/07/2014 09:21:30

Hristo_Penchev 389 Точки

Здравей, колега,

Не мога да открия решението ти, но ми е интересно - как проверяваш дали трите точки образуват триъгълник? С неравенства просто е най-лесно. Иначе сигурно има и други начини, но не ми хрумват в момента. Имам някакъв спомен от някъде, че double оставя паразитни числа и не е напълно точен, съответно от там може да ти дава, че трите точки са на една линия, а да не са всъщност. В момента само гадая, понеже не съм видял кода ти.

Както и да е, ето моето решение с double и неравенства. Просто е и работи. Сложих и някои коментари:

http://pastebin.com/NFT7B4K1

13/07/2014 10:21:07

Filkolev 4482 Точки

Проблемът на колегата идва оттам, че е намерил точки, за които авторското решение и Judge дават грешен отговор (не че не му признават точки, а самият отговор подаден на Judge не е верен).

Трите точки с координати (0, 0), (2, 2) и (6, 6) лежат на една права, но проверката чрез неравенствата на триъгълника връща true и лице на "триъгълника" - 0.0 или нещо такова. Т.е. заради неточностите при работа с floating point числа неравенствата на триъгълника излизат верни по грешка.

Аз лично след като получих 100 точки хич не съм се заглеждал дали има някъде такива несъответствия, макар че със сигурност проверих поне няколко точки, които лежат на една права, но явно не съм уцелил такива, за които се получава грешка (вероятно има и други освен посочената тройка).

13/07/2014 10:41:53