回溯法求解密码问题算法设计与分析

124 阅读 0 评论 82 点赞

我是靠谱客的博主虚心微笑，这篇文章主要介绍回溯法求解密码问题算法设计与分析，现在分享给大家，希望可以做个参考。

[问题描述]给定一个整数n和一个由不同大写字母组成的字符串(长度大于5、小于12).每个字母在字母表中对应有一个序数（A=1，B=2…Z=26）从str中选择5个字母构成密码，例如选取的5个字母为v.w.x.y和z.它们要满足v的序数-(w的序数)2+(x的序数)3-(y的序数)4+(z的序数)5=n。例如，给定的n=1、字符电str为"ABCDEFGHIKL"，一个可能的解是"FIECB" .因为6-92+5 -34 +25=1.但这样的解可以有多个，最终结果是按字典序最大的那个,所以这里的正确答案为"LKEBA"。

输人描述:每一行为n和str,以输人n=0结束。

输出描述:每一行输出相应的密码，当密码不存在时输出no solution"。

输人样例:

1 ABCDEFGHIJKL

11700519 ZAYEXIWOVU

3072997 SOUGHT

1234567 THEQUICKFROG

样例输出:

LKEBA

YOXUZ

GHOST

no solution

解题思路

本题也是排列树问题，只是并非所输入字符的全排列，而是任选5个字符的排列，解题方法比上一题稍复杂，我采用标记数组来防止重复选择，用一个变量findone来标记对于给出的n和字符串方程是否有解，另外还要定义一个比较字符串大小的函数来比较每次求得的解，根据字典序筛选出最优解。

复制代码

#include<iostream>
#include<math.h>
#include<string>
using namespace std;
char value[6]={'A'};
//存放解
char bestv[6]={'A'};
//存放最优解
int flag[50]={0};
//标记元素是否被选过
int N=0;
//存放序列长度
char seq[50];
bool findone=false;
//标记是否求得解
//比较两个字符串的大小 ,a[]大时返回true
bool bigger (char a[],char b[]){
bool flag=true;
for(int i=1;i<=N;i++){
if(a[i]>b[i])break;
else if(a[i]<b[i]){
flag=false;
break;
}
}
return flag;
}
//字符串拷贝,b[]拷贝到a[]
void copy(char a[],char b[]){
for(int i=1;i<=N;i++){
a[i]=b[i];
}
}
//检查元素是否满足方程
bool check(char a,char b,char c,char d,char e,double n){
bool result=false;
if(pow(a-'A'+1,1)-pow(b-'A'+1,2)+pow(c-'A'+1,3)-pow(d-'A'+1,4)+pow(e-'A'+1,5)==n)
result=true;
return result;
}
//输出问题的解
void display(char best[]){
for(int i=1;i<=5;i++){
cout<<best[i];
}
cout<<endl;
}
//问题求解
void dfs(int i,int n){
if(i>5){
if(check(value[1],value[2],value[3],value[4],value[5],n)){
findone=true;
//标记找到了一个解
if(bigger(value,bestv))
// 字符串value比bestv大
copy(bestv,value);
}
}
else{
for(int j=1;j<=N;j++){
if(flag[j]==0){
//第j个字母还没有被选择
flag[j]=1;
value[i]=seq[j];
dfs(i+1,n);
//给下一个赋值
}
flag[j]=0;
//回溯
}
}
}
int main(){
char all[20][6];
//存放所有最优解
int k=0;
do{
double n1;
cin>>n1;
//接收题目中等式右边的n
if(n1==0)
//n等于0时退出循环
break;
findone=false;
//将所有全局变量都恢复到最初值
for(int h=0;h<6;h++){
value[h]='A';
bestv[h]='A';
}
flag[50]={0};
int j=1;
//从下标1开始接收字符串，存进seq里面
for(;;j++){
seq[j]=cin.get();
if(seq[j]=='n')
// 回车时结束本次字符串的输入
{
j--;
break;
}
}
N=j;
//保存字符串长度
dfs(1,n1);
if(findone==true)
//有解的情况
copy(all[k],bestv);
//保存最优解
else
//无解的情况
all[k][0]='n';
k++;
}while(true);
for(int p=0;p<k;p++)
//输出所有解
if(all[p][0]=='n')
//无解的情况
cout<<"no solution";
else
//有解的情况
display(all[p]);
return 0;
}

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include<iostream>
#include<math.h>
#include<string>
using namespace std;
char value[6]={'A'};
//存放解
char bestv[6]={'A'};
//存放最优解
int flag[50]={0};
//标记元素是否被选过
int N=0;
//存放序列长度
char seq[50];
bool findone=false;
//标记是否求得解
//比较两个字符串的大小 ,a[]大时返回true
bool bigger (char a[],char b[]){
bool flag=true;
for(int i=1;i<=N;i++){
if(a[i]>b[i])break;
else if(a[i]<b[i]){
flag=false;
break;
}
}
return flag;
}
//字符串拷贝,b[]拷贝到a[]
void copy(char a[],char b[]){
for(int i=1;i<=N;i++){
a[i]=b[i];
}
}
//检查元素是否满足方程
bool check(char a,char b,char c,char d,char e,double n){
bool result=false;
if(pow(a-'A'+1,1)-pow(b-'A'+1,2)+pow(c-'A'+1,3)-pow(d-'A'+1,4)+pow(e-'A'+1,5)==n)
result=true;
return result;
}
//输出问题的解
void display(char best[]){
for(int i=1;i<=5;i++){
cout<<best[i];
}
cout<<endl;
}
//问题求解
void dfs(int i,int n){
if(i>5){
if(check(value[1],value[2],value[3],value[4],value[5],n)){
findone=true;
//标记找到了一个解
if(bigger(value,bestv))
// 字符串value比bestv大
copy(bestv,value);
}
}
else{
for(int j=1;j<=N;j++){
if(flag[j]==0){
//第j个字母还没有被选择
flag[j]=1;
value[i]=seq[j];
dfs(i+1,n);
//给下一个赋值
}
flag[j]=0;
//回溯
}
}
}
int main(){
char all[20][6];
//存放所有最优解
int k=0;
do{
double n1;
cin>>n1;
//接收题目中等式右边的n
if(n1==0)
//n等于0时退出循环
break;
findone=false;
//将所有全局变量都恢复到最初值
for(int h=0;h<6;h++){
value[h]='A';
bestv[h]='A';
}
flag[50]={0};
int j=1;
//从下标1开始接收字符串，存进seq里面
for(;;j++){
seq[j]=cin.get();
if(seq[j]=='n')
// 回车时结束本次字符串的输入
{
j--;
break;
}
}
N=j;
//保存字符串长度
dfs(1,n1);
if(findone==true)
//有解的情况
copy(all[k],bestv);
//保存最优解
else
//无解的情况
all[k][0]='n';
k++;
}while(true);
for(int p=0;p<k;p++)
//输出所有解
if(all[p][0]=='n')
//无解的情况
cout<<"no solution";
else
//有解的情况
display(all[p]);
return 0;
}