大师作文网数据结构与算法 求单调递增函数值
来源：学生作业帮 编辑：大师作文网作业帮 分类：数学作业 时间：2024/11/18 11:08:13
数据结构与算法 求单调递增函数值
第一题,对于单调函数,增倍折半法就可以搜索到结果了.大概流程是这样：
首先判断f(0)跟输入的y值的大小,如果f(0)>y,那么说明要求的x<0,否则x>0,当然如果f(0)==y,那么自然要求的x的就是0了.
对于x>0的情况,现在要设法找到一个区间[a,b],使得x>a且x<b,方法就是假设x0=1,f(x0)如果比y小,那么令x0=2*x0,就是说增倍,然后再判断现在的f(x0)和y的关系,循环这个过程直到f(x0)>y了,那么就知道区间[a,b]就是现在的区间[x0/2,x0],然后再对区间进行折半,判断f((a+b)/2)跟y的关系,如果比y大,就让b=(a+b)/2,否则让a=(a+b)/2,每次都要判断是否相等,循环折半直到找到要求的x.
对于x<0的情况与x>0完全类似.
第二题,10进制数210485=2*10^5+1*10^4+0*10^3+4*10^2+8*10^1+5*10^0,那么13进制只不过就是把10变成13而已,也就是说13进制数210485的话,就是：（等号前是13进制,后面是10进制）
(210485)13=(2*13^5+1*13^4+0*13^3+4*13^2+8*13^1+5*13^0)10
只要计算出来就行了,取低四位就方法就是用求出来的10进制数对10000取余数,就自然得到后四位了.
首先判断f(0)跟输入的y值的大小,如果f(0)>y,那么说明要求的x<0,否则x>0,当然如果f(0)==y,那么自然要求的x的就是0了.
对于x>0的情况,现在要设法找到一个区间[a,b],使得x>a且x<b,方法就是假设x0=1,f(x0)如果比y小,那么令x0=2*x0,就是说增倍,然后再判断现在的f(x0)和y的关系,循环这个过程直到f(x0)>y了,那么就知道区间[a,b]就是现在的区间[x0/2,x0],然后再对区间进行折半,判断f((a+b)/2)跟y的关系,如果比y大,就让b=(a+b)/2,否则让a=(a+b)/2,每次都要判断是否相等,循环折半直到找到要求的x.
对于x<0的情况与x>0完全类似.
第二题,10进制数210485=2*10^5+1*10^4+0*10^3+4*10^2+8*10^1+5*10^0,那么13进制只不过就是把10变成13而已,也就是说13进制数210485的话,就是：（等号前是13进制,后面是10进制）
(210485)13=(2*13^5+1*13^4+0*13^3+4*13^2+8*13^1+5*13^0)10
只要计算出来就行了,取低四位就方法就是用求出来的10进制数对10000取余数,就自然得到后四位了.