А где код вашей программы?
| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Помогите советом |
| Автор: kosmos134 28.2.2013, 12:24 |
| Здравствуйте форумчане, подскажите пожалуйста как решить такую проблему: Ведущий загадывает слово Х и сообщает нам количество букв в нем. Буквы не повторяются. Слова реальные существительные русского языка. Игроки выкладывают варианты слов, затем ведущий, если слово не было отгадано выдает такой список следующих строк: Слово число 1,число 2 ,где слово - это слово названное игроком, число 1 - число букв в слове игрока, которые есть в слове ведущего, число 2 - число букв в слове игрока, которые кроме того, что есть в слове ведущего, стоят на тех же самых местах. Нужно составить программу которая бы по этому списку слов и количеству букв выдавала бы слово, которое загадал ведущий. P.S. Программу я составил перебором всех комбинаций букв в слове нужной длинны. Проблема в том что при малом количестве букв меня все устраивает, но если задать слово к примеру из 10 букв, то результата придется ждать очень долго. Может кто подскажет как можно написать программу которая выполнялась бы довольно таки быстро? |
| Автор: Vasya 28.2.2013, 13:43 |
| Написать программу, работающую быстро. довольно сложно А где код вашей программы? |
| Автор: kosmos134 28.2.2013, 14:11 | ||
type TRec_word=record s:string; a,b:integer; end; TAr_words=array[0..99] of TRec_word; var n_char:integer; n_words:integer; ar_words:TAr_words; minword,maxword:string; tn,tm:integer; function Down_Case(s:string):string; var i,j,c:byte; begin for i:=1 to length(s) do begin c:=ord(s[i]); case c of 168:for j:=1 to 16 do inc(s[i]); 192..223:for j:=1 to 32 do inc(s[i]); end; end; Down_Case:=s; end; function t2(s:string):boolean; var a,b:integer; i,j:byte; begin t2:=true; for j:=0 to n_words do begin a:=0;b:=0; for i:=1 to length(s) do begin if pos(s[i],ar_words[j].s)>0 then begin inc(a); if i=pos(s[i],ar_words[j].s) then inc(b) end end; if (a<>ar_words[j].a)or(b<>ar_words[j].b) then begin t2:=false; break end; end; inc(tn); end; procedure t(n:byte;s:string); var c:char; i,j:integer; begin for c:='а' to 'я' do if pos(c,s)=0 then begin s:=s+c; if length(s)<n_char then t(n-1,s) else begin //showmessage(s); if t2(s) then j:=form1.Memo2.Lines.Add(s) end; delete(s,length(s),1) end end; procedure TForm1.Button1Click(Sender: TObject); var i,j,k:integer; s,s1:string; word:string; begin tn:=0; button1.Enabled:=false; val(combobox1.Text,n_char,i); n_words:=memo1.Lines.Count-1; for i:=0 to n_words do begin s:=memo1.Lines.Strings[i]; s:=Down_Case(s); j:=pos(' ',s); ar_words[i].s:=copy(s,1,j-1);delete(s,1,j); j:=pos(':',s); str(j,s1); //showmessage(s1); val(copy(s,1,j-1),ar_words[i].a,k); delete(s,1,j); val(copy(s,1,length(s)),ar_words[i].b,k); s1:=''; s1:=ar_words[i].s; str(ar_words[i].a,s);s1:=s1+s; str(ar_words[i].b,s);s1:=s1+','+s; end; for i:=1 to n_char do begin minword:=minword+chr(223+i); maxword:=maxword+chr(255-i+1) end; if n_char>6 then begin for i:=n_char downto 8 do minword[i]:=minword[i-1]; minword[7]:='ё'; end; word:=minword; //pred(word[n_char]); //проверка на выполнение подсказки t(n_char-1,'');//проверка на повтор букв button1.Enabled:=true; end; |
| Автор: Akina 28.2.2013, 14:38 |
| Игра называется "Быки и коровы". Реализаций - дохрена. Ищи. |
| Автор: kosmos134 28.2.2013, 16:29 | ||
Спасибо в первую очередь за просвящение в названии игры, но в нете натыкаюсь на алгоритмы как бы сказать поэтапного отгадывания, а мне скорее из уже готовых ответов(которые могли даваться и не по алгоритму, а просто как первое попавшееся слово) нужно получить слово либо если их несколько то список слов, среди которых есть и слово, которое загадал ведущий. У меня есть несколько предположений, кроме полного перебора, что слишком долго. Один вариант это сделать словарь слов и потом из него искать. метод практически тот же, но гораздо меньше вариантов. Но я не уверен в его эффективности, да и лишняя проблема со словарем. второй вариант я думаю может можно как нибудь из слов игроков пытаться собрать загаданное слово. Не знаю конечно возможно это или нет, и не знаю как подойти к этому методу. Может сможете подсказать? буду очень благодарен. |
| Автор: Akina 28.2.2013, 16:32 | ||
Существование словаря в ДАННОЙ ФОРМУЛИРОВКЕ ЗАДАЧИ даже не обсуждается - он обязан быть, и в нём обязано существовать любое из слов, как загаданное, так и предлагаемое отгадывающими. |
| Автор: kosmos134 28.2.2013, 16:36 | ||
Он конечно существует. Великий русский язык, который постоянно развивается и я сомневаюсь что кто либо знает его в совершенстве |
| Автор: volatile 1.3.2013, 00:29 | ||
неправильный подход. перебирать нужно не перестановку букв, (этих перестановок космическое число) перебирать нужно словарь русских слов (сколько их там сто тыщ, двести тыщ?) с проверкой на заданное условие. Весь словарь русских+английских+китайских слов перебрать можно за несколько миллисекунд. |
| Автор: kosmos134 1.3.2013, 21:32 | ||
использование словаря имеет некоторые неудобства. 1. проблема нахождение полного словаря русского языка 2. через какое-то время найденый сейчас словарь станет неактуальным. Придется его постоянно обновлять. может имеется подход получения без словаря? хотябы часть слова получить из тех данных что сообщил ведущий. |
| Автор: volatile 1.3.2013, 23:19 | ||
kosmos134, без словаря программа будет выдавать кучу не имющих смысла последовательностей букв, удовлетворяющих условиям. и этот список может быть не на один мегабайт. Как вы будет отсеивать эту помойку без словаря ??? |
