Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 16, средняя оценка - 4.94
Leonman
15 / 15 / 0
Регистрация: 17.06.2012
Сообщений: 270
#1

Комбинаторика. Вывести все слова, которые можно составить из данных букв - C++

11.07.2015, 18:54. Просмотров 2424. Ответов 33
Метки нет (Все метки)

Всем привет.

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

Задание:
Вывести все слова, которые можно составить из данных букв, длинна слова соответственно тоже дана.

Вот я и подумал. Полюбому надо использовать размещение из n(количество всех данных букв) по m(длина слова). Начал рыть просторы, но ничего толком не нашел. Были варианта, но все они работают очень долго, так как на вход подаются довольно большие значения n и m(например n = 20, m = 13).

Немогли бы вы, могучии знатоки алгоритмов размещения, помочь мне в с данным вопросом, тоесть предоставить алгоритм, который не работал бы пол часа, ну или дать ссылки, где бы я мог почитать полезную информацию?

Спасибо за внимание.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.07.2015, 18:54
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Комбинаторика. Вывести все слова, которые можно составить из данных букв (C++):

Найти в файле все слова, которые можно сложить из букв заданного слова - C++
Дано слово р и файл f.найти в файле f все слова которые можна сложить с букв слова р.

Вывести те слова, которые отличаются от последнего слова и удовлетворяют условию, что в слове нет повторяющихся букв - C++
Короче я сделал так #include <stdio.h> #include <ctype.h> #include <string.h> #include <stdlib.h> void main() { int const...

Можно ли из букв слова X составить слово Y? - C++
проверьте , можно ли из букв слова Х составить слово У.Пожалуйста помогите , вобще не понимаю как это делать(

Вывести все слова текста, которые отличны от последнего слова, предварительно преобразовав их - C++
Решить задачу на обработку текста, используя функции работы со строками. Предполагается, что исходным является текстовый файл. В текст...

Определить, можно ли из букв одного слова составить другое - C++
Даны два слова, состоящие из одинакового количества букв(количество букв известно заранее). Определить, можно ли из букв одного слова,...

Определить сколько слов можно составить из букв прочитанного слова - C++
Прошу помощи, задание : Считываю слово с файла, например, abb,нужно посчитать, сколько других слов можно из него составить и вывести. Т.е....

33
Croessmah
Ушел
Эксперт CЭксперт С++
13557 / 7707 / 872
Регистрация: 27.09.2012
Сообщений: 18,996
Записей в блоге: 3
Завершенные тесты: 1
11.07.2015, 19:01 #2
Цитата Сообщение от Leonman Посмотреть сообщение
но все они работают очень долго
угу
Цитата Сообщение от Leonman Посмотреть сообщение
(например n = 20, m = 13)
если все буквы разные, то у нас имеется 81920000000000000 (2013) различных комбинаций.

По сути, у нас просто анаграмма.
Как вариант - достать словарик слов и в нем искать слова, которые можно составить из данных букв :-)
0
Leonman
15 / 15 / 0
Регистрация: 17.06.2012
Сообщений: 270
11.07.2015, 19:43  [ТС] #3
Croessmah, собственно это второй этап. У меня была такая идея, что сначала я получу массив всевозможных слов, которые составленны из данных мне букв, а после сравниваю массив с полученными словами и массив слов из словаря и считаю сколько совпадений. Но для этого надо получить все возможные варианты слов.
0
D_Gon
24 / 13 / 5
Регистрация: 09.07.2015
Сообщений: 47
11.07.2015, 20:06 #4
20*19*...*10*9*8
Комбинаций 482.718.652.416.000 ~ 5*10^14
Частота моего процессора 3,1ГГц ~ 3*10^9
Пусть процессор составляет слово за 1 такт
Тогда мне нужно ( 5*10^14 )/( 3*10^9 ) секунд ~ 1.5*10^5 ~ 43 часа
Вывести на консоль гораздо дольше.
0
S_el
2113 / 1633 / 308
Регистрация: 15.12.2013
Сообщений: 6,400
11.07.2015, 20:12 #5
Цитата Сообщение от Leonman Посмотреть сообщение
Вывести все слова, которые можно составить из данных букв, длинна слова соответственно тоже дана.
Проще словарь перебрать на совпадение.Так оно намного быстрее будет.
0
Excalibur921
546 / 383 / 59
Регистрация: 12.10.2013
Сообщений: 2,656
11.07.2015, 20:17 #6
Цитата Сообщение от Leonman Посмотреть сообщение
Вывести все слова, которые можно составить из данных букв, длинна слова соответственно тоже дана.
Комп может переставлять буквы хаотически это будут слова со значением? Нет… значит нет другого способа как создавать огромную базу данных по типу слова длинной 3 буквы))) из таких букв потом из таких…
Разве может быть альтернатива? А если просто переставлять буквы будет абракадабра для человека но не для алгоритма, А потом искать опять по огромной базе существует ли такое слово у человеков. А сленг?
0
Leonman
15 / 15 / 0
Регистрация: 17.06.2012
Сообщений: 270
11.07.2015, 20:18  [ТС] #7
S_el, так мне же его надо переберать, когда мне есть с чем сравнивать(тоесть санчала надо получить возможные варианты) или что вы имеете ввиду?
0
ampermetr
23 / 23 / 9
Регистрация: 01.05.2015
Сообщений: 174
11.07.2015, 20:23 #8
Leonman, я бы сделал наоборот - разбил бы орфографический словарь на 30 (или 31, не уверен есть ли слова, начинающиеся на Ы) файл. К примеру искомое слово содержит 10 букв, значит нужно перебрать варианты всего из 10 файлов. Потом отсеиваем слова, не содержащие заданных букв, и в конце отсеиваем слова длиннее 10 букв. Мне кажется так будет намного быстрее.
0
Excalibur921
546 / 383 / 59
Регистрация: 12.10.2013
Сообщений: 2,656
11.07.2015, 20:45 #9
А зачем сортировать каждый раз если достаточно сделать базу данных 1 раз. В итоге на вход будет 2 числа, применяемые буквы и их количество. Сначала отсканить словарик, потом проанализировать на количество букв и какие буквы использованы.
И будет мгновенный результат без поиска каждый раз.
0
Leonman
15 / 15 / 0
Регистрация: 17.06.2012
Сообщений: 270
11.07.2015, 20:54  [ТС] #10
ampermetr, вариант, попробую.

