珠玉のプログラミングのお題を python で書いてみた : 2
#!/bin/env python """ 2.2 the binary search in everywhere(P13-15) Problem A finding the lack of integer """ import random # global ERROR = -1 max_num = 10 element_num = 9 max_digit = 8 def main(): # input data input_data = random.sample(xrange(0,max_num), element_num) print "input : " + str(input_data) # investigate lack number lack_num = lacking_binary_search(input_data, max_digit, '') print "lack number : ", lack_num # verify lack number for i in input_data: if i == lack_num: return ERROR def lacking_binary_search(tlist, tdigit, rbin): tbin = '' zero = [] none_zero = [] zero_cnt, none_zero_cnt = 0, 0 tdigit -= 1 # divide less or much by binary for i in tlist: tbin = dec2bin(i, max_digit) if tbin[tdigit] == '0': zero.append(i) zero_cnt += 1 else: none_zero.append(i) none_zero_cnt += 1 # get lack number binary string if zero_cnt <= none_zero_cnt: rbin += '0' if zero_cnt == 0: return int(rbin[::-1], 2) return lacking_binary_search(zero, tdigit, rbin) else: rbin += '1' if none_zero_cnt == 0: return int(rbin[::-1], 2) return lacking_binary_search(none_zero, tdigit, rbin) def dec2bin(dec, digit): bin = '' while (digit > 0): bin += str(dec % 2) dec = int(dec / 2) digit -= 1 return bin[::-1] if __name__ == '__main__': r = main() if r == ERROR: print "NG NG NG"
実行結果。
input : [5, 8, 0, 9, 4, 3, 1, 7, 6] lack number : 2