欢迎光临
我们一直在努力

模拟除法【NOIP每日一练26(解析)】

【问题描述】

在进行正整数的除法运算时,可以通过减法来实现。

例如x¸y=Q..R(Q:商,R:余数)可通过下列的方式实现:

while(r>=y)

结果,商在q中,余数在r中。

【算法说明】

上面的算法有一个缺点,就是当x比较大、y比较小时,则运算的次数非常多,速度太慢。为提高速度,下面给出改进的算法:先找一个非常接近x的数w,且满足:w=y×2^k,y×2^(k-1)≤x<w,然后通过减法与移位的运算,以较少的运算次数完成除法。

注:改编自第三届全国青少年信息学(计算机)奥林匹克分区联赛2-2

【答案解析】

(2)w=w+w

(3)w>y

(4)q=q+q

小智编程由硅谷人工智能专家伯克利大学熊宇红博士和清华大学靳简明博士后创立。为5~18岁青少年量身定制线下小班素质课程,通过学习Scratch、Python、C++、信息学奥赛,培养解决复杂问题的能力、提高逻辑思维能力和计算能力,实现与未来的对话。

寒假营信息:

赞(17)
分享到: 更多

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址