本文介绍了递归函数永远不会终止的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我遇到了这个必须用递归解决的问题。



梯形游戏这个词是由Lewis Carroll在1877年发明的。这个想法是

以一个起始单词开头并一次更改一个字母,直到到达结尾单词

。沿途的每个单词都必须是英文单词。

例如,从FISH开始,您可以通过以下阶梯向MAST

创建一个单词阶梯:

FISH,WISH,WASH,MASH,MAST

编写一个程序,使用递归来查找单词ladder,给出一个开始

单词和结束单词,或者确定是否存在字梯。



我尝试过:



这是我的代码:

I was given this problem that must be solved using recursion.

The word ladder game was invented by Lewis Carroll in 1877. The idea is
to begin with a start word and change one letter at a time until arriving at
an end word. Each word along the way must be an English word.
For example, starting from FISH you can make a word ladder to MAST
through the following ladder:
FISH, WISH, WASH, MASH, MAST
Write a program that uses recursion to find the word ladder given a start
word and an end word, or determines if no word ladder exists.

What I have tried:

Here is my code:




#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但没有终止或输出任何其他内容。



I have tested the functions and they work well except for the recursion part of the word_bridge function. When I added a simple output line cout<<"123" right before the recursive part and ran the program, the program output 123 but didn't terminate or output anything else.

推荐答案

bridge[0].push_back("ade");

并在调试器中运行您的应用。

当它到达断点时,它会停止,让你接管。您可以跨越行,逐步进入函数,查看(或更改)变量的内容。因此,请查看每一行,并确切了解运行时应该发生的事情。然后执行该行,看看发生了什么。这是你的期望吗?如果是这样,继续下一行。如果没有,为什么不呢?它做了什么?为什么它没有达到你的预期呢?



这是一项技能 - 在现实生活中也是一项非常有价值的技能 - 但开发它的唯一方法是使用它:你使用得越多越好!在这样的小程序上学习和开发技能要容易得多,而不是主要由不同的开发人员编写的100,000行庞然大物!



所以给它尝试一下,看看你能找到什么 - 它可能令人沮丧,但当你发现问题是什么时,这是开发中真正有趣的部分!

And run your app in the debugger.
When it hits the breakpoint, it will stop, and let you take over. You can step over lines, step into functions, and look at (or change) the content of variables. So look at each line, and work out exactly what should happen when it runs. Then execute the line, and look at what did happen. Is it what you expected? If so, continue for the next line. If not, why not? What did it do? Why didn't it do what you expected?

This is a skill - and a very valuable one in real life as well - but the only way to develop it is to use it: the more you use it the better you get! And it's a lot easier to learn and develop the skill on a little program like this, rather than a 100,000 line behemoth mostly written by a different developer!

So give it a try, and see what you can find out - it can be frustrating, but it's the real fun part of development when you find out what the problem is!


int count[size];
for (int i=0;i<size;i++)>
{
    count[i]=0;
}



如果在编译时已知 size ,则此代码可以正常工作。 br />
size 在运行时更改时,你需要一个指针,你必须手动分配和释放内存。

]

[]

这个错误是令人讨厌的,因为你的代码正在摧毁堆栈,每次你调用一个函数时,堆栈都会破坏你的变量。


This code works perfectly if size is known at compile time.
When size change at runtime, you need a pointer and you have to manually allocate and free memory.
malloc - C++ Reference[^]
std::malloc - cppreference.com[^]
This bug is nasty because your code is trashing the stack and every time you call a function, the stack is trashing your variable.


这篇关于递归函数永远不会终止的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

08-20 05:48
查看更多