За два курса в университете понял, что я ни черта не умею программировать. Сейчас хочу решить эту проблему. Для думаю нужно выяснить, что мне нужно повторить. Алгоритмическое мышление хромает и знания языка хромают. Вот выкладываю задачку которую пытался решить. Условие задачи: Найти количество различных элементов в массиве. Задачки решена не правильно, но пока я не могу понять как решить. С помощью этой задачи хочу выявить свои пробелы и получить рекомендации как их устранить. Заранее благодарен. 



Это сообщение отредактировал(а) ArniLand - 20.6.2011, 21:57

так а где?

Извините, исправил первый пост.

эта задачка интереснее решается с помощью хеш-таблицы.. привожу самый приметивный пример:



алгоритм можно улучшить, если не брать чистый индекс для хеша, а получать его другим путем.. тогда можно сократить размер результирующего массива..

сорри что оффтоп и на Си.. 

Это сообщение отредактировал(а) fish9370 - 20.6.2011, 22:05

Это сообщение отредактировал(а) triclosan - 20.6.2011, 22:26

fish9370
старо))) может памяти не хватить

я же говорю, что нужно хеш улучшить.. сделать перемешаную таблицу..   

пример учебный.. зато как изящно..

Это сообщение отредактировал(а) fish9370 - 20.6.2011, 22:57

fish9370 
при чем тут определение "хеш"? 

набери в google: таблица с вычисляемым входом

вот это изящно , где esi= начала массива arr_res, ebp = элемент массива arr
но это нифига не хеш ))) 

500mhz, ты тему читал? я уже и извинился за оффтоп.. и рассказал как нужно сделать.. что нужно доработать прогу и использовать перемешаную таблицу - специально для тебя писал..

а ты приводишь код на асме? мужик, че ты там куришь?   

fish9370
 какая разница на чем код ? ))) тут главное алгоритм )))

хорошо, где у тебя будет хранится результирующий массив? ты упрекнул мой алгоритм, что ему не хватит памяти при больших числах.. переадресую этот вопрос тебе..

как поведет себя твой алгоритм при больших числах? сколько памяти понадобится?

4 gb в худшем варианте )))

всего лишь?

я использую перемешанную таблицу и сведу размер результирующего массива к размеру входного.. для любых чисел..

а тебе слабо?   

да запросто ) как два байта переслать

докажешь?   

на пиво?   

если ты из Москвы, то давай на пиво..   

не я в киеве )

вобщем если есть интерес и время, то сделай.. вообще было бы прикольно посмотреть это на асме..   

Горячие финские парни, не спорьте.

Мой вариант.
В СТЛ есть мап. Он как будто специально сделан для такой задачи.

Вот собственно и всё! Осталось только вывести количество каждого значения.

http://liveworkspace.org/code/2c2bee1993a4...69b3cb5bc84161c

Это сообщение отредактировал(а) volatile - 21.6.2011, 01:16

да.. он для такой задачи.. вообще я этому научился еще на PHP, там это развито еще круче, я специально не стал этого приводить.. 

volatile
да мы уже не о том спорим )))
если максимальный элемент массива dword 0xffffffff то памяти может не хватить 

500mhz, вообще то если просто перевести код fish9370 на асм то получится что он просто будет жрать много памяти особенно при отрицательных значениях в массиве.



разве не правильней будет



вроде это то что нужно автору

Это сообщение отредактировал(а) asmdzen - 21.6.2011, 09:51

asmdzen, а что по-твоему является различными элементами массива?
На мою логику так: 10, 8, 9, 2. 
Т. е. всего 4 различных элемента. А твоя программа выводит 6.
И второй цикл ты начинаешь с i + 1, а я все же думаю, что нужно сравнивать со всеми элементами массива, кроме самого себя. Например, так - дошел ты до последней единички в массиве и сравниваешь ее с 8, 9, 2. И получается, что она различный элемент? Не думаю.

Это сообщение отредактировал(а) Teleport - 21.6.2011, 11:54

Teleport, различные элементы я понимаю 10, 8, 9, 3, 2, 1, то есть все элементы без повторов
ведь не сказано же "не повторяющихся" элементов. может я неправильно понял условие. покажите как будет правильно по вашему.

В условии сказано 

По-моей логике элементы различные - это 10, 8, 9, 2.  А элементы 3 и 1 повторяются и не являются различными.

Teleport, т.е. различных != уникальных?
по моей логике 10, 8, 9, 3, 2, 1 все различные между собой, остальные уже повторы ))

asmdzen, не знаю кто из нас прав  
Твою логику понял. 

извеняюсь за некропостинг,но заинтерисовала задача,решил попробовать решить,вот что пришло на ум



что скажите по поводу такого алгаритма решения
алгоритм построен на том,что программа берет массив и проверяет все элементы массива предшествующие этому массива и если не находит такого-же то инкрементирует счетчик,наверное можно было решить более красиво с таким же алгаритмом,у меня вышло весьма неуклюже

Это сообщение отредактировал(а) ShadowC - 3.10.2011, 00:43

ShadowC, время выполнения вашего алгоритма N^2.
Чтобы почувствовать нужно взять большой массив.
Если в массиве миллион элементов, то понадобится порядка 10^12 итераций.

Другими словами программа будет работать целый день, тогда как можно все сделать за 1 минуту.

ну наверное можно даже с моими знаниями(8-ая глава книги дейтлов),но я сам обучаюсь без учителя,поэтому у меня сейчас не стоит вопрос об эффективности программ,а все силы направлены на то что бы решить задачу,думаю когда поднатаскаюсь до нормального уровня там можно будет и быстродействие подумать...

P.S. а вообще есть такая идея,не знаю поможет ли - вначале отсортировать массив и в отсортированном массиве такой алгоритм пойдет просто мгновенно,потому что повторяющиеся элементы будут стоять рядом и шаг для проверки любого элемента массива будет равен одному

Это сообщение отредактировал(а) ShadowC - 3.10.2011, 15:07

Этот вариант был давно уже предложен. Правда, он тоже не особо оптимален из-за использования двусвязного списка.



Это сообщение отредактировал(а) bsa - 3.10.2011, 15:42

я пренципиально не читал тему и думал сам,а то так не интересно...
кстате bsa ты опытный в этом деле у меня к тебе вопрос ну и ко всем кто на него может ответить,какой самый быстрый алгоритм сортировки?

Это сообщение отредактировал(а) ShadowC - 3.10.2011, 15:52

хоть вопрос не мне, все равно кой чего отпишу:

если сильно интересует эта тема читай книгу "Искусство_программирования" Дональда Кнута, том3

если побыстрому то на вики есть кое-что

я точно незнаю какой, оно вроде зависит от того сколько элементов