|
0 / 0 / 0
Регистрация: 29.09.2018
Сообщений: 32
|
||||||
Хеш-таблица09.01.2019, 22:12. Показов 1606. Ответов 7
Метки нет (Все метки)
Всем, привет! Реализовал словарь на основе хеш-таблицы. Ключ - это буква, на которую начинаются слова, например, "а" - все слова на "а" и т.д. Задача такая: задаётся исходное слово, необходимо из его букв составить слова. Мой алгоритм работает так: переопределил ассоциативный контейнер так, чтобы ключами являлись буквы алфавита, т.е. значениями будут слова, которые начинаются на а, на б и т.д. После я заполняю ассоциативный контейнер words, который содержит слова, начинающиеся на определенную букву и ключами являются их длины. После мы ищем слова в words, длина которых не больше длины заданного слова( это хорошо работает на словах средней и маленькой длины). При длинных словах, чтобы избежать перебора всего словаря, создан контейнер letters_of_word который содержит не повторяющиеся буквы заданного слова. В начале заполнения структуры words проверяется условие на присутствие буквы в контейнере letters_of_word.(Это условие позволяет отсеять повторяющиеся буквы). Таким образом, мы проходим не весь словарь, а только слова, которые начинаются на буквы заданного слова. Можно ли улучшить данный алгоритм?) Исходный код:
0
|
||||||
| 09.01.2019, 22:12 | |
|
Ответы с готовыми решениями:
7
Хеш таблица Хеш-таблица Хеш-таблица |
|
1394 / 1023 / 325
Регистрация: 28.07.2012
Сообщений: 2,813
|
|||
| 09.01.2019, 22:33 | |||
|
Добавлено через 3 минуты
0
|
|||
|
0 / 0 / 0
Регистрация: 29.09.2018
Сообщений: 32
|
|
| 09.01.2019, 22:42 [ТС] | |
|
nonedark2008, слово - это строка(набор букв, например - "шишка"), записанная в контейнер word, берется из файла. Нужно найти такие слова из словаря, которые можно составить из заданного слова, т.е использовать те символы, которые есть в заданной строке.
Например в argv[2] задано слово шишка В argv[3] запишутся слова а и ишак к ш шик шиш шишак шишка
0
|
|
|
1394 / 1023 / 325
Регистрация: 28.07.2012
Сообщений: 2,813
|
|||
| 10.01.2019, 00:00 | |||
|
В первом случае не вижу способа лучше, чем последовательно читать каждое слово и сразу же его проверять на соблюдение условий. Ты в своем решении зачем-то разделил слова по первой букве: Второй случай сильно зависит от размера словаря, от ограничений по памяти и от необходимой скорости работы.
0
|
|||
|
0 / 0 / 0
Регистрация: 29.09.2018
Сообщений: 32
|
|||
| 10.01.2019, 17:10 [ТС] | |||
|
nonedark2008,
В принципе сложность моего алгоритма зависит от размера словаря, т.е линейна. Может быть можно как то улучшить ещё?)
0
|
|||
|
1394 / 1023 / 325
Регистрация: 28.07.2012
Сообщений: 2,813
|
||
| 10.01.2019, 18:19 | ||
|
Такого рода оптимизации имели бы смысл, если запросов было бы много, а так...
0
|
||
|
0 / 0 / 0
Регистрация: 29.09.2018
Сообщений: 32
|
|
| 10.01.2019, 18:29 [ТС] | |
|
nonedark2008, а если не оптимизировать чтение из словаря, а оптимизировать поиск подходящих слов?
0
|
|
|
1394 / 1023 / 325
Регистрация: 28.07.2012
Сообщений: 2,813
|
||
| 10.01.2019, 19:28 | ||
|
Взять каждое слово из словаря, отсортировать все буквы в алфавитном порядке. А затем из преобразованных слов построить префиксное дерево. По такому дереву можно передвигаться, сразу игнорируя те ветви, которые однозначно не могут быть порождены из заданного слова.
0
|
||
| 10.01.2019, 19:28 | |
|
Помогаю со студенческими работами здесь
8
Хеш-таблица Хеш Таблица
хеш таблица Хеш-таблица Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами
8Observer8 20.02.2026
Содержание блога
Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .
|
Конвертировать закладки radiotray-ng в m3u-плейлист
damix 19.02.2026
Это можно сделать скриптом для PowerShell. Использование
. \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json>
Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом.
# Check if. . .
|
Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI
Eddy_Em 18.02.2026
Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так:
https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347
Основана на STM32F303RBT6.
На борту пять. . .
|
Камера Toupcam IUA500KMA
Eddy_Em 12.02.2026
Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
|
|
И ясному Солнцу
zbw 12.02.2026
И ясному Солнцу,
и светлой Луне.
В мире
покоя нет
и люди
не могут жить в тишине.
А жить им немного лет.
|
«Знание-Сила»
zbw 12.02.2026
«Знание-Сила»
«Время-Деньги»
«Деньги -Пуля»
|
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 12.02.2026
Содержание блога
Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .
|
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 11.02.2026
Содержание блога
Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .
|