Рекурсивная функция никогда не завершается
Мне дали эту задачу, которая должна быть решена с помощью рекурсии.
Слово "лестничная игра" было изобретено Льюисом Кэрроллом в 1877 году. Идея такова
начать с начального слова и менять по одной букве за раз, пока не дойдете до
последнее слово. Каждое слово на этом пути должно быть английским.
Например, начиная с рыбы, вы можете сделать слово лестница к мачте
через следующую лестницу:
РЫБА, ЖЕЛАНИЕ, МЫТЬЕ, ПЮРЕ, МАЧТА
Напишите программу, которая использует рекурсию для поиска слова лестница с заданным началом
Слово и конечное слово, или определяет, существует ли лестница слов.
Что я уже пробовал:
Вот мой код:
#include<fstream>
#include<iostream>
#include<cstdlib>
#include<string>
#include<vector>
using namespace std;
bool possible_bridge(string a, string b)//determine if a bridge can be formed between two strings
{
if (a.length()!=b.length())
{
return false;
}
bool difference=false;
for (int i=0;i<a.length();i++)
{
if ((a[i]!=b[i])&&(!difference))
{
difference=true;
}
else if ((a[i]!=b[i])&&(difference))
{
return false;
}
}
return true;
}
bool isRepeat(vector<string>& no_repeat,string word)//determine if there is already an indentical string in the vector
{
for (int i=0;i<no_repeat.size();i++)
{
if (no_repeat[i]==word)
{
return true;
}
}
return false;
}
void word_bridge(string last,vector<string>bridge[],bool& found,int size)
{
ifstream fin;
int count[size];
for (int i=0;i<size;i++)
{
count[i]=0;
}
for (int i=0;i<size;i++)
{
string word;
fin.open("text.dat");
while (fin>>word)
{
if ((possible_bridge(word,bridge[i][bridge[i].size()-1]))&&(!isRepeat(bridge[i],word)))
{
count[i]++;
}
}
fin.close();
}
int total=0;
for (int i=0;i<size;i++)
{
total+=count[i];
}
if (total==0)
{
cout<<"no ladder available\n";
return;
}
int n(0),i(0);
vector<string>temp[total];
for (int k=0;k<total;k++)
{
temp[k]=bridge[i];
n++;
if (n==count[i])
{
i++;
n=0;
}
}
n=0;
i=0;
string word;
fin.open("text.dat");
for (int k=0;k<total;k++)
{
do
{
fin>>word;
} while (!((possible_bridge(word,temp[k][temp[k].size()-1]))&&(!isRepeat(temp[k],word))));
temp[k].push_back(word);
n++;
if (n==count[i])
{
i++;
n=0;
fin.close();
fin.open("text.dat");
}
}
if (fin.is_open())
{
fin.close();
}
for (int i=0;i<total;i++)
{
if (temp[i][temp[i].size()-1]==last)
{
for (int k=0;k<temp[i].size();k++)
{
found=true;
cout<<temp[i][k]<<" ";
}
return;
}
}
if (!found)
{
word_bridge(last,temp,found,total);
}
}
int main()
{
vector<string>bridge[1];
bridge[0].push_back("ade");
bool found=false;
word_bridge("bqe",bridge,found,1);
}
Я протестировал эти функции, и они хорошо работают, за исключением рекурсивной части функции word_bridge. Когда я добавил простую выходную строку cout<<"123" прямо перед рекурсивной частью и запустил программу, программа вывела 123, но не завершила работу и не вывела ничего другого.
jeron1
Вы не задали ни одного вопроса.