DouKaku?

ここでいう法演算とは，与えられた数(ここでは「法」と言います)で剰余をとりながら行う計算のことです．たとえば，法が10である場合，以下のように計算します．

• 足し算

  • 1 + 2 = 3
  • 7 + 3 = 0 (10を10で割った余りは0)
  • 11 + 12 = 1 + 2 = 3

• 引き算

  • 3 - 2 = 1
  • 2 - 3 = 9

• 掛け算

  • 2 * 3 = 6
  • 11 * 12 = 1 * 2 = 2
  • 18 * 39 = 8 * 9 = 2

式と法を与えたときに，このような法演算を行い，計算結果を表示するプログラムを作成してください．

注意点

• プログラムの入力には，式と法が与えられます．

  • 式に現れる数は，整数のみと仮定してかまいません．しかし，法より大きな数が与えられるかもしれませんし，負の数が与えられるかもしれません．
  • 法は2以上の正整数のみが与えられます．
  • 式と法は，プログラムにとって都合のよい形式で与えられると仮定してかまいません．ソースコード中に埋め込んでしまってもかまいません．

• 足し算，引き算，掛け算に対応してください．

  • 法10の世界においては，1 - 2 と 1 + 8 は同じ意味です．引き算の計算においては，この性質を使い，足し算に変換してから計算してもかまいません．

• プログラムの出力として，計算結果を表示して下さい．

• 与えられた式の中に，範囲外の数(負の数や，法の数以上の数)が現れた時には，必ず一度，式全体を正規化し，その結果を表示してから計算を行って下さい．

  • ここでいう「正規化」とは，式の中のすべての項をいったん法で剰余をとり，0以上，法-1以下の範囲になるようにする，ということです
  • 正規化をする際に，引き算を足し算へ変換する処理を一緒に行ってもかまいません．
  • 計算過程で範囲外の数が現れたときには，正規化を行うことが望ましいですが，必ずしも行う必要はありません．(最終的な計算結果が正しければよしとします)

アルゴリズムよりも、言語ごとのイディオムを問うような問題かなと思いました。

用途によると思いますが、式を埋め込むならマクロが手軽です。

  (with-modular m <式> ...)

と書くと<式> 内の演算がmod m で行われます。


 gosh> (with-modular 10 (list (+ 1 2) (+ 7 3) (+ 11 12)))
 (3 0 3)
 gosh> (with-modular 10 (list (- 3 2) (- 2 3)))
 (1 9)
 gosh> (with-modular 10 (list (* 2 3) (* 11 12) (* 18 39)))
 (6 2 2)
 gosh> (with-modular 10 (+ (- 1 2) (* 3 4) (+ 5 6 7) (* 8 9)))
 1

1
2
3
4
5
6
7
8
9

(define-macro (with-modular m . body)
  `(let ((+ (make-modular + ,m))
         (- (make-modular - ,m))
         (* (make-modular * ,m)))
     ,@body))

(define (make-modular op m)
  (lambda xs
    (modulo (apply op (map (cut modulo <> m) xs)) m)))

一方、式を外部から与えたいなら、+, -, * の束縛がmodular arithmeticに置き換わったようなモジュールを用意してその中でevalするという手が使えます。

 gosh> (eval-modular 10 '(+ 2 9))
 1
 gosh> (eval-modular 10 '(- 2 9))
 3
 gosh> (eval-modular 10 '(* 2 9))
 8

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

(define (make-modular op m)
  (lambda xs
    (modulo (apply op (map (cut modulo <> m) xs)) m)))

(define (make-modular-module m)
  (let1 mod (make-module #f)
    (eval `(define + ,(make-modular + m)) mod)
    (eval `(define - ,(make-modular - m)) mod)
    (eval `(define * ,(make-modular * m)) mod)
    mod))

(define (eval-modular m expr)
  (eval expr (make-modular-module m)))