![](https://iknow-base.cdn.bcebos.com/lxb/notice.png)
算法的子集和数问题
要求用1.掌握回溯法解题的基本思想;2.掌握回溯算法的设计方法;3.针对子集和数问题,熟练掌握回溯递归算法、迭代算法的设计与实现。4用算法来做...
要求用1. 掌握回溯法解题的基本思想;
2. 掌握回溯算法的设计方法;
3. 针对子集和数问题,熟练掌握回溯递归算法、迭代算法的设计与实现。
4用算法来做 展开
2. 掌握回溯算法的设计方法;
3. 针对子集和数问题,熟练掌握回溯递归算法、迭代算法的设计与实现。
4用算法来做 展开
展开全部
回溯算法设计2008-05-29 10:15 P.M.[实验目的]
1. 掌握回溯法解题的基本思想;
2. 掌握回溯算法的设计方法;
3. 针对子集和数问题,熟练掌握回溯递归算法、迭代算法的设计与实现。
[预习要求]
1. 认真阅读教材或参考书, 掌握回溯法解题的基本思想, 算法的抽象控制策略;
2. 了解子集和数问题及解向量的定长和变长状态空间表示;
3. 针对解向量的定长表示, 设计状态空间树节点扩展的规范(限界)函数及实现方法;
4. 分析深度优先扩展状态空间树节点或回溯的条件;
5. 分析和设计生成解向量各分量可选值的实现方法;
6. 设计和编制回溯算法的递归和迭代程序。
[参考数据类型或变量]
float s; // 表示有可能抵达答案节点的子路径上的元素之和;
float r; // 尚未测试的剩余集合元素之和;
float w[n]; // 存储原始集合的n个元素, 根据问题实例初始化;
int x[n]; // 定长表示的解向量, 各元素初始值为0;
[参考子程序接口与功能描述]
void RecursiveSubset(float s, float r, int k)
功能: 针对问题实例的递归回溯算法。
void IterativeSubset(int m)
功能: 针对问题实例的迭代回溯算法。
void InitializeInstanse(void)
功能: 问题实例的初始化函数, 初始化子集和数M , w, x向量, s, r。
[实验步骤]
1. 录入、修改并测试你的程序,直至正确为止;
2. 针对问题实例,实录运行时的输入、输出界面;
3. 将你的程序和实录的界面存盘备用。
[实验报告要求]
1. 阐述实验目的和实验内容;
2. 提交模块化的实验程序源代码;
3. 简述程序的测试过程,提交实录的输入、输出界面;
4. 鼓励对实验内容展开讨论,鼓励提交思考与练习题的代码和测试结果。
[思考与练习]
1. 试针对解向量的变长表示设计回溯算法,上机测试正确性。
2. 试针对0/1背包问题设计回溯算法,比较与子集和数问题的算法差异。
#include<stdio.h>
#define n 3
float s; /*表示有可能抵达答案节点的子路径上的元素之和;*/
float r; /*尚未测试的剩余集合元素之和;*/
float w[n]={2,3,4}; /*存储原始集合的n个元素, 根据问题实例初始化;*/
int x[n]; /*定长表示的解向量, 各元素初始值为0;*/
int M;
int k;
void RecursiveSubset(float s, float r, int k)/*针对问题实例的递归回溯算法*/
{int i;
x[k-1]=1;
if(s+w[k-1]==M)
{for(i=0;i<n;i++)
printf("%2d",x[i]);
printf("\n");}
else if(((s+r)>=M)&&((s+w[k-1]+w[k]<=M)))
RecursiveSubset(s+w[k-1],r-w[k-1],k+1);
if((s+r-w[k-1]>=M)&&((s+w[k])<=M))
{x[k-1]=0;
RecursiveSubset(s,r-w[k-1],k+1);
}
}
void IterativeSubset(int m)/*针对问题实例的迭代回溯算法*/
{int i;
for(i=0;i<m;i++) x[i]=2;
for(i=k-1;i<n;i++) r+=w[i];
k=1;
while(k>0)
{--x[k-1];
if(x[k-1]==0)
{if((s+r-w[k-1]>=M)&&(s+w[k]<=M))
{s+=x[k-1]*w[k-1];
r-=w[k-1];
k++;
continue;
}
else{
--k;
s-=x[k-1]*w[k-1];
r+=w[k-1];
for(i=k;i<m-1;i++)
x[i]=2;
continue;
}
}
if(s+w[k-1]==M)
for(i=0;i<n;i++)
{printf("%2d",x[i]);}
else if((s+r>=M)&&(s+w[k-1]+w[k]<=M))
{s+=w[k-1];r-=w[k-1];k++;}
}
printf("\n");
}
void InitializeInstanse(void) /*问题实例的初始化函数, 初始化子集和数M , w, x向量, s, r*/
{int i;
printf("Enter M:");
scanf("%d",&M);
for(i=0;i<n;i++)x[i]=0;
for(i=k-1;i<n;i++) r+=w[i];
for(i=0;i<k-2;i++) s+=x[i]*w[i];
}
main()
{InitializeInstanse();
RecursiveSubset(s,r,k);
IterativeSubset(n);
system("pause");
1. 掌握回溯法解题的基本思想;
2. 掌握回溯算法的设计方法;
3. 针对子集和数问题,熟练掌握回溯递归算法、迭代算法的设计与实现。
[预习要求]
1. 认真阅读教材或参考书, 掌握回溯法解题的基本思想, 算法的抽象控制策略;
2. 了解子集和数问题及解向量的定长和变长状态空间表示;
3. 针对解向量的定长表示, 设计状态空间树节点扩展的规范(限界)函数及实现方法;
4. 分析深度优先扩展状态空间树节点或回溯的条件;
5. 分析和设计生成解向量各分量可选值的实现方法;
6. 设计和编制回溯算法的递归和迭代程序。
[参考数据类型或变量]
float s; // 表示有可能抵达答案节点的子路径上的元素之和;
float r; // 尚未测试的剩余集合元素之和;
float w[n]; // 存储原始集合的n个元素, 根据问题实例初始化;
int x[n]; // 定长表示的解向量, 各元素初始值为0;
[参考子程序接口与功能描述]
void RecursiveSubset(float s, float r, int k)
功能: 针对问题实例的递归回溯算法。
void IterativeSubset(int m)
功能: 针对问题实例的迭代回溯算法。
void InitializeInstanse(void)
功能: 问题实例的初始化函数, 初始化子集和数M , w, x向量, s, r。
[实验步骤]
1. 录入、修改并测试你的程序,直至正确为止;
2. 针对问题实例,实录运行时的输入、输出界面;
3. 将你的程序和实录的界面存盘备用。
[实验报告要求]
1. 阐述实验目的和实验内容;
2. 提交模块化的实验程序源代码;
3. 简述程序的测试过程,提交实录的输入、输出界面;
4. 鼓励对实验内容展开讨论,鼓励提交思考与练习题的代码和测试结果。
[思考与练习]
1. 试针对解向量的变长表示设计回溯算法,上机测试正确性。
2. 试针对0/1背包问题设计回溯算法,比较与子集和数问题的算法差异。
#include<stdio.h>
#define n 3
float s; /*表示有可能抵达答案节点的子路径上的元素之和;*/
float r; /*尚未测试的剩余集合元素之和;*/
float w[n]={2,3,4}; /*存储原始集合的n个元素, 根据问题实例初始化;*/
int x[n]; /*定长表示的解向量, 各元素初始值为0;*/
int M;
int k;
void RecursiveSubset(float s, float r, int k)/*针对问题实例的递归回溯算法*/
{int i;
x[k-1]=1;
if(s+w[k-1]==M)
{for(i=0;i<n;i++)
printf("%2d",x[i]);
printf("\n");}
else if(((s+r)>=M)&&((s+w[k-1]+w[k]<=M)))
RecursiveSubset(s+w[k-1],r-w[k-1],k+1);
if((s+r-w[k-1]>=M)&&((s+w[k])<=M))
{x[k-1]=0;
RecursiveSubset(s,r-w[k-1],k+1);
}
}
void IterativeSubset(int m)/*针对问题实例的迭代回溯算法*/
{int i;
for(i=0;i<m;i++) x[i]=2;
for(i=k-1;i<n;i++) r+=w[i];
k=1;
while(k>0)
{--x[k-1];
if(x[k-1]==0)
{if((s+r-w[k-1]>=M)&&(s+w[k]<=M))
{s+=x[k-1]*w[k-1];
r-=w[k-1];
k++;
continue;
}
else{
--k;
s-=x[k-1]*w[k-1];
r+=w[k-1];
for(i=k;i<m-1;i++)
x[i]=2;
continue;
}
}
if(s+w[k-1]==M)
for(i=0;i<n;i++)
{printf("%2d",x[i]);}
else if((s+r>=M)&&(s+w[k-1]+w[k]<=M))
{s+=w[k-1];r-=w[k-1];k++;}
}
printf("\n");
}
void InitializeInstanse(void) /*问题实例的初始化函数, 初始化子集和数M , w, x向量, s, r*/
{int i;
printf("Enter M:");
scanf("%d",&M);
for(i=0;i<n;i++)x[i]=0;
for(i=k-1;i<n;i++) r+=w[i];
for(i=0;i<k-2;i++) s+=x[i]*w[i];
}
main()
{InitializeInstanse();
RecursiveSubset(s,r,k);
IterativeSubset(n);
system("pause");
推荐律师服务:
若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询
广告 您可能关注的内容 |