BFS(二):数的变换
2019-08-16 07:46:40来源:博客园 阅读 ()
BFS(二):数的变换
【例1】整数变换(POJ 3278 “Catch That Cow”)
给定两个整数a和b(0 ≤a,b≤100,000),要求把a变换到b。变换规则为:(1)当前数加1;(2)当前数减1;(3)当前数加倍。
编写程序求从a到b最少需要的变换次数。
例如,从5变换到17,最少需要4歩,具体过程为:5-10-9-18-17。
(1)编程思路。
用数组que[100001]模拟队列,队头指针front和队尾指针rear的初始值均为0。
定义数组visit[100001]标记某数是否产生并记录该数产生所需的最少变换步数。初始时,所有元素值均为-1,visit[i]=-1表示整数i未变换出来,visit[i]=n表示整数i从初始数开始经过n次变换得到。
为体会visit数组的作用,我们以整数5开始变换为例说明。由于5是初始数,所以置visit[5]=0。
由于按3种变换规则,5可以变换为4,6和10,因此置visit[4]=visit[6]=visit[10]=visit[5]+1=1,即4、6和10这3个数通过1次变换得到;4可以变换为3、5(visit[5]!=-1,已访问过不再处理)和8,因此置visit[3]=visit[8]=visit[4]+1=2,即3和8可以通过2次变换得到。……
(2)源程序。
#include <iostream>
using namespace std;
int main()
{
int a, b,front,rear,t,i;
int que[100001]={0},visit[100001];
cin>>a>>b;
for (i=0;i<=100000;i++)
visit[i]=-1;
front = 0, rear = 0;
que[rear++] = a; // 初始元素a 入队
visit[a] = 0;
while (front != rear)
{
t = que[front++];
if (t == b)
{
cout<<visit[t]<<endl;
break;
}
if (t > 0 && visit[t-1]==-1)
{
visit[t-1] = visit[t]+1;
que[rear++] = t-1;
}
if (t < 100000 && visit[t+1]==-1)
{
visit[t+1] = visit[t]+1;
que[rear++] = t+1;
}
if (t <= 50000 && visit[t*2]==-1)
{
visit[t*2] = visit[t]+1;
que[rear++] = t*2;
}
}
return 0;
}
【例2】质数变换(POJ 3126 “Prime Path”)
给定两个四位质数a和b,要求把a变换到b。变换的过程要求:(1)每次变换出来的数都是一个四位质数;(2)每一步变换所得的质数与前一步得到的质数只能有一个位不同。
编写程序求从a到b最少需要的变换次数,无法变换则输出Impossible。
例如,从1033变换到8179最少需要6歩,具体变换过程为1033、1733、3733、3739、3779、8779、8179。
(1)编程思路。
定义数组char prime[10000];来进行质数的判断,prime[x]=‘1’表示整数x是质数,prime[x]=‘0’表示整数x不是质数。采用筛法构建质数判定表prime[10000]。
在整数x进行变换时,可分别对x的千位、百位、十位和个位进行 (可用循环for (i=0;i<4;i++) 处理),每位上可由0~9这10种选择(可用循环 for (j=0;j<10;j++)处理)。即数的变换可以采用一个二重循环处理。若变换出的整数num如果是一个4位数(num>=1000),且没有访问过(visit[num]=-1),还是质数(prime[num]='1'),则将产生的整数num入队。
(2)源程序及运行结果。
#include <iostream>
using namespace std;
char prime[10000];
void GetPrime() // 用筛法构建质数判定表
{
int i,j;
for (i=2;i<10000;i++)
prime[i]='1';
for(i=2;i<10000;i++)
{
if (prime[i]=='1')
for (j=2*i;j<10000;j+=i)
prime[j]='0';
}
prime[1]='0';
}
void BFS(int k,int m)
{
int visit[10000],que[10000],a[4]={1,10,100,1000};
int front,rear,i,j,s,x,y,num;
for (i=1000;i<10000;i++)
visit[i]=-1;
front=rear=0;
que[rear++]=k; // k入队
visit[k]=0;
while(front!=rear)
{
s=que[front++]; // 队头元素出队
if (s==m)
{
cout<<visit[s]<<endl;
return;
}
for (i=0;i<4;i++)
{
for (j=0;j<10;j++)
{
x=s/(a[i]*10);
y=s%a[i];
num=x*a[i]*10+j*a[i]+y;
if (num>1000 && visit[num]==-1 && prime[num]=='1')
{
que[rear++]=num; // 变换后的质数入队
visit[num]=visit[s]+1;
}
}
}
}
cout<<"Impossible"<<endl;
}
int main()
{
int n,k,m;
GetPrime();
cin>>n;
while (n--)
{
cin>>k>>m;
BFS(k,m);
}
return 0;
}
原文链接:https://www.cnblogs.com/cs-whut/p/11150285.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:基数排序的可复用实现(C++11/14/17/20)
下一篇:相似基因
- Z 字形变换 2020-04-14
- BFS和队列 2020-01-18
- 矩阵乘法(六):几何变换 2019-09-08
- dfs/bfs专项训练 2019-08-16
- BFS(一):广度优先搜索的基本思想 2019-08-16
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash