|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
19.06.2016, 15:55 | #1 |
Регистрация: 18.08.2014
Сообщений: 8
|
Восполнить пробелы в знаниях
Добрый день, уважаемые программисты! Хочется задать теоретический вопрос. Решал я задачку на одном известном ресурсе. Задача называется A-B. Два неотрицательных числа, которые не превышают 10^1000 степени. Нужно вычесть одно из другого. Решил я цифры числа хранить в массиве.
Отсюда суть вопроса возникает! Создал свой тип Код:
Написал код, отправил на проверку и обнаружил, что программа прошла 13 тестов из 15. На 14 завалилась. Целый день я тестил свою программу разными входными данными и даже дважды ее улучшал, но не в том направлении, т.к. 14 тест мне уже в восьмой раз показывал Wrong answer. И тут я просто от безысходности заменил -9..9 на integer и всё! Задача была сдана! Объясните пожалуйста, почему так???? Ведь цифры не превышают диапазон -9..9, что там такое случилось? И попутно задам второй вопрос, чтобы не засорять форум: что эффективнее использовать(память/время) для хранения чисел: список или же динамический массив? Спасибо! |
19.06.2016, 17:32 | #2 | |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
Цитата:
покажите ваш код. Но вообще, ваш фокус с -9..9 не мог дать большого выигрыша. Вы сколько хотели выиграть? 1002 записи Integer в массиве это 4 кибобайта (для 32 битных приложений). Вы сколько выиграть хотели, 2 килобайта? |
|
19.06.2016, 17:34 | #3 | |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
Цитата:
Чаще всего динамический массив занимает меньше места и более эффективен для прямого доступа к любому элементу. Но ещё раз повторю - всё зависит от задачи и от используемого алгоритма решения. Последний раз редактировалось Serge_Bliznykov; 19.06.2016 в 21:24. |
|
19.06.2016, 19:40 | #4 |
Регистрация: 18.08.2014
Сообщений: 8
|
Большое спасибо за ответы
|
19.06.2016, 21:45 | #5 |
мальчик-помогай =)
Форумчанин
Регистрация: 16.09.2010
Сообщений: 522
|
Могли бы человеку указать и на очевидные ляпы:
- отрицательные числа вовсе не стоит хранить в "разрядах"... диапазон сокращаем до 0..9 + храним знак числа рядом - НЕ эффективно хранить числа в десятичной системе... в лучшем случае, это 1 байт на разряд (эти -9..9 никто не упакует в 5 бит, а сохранит как полный байт, который ещё и "разнесёт" до 4 байт, при типичных настройках и без packed-a) - если перескочить теорию, то стоит хранить в Word, а вычисления производить в Cardinal....тогда основные операции (сложение, вычитание и умножение) можно реализовать относительно просто, разделяя промежуточный результат простыми mod/div, битовыми операциями или трюками с памятью (читать Cardinal как два Word-а) - очень стоит почитать теорию про длинную арифметику...... можно реализовать простые операции и "в лоб", но это будет намного менее эффективно, чем специальные алгоритмы |
20.06.2016, 07:56 | #6 | |||
Старожил
Регистрация: 04.02.2009
Сообщений: 17,351
|
Цитата:
Цитата:
Я бы так делал: Код:
Цитата:
Маньяк-самоучка
Utkin появился в результате деления на нуль. Осторожно! Альтернативная логика Последний раз редактировалось Utkin; 20.06.2016 в 08:07. |
|||
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Паскаль. Пробелы. | minimesqa | Паскаль, Turbo Pascal, PascalABC.NET | 4 | 12.04.2013 19:13 |
пробелы :( | Odyssey | C# (си шарп) | 10 | 17.04.2012 16:58 |
Какие то пробелы | serres | PHP | 2 | 03.05.2011 13:44 |
Пробелы | Progs1024 | Помощь студентам | 1 | 25.10.2009 21:06 |