Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 15.08.2009, 01:04
гость

 
Сообщений: n/a

Нужна помощь по алгоритмам
Добрый день.
Нуждаюсь в небольшой консультации по двум задачкам (с++).

1)Дан массив размера N из целых чисел, принимающих значения от 1 до M, при этом одно число в этом массиве повторяется 2 раза. Найти это число за время O(N)

2)Решить как минимум двумя способами (простым и быстрым) следующую задачу : написать функцию, которая возвращаетколичество нулевых бит в символах строки (не считая нулевой символ в конце строки). На входе алгоритма - const char*.

Заранее спасибо.
  #2  
Старый 15.08.2009, 07:38
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Это очень распространенные задачки.
Они рассчитаны на то, что человек знает некоторые мелкие хитрости, или может сам их придумать.
Если подсказать, то вы будете знать пару малоценных трюков и еще пару таких, что иногда могут пригодиться.
Однако реальная польза будет, только если самостоятельно попробовать решить. Начинайте решать, генерируйте идеи, далее подскажем. А без усилий со стороны автора - не хочется что-то..
  #3  
Старый 15.08.2009, 22:16
гость

 
Сообщений: n/a

Цитата:
1)Дан массив размера N из целых чисел, принимающих значения от 1 до M, при этом одно число в этом массиве повторяется 2 раза. Найти это число за время O(N)
Используй поразрядную сортировку (radix sort), потом пройдись по отсортированному списку и найди пару соседних одинаковых элементов. Или используй хеш-таблицы, будет O(N) времени *в среднем*.

Имей ввиду, что в стандартной библиотеке C++ нет ни того ни другого, кстати.

Цитата:
2)Решить как минимум двумя способами (простым и быстрым) следующую задачу : написать функцию, которая возвращаетколичество нулевых бит в символах строки (не считая нулевой символ в конце строки). На входе алгоритма - const char*.
Задание поставлено некорректно или неполно. Что значит число нулевых бит в строки? Что там происходит с кодировками? Пусть у меня строка "вася" подана в кодировке UTF8 (нынче стандартная кодировка во всех современных ОС кроме виндовс), скока там нулевых бит будет? И как это понимать, какой способ будет простым, какой быстрым - тут всё слишком субъективно в такой задаче.
  #4  
Старый 15.08.2009, 23:15
гость

 
Сообщений: n/a

Сообщение от гость Посмотреть сообщение
1)Дан массив размера N из целых чисел, принимающих значения от 1 до M, при этом одно число в этом массиве повторяется 2 раза. Найти это число за время O(N)
Я встречал очень похожую задачку. Только M=N-1. В этом случае все что было нужно это проссуммировать массив а затем вычислить x=SUM-M(M-1)/2+M. x это и есть нужное число.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Программы на C++, нужна помощь starcode Реализация, исходники, языки 4 14.08.2009 18:29
Нужна помощь по ассемблеру! jekahm Реализация, исходники, языки 2 10.06.2009 14:33
нужна помощь гость Работа 0 13.05.2009 01:19
нужна помощь cheater_Ok Реализация, исходники, языки 5 15.03.2008 16:49