logo资料库

C++回溯算法实验报告.doc

发布时间：2022-06-15 发布人：admin 分类：说明书 资料大小：0.11M 资料格式：doc 举报 版权申诉
第1页 / 共6页
第2页 / 共6页
第3页 / 共6页
第4页 / 共6页
第5页 / 共6页
第6页 / 共6页
资料共6页，全文预览结束
    1.
    一. 实验目的及实验环境 实验目的:了解回溯法并且熟练运用。 环境：devc++。 二. 实验内容 1. 删数问题 给定 n 位正整数 a，去掉其中任意 k 个数字后，剩下的数字 按原次序排列成一个新的正整数 n (1<=n<=200)位的正整数 a 和 k，k 小于 n。 2.整数变换 给定整数 i 的 f 变换和 g 变换分别为 f(i)=3*i;g(i)=└ i/2 ┘；└ ┘表示向下取整。现在给定 n，m，即通过 f 和 g 变换把 n 变为 m，求所需变换最小的次数。 三．方案设计 1. 这个问题是最优子结构问题，即局部最优能决定全局最优解， 可以使用贪心算法进行解决。n 个正整数去掉 s 个数字，求使得到 的新的正整数最大的删除方案可以等价为：对于 n 个正整数组成的 数字，一个一个地依次去掉 s 个数字，要求每删除一个数时，都使 删除后的新的正整数最小。因此问题转化为求解删除一个数字时是 新的数字最小的方案，求得这个方案后只需要对其执行 s 次即可。 2. 将变换的次数 step 先设置为 1，使用 dfs（1，n）进行迭代加 深搜索，如果搜索到了，则输出结果；否则，将 step 递增一次， 继续执行 def 直到找到或者超过最大变换次数。 dfs（dep，n）迭代加深搜索，每次都进行 3*n 和 n/2，并从这两分 支不断延续两个分支下去，直到找到或者超出界限为止。
    四．测试数据及运行结果 1. 2.
    五．总结 1． 实验过程中遇到的问题及解决办法及对调试过程的心得体会。 开始时思路不是很清晰，但后来通过 csdn 得到了启发思路，最终 解决了这些问题，以后还是要加大对算法题的练习，不然就会生 疏。 六．附录：源代码（电子版） 1. #include #include char num[100]; int main(void){ int n,i; printf("请输入正整数 n: "); scanf("%s",num); printf("输入要删除的位数："); scanf("%d",&n); if(n>=strlen(num)){ printf("%d",0); return 0; } while(n--){ i=0; //每次开始将 i 初始化为 0，表示重新开始检测下 降点 while(i
    for(int j=i;j #include using namespace std; const int MAX = 25; int n, m; int bestx[MAX+1];//变换序列 int step=1; //搜索深度，逐步加深 bool found = false; //两种变换 int change(int status, int n){ //0 为 g 1 为 f return status?n*3:n/2; } //迭代加深搜索
    bool dfs(int dep, int n){ if(dep > step){ //超过限制深度 return false; } for(int i=0; i<2; i++){ int temp = change(i, n); bestx[dep] = i; //记录当前变换状态 if(temp == m || dfs(dep+1, temp)){//已找到 found = true; return true; } } return false; } int main(void){ cout << "请输入正整数 n 和 m："; cin >>n>>m;
    while(true){ if(dfs(1, n) || ++step > MAX){ //找到 || 超过限 制深度 if(found){ cout << n << "变为" << m << "最少的变换次数 为：" << step << endl; cout << "变换过程为："; for(int i=step; i>=1; i--){ bestx[i]?cout<<'f':cout<<'g'; cout << " 超 过 默 认 变 换 步 数 ("<
    分享到：
    赞 收藏

    相关推荐

    资料库

    后端

    共收录2142份资料，累计10个分类，关注成员有19位，主要包括：Perl,Docker,Delphi,VB,PHP,Java,C,C#,Python,C++

    热门标签

    Perl Docker Delphi VB PHP Java C C# Python C++

    最新资料