Добавлено через 4 минуты
Excalibur921, данные на вход подаются в такой формате:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
13
5 a i n n v o x z
10 g o l a u r r c t d s o i i e h
4 o o m s q u c
13 i r a l e n n g o g m m y n e r v t i i
8 x e c l r k z d s e u p o
12 c e l e k b s s c o c a l z j i k t l
3 a t p z a
11 h k a e b b t u n f i q i l a n m
10 a e c s e d g r o s v d e p w m
9 e g a j t r b k r m s t o i
8 e l l a l a b b c c r y u
10 b a e e u s t i f u w a j d u i
4 o r s w m m g
где первое число, длина слова, а далее буквы из которых надо составить это слово/слова
0
Excalibur921
546 / 383 / 59
Регистрация: 12.10.2013
Сообщений: 2,656
11.07.2015, 21:03 #11
Цитата Сообщение от Leonman Посмотреть сообщение
ampermetr, вариант,
И будет система с
Цитата Сообщение от Leonman Посмотреть сообщение
но все они работают очень долго,
Потому как скорей всего такой подход там и есть в виду простоты и очевидности. Время на поиск и сортировку и идет =).

Добавлено через 8 минут
Цитата Сообщение от Leonman Посмотреть сообщение
10 a e c s e d g r o s v d e p w m
А где сортировка по алфавиту + если две буквы? Наверно быстрей чем я предложил метода не существует, т.к это уже все возможные решения. В итоге длинна слова и буквы превращаются в одно число просто указатель на фаил какие слова вывести…Вам же нужна имена скорость? Ну вот… один такт))).Только вот база наверно страшная… И предварительное ее создание долго.
0
Croessmah
Ушел
Эксперт CЭксперт С++
13557 / 7707 / 872
Регистрация: 27.09.2012
Сообщений: 18,996
Записей в блоге: 3
Завершенные тесты: 1
11.07.2015, 21:06 #12
Качаем словарь. Сортируем в нем все слова по длине (можно и по алфавиту, чтобы еще эффективнее искать потом). Всё, наш словарь готов.
В проге, при загрузке, запоминаем где в словаре начинаются слова определенной длины(можно это указать в начале файла или в отдельном файле с конфигом). Попалось слово из 7 букв? Пожалуйста, идем по необходимому смещению и уже отсюда начинаем все слова сравнивать по маске. Есть совпадение? Запоминаем слово и ищем дальше. И в таком темпе пока не дойдем до смещения, соответствующего словам с длиной 8 символов. Можно организовать добавление слов в словарь и т.д.
0
Excalibur921
546 / 383 / 59
Регистрация: 12.10.2013
Сообщений: 2,656
11.07.2015, 21:34 #13
Цитата Сообщение от Croessmah Посмотреть сообщение
Запоминаем слово и ищем дальше. И в таком темпе
Цитата Сообщение от Excalibur921 Посмотреть сообщение
И будет система с
Цитата Originally Posted by Leonman View Post
но все они работают очень долго,
Вот простая аналогия отбалды:
Что вы хотите ТС?
1)База данных 500 гиг вводите вопрос сразу ответ.
2)База данных 10 гиг ждете 30 минут ответ.
Ваш выбор?
Метод что я привел можно только ухудшать =).

Добавлено через 14 минут
А вообще наверно аналогия сильно не правильная. В словарике каждое слово уникально. Значит размер базы данных не может быть больше самого словаря. А тормазность ответа именно в не желании создавать базу данных ответов что я описал.
Значит выбор такой
1) искать в словарике разбитом на куски и ждать
2) получить готовый ответ предварительно перемолов все варианты и создав базу данных ответов.
0
S_el
2113 / 1633 / 308
Регистрация: 15.12.2013
Сообщений: 6,400
11.07.2015, 21:37 #14
Цитата Сообщение от Leonman Посмотреть сообщение
так мне же его надо переберать, когда мне есть с чем сравнивать
считали слово,отсортировали и проверяете его наличие в отсортированном словаре.

P.S Сам словарь в каком виде и где хранится?
0
Leonman
15 / 15 / 0
Регистрация: 17.06.2012
Сообщений: 270
11.07.2015, 22:59  [ТС] #15
Цитата Сообщение от Croessmah Посмотреть сообщение
Пожалуйста, идем по необходимому смещению и уже отсюда начинаем все слова сравнивать по маске.
ну тоесть вы все равно предлогаете использовать размещение или я опять не правильно понял. У меня один вопрос, как получить все слова, чтоб я мог сравнивать с отсортированным массивом?

Добавлено через 55 секунд
Цитата Сообщение от S_el Посмотреть сообщение
считали слово,отсортировали
, так откуда его считывать то? Словарь храниться в .txt

Добавлено через 2 минуты
Возможно я некорректно/непонятно объяснил задание.
вот такая строчка на вход:
C++
1
5 a i n n v o x z
значит, что я должен на выход предоставить количество слов, длинна которых 5 знаков, которые состоят из вот этих букв:
C++
1
a i n n v o x z
+ чтоб это слово существовало в природе
0
11.07.2015, 22:59
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.07.2015, 22:59
Привет! Вот еще темы с ответами:

Требуется найти слова, которые можно составить из данного - C++
Здравствуйте. Пользователь вводит слово. Слова, которые вообще известны, находятся в текстовом документе #include <iostream> ...

Работа из строками. Удалить все слова, которые начинаются с согласных букв - C++
Здравствуйте! Помогите решить задачу: пользователь вводит строку. Нужно ее записать в обратном порядке, посчитать количество чисел в...

Вывести только те слова сообщения, которые содержат не более чем n букв - C++
Можете помочь написать программу? Желательно просто и используя using namespace std; Я не сильно понимаю как работать со строками, поэтому...

Вывести только те слова сообщения, которые содержат не более чем n букв - C++
Дана строка, в которой содержится осмысленное текстовое сообщение. Слова сообщения разделяются пробелами и зна Вывести только те слова...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.