设为首页 加入收藏

TOP

BFS(二):数的变换(一)
2019-07-08 12:10:07 】 浏览:126
Tags: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; &n

首页 上一页 1 2 3 下一页 尾页 1/3/3
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇右值引用和移动语义 下一篇关于引用参数设置默认值的问题

最新文章

热门文章

Hot 文章

Python

C 语言

C++基础

大数据基础

linux编程基础

C/C++面试题目