问题描述
求多个正整数以二进制形式进行累加时,需要多少次进位?
解题思路
看到这个问题的时候,尝试两种方法:
-
1我首先以二进制形式从1累加到16,尝试发现里面的规律,也为以后验证代码的正确性做基础。
-
2当没有特殊的规律出现时,我就总结其中哪些运算是重复的,把重复的提取出来,然后多次计算来达到最终的计算目的。我首先把问题拆解为计算任意两个正整数相加时的进位数,然后在逐个相加计算总的进位数。
TIM图片20181026154154.jpg
伪代码
while (length > 0):
if第一次加:
if两个数最后一位都是1
进位数加一count++
记录向前进位,x=1
else
count=count
不记录向前进位,x=0
else:
if 记录向前进位:
if 最后的位数有一个是1:
进位数加一count++
记录向前进位,x=1
else
count=count
不记录向前进位,x=0
else:
if 最后的位数都是1:
进位数加一count++
记录向前进位,x=1
else
count=count
不记录向前进位,x=0
length = length - 1
flg = 0
return count
代码
# -*- coding: utf-8 -*-
"""
@author: 风
@file: py_03.py
@time: 2018/10/25 23:58
@contact: 254305068@qq.com
"""
def mn_bin_count(m, n):
m = bin(m)
n = bin(n)
m = m[2:len(m)]
n = n[2:len(n)]
len_m = len(m)
len_n = len(n)
length = 0
if len_m < len_n:
length = len_n
m = '0' * (len_n - len_m) + m # m,n长度一样了
else:
length = len_m
n = '0' * (len_m - len_n) + n # m,n长度一样了
count = 0
x = 0
flg = 1
len_n = len_m = length
# print(len_m, len_n, length,m,n,type(m))
while (length > 0):
a = int(m[length - 1])
b = int(n[length - 1])
# print("a,b",a,b)
if flg:
if (a and b):
count = count + 1
x = 1
else:
count = count
x = 0
else:
if x:
if (a or b):
count = count + 1
x = 1
else:
count = count
x = 0
else:
if (a and b):
count = count + 1
x = 1
else:
count = count
x = 0
length = length - 1
flg = 0
return count
# print(mn_bin_count(15, 15))
# print(mn_bin_count(11, 55))
# print(mn_bin_count(2, 3))
# print(mn_bin_count(5, 3))
# print(mn_bin_count(3, 5))
# print(mn_bin_count(21, 7))
# print(mn_bin_count(7, 21))
count = 0
sums = 0
for i in range(10,16):
sums = sums + i
count = count+mn_bin_count(sums, i+1)
print(sums, i + 1)
print("flag",count)
# print(count)
补充一个编程厉害的朋友代码,以供参考
def translate2bin(m):
array=[]
n=m
while(n):
temp=n
n=n//2
array.append(temp%2)
array.reverse()
return array
def cishu(m,n):
array_m=translate2bin(m)
array_n=translate2bin(n)
length=max([len(array_m),len(array_n)])
array_m=[0]*(length-len(array_m))+array_m
array_n=[0]*(length-len(array_n))+array_n
temp=0
cishu=0
for i in range(length):
temp=array_m[length-i-1]+array_n[length-i-1]+temp
temps=temp
temp=temp//2
if(temps>=2):
cishu+=1
return cishu
def cal(low,high):
total=0
temp=low
for j in range(low+1,high+1):
total+=cishu(temp,j)
temp=temp+j
return total
result=cal(100,1000)
print(result)
网友评论