字串变换
发布网友
发布时间：2022-05-01 15:24
共1个回答
热心网友
时间：2023-10-21 16:23
从A到B最少1 步 最多可能走 N 步
每步有M种方法可选
只要找对一条路径就结束
总共有方法数是
1: M
2: M^2
3: M^3
..
N: M^N
------- +
M+M^2+...+M^M
利用穷举法递归搜索
M=3 N=10 时
3+3^2+3^3+3^4+3^5+3^6+...+3^10
=88572
#include <iostream>
#include <cmath>
#include <cstring>
#include <iomanip.h>
//定义最大搜索深度
#define NX 10
//规则数
#define M 3
using namespace std;
bool tc(char * a,char * b,char * a1,char * b1){ //按给定规则转换串 成功true
int ika=0;
int ikb=0;
bool found=true;
bool changed=false;
int lena1=strlen(a1);
int lenb1=strlen(b1);
while(a[ika]){
found=true;
for(int i=0;i<lena1;i++){
if(a[ika+i]!=a1[i]){
found=false;
break;
}
}
if(found){
changed=true;
ika+=lena1;
for(int j=0;j<lenb1;j++){
b[ikb]=b1[j];
ikb++;
}
}else{
b[ikb++]=a[ika++];
}
}
return changed;
};
bool comp(char * a,char *b){ //字串比较
int len=strlen(a);
if (len!=strlen(b)){
return false;
}
for(int i=0;i<len;i++){
if(a[i]!=b[i])return false;
}
return true;
};
bool tz(char * a , char * b ,char c[][2][20],int n,int m)
//深度优先递归算法搜索 广度优先算法仅将 tz 调用部分放到循环完成以后
{
char aa[m][20];
if(n>NX)return false; //搜索深度控制
cout.width(22);
cout<<a<<"?===>";
cout.width(22);
cout<<b<<endl;
for(int xi=0;xi<m;xi++){
if(tc(a,aa[xi],c[xi][0],c[xi][1])){
if(comp(aa[xi],b)){
cout.width(22);
cout<<a<<" ==> ";
cout.width(22);
cout<<aa[xi];
cout.width(20);
cout<<c[xi][0]<<"-->";
cout.width(20);
cout<<c[xi][1]<<endl;
return true; //搜索结束找到结果
}else{
if(tz(aa[xi],b,c,n+1,m)){搜索该支
cout.width(22);
cout<<a<<" ==> ";
cout.width(22);
cout<<aa[xi];
cout.width(20);
cout<<c[xi][0]<<"-->";
cout.width(20);
cout<<c[xi][1]<<endl;
return true;//搜索结束找到结果
}else{
continue;//专向下一支
}
}
}else{
continue; //该分支不再向下搜索
}
}
return false;
}
int main()
{
char a[20]="abcd";
char b[20]="xyz";
char c[6][2][20]={"abc","xu","ud","y","y","yz"};
if (tz(a,b,c,0,3)){
cout.width(22);
cout<<a<<" ==> ";
cout.width(22);
cout<<b;
cout<<"solved!!"<<endl;;
}else{
cout<<"unsolved!!"<<endl;
}
}
热心网友
时间：2023-10-21 16:23
从A到B最少1 步 最多可能走 N 步
每步有M种方法可选
只要找对一条路径就结束
总共有方法数是
1: M
2: M^2
3: M^3
..
N: M^N
------- +
M+M^2+...+M^M
利用穷举法递归搜索
M=3 N=10 时
3+3^2+3^3+3^4+3^5+3^6+...+3^10
=88572
#include <iostream>
#include <cmath>
#include <cstring>
#include <iomanip.h>
//定义最大搜索深度
#define NX 10
//规则数
#define M 3
using namespace std;
bool tc(char * a,char * b,char * a1,char * b1){ //按给定规则转换串 成功true
int ika=0;
int ikb=0;
bool found=true;
bool changed=false;
int lena1=strlen(a1);
int lenb1=strlen(b1);
while(a[ika]){
found=true;
for(int i=0;i<lena1;i++){
if(a[ika+i]!=a1[i]){
found=false;
break;
}
}
if(found){
changed=true;
ika+=lena1;
for(int j=0;j<lenb1;j++){
b[ikb]=b1[j];
ikb++;
}
}else{
b[ikb++]=a[ika++];
}
}
return changed;
};
bool comp(char * a,char *b){ //字串比较
int len=strlen(a);
if (len!=strlen(b)){
return false;
}
for(int i=0;i<len;i++){
if(a[i]!=b[i])return false;
}
return true;
};
bool tz(char * a , char * b ,char c[][2][20],int n,int m)
//深度优先递归算法搜索 广度优先算法仅将 tz 调用部分放到循环完成以后
{
char aa[m][20];
if(n>NX)return false; //搜索深度控制
cout.width(22);
cout<<a<<"?===>";
cout.width(22);
cout<<b<<endl;
for(int xi=0;xi<m;xi++){
if(tc(a,aa[xi],c[xi][0],c[xi][1])){
if(comp(aa[xi],b)){
cout.width(22);
cout<<a<<" ==> ";
cout.width(22);
cout<<aa[xi];
cout.width(20);
cout<<c[xi][0]<<"-->";
cout.width(20);
cout<<c[xi][1]<<endl;
return true; //搜索结束找到结果
}else{
if(tz(aa[xi],b,c,n+1,m)){搜索该支
cout.width(22);
cout<<a<<" ==> ";
cout.width(22);
cout<<aa[xi];
cout.width(20);
cout<<c[xi][0]<<"-->";
cout.width(20);
cout<<c[xi][1]<<endl;
return true;//搜索结束找到结果
}else{
continue;//专向下一支
}
}
}else{
continue; //该分支不再向下搜索
}
}
return false;
}
int main()
{
char a[20]="abcd";
char b[20]="xyz";
char c[6][2][20]={"abc","xu","ud","y","y","yz"};
if (tz(a,b,c,0,3)){
cout.width(22);
cout<<a<<" ==> ";
cout.width(22);
cout<<b;
cout<<"solved!!"<<endl;;
}else{
cout<<"unsolved!!"<<endl;
}
}
热心网友
时间：2023-10-21 16:23
从A到B最少1 步 最多可能走 N 步
每步有M种方法可选
只要找对一条路径就结束
总共有方法数是
1: M
2: M^2
3: M^3
..
N: M^N
------- +
M+M^2+...+M^M
利用穷举法递归搜索
M=3 N=10 时
3+3^2+3^3+3^4+3^5+3^6+...+3^10
=88572
#include <iostream>
#include <cmath>
#include <cstring>
#include <iomanip.h>
//定义最大搜索深度
#define NX 10
//规则数
#define M 3
using namespace std;
bool tc(char * a,char * b,char * a1,char * b1){ //按给定规则转换串 成功true
int ika=0;
int ikb=0;
bool found=true;
bool changed=false;
int lena1=strlen(a1);
int lenb1=strlen(b1);
while(a[ika]){
found=true;
for(int i=0;i<lena1;i++){
if(a[ika+i]!=a1[i]){
found=false;
break;
}
}
if(found){
changed=true;
ika+=lena1;
for(int j=0;j<lenb1;j++){
b[ikb]=b1[j];
ikb++;
}
}else{
b[ikb++]=a[ika++];
}
}
return changed;
};
bool comp(char * a,char *b){ //字串比较
int len=strlen(a);
if (len!=strlen(b)){
return false;
}
for(int i=0;i<len;i++){
if(a[i]!=b[i])return false;
}
return true;
};
bool tz(char * a , char * b ,char c[][2][20],int n,int m)
//深度优先递归算法搜索 广度优先算法仅将 tz 调用部分放到循环完成以后
{
char aa[m][20];
if(n>NX)return false; //搜索深度控制
cout.width(22);
cout<<a<<"?===>";
cout.width(22);
cout<<b<<endl;
for(int xi=0;xi<m;xi++){
if(tc(a,aa[xi],c[xi][0],c[xi][1])){
if(comp(aa[xi],b)){
cout.width(22);
cout<<a<<" ==> ";
cout.width(22);
cout<<aa[xi];
cout.width(20);
cout<<c[xi][0]<<"-->";
cout.width(20);
cout<<c[xi][1]<<endl;
return true; //搜索结束找到结果
}else{
if(tz(aa[xi],b,c,n+1,m)){搜索该支
cout.width(22);
cout<<a<<" ==> ";
cout.width(22);
cout<<aa[xi];
cout.width(20);
cout<<c[xi][0]<<"-->";
cout.width(20);
cout<<c[xi][1]<<endl;
return true;//搜索结束找到结果
}else{
continue;//专向下一支
}
}
}else{
continue; //该分支不再向下搜索
}
}
return false;
}
int main()
{
char a[20]="abcd";
char b[20]="xyz";
char c[6][2][20]={"abc","xu","ud","y","y","yz"};
if (tz(a,b,c,0,3)){
cout.width(22);
cout<<a<<" ==> ";
cout.width(22);
cout<<b;
cout<<"solved!!"<<endl;;
}else{
cout<<"unsolved!!"<<endl;
}
}
