锁定老帖子 主题:来来来,有兴趣的人便来战这算法题吧:
该帖已经被评为精华帖
|
|
---|---|
作者 | 正文 |
发表时间:2005-08-16
femto 写道 那就cast成long再说。。
转成long固然不错,不过不是出题者的本意。试试不转型看? |
|
返回顶楼 | |
发表时间:2005-08-16
jkit给出答案吧,这种考虑溢出最麻烦了
还是作那道找最大正反一样的字符串题目吧 |
|
返回顶楼 | |
发表时间: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);; } |
|
返回顶楼 | |
发表时间: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通不过。 |
|
返回顶楼 | |
发表时间: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 就行了。 |
|
返回顶楼 | |
发表时间:2005-08-16
java的>>是signed shift,移位完了要填充原来的符号位的。而,>>>是unsigned shift,恐怕跟c不一样。
而且java也没有unsigned int |
|
返回顶楼 | |
发表时间: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]; } |
|
返回顶楼 | |
发表时间: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]; } 嗯嗯,想到用数组的确是有点意思的。 |
|
返回顶楼 | |
发表时间:2005-08-16
嗯,用数组是挺有趣的。
|
|
返回顶楼 | |
发表时间:2005-08-18
帖子怎么几天了还在海区?
加个精摆到编程区啊…… |
|
返回顶楼 | |