Повідомлень: 151 Звідки: Lviv NU FAMI Зареєстрований: 30.04.06
Опубліковано 14-09-2009 00:26
Ого! Я глянув сорс і мені стало цікаво його поправити докінця, щоби він працював, був дуже здивований кількістю помилок. Перша помилка полягає в тому, що в нас порядок обходу вершин буде не обовязково проти годинникової стрілки. Друга помилка, полягає в переповненні базового типу при деяких обрахунках, а саме, у двох місцях, тобто різних циклах. Третя помилка полягає в відносно довгому виконанні допоміжної функції, спробуйте її оптимізувати, існують набагато швидші методи, пошукайте в інтернеті.
Так, першу помилку виправив.. Там неуважність, ну то таке, тепер ВА 6) Це вже краще... За другу помилку зрозумів, та ше не виправив... Хіба сильно впливає на час?! А от за переповнення типу я не зрозумів.. Можна детальніше?)
Повідомлень: 151 Звідки: Lviv NU FAMI Зареєстрований: 30.04.06
Опубліковано 17-09-2009 20:56
Хіба сильно впливає на час?
Дуже, таймліміт дало
А от за переповнення типу я не зрозумів.. Можна детальніше?)
Прикинь якою буде максимальна площа, при заданих умовах, та порівняй з максимальним значенням 4-байтового інтеджера, адже всі обчислення при твоїй реалізації ведуться в інтеджерах, а вже пізніше приводяться до типу з плаваючою комою.
Ну, поправив.. Вирішив навить мову змінити... От шо вийшло.. ВА4... Чого? Масив не переповнюється, використовую __int64 і все ніби норм.. Знайшов оптимальнішу підпограму і помилок з вищеперерахованих здається немає! Так ж у чому помилка? Допоможіть, будь-ласка!((
Повідомлень: 151 Звідки: Lviv NU FAMI Зареєстрований: 30.04.06
Опубліковано 11-11-2009 00:57
Спробував виправити сорс так щоби він став правильним. Це було не так просто.
1) Переповнення там далі присутнє.(Підказка. Якщо множити два інти то результатом буде також інт, незалежно якому типу це значення присвоюється).
2) Ділення використовується цілочисельне і зберігається результат у ціле число! Нехай x та y - непарні додатні числа, звісно ж цілі. Тоді [x / 2] + [y / 2] = [(x + y) / 2] - 1. Де [.] - ціла частина, себто вжито знову ж таки цілочисельне ділення. Подумайте над цим.
3) Якщо від змінної беззнакового типу відняти більше значення, ніж в ній збережено, то отримається практично той самий оверфлов, тільки з іншого боку.
Birthday(s):
![mylyanyk.ivan [Lviv_NU]](../themes/Brasil-Fusion/forum/yahoo.gif)
.. От шо вийшло.. ВА4... Чого? Масив не переповнюється, використовую __int64 і все ніби норм.. Знайшов оптимальнішу підпограму і помилок з вищеперерахованих здається немає! Так ж у чому помилка? Допоможіть, будь-ласка!((
