問題2.5
今回は同じ問題を２通りの方法で解いてみました。
１個目が、最初に何も考えずに解いた解法。
２個目が、解答みて再帰使ってたので、そちらを取り入れたもの。
どっちがいいんでしょうねぇ。
たしかに１個目はきれいじゃないからバグも出やすい感じ。再帰の方がコードも短くシンプル。
でもやっぱり再帰の脳が頭の中にないから、これはこれで間違いそう。
慣れの問題？
問題
各ノードの要素が1桁の数である連結リストで表された2つの数があります。一の位がリストの先頭になるように、各位の数は逆順に並んでいます。このとき2つの数の和を求め、それを連結リストで表したものを返す関数を書いてください。
例
入力：(7 -> 1 -> 6) + (5 -> 9 -> 2) -> 617 + 295
出力：2 -> 1 -> 9 -> 912
importしてるpylist.pyは問題2.1で作ったものです。
http://d.hatena.ne.jp/takuto1981/20121211/1355198127
2-5.py (1個目の解法)
#encoding: utf-8 from pylist import Cell from pylist import LinkedList def list_addition(linked_list1, linked_list2): ''' 各ノードの要素が1桁の数字で構成された2つのリストの足し算を行う関数。 リストは一の位が先頭になるよう、逆順に並んでいる。 結果も逆順のリストで返す。 >>> linked_list1 = LinkedList() >>> linked_list1.insert(0, 1) >>> linked_list1.insert(1, 2) >>> linked_list1.insert(2, 3) >>> linked_list2 = LinkedList() >>> linked_list2.insert(0, 4) >>> linked_list2.insert(1, 5) >>> linked_list2.insert(2, 9) >>> result_list = list_addition(linked_list1, linked_list2) >>> result_list.index(5) 0 >>> result_list.index(7) 1 >>> result_list.index(2) 2 >>> result_list.index(1) 3 >>> linked_list1 = LinkedList() >>> linked_list1.insert(0, 1) >>> linked_list2 = LinkedList() >>> linked_list2.insert(0, 4) >>> linked_list2.insert(1, 6) >>> linked_list2.insert(2, 7) >>> result_list = list_addition(linked_list1, linked_list2) >>> result_list.index(5) 0 >>> result_list.index(6) 1 >>> result_list.index(7) 2 ''' # 結果のリスト格納用 result_list = LinkedList() # linked_list1とlinked_list2の先頭セルを取得 cell1 = linked_list1.get_top() cell2 = linked_list2.get_top() # 2つのリストの足し算処理 counter = 0 # 繰り上げ用 carry = 0 # 各桁の足し算用 tmp_value = carry while True: if not cell1 and not cell2 and carry == 0: break # 2つのリストの各桁と繰り上げ数の足し算 if cell1: tmp_value += cell1.get_data() cell1 = cell1.get_next() if cell2: tmp_value += cell2.get_data() cell2 = cell2.get_next() # 繰り上げ考慮 if tmp_value >= 10: carry = 1 result_list.insert(counter, tmp_value - 10) else: carry = 0 result_list.insert(counter, tmp_value) # 次の桁に繰り上げを渡す tmp_value = carry counter += 1 return result_list def _test(): import doctest doctest.testmod() if __name__ == '__main__': _test()
2-5r.py (2個目の解法)
#encoding: utf-8 from pylist import Cell from pylist import LinkedList def list_addition_recursion(cell1, cell2, carry): ''' 各ノードの要素が1桁の数字で構成された2つのリストの足し算を行う関数。 リストは一の位が先頭になるよう、逆順に並んでいる。 結果も逆順のリストで返す。 >>> linked_list1 = LinkedList() >>> linked_list1.insert(0, 1) >>> linked_list1.insert(1, 2) >>> linked_list1.insert(2, 3) >>> linked_list2 = LinkedList() >>> linked_list2.insert(0, 4) >>> linked_list2.insert(1, 5) >>> linked_list2.insert(2, 9) >>> result_list = list_addition_recursion(linked_list1.get_top(), linked_list2.get_top(), 0) >>> print result_list.get_data() 5 >>> print result_list.get_next().get_data() 7 >>> print result_list.get_next().get_next().get_data() 2 >>> print result_list.get_next().get_next().get_next().get_data() 1 >>> linked_list1 = LinkedList() >>> linked_list1.insert(0, 1) >>> linked_list2 = LinkedList() >>> linked_list2.insert(0, 4) >>> linked_list2.insert(1, 6) >>> linked_list2.insert(2, 7) >>> result_list = list_addition_recursion(linked_list1.get_top(), linked_list2.get_top(), 0) >>> print result_list.get_data() 5 >>> print result_list.get_next().get_data() 6 >>> print result_list.get_next().get_next().get_data() 7 ''' # 各桁の足し算結果格納用セル result_cell = Cell(0) # 足し算用 tmp_value = carry # 再帰終了条件 if not cell1 and not cell2 and carry == 0: return None # 足し算処理 if cell1: tmp_value += cell1.get_data() if cell2: tmp_value += cell2.get_data() # データを格納して、次の桁を再帰処理 result_cell.set_data(tmp_value % 10) next_cell = list_addition_recursion(cell1.get_next() if cell1 else None, cell2.get_next() if cell2 else None, 1 if tmp_value >= 10 else 0) result_cell.set_next(next_cell) return result_cell def _test(): import doctest doctest.testmod() if __name__ == '__main__': _test()
