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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 16, средняя оценка - 5.00
proger2030
11 / 11 / 2
Регистрация: 15.11.2010
Сообщений: 256
#1

поиск в ширину(Рекурсивный) - C++

06.10.2011, 23:09. Просмотров 2138. Ответов 7
Метки нет (Все метки)

Программа запускается но выдает ошибку(Задача такая: Создать программу для решения задачи построения слова из некоторого множества букв (игра Scrabble) используя алгоритмы поиска в глубину и в ширину. Длина слова не менее 5 букв. )
Код программы
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include "stdafx.h"
#include <iostream>
#include <string>
#include <Windows.h>
using namespace std;
string str1 =  "forum"; //
string str2 ="murof"; //
int ArrMax[1000];
string Arr[2000][2000];
int N = 0;
string pastSymbol(string str, string symbol, int position);
void recShir(int k, string str );
 
 
int _tmain(int argc, _TCHAR* argv[])
{
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
 
    Arr[0][0] = str2.substr(0, 1);
   ArrMax[0] = 1;
    recShir(1, str2.substr(0, 1));
 
    return 0;
}
 
 
string pastSymbol(string str, string symbol, int position){
    string tmp;
    tmp = str.substr(0, position);
    tmp = tmp + symbol;
    tmp = tmp + str.substr(position, str.length() - position + 1);
 
    return tmp;    
 }
 
void recShir(int k, string str ) {
    int i, j;
    string tmp;
    string sym;
    for (i = 0; ArrMax[k-1]; i++) {
              sym = str2.substr(k, 1);
        for (j = 0; str.length(); j++) {
            tmp = pastSymbol(Arr[k-1][i], sym, j);
            N = N + 1;
            cout << tmp << endl;
            Arr[(k-1)+1][(i)*(k+1) +j] = tmp;
            if(tmp == str1)  cout << "Слово найдено на " <<  N  << " шаге\n";   // тут можно добавить break; 
            
                }
    break; //тут тоже но тогда будет искать в глубину(Если добавить два break)
    }
    
    ArrMax[(k-1)+1] =(k+1)*ArrMax[k-1];
    if (tmp.length() < str1.length()) 
        recShir(k + 1, tmp);    
}
0
Миниатюры
поиск в ширину(Рекурсивный)  
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.10.2011, 23:09
Здравствуйте! Я подобрал для вас темы с ответами на вопрос поиск в ширину(Рекурсивный) (C++):

Рекурсивный поиск в списке - C++
Добрый вечер. Я решал одну задачку из книги Х.Дейтела и П.Дейтела &quot;Как программировать на C++&quot; и у меня возникла одна проблема. ...

рекурсивный поиск файлов - C++
Всем привет! Нажно реализовать поиск файлов по маске. Набрасал вот такой код: int search_file(string disk, string mask) { char...

Рекурсивный поиск в глубину - C++
Нужно найти путь по простому лабиринту от точки к точке, используя в программе рекурсивный поиск в глубину. Фотографию примера лабиринта...

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

Помогите зациклить рекурсивный поиск - C++
Помогите зациклить поиск(пока работает для 2 список, если их больше не работает), вот часть кода if(NamebType.compare(&quot;Struct&quot;)==0) { ...

Рекурсивный поиск файлов и папок - C++
в консоли выводится бесконечный повторяющийся список, как этого избежать?! #include &lt;stdio.h&gt; #include &lt;windows.h&gt; #include &lt;conio.h&gt;...

7
ValeryS
Модератор
6729 / 5138 / 485
Регистрация: 14.02.2011
Сообщений: 17,247
06.10.2011, 23:16 #2
Цитата Сообщение от proger2030 Посмотреть сообщение
if(tmp == str1) cout << "Слово найдено на " << N << " шаге\n"; break;
бряк выполняется всегда
так же как и бряк в 52 строке
в результате
Цитата Сообщение от proger2030 Посмотреть сообщение
if (tmp.length() < str1.length())
всегда истина
и мы исчерпали стек!!!
поакуратней надо с рекурсией
пользуйся отладчиком
0
proger2030
11 / 11 / 2
Регистрация: 15.11.2010
Сообщений: 256
06.10.2011, 23:31  [ТС] #3
Цитата Сообщение от ValeryS Посмотреть сообщение
бряк выполняется всегда
так же как и бряк в 52 строке
в результате

всегда истина
и мы исчерпали стек!!!
поакуратней надо с рекурсией
пользуйся отладчиком
Мы можем подправит это как-то ?
0
ValeryS
Модератор
6729 / 5138 / 485
Регистрация: 14.02.2011
Сообщений: 17,247
06.10.2011, 23:49 #4
первый бряк леххко
C++
1
2
3
4
5
if(tmp == str1)  
{
  cout << "Слово найдено на " <<  N  << " шаге\n"; 
  break; 
}
со вторым сложнее (ты хочешь выйти из обоих циклов????)
самое простое но не самое правильное использовать GOTO
C++
1
2
3
4
5
6
7
8
9
10
11
    if(tmp == str1) 
          {
            cout << "Слово найдено на " <<  N  << " шаге\n";   // тут можно добавить break; 
           goto metka;
          }        
      
             }
        //break; //тут тоже но тогда будет искать в глубину(Если добавить два break)
        }
metka:
.......................................
пошукай тут на форуме была тема как выйти из вложенных циклов
можно
использовать флаги
проверять счетчики
использовать гото
и самое лучшее (по моему)
обернуть циклы в функцию
0
proger2030
11 / 11 / 2
Регистрация: 15.11.2010
Сообщений: 256
07.10.2011, 00:09  [ТС] #5
Цитата Сообщение от ValeryS Посмотреть сообщение
пошукай тут на форуме была тема как выйти из вложенных циклов
можно
использовать флаги
проверять счетчики
использовать гото
и самое лучшее (по моему)
обернуть циклы в функцию
ты в бэйсике не пишешь ?
0
ValeryS
Модератор
6729 / 5138 / 485
Регистрация: 14.02.2011
Сообщений: 17,247
07.10.2011, 00:15 #6
Цитата Сообщение от proger2030 Посмотреть сообщение
ты в бэйсике не пишешь ?
уже лет 20 не пишу
0
proger2030
11 / 11 / 2
Регистрация: 15.11.2010
Сообщений: 256
07.10.2011, 00:30  [ТС] #7
Цитата Сообщение от ValeryS Посмотреть сообщение
уже лет 20 не пишу
просто у меня эта программа работает нормально в бэйсике! Может посмотришь ?
Visual Basic
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
Dim Arr(1000, 1000) As String
Dim ArrMax(1000) As Integer
Dim N As Integer
Dim max As Integer 'ÄëèГ*Г* ñëîâГ*
Dim str1 As String, str2 As String 'ÈñõîäГ*Г*Гї ñòðîêГ*, Г*Г*áîð ГЎГіГЄГў
Function pastSymbol(str As String, symbol As String, position As Integer) As String
    Dim tmp As String
    tmp = Mid(str, 1, position - 1)
    tmp = tmp + symbol
    tmp = tmp + Mid(str, position, Len(str) - position + 1)
    pastSymbol = tmp
End Function
Sub rec(k As Integer, str As String)
    Dim i As Integer, j As Integer
    Dim tmp As String
    Dim sym As String
    sym = Mid(str2, k + 1, 1)
    For j = 1 To Len(str) + 1
        tmp = pastSymbol(str, sym, j)
        N = N + 1
        List1.AddItem (CStr(N) + ")" + tmp)
        If tmp = str1 Then Label1.Caption = Label1.Caption + "Ñëîâî Г*Г*éäåГ*Г® Г*Г* " + CStr(N) + "ГёГ*ГЈГҐ" + vbCrLf
        If Len(tmp) < max Then Call rec(k + 1, tmp)
    Next
End Sub
Sub recShir(k As Integer, str As String)
    Dim i As Integer, j As Integer
    Dim tmp As String
    Dim sym As String
 
    For i = 1 To ArrMax(k)
        sym = Mid(str2, k + 1, 1)
        For j = 1 To Len(str) + 1
            tmp = pastSymbol(Arr(k, i), sym, j)
            N = N + 1
            List1.AddItem (CStr(N) + ")" + tmp)
            Arr(k + 1, (i - 1) * (k + 1) + j) = tmp
            If tmp = str1 Then Label1.Caption = Label1.Caption + "Ñëîâî Г*Г*éäåГ*Г® Г*Г* " + CStr(N) + "ГёГ*ГЈГҐ" + vbCrLf
        Next
    Next
    ArrMax(k + 1) = (k + 1) * ArrMax(k)
    If Len(tmp) < max Then Call recShir(k + 1, tmp)
End Sub
Private Sub Command1_Cglick()
        
End Sub
 
Private Sub Command1_Click()
    List1.Clear
    N = 0
    Label1.Caption = ""
    str1 = CStr(Text1.Text)
    str2 = CStr(Text2.Text)
    max = Len(str1)
    Call rec(1, Mid(str2, 1, 1))
End Sub
 
Private Sub Command2_Click()
    List1.Clear
    N = 0
    Label1.Caption = ""
    str1 = CStr(Text1.Text)
    str2 = CStr(Text2.Text)
    max = Len(str1)
    Arr(1, 1) = Mid(str2, 1, 1)
    ArrMax(1) = 1
    Call recShir(1, Mid(str2, 1, 1))
End Sub
 
Private Sub Form_Load()
    N = 0
End Sub
0
ValeryS
Модератор
6729 / 5138 / 485
Регистрация: 14.02.2011
Сообщений: 17,247
07.10.2011, 00:41 #8
Цитата Сообщение от proger2030 Посмотреть сообщение
Может посмотришь ?
посмотрел
ничего не понял
Цитата Сообщение от proger2030 Посмотреть сообщение
If tmp = str1 Then Label1.Caption = Label1.Caption + "Слово найдено на " + CStr(N) + "шаге" + vbCrLf
Next
Next
у тебя же здесь нет досрочного выхода из циклов

Добавлено через 1 минуту
циклы крутятся до конца
а в С ты бряки ставишь ????

Добавлено через 4 минуты
Цитата Сообщение от proger2030 Посмотреть сообщение
If Len(tmp) < max
и

Цитата Сообщение от proger2030 Посмотреть сообщение
if (tmp.length() < str1.length())
несколько разные условия не находишь?
0
07.10.2011, 00:41
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.10.2011, 00:41
Привет! Вот еще темы с ответами:

Рекурсивный и нерекурсивный поиск в глубину - C++
Не уверен в правильности работы даной функции. Если начинать с вершины 2, то рекурсивный и нерекурсивный поиски дадут одинаковые...

Рекурсивный, линейный поиск с использованием вектора - C++
Изучаю C++ по книжке Дейтелов &quot;Как прогарммировать на C++&quot;. Попалась задача на рекурсию: &quot;(Поиск наименьшего значения в массиве) Напишите...

поиск в ширину - C++
Помогите объяснить это по русски каждую строчку что тут написнао . #include &lt;cstdio&gt; #include &lt;vector&gt; #include &lt;stack.h&gt; #include...

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


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

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

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