Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 16, средняя оценка - 5.00
proger2030
 Аватар для proger2030
11 / 11 / 2
Регистрация: 15.11.2010
Сообщений: 256
06.10.2011, 23:09     поиск в ширину(Рекурсивный) #1
Программа запускается но выдает ошибку(Задача такая: Создать программу для решения задачи построения слова из некоторого множества букв (игра 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);    
}
Миниатюры
поиск в ширину(Рекурсивный)  
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.10.2011, 23:09     поиск в ширину(Рекурсивный)
Посмотрите здесь:

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

всегда истина
и мы исчерпали стек!!!
поакуратней надо с рекурсией
пользуйся отладчиком
Мы можем подправит это как-то ?
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,051
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:
.......................................
пошукай тут на форуме была тема как выйти из вложенных циклов
можно
использовать флаги
проверять счетчики
использовать гото
и самое лучшее (по моему)
обернуть циклы в функцию
proger2030
 Аватар для proger2030
11 / 11 / 2
Регистрация: 15.11.2010
Сообщений: 256
07.10.2011, 00:09  [ТС]     поиск в ширину(Рекурсивный) #5
Цитата Сообщение от ValeryS Посмотреть сообщение
пошукай тут на форуме была тема как выйти из вложенных циклов
можно
использовать флаги
проверять счетчики
использовать гото
и самое лучшее (по моему)
обернуть циклы в функцию
ты в бэйсике не пишешь ?
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,051
07.10.2011, 00:15     поиск в ширину(Рекурсивный) #6
Цитата Сообщение от proger2030 Посмотреть сообщение
ты в бэйсике не пишешь ?
уже лет 20 не пишу
proger2030
 Аватар для 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
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.10.2011, 00:41     поиск в ширину(Рекурсивный)
Еще ссылки по теме:

Поиск в ширину C++
Рекурсивный поиск файла. Падаю C++
C++ Рекурсивный поиск в списке

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

Или воспользуйтесь поиском по форуму:
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,051
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())
несколько разные условия не находишь?
Yandex
Объявления
07.10.2011, 00:41     поиск в ширину(Рекурсивный)
Ответ Создать тему
Опции темы

Текущее время: 00:23. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru