アルゴリズム(第4版)ノートPage 47.pdf


アルゴリズム(第4版).[美]Robert Sedgewickノート:
47ページ目には興味深いアルゴリズムがあり、2つの10進数の加算から1つの10進数と1つの2進数の各積の加算に再帰的に実現した.
 1 #!/usr/bin/env python3
  2 #coding=utf-8
  3 ################################################ 
  4 # File Name: p47.py
  5 # Author: Yu LingJun
  6 # mail: [email protected]
  7 # Created Time: 2018-09-28
  8 ################################################ 
  9 #       , 2 10       ,  1 10           。
 10 def f(a,b):
 11     if int(b) == 0:
 12         return 0;
 13     elif int(b)%2 == 0 :
 14         y1=f(a+a,b/2)
 15         print("previously b:%d,b mod 2:%d,a:%d,f():%d"%(b,int(b%2),a,y1))
 16         return y1
 17     else :
 18         y2=f(a+a,b/2)+a
 19         print("previously b:%d,b mod 2:%d,a:%d,f():%d"%(b,int(b%2),a,y2))
 20         return y2
 21 
 22 a=f(21,12)
 23 print(a)
 24 
 25 def Binary(a):
 26     if int(a)==0:
 27         return 0
 28     elif int(a)%2 == 0 :
 29         print('0')
 30         return Binary(a/2)
 31     elif int(a)%2 == 1 :
 32         print('1')
 33         return Binary(a/2)
 34 Binary(12)