算法_1： 数论

2019-04-13 17:12发布

站内文章 / 模拟电子
10836 0 1700

除法

  • 记：a | b 表示 a 整除 b
  • q=a div d； r=a mod d —– a=dq+r
    101 = 11 * 9+2————— 9=101 div 11； 2=101 mod 11

模算术

  • m整除 a-b 时 称 a 模 m 同余 b。
  • 记： a ≡ b (mod m)——- 同余式
    17是否模6同余5———17 ≡ 5(mod 6) : 6 整除 17-5
  • a ≡ b (mod m) 当且仅当 a mod m=b mod m

模m算术

  • a+mb=(a+b) mod m
  • a⋅mb=(a⋅b) mod m

整数的表示和算法

  • 整数的表示
    n=akbk+ak−1bk−1+......+a1b+a0
  • 进制转换
241=2*120 +1 120=2*60 + 0 60 =2*30 + 0 30= 2*15 + 0 15= 2*7 + 0 7= 2*3 + 1 3= 2*1 + 1 1= 2*0 + 1 (241)10=(11100001)
算法 : 构造b进制展开式 procedure base b expansion
q:=n
k:=0 while  q≠0
ak:=1 mod b
q:=q div b
k:=k+1 return(ak−1......a1a0)

整数加法运算

  • 原理：
    a=(an−1....a1a0)2和 b=(bn−1.....b1b0) a0+b0=c0∗2+s0——c0是进位
    a1+b1+c0=c1∗2+s0
    sn=cn−1是首位
  • 例子 ： a=(1110) 和 b=(1011) a0+b0=0+1=0∗2+1—–c0=0,s0=1
    a1+b1

热门文章