Download presentation
Presentation is loading. Please wait.
1
小学生游戏
2
题目规则 题目先给出数a(a是一个正整数，不超过50位)，再给出目标数b（同样是一个正整数，不超过50位）， 数的运算有三种： 1：使当前数加上 2：使当前数加上2006 3：使当前数乘2
3
例1：小艺给出数a=1，给出数b=1987437 那么最快我们经过3次指定运算可以使1变成1987437 1
例1：小艺给出数a=1，给出数b= 那么最快我们经过3次指定运算可以使1变成 1*2=2；（第3种变换） = ；（第1种变换） = ；（第2种变换） 例2：小艺给出数a=1，给出数b=128 那么最快我们经过7次指定运算可以使1变成128 1*2*2*2*2*2*2*2=128（均采用第3种变换），但是因为n>6，所以按题意输出-1。
4
1.模型 将状态A转化为状态B 2.算法设计 比较容易想到的也是比较典型的 深度优先搜索,广度优先搜索 3.比较两种算法 因为是求最短的变换次数,考虑用广度优先搜索. 优点:搜索到的结果必然是变换次数最少的 缺点:需要较大存储空间(以空间为代价)
5
结构图
6
广度优先搜索 广度优先实行一层一层扩展结点 Q1=1;//指向每一层第一个结点 Q2=1;//指向每一层最后一个结点 do {
for (i=Q1;i<=Q2;i++) expand(i);//扩展第i个结点 Q1=Q3;//改变Q1指向下一层第一个结点Q3 Q2=Q4;//改变Q2指向下一层最后一个结点Q4 }while((Q1>Q2)||(解的数目num>0));
7
广度优先搜索 具体扩展每个结点的过程 Void expand(int i) { for (j=1;j<=n;j++)
then { 记录新结点；判断是否为解； Q4++; }
8
值得注意的地方 １．变换次数为０的情况 如果算法不能照顾到这种情况，那就事先先判断处理一下． ２．大数据的情况
数据精度不够，或者数据会溢出．考虑用高精度．（用数组存储一个大数）
Similar presentations
