• 如果您想对本站表示支持,请随手点击一下广告即可~
  • 本站致力于提供原创、优秀的技术文章~
  • 有任何疑问或建议 均可以在站点右侧栏处 通过各种方式联系站长哦~
  • POJ1426 – Find The Multiple

    ACM-POJ EXP 201阅读 2评论

    全解题报告索引目录 -> 【北大ACM – POJ试题分类


    大致题意

    给出一个整数n,(1 <= n <= 200)。求出任意一个它的倍数m,要求m必须只由十进制的’0’或’1’组成。

    解题思路

    首先暴力枚举肯定是不可能的 1000ms 想不超时都难,而且枚举还要解决大数问题。。

    要不是人家把这题放到搜索,怎么也想不到用BFS。。。

    解题方法BFS+同余模定理

    不说废话。

    首先说说朴素的不剪枝搜索方法

    我以n=6为例

    首先十进制数,开头第一个数字(最高位)一定不能为0,即最高位必为1

    设6的 ”01十进制倍数” 为k,那么必有k%6 = 0

    现在就是要用BFS求k值

    1、先搜索k的最高位,最高位必为1,则此时k=1,但1%6 =1 != 0

    因此k=1不是所求,存储余数 1

    2、搜索下一位,下一位可能为0,即 k*10+0,此时k=10,那么k%6=4

    可能为1,即 k*10+1,此时k=11,那么k%6=5

    由于余数均不为0,即k=10与k=11均不是所求

    3、继续搜索第三位,此时有四种可能了:

    对于k=10,下一位可能为0,即 k*10+0,此时k=100,那么k%6=4

       下一位可能为1,即 k*10+1,此时k=101,那么k%6=5

    对于k=11,下一位可能为0,即 k*10+0,此时k=110,那么k%6=2

       下一位可能为1,即 k*10+1,此时k=111,那么k%6=3

    由于余数均不为0,即k=100,k=101,k=110,k=111均不是所求

    4、继续搜索第四位,此时有八种可能了:

    对于k=100,下一位可能为0,即 k*10+0,此时k=1000,那么k%6=4

       下一位可能为1,即 k*10+1,此时k=1001,那么k%6=5

    对于k=101,下一位可能为0,即 k*10+0,此时k=1010,那么k%6=2

       下一位可能为1,即 k*10+1,此时k=1011,那么k%6=3

    对于k=110,下一位可能为0,即 k*10+0,此时k=1100,那么k%6=2

       下一位可能为1,即 k*10+1,此时k=1101,那么k%6=3

    对于k=111,下一位可能为0,即 k*10+0,此时k=1110,那么k%6=0

       下一位可能为1,即 k*10+1,此时k=1111,那么k%6=1

    我们发现k=1110时,k%6=0,即1110就是所求的倍数

    从上面的演绎不难发现,用BFS是搜索 当前位数字 (除最高位固定为1),因为每一位都只有0或1两种选择,换而言之是一个双入口BFS

    本题难点在于搜索之后的处理:对余数的处理,对大数的处理,余数与所求倍数间的关系


    接下来说说处理大数问题和剪枝的方法:

    首先我们简单回顾一下 朴素搜索 法:

    从上面可以看出余数的存数顺序(逐层存储):

    用数组mod[]存储余数,其中mod[0]不使用,由mod[1]开始

    那么mod中的余数依次为: 1 4 5 4 5 2 3 4 5 2 3 2 3 0 共14个

    即说明我们得到 余数0 之前,做了14步*10的操作,那么当n值足够大的时候,是很容易出现k为大数的情况(事实上我做过统计,200以内的n,有18个n对应的k值为大数

    那么我们再用int去存储k就显得不怎么明智了。

    为了处理所有情况,我们自然会想到 是不是应该要用int[]去存储k的每一位?

    而又由于k是一个01序列,那能不能**把 *10得到k每一位的问题 转化为模2的操作得到k的每一位(0或1) **呢?

    答案是可以的

    首先我们利用 同余模定理 对得到余数的方式进行一个优化

     
    (a*b)%n = (a%n *b%n)%n
    (a+b)%n = (a%n +b%n)%n

    随便抽取上面一条式子为例

    前一步 (11*10+0)%6=2 即k=110 , k%6=2

    当前步 (110*10+0)%6=2

    由同余模定理 (110*10+0)%6 = ((110*10)%6+0%6 )%6 = ((110%6 * 10%6)%6 +0 )%6 = (11*10+0)%6 = 2

    所以当前步(110*10+0)%6可以转变为 (2*10+0)%6=2

    很显然地,这种处理把k=110 等价于 k=2

    即用 前一步操作得到的余数 代替 当前步的k值

    而n在200的范围内, 余数值不可能超过3位数, 这就解决了 大数的问题


    通过这种处理手法,我们只需在BFS时顺手存储一个 余数数组mod[] ,就能通过mod[i-1]得到mod[i] ,直到mod[i]==0 时结束,大大减少了运算时间

    前面已经提到,n=6时,求余操作进行了14次,对应地,BFS时*10的操作也进行了14次。

    令i=14,通过观察发现,i%2恰好就是 6 的倍数的最低位数字

    i/2 再令 i%2 ,恰好就是 6 的倍数的 次低位数字。。。

    循环这个操作,直到i=0,就能得到 6的 01倍数(一个01队列),倒序输出就是所求

    这样就完成了 *10操作到 %2操作的过渡

    由于n值有限,只是1到200的整数,因此本题也可以用打表做,通过上面的方法得到结果后,就把1~200的倍数打印出来,重新建立一个程序,直接打表就可以了。

    不过打表比上面介绍的方法快不了多少

    转载请注明:EXP 技术分享博客 » POJ1426 – Find The Multiple

    喜欢 (5) 分享 (0)
    发表我的评论
    取消评论

    表情

    Hi,您需要填写昵称和邮箱!

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址
    (2)个小伙伴在吐槽
    1. “前一步 (1110+1)%6=2 即k=110 , k%6=2 当前步 (11010+1)%6=2” 这两句话是不是笔误啦,是不是应该是 “前一步 (1110+0)%6=2 即k=110 , k%6=2 当前步 (11010+0)%6=2”
      chj5chj52018-07-06 19:23 回复
      • 感谢指正,已修正 :grin:
        EXP2018-07-07 17:58 回复