论坛首页 综合技术论坛

来来来,有兴趣的人便来战这算法题吧:

浏览 45083 次
该帖已经被评为精华帖
作者 正文
   发表时间:2005-08-16  
femto 写道
那就cast成long再说。。


转成long固然不错,不过不是出题者的本意。试试不转型看?
0 请登录后投票
   发表时间:2005-08-16  
jkit给出答案吧,这种考虑溢出最麻烦了
还是作那道找最大正反一样的字符串题目吧
0 请登录后投票
   发表时间:2005-08-16  
jkit 写道
Elminster 写道
jkit 写道
同学转发给我的一个题,借楼主宝地凑热闹。
不使用条件判断语句(直接或者间接都不允许,比如调用了库函数,但是库函数用到了也不行),得到两个整数中大的那个。相当于自己实现max(int, int),但是不能用到条件判断语句,如if, while. ?等。

有兴趣的人试试。
(注:我已经做出来了,不要认为是我想找人做题)


这种题便就 …… 那啥了呀,(a>b)*a + (b>a)*b + (a==b)*a ,都是些运算符或者位运算的技巧。


忘了说了,大于小于等条件判断符号也包括在内,属于不能使用的。(另外,在java语言里面boolean是不能当成0,1的。虽然题目没有限定语言。但是逻辑运算根据题目是不能使用的,都能直接大于小于了,题目还有什么意义。)

当然,确实是位运算的技巧。


不许用判断,用位运算不是一样么?当然要考虑溢出是麻烦点:

int max_same(int a, int b);
{
    int should_be_a = 1 - ((a-b);>>31);;
    return should_be_a*a + (1-should_be_a);*b;
}

int max_different(int a, int b);
{
    int should_be_a = 1 - a>>31;
    return should_be_a*a + (1-should_be_a);*b;
}

int max(int a, int b);
{
    int sign_a = a>>31;
    int sign_b = b>>31;
    int same = 1 - sign_a ^ sign_b;

    return same*max_same(a, b); + (1-same);*max_different(a, b);;
}
0 请登录后投票
   发表时间:2005-08-16  
to Elminster:
可测试过边界?

Max3 m = new Max3();
System.out.println(m.max(Integer.MAX_VALUE, 1) == Math.max(Integer.MAX_VALUE, 1));
        System.out.println(m.max(Integer.MAX_VALUE, 0) == Math.max(Integer.MAX_VALUE, 0));
        System.out.println(m.max(Integer.MAX_VALUE, -1) == Math.max(Integer.MAX_VALUE, -1));
        System.out.println(m.max(Integer.MAX_VALUE, Integer.MAX_VALUE-1) == Math.max(Integer.MAX_VALUE, Integer.MAX_VALUE-1));
        System.out.println(m.max(Integer.MAX_VALUE, Integer.MAX_VALUE) == Math.max(Integer.MAX_VALUE, Integer.MAX_VALUE));
        System.out.println(m.max(Integer.MAX_VALUE, Integer.MIN_VALUE) == Math.max(Integer.MAX_VALUE, Integer.MIN_VALUE));
        System.out.println(m.max(1, Integer.MIN_VALUE) == Math.max(1, Integer.MIN_VALUE));
        System.out.println(m.max(0, Integer.MIN_VALUE) == Math.max(0, Integer.MIN_VALUE));
        System.out.println(m.max(-1, Integer.MIN_VALUE) == Math.max(-1, Integer.MIN_VALUE));
        System.out.println(m.max(Integer.MIN_VALUE+1, Integer.MIN_VALUE) == Math.max(Integer.MIN_VALUE+1, Integer.MIN_VALUE));
        System.out.println(m.max(Integer.MIN_VALUE, Integer.MIN_VALUE) == Math.max(Integer.MIN_VALUE, Integer.MIN_VALUE));

好几个case通不过。
0 请登录后投票
   发表时间:2005-08-16  
jkit 写道
to Elminster:
可测试过边界?

Max3 m = new Max3();
System.out.println(m.max(Integer.MAX_VALUE, 1) == Math.max(Integer.MAX_VALUE, 1));
        System.out.println(m.max(Integer.MAX_VALUE, 0) == Math.max(Integer.MAX_VALUE, 0));
        System.out.println(m.max(Integer.MAX_VALUE, -1) == Math.max(Integer.MAX_VALUE, -1));
        System.out.println(m.max(Integer.MAX_VALUE, Integer.MAX_VALUE-1) == Math.max(Integer.MAX_VALUE, Integer.MAX_VALUE-1));
        System.out.println(m.max(Integer.MAX_VALUE, Integer.MAX_VALUE) == Math.max(Integer.MAX_VALUE, Integer.MAX_VALUE));
        System.out.println(m.max(Integer.MAX_VALUE, Integer.MIN_VALUE) == Math.max(Integer.MAX_VALUE, Integer.MIN_VALUE));
        System.out.println(m.max(1, Integer.MIN_VALUE) == Math.max(1, Integer.MIN_VALUE));
        System.out.println(m.max(0, Integer.MIN_VALUE) == Math.max(0, Integer.MIN_VALUE));
        System.out.println(m.max(-1, Integer.MIN_VALUE) == Math.max(-1, Integer.MIN_VALUE));
        System.out.println(m.max(Integer.MIN_VALUE+1, Integer.MIN_VALUE) == Math.max(Integer.MIN_VALUE+1, Integer.MIN_VALUE));
        System.out.println(m.max(Integer.MIN_VALUE, Integer.MIN_VALUE) == Math.max(Integer.MIN_VALUE, Integer.MIN_VALUE));

好几个case通不过。


事实上我完全没试过 ……
好吧,检查了一下,发现是记错了对有符号整数做移位的规则 —— 这符号位竟然是不动的么?那么只要对上面所有的 >> 31 处加上一个 & 0x00000001 就行了。
0 请登录后投票
   发表时间:2005-08-16  
java的>>是signed shift,移位完了要填充原来的符号位的。而,>>>是unsigned shift,恐怕跟c不一样。
而且java也没有unsigned int
0 请登录后投票
   发表时间:2005-08-16  
也不卖关子了,说答案吧。

分析:因为不能使用条件判断,怎么才能实现分支呢?灵机一动,用数组!将条件的0,1作为数组下标不就实现分支了麽?
于是很快写出程序
        int[] num = {a, b};
        return num[(a - b); >>> 31];


虽然巧妙,但是并不完美,因为有溢出在里面。
进一步考虑,以上溢出只能在a,b不同符号的时候才能出现,于是对上面的结果进行修正。手法同样,既然想到了用数组,下面就继续发挥数组的妙用。
    public int max(int a, int b); {
        int[] num = {a, b};
        int[][] max = {{0, a},{b, 0}};
        max[0][0] = max[1][1] = num[(a - b); >>> 31];
        return max[a >>> 31][b >>> 31];
    }
0 请登录后投票
   发表时间:2005-08-16  
jkit 写道
也不卖关子了,说答案吧。

分析:因为不能使用条件判断,怎么才能实现分支呢?灵机一动,用数组!将条件的0,1作为数组下标不就实现分支了麽?
于是很快写出程序
        int[] num = {a, b};
        return num[(a - b); >>> 31];


虽然巧妙,但是并不完美,因为有溢出在里面。
进一步考虑,以上溢出只能在a,b不同符号的时候才能出现,于是对上面的结果进行修正。手法同样,既然想到了用数组,下面就继续发挥数组的妙用。
    public int max(int a, int b); {
        int[] num = {a, b};
        int[][] max = {{0, a},{b, 0}};
        max[0][0] = max[1][1] = num[(a - b); >>> 31];
        return max[a >>> 31][b >>> 31];
    }


嗯嗯,想到用数组的确是有点意思的。
0 请登录后投票
   发表时间:2005-08-16  
嗯,用数组是挺有趣的。
0 请登录后投票
   发表时间:2005-08-18  
帖子怎么几天了还在海区?
加个精摆到编程区啊……
0 请登录后投票
论坛首页 综合技术版

跳转论坛:
Global site tag (gtag.js) - Google Analytics