多項式の加算 - みずぴー日記

30分プログラム、その605。SICPに乗ってた多項式の加算をやってみよう。
輪講でやってる計算機プログラムの構造と解釈に、多項式の演算を定義してみよう、というのがでてきたのでやってみる。
わりかし大変だったので、変数が1個の多項式だけを対象にして、加算だけを書いてみた。

使い方

# x + 3
p1 = poly("x",[term(1,1),term(0,3)])

# x^2 + 1
p2 = poly("x",[term(2,1),term(0,1)])

print p1      # 1x^1 + 3x^0
print p2      # 1x^2 + 1x^0
print p1 + p2 # 1x^2 + 1x^1 + 4x^0

ソースコード

#! /usr/bin/python
# -*- mode:python; coding:utf-8 -*-
#
# poly.py -
#
# Copyright(C) 2009 by mzp
# Author: MIZUNO Hiroki / mzpppp at gmail dot com
# http://howdyworld.org
#
# Timestamp: 2009/06/17 21:13:54
#
# This program is free software; you can redistribute it and/or
# modify it under MIT Lincence.
#

class poly:
    def __init__(self,variable,terms):
        self.variable = variable
        self.terms    = terms

    def __add__(self,o):
        if self.variable == o.variable:
            return poly(self.variable,add_terms(self.terms,o.terms))
        else:
            raise ValueError

    def __str__(self):
        return " + ".join(map(lambda t: "%d%s^%d" % (t.coeff,self.variable,t.order),self.terms))
    def __repr__(self):
        return "<poly:%s>" % str(self)

def add_terms(L1,L2):
    if L1 == [] and L2 == []:
        return []
    elif L1 == []:
        return L2
    elif L2 == []:
        return L1
    else:
        (x,xs) = L1[0],L1[1:]
        (y,ys) = L2[0],L2[1:]
        if x.order == y.order:
            return [x+y] + add_terms(xs,ys)
        elif x.order < y.order:
            return [y] + add_terms(L1,ys)
        elif x.order > y.order:
            return [x] + add_terms(xs,L2)

class term:
    def __init__(self,order,coeff):
        self.order = order
        self.coeff = coeff

    def __repr__(self):
        return "<%d?^%d>" % (self.coeff,self.order)

    def __add__(self,o):
        if self.order == o.order:
            return term(self.order,self.coeff + o.coeff)
        else:
            raise ValueError

# x + 3
p1 = poly("x",[term(1,1),term(0,3)])

# x^2 + 1
p2 = poly("x",[term(2,1),term(0,1)])

print p1 + p2

参考

過去の30分プログラム