|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
06.11.2007, 16:15 | #1 |
Регистрация: 05.11.2007
Сообщений: 3
|
Поиск непарного числа в файле
в файле unmarried.dat через пропуск записаны номера кроликов, которые являются натуральными числами и не превышают 2•10^9.
в исходящем файле unmarried.sol записать одно число ( номер кролика) у которого нет пары Пример unmarried.dat 1 6 2 3 4 6 3 1 2 3 4 3 6 unmarried.sol 6 Задача нужна для паскаля!!! Темы называем по-нормальному!!! SupVis Последний раз редактировалось SuperVisor; 07.11.2007 в 08:24. |
06.11.2007, 16:40 | #2 |
Белик Виталий :)
Старожил
Регистрация: 23.07.2007
Сообщений: 57,097
|
Пробуй так:
Код:
I'm learning to live...
|
06.11.2007, 17:16 | #3 |
Delphi/C++/C#
Участник клуба
Регистрация: 29.10.2006
Сообщений: 1,972
|
Решение правильное
Но задачка знакомая... Это типичная олимпиадная задача, с ограничением по времени, а количество чисел во входном файле на (кажется) 3 тесте более 4000. В итоге программа не пройдёт по времени. На олимпиаде выход нашёл - через множества (set of) |
06.11.2007, 17:19 | #4 |
Регистрация: 05.11.2007
Сообщений: 3
|
zetrix
скажи как правильно пожайлуста ! Для паскаля! |
20.12.2009, 14:13 | #5 |
Форумчанин
Регистрация: 10.10.2009
Сообщений: 680
|
Решается за линейное время, xor-ом, сначала ответ =0, потом в цикле
Код:
Если на сервере есть место для тестов, то могут дать несколько миллионов чисел во входном файле и 1 секунду времени. Stilet , решение неверное. Ведь, согласно огриничениям, могут быть числа длиною более 1 цифры. Даже если и за таким вот принципом, то надо сначала допмассивы заполнить под длину, потом еще полчаса извращатся... |
20.12.2009, 16:47 | #6 |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
LeBron, надеюсь, Вас не смущает, что тема два года назад была?
Алгоритм с XOR просто отличный. простой и супербыстрый. Есть один нюансик. А где в условии сказано, что такой кролик ОДИН?! Если в списке есть несколько кроликов без пары, то ответ будет XOR номеров всех этих кроликов - то бишь - какое-то бессмысленное число... |
20.12.2009, 19:00 | #7 | |
Форумчанин
Регистрация: 10.10.2009
Сообщений: 680
|
Цитата:
Написано вот сдесь: , да и сразу видно, что такое число одно - по формулировке задачи ясно всем, кто хоть немного с задачами программирования знаком, для нескольких чисел она неразрешима подобным образом(лучший более-менее удобный вариант дает n*log(n), можно быстрее с большой константой) и не несет в себе ценности задачи (для нескольких чисел придется срезать ограничения и тогда решение больно уж примитивное). |
|
20.12.2009, 20:02 | #8 | |||
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
Цитата:
и ещё. чисто удовлетворения любопытства ради... Цитата:
я бы лично, если бы такая задача встретилась мне в жизни, решал бы её через динамические структуры (хоть массивы, хоть связные списки) или коллекции. Там принцип такой - если число уже есть в НАБОРЕ (потребуется поиск), то удаляем имеющееся число из набора, если его там нет, добавляем. плюс такого решения - в результате имеем ВСЕ непарные числа... минус - сложность реализации и, разумеется, высокие требования к памяти и скорости работы... |
|||
20.12.2009, 20:40 | #9 | ||
Форумчанин
Регистрация: 10.10.2009
Сообщений: 680
|
Цитата:
Цитата:
Пример: после сортировки у нас 0 0 0 0 1 1 1 1 1 1 1 2 3 4 4 4 4 5 5 6 6 7 7 7 7. Нечетное число раз встречаются 1, 2, 3 - эти числа без пары. |
||
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Поиск в файле | Zandrey | Microsoft Office Excel | 8 | 05.09.2008 12:23 |
поиск в файле | Elm0 | Паскаль, Turbo Pascal, PascalABC.NET | 14 | 07.06.2008 22:41 |
Расчет числа строк в типизированном файле | 1234 | Паскаль, Turbo Pascal, PascalABC.NET | 6 | 20.05.2008 11:14 |
являются ли числа в файле упорядоченными | Pohmel | Помощь студентам | 6 | 21.04.2008 16:12 |
Поиск в файле | asale | Microsoft Office Excel | 1 | 15.05.2007 23:33 |