y***m
发帖数: 7027 | 1 五、实现一个整数除法的函数，不使用除号，可以使用加号、减号和乘号，函数只返回
商.
function(int x,y){
n=x;k=0;
while(n>y){
n=n-y;
k++;
}
return k;
} |
p******r
发帖数: 2999 | 2 you can only get 60pts with this algorithm
【在 y***m 的大作中提到】
: 五、实现一个整数除法的函数，不使用除号，可以使用加号、减号和乘号，函数只返回
: 商.
: function(int x,y){
: n=x;k=0;
: while(n>y){
: n=n-y;
: k++;
: }
: return k;
: }
|
s*****n
发帖数: 231 | 3 agree, how about the sign? |
l*****a
发帖数: 14598 | 4 the most important
what will happen if y==0
【在 y***m 的大作中提到】
: 五、实现一个整数除法的函数，不使用除号，可以使用加号、减号和乘号，函数只返回
: 商.
: function(int x,y){
: n=x;k=0;
: while(n>y){
: n=n-y;
: k++;
: }
: return k;
: }
|
R***i
发帖数: 78 | 5 还有一个bug， x,y相等时，k=0
【在 l*****a 的大作中提到】
: the most important
: what will happen if y==0
|
e*****e
发帖数: 1275 | 6 而且你要学会用shift.
其实我最喜欢用E^(log(X)-log(Y))
可惜他们不喜欢... |
f*********i
发帖数: 197 | 7 这个方法很好啊,赞一个,为什么他们不喜欢?
【在 e*****e 的大作中提到】
: 而且你要学会用shift.
: 其实我最喜欢用E^(log(X)-log(Y))
: 可惜他们不喜欢...
|
l*****a
发帖数: 14598 | 8 你觉得这个精确吗？
after u got log(x)
【在 f*********i 的大作中提到】
: 这个方法很好啊,赞一个,为什么他们不喜欢?
|
|
Z**********4
发帖数: 528 | 9 public static double Mydivide(int a, int b, int n)
{
if(b==0)
{
System.out.println("b is 0, Error!");
System.exit(1);
}
double A=a;
double B=b;
double PartInt=0;
while(A>=B)
{
PartInt=PartInt+1.0;
A-=B;
}
double t=0.1;
double PartDeci=0;
while(n>0)
{
B=B*0.1;
for(int i=0;i<10;i++)
{
if(A>=B)
{
PartDeci+=t;
A-=B;
}
}
t=t*0.1;
n--;
}
return (PartInt+PartDeci);
}
这个算的是a/b 保留n位小数 |
Z**********4
发帖数: 528 | 10 我这个是都是正整数情况
如果有负数的话稍微改改就行 用迭代 |
|
|
r*****e
发帖数: 792 | 11 用那么多double的干什么，有点画蛇添足啊,原题只要返回整数的商就好了。
我写了个递归的，用对除数移位的方法，不过不知道是不是有更好的算法？
正在把递归的改成非递归的。
【在 Z**********4 的大作中提到】
: 我这个是都是正整数情况
: 如果有负数的话稍微改改就行 用迭代
|
v*****d
发帖数: 348 | 12 呵呵，我被A家考到过这题。m/n, 商的范围是[0,m], 用binary search
【在 y***m 的大作中提到】
: 五、实现一个整数除法的函数，不使用除号，可以使用加号、减号和乘号，函数只返回
: 商.
: function(int x,y){
: n=x;k=0;
: while(n>y){
: n=n-y;
: k++;
: }
: return k;
: }
|
v*****d
发帖数: 348 | 13 然后这个"binary"用右移实现
【在 v*****d 的大作中提到】
: 呵呵，我被A家考到过这题。m/n, 商的范围是[0,m], 用binary search
|
C***y
发帖数: 2546 | 14 那每次得到middle以后，怎么得到middle*n?可以直接用乘法？还是也需要用加法实现？
【在 v*****d 的大作中提到】
: 然后这个"binary"用右移实现
|
v*****d
发帖数: 348 | 15 恩，可以用乘法。
现？
【在 C***y 的大作中提到】
: 那每次得到middle以后，怎么得到middle*n?可以直接用乘法？还是也需要用加法实现？
|
Z**********4
发帖数: 528 | 16 我这个不用double答案是不对的
你试试看
【在 r*****e 的大作中提到】
: 用那么多double的干什么，有点画蛇添足啊,原题只要返回整数的商就好了。
: 我写了个递归的，用对除数移位的方法，不过不知道是不是有更好的算法？
: 正在把递归的改成非递归的。
|
z*d
发帖数: 18 | 17 #include
#include
int divide (int x, int y) {
int m, n, sign_m, sign_n;
int j, k, l;
if (y == 0) {
printf("Dvided by 0 error! \n");
assert(0);
}
if (x < 0) {
m = -x;
sign_m = -1;
}
else {
m = x;
sign_m = 1;
}
if (y < 0) {
n = -y;
sign_n = -1;
}
else {
n = y;
sign_n = 1;
}
j = 0;
l = m;
while(1) {
k = (j+l)/2;
if (k*n > m)
l = k;
else
j = k;
if((j==l) || (j==(l-1)))
break;
}
if((sign_m + sign_n) == 0)
return -j;
else
return j;
}
【在 y***m 的大作中提到】
: 五、实现一个整数除法的函数，不使用除号，可以使用加号、减号和乘号，函数只返回
: 商.
: function(int x,y){
: n=x;k=0;
: while(n>y){
: n=n-y;
: k++;
: }
: return k;
: }
|
Z**********4
发帖数: 528 | 18 额。。汗一个 没有看到原题只要求整数。。。
恩恩
【在 r*****e 的大作中提到】
: 用那么多double的干什么，有点画蛇添足啊,原题只要返回整数的商就好了。
: 我写了个递归的，用对除数移位的方法，不过不知道是不是有更好的算法？
: 正在把递归的改成非递归的。
|
r*****e
发帖数: 792 | 19 你的code直接用了/啊！
还有做乘法的时候有可能
因为太大而出错，本来正的
变负了。还有一个建议，
变量名字长点好，要让自己
和别人好理解。都是ijklmn
的不好读。
【在 z*d 的大作中提到】
: #include
: #include
: int divide (int x, int y) {
: int m, n, sign_m, sign_n;
: int j, k, l;
: if (y == 0) {
: printf("Dvided by 0 error! \n");
: assert(0);
: }
: if (x < 0) {
|
z*d
发帖数: 18 | 20 Thanks. You're right.
For the divide by 2, is it OK to use right shift by 1 bit?
For potential overflow, we can use long to fix it. Right?
【在 r*****e 的大作中提到】
: 你的code直接用了/啊！
: 还有做乘法的时候有可能
: 因为太大而出错，本来正的
: 变负了。还有一个建议，
: 变量名字长点好，要让自己
: 和别人好理解。都是ijklmn
: 的不好读。
|
|
|
z*d
发帖数: 18 | 21 How about this one? Any suggestions or corrections will be highly
appreciated.
#include
#include
int divide (int x, int y) {
long long dividend, divisor, sign_dividend, sign_divisor;
long long low, middle, high;
int quotient;
/* check whether divisor is 0 */
if (y == 0) {
printf("Dvided by 0 error! \n");
assert(0);
}
/* unsign both dividend and divisor and mark the signess */
if (x < 0) {
dividend = -x;
sign_dividend = -1;
}
else {
dividend = x;
sign_dividend = 1;
}
if (y < 0) {
divisor = -y;
sign_divisor = -1;
}
else {
divisor = y;
sign_divisor = 1;
}
/* case dividend is equal to divisor */
if(dividend == divisor) {
if((sign_dividend + sign_divisor) == 0)
return -1;
else
return 1;
}
/* case divisor is 1 */
if(divisor == 1) {
quotient = (int)dividend;
if((sign_dividend + sign_divisor) == 0)
return -quotient;
else
return quotient;
}
/* binary search the quotient */
low = 0;
high = dividend;
while(1) {
middle = (low+high)>>1;
if (middle*divisor > dividend)
high = middle;
else
low = middle;
if((low==high) || (low==(high-1)))
break;
}
if(high*divisor == dividend)
quotient = (int)high;
else
quotient = (int)low;
if((sign_dividend + sign_divisor) == 0)
return (-quotient);
else
return quotient;
}
【在 r*****e 的大作中提到】
: 你的code直接用了/啊！
: 还有做乘法的时候有可能
: 因为太大而出错，本来正的
: 变负了。还有一个建议，
: 变量名字长点好，要让自己
: 和别人好理解。都是ijklmn
: 的不好读。
|
r*****e
发帖数: 792 | 22 I guess the right shift is allowed.
But I still think there is a possibility to have overflow
even though long is used. Actually, I don't think multiplication
is needed and I think sub/add is enough to avoid potential problem
and also good for performance, i.e., faster than multiplication
when you think the deeper implementation.
Have not written my own version by bin-search though.
【在 z*d 的大作中提到】
: Thanks. You're right.
: For the divide by 2, is it OK to use right shift by 1 bit?
: For potential overflow, we can use long to fix it. Right?
|
z*d
发帖数: 18 | 23 With long long type, it should be ok for the overflow issue, I think.
As for the performance, I'm also curious whether there is binary search
solution with only add/sub operations, instead of multiplication.
【在 r*****e 的大作中提到】
: I guess the right shift is allowed.
: But I still think there is a possibility to have overflow
: even though long is used. Actually, I don't think multiplication
: is needed and I think sub/add is enough to avoid potential problem
: and also good for performance, i.e., faster than multiplication
: when you think the deeper implementation.
: Have not written my own version by bin-search though.
|
y***m
发帖数: 7027 | 24 看来还是蛮多细节疏忽了...
function int calc(int x,y){
if(y==0)
return null;
else if (x==0)
return 0;
if (x>0)
c = 1;
else
c = -1;
if (y>0)
d = 1;
else
d = -1;
int n = x*c;
int m = y*d;
if(n
return 0;
int k=0;
while(n>=m){
k++;
n=n-m;
}
return k*c*d;
}
【在 l*****a 的大作中提到】
: the most important
: what will happen if y==0
|
