dfs递归回溯的一个好奇怪的问题，大家来看看
本帖最后由 1847292359 于 2022-1-21 14:50 编辑楼主在学习深度搜索回溯，碰到了一个好奇怪的问题，我附上图和代码一起描述问题，大家结合两者看一下
我跟着代码边跑边分析，并且用cout输出以便理清代码执行状况，问题在输出那句“7J5”，他表示将进入dfs（7），并且是当前在x=5的时候进入的，但是所写代码里面判断当x=5的时候我并没有让他进入dfs(7),那么他这句输出为什么会这样？结合代码跑一遍，不是应该继续退到上一个x吗？
是代码写得有问题还是我理解dfs有问题呢？（代码是C++写的简单dfs）
#include<bits/stdc++.h>
using namespace std;
bool yg;
//yg = 用过用来判断的
void dfs(int x)
{
yg = 1;//每来一次就先占了他后面再释放
switch(x) {
case 1:
if(!yg){
cout<<"2J"<<x<<endl;//J=叫他进的数
dfs(2) ;
}
if(!yg){
cout<<"4J"<<x<<endl;
dfs(4) ;
}
case 2:
if(!yg){
cout<<"3J"<<x<<endl;
dfs(3) ;
}
if(!yg){
cout<<"7J"<<x<<endl;
dfs(7) ;
}
case 3:
if(!yg){
cout<<"4J"<<x<<endl;
dfs(4) ;
}
if(!yg){
cout<<"5J"<<x<<endl;
dfs(5) ;
}
if(!yg){
cout<<"7J"<<x<<endl;
dfs(7) ;
}
case 4:if(!yg){
cout<<"5J"<<x<<endl;
dfs(5) ;
}
if(!yg){
cout<<"3J"<<x<<endl;
dfs(3) ;
}
case 5: //问题这里
if(!yg){
cout<<"6J"<<x<<endl;
dfs(6) ;
}
if(!yg){
cout<<"4J"<<x<<endl;
dfs(4) ;
}
if(!yg){
cout<<"3J"<<x<<endl;
dfs(3) ;
}
case 6:
if(!yg){
cout<<"5J"<<x<<endl;
dfs(5) ;
}
if(!yg){
cout<<"7J"<<x<<endl;
dfs(7) ;
}
case 7:
if(!yg){
cout<<"6J"<<x<<endl;
dfs(6) ;
}
if(!yg){
cout<<"3J"<<x<<endl;
dfs(3) ;
}
if(!yg){
cout<<"2J"<<x<<endl;
dfs(2) ;
}
}
yg = 0;//这次用完了 释放
cout<<x<<"t"<<endl;//t表示退出即x退出了
}
int main(){
dfs(1) ;
}
就是每次dfs完了之后他应该退回到上一个让他进入dfs的地方继续执行下去，但是这里为什么会出现这种情况？
按照本例代码运行的理论走势，他应该是一直退到x=3的情况，然后进入dfs（5）
但他实际走向并不是这样，不知道为什么
希望大家可以解答下，一直搞不明白 本帖最后由 1847292359 于 2022-1-21 14:48 编辑
smldhz 发表于 2022-1-21 14:31
switch case break
我并不想让他这么快就break
我是想让他在当前情况继续判断下去
也就是说当他回溯之后，继续根据x的情况判断下去 （比如x=5，他还会根据条件情况进入dfs（6）/dfs（4）/dfs（3），如果都不符合条件才跳到末尾结束当前一轮的switch）
按照本例代码运行的理论走势，他应该是退到x=3的情况，然后进入dfs（5）
但他实际走向并不是这样，不知道为什么 我在观看学习。 switch case break 3楼正解，switch遇到break结束,或者程序默认执行到末尾结束. 本帖最后由 1847292359 于 2022-1-21 14:47 编辑
SpeII 发表于 2022-1-21 14:35
3楼正解，switch遇到break结束,或者程序默认执行到末尾结束.
我并不想让他这么快就break
我是想让他在当前情况继续判断下去
也就是说当他回溯之后，继续根据x的情况判断下去 （比如x=5，他还会根据条件情况进入dfs（6）/dfs（4）/dfs（3），如果都不符合条件才跳到末尾结束当前一轮的switch）
按照本例代码运行的理论走势，他应该是退到x=3的情况，然后进入dfs（5）
但他实际走向并不是这样，不知道为什么 1847292359 发表于 2022-1-21 14:40
我并不想让他这么快就break
我是想让他在当前情况继续判断下去
switch的case穿透，后面case都会执行 1847292359 发表于 2022-1-21 14:40
我并不想让他这么快就break
我是想让他在当前情况继续判断下去
不是你想的那样 case 5: 执行完了之后就return了 case 5: 之后没有break的话 case 6 7 都会被执行
是的 你没看错 case 5:之后的所有case 都会进去并执行
你可以跑个例子看看
#include <iostream>
using namespace std;
int main(){
int x = 3;
switch(x){
case 1:
cout << "1" << endl;
case 2:
cout << "2" << endl;
case 3:
cout << "3" << endl;
case 4:
cout << "4" << endl;
case 5:
cout << "5" << endl;
}
return 0;
} 楼上的回复是对的。
楼主的问题要解决的话，可以在case 6：前一行加个break;，就是在楼主想做的三个判断完成之后加，这样就可以都判断完，然后不会执行case 6及之后的case了。不加break;会导致后面的所有case都被执行一遍。 z1390595 发表于 2022-1-21 16:39
楼上的回复是对的。
楼主的问题要解决的话，可以在case 6：前一行加个break;，就是在楼主想做的三个判断完 ...
确实是那个switch的问题，我把他改为了if
我写这段代码目的是为了解决上图这个问题
代码如下（字母我用如图的数字代替，一串数字组合表示一个字符表达）
#include<bits/stdc++.h>
using namespace std;
int ans = 0;
string z;
string sz;
bool yg;
void dfs(int x)
{
ans ++;
z = z + to_string(x);
sz = z;
yg = 1;//每来一次就先占了他后面再释放
if(x == 1){
if(!yg){
dfs(2) ;
}
if(!yg){
dfs(4) ;
}
}
else if(x ==2 ){
if(!yg){
dfs(3) ;
}
if(!yg){
dfs(7) ;
}
}
else if(x ==3 ){
if(!yg){
dfs(4) ;
}
if(!yg){
dfs(5) ;
}
if(!yg){
dfs(7) ;
}
}
else if(x ==4 ){
if(!yg){
dfs(5) ;
}
if(!yg){
dfs(3) ;
}
}
else if(x ==5 ){
if(!yg){
dfs(6) ;
}
if(!yg){
dfs(4) ;
}
if(!yg){
dfs(3) ;
}
}
else if(x ==6 ){
if(!yg){
dfs(5) ;
}
if(!yg){
dfs(7) ;
}
}
else if(x ==7 ){
if(!yg){
dfs(6) ;
}
if(!yg){
dfs(3) ;
}
if(!yg){
dfs(2) ;
}
}
z.pop_back(); //删除最后一个数字
yg = 0;//这次用完了 释放
//cout<<x<<"t"<<endl;//t表示退出即x退出了
}
int main(){
dfs(1) ;//表示从第一个开始跑
z = "";
dfs(2) ; //第一个跑完了，接着不要第一个跑第二个数字
z = "";
dfs(3) ;
z = "";
dfs(4) ;
z = "";
dfs(5) ;
z = "";
dfs(6) ;
z = "";
dfs(7) ;
set <string> set; //整一个set来去重
for(int e = 0;e<=ans;e++){
int len = sz.size();
sort(&sz,&sz); //统一排序比如“1234”和“4213”是同一个 ，排序后set会自动去重
}
for(int e = 0;e<=ans;e++){
set.insert(sz) ; //排序好之后添加到set里面，如果重复了set会自动忽略
}
cout<<set.size();//最后获取数量
}
正确求解答案是80，我这段代码输出是74。。不知道哪里出错了。。
页:
[1]
2