實(shí)現(xiàn)的一個(gè)具體算法實(shí)例
這個(gè)算法的功能是
在向下取整的意義上的除法
具體來說 對(duì)于任何一個(gè)非負(fù)整數(shù)c
和正整數(shù)d 我們都需要在做完除法之后
再實(shí)施向下取整 得到一個(gè)整數(shù)
那么這個(gè)輸出
實(shí)際上也就是不超過c/d的那個(gè)最大整數(shù)
我們可以將它表述為
在所有那些與d相乘以后
不大于c的整數(shù)x中的最大值
也可以等效的表述為
在所有乘以d以后嚴(yán)格的小于c+1的
那些整數(shù)x中的最大值
這樣一種重新的表述
其實(shí)不光是文字上的一個(gè)轉(zhuǎn)換
更重要的是
它為我們提供了一個(gè)對(duì)應(yīng)的算法思路
我們可以將它表述并且實(shí)現(xiàn)如下
具體來講 我們需要保留c+1
并且以它為基礎(chǔ) 反復(fù)的從中去減除d
因?yàn)镽AM模型只支持加或者減運(yùn)算
不斷的減除
直到對(duì)應(yīng)的那個(gè)寄存器R[0]發(fā)生下溢
也就是說 它不再是一個(gè)正數(shù)
這個(gè)時(shí)候 我們統(tǒng)計(jì)下
在此之前所做過減法運(yùn)算次數(shù)
那么它就是我們所要得到的輸出
我們可以將整個(gè)這個(gè)思路兌現(xiàn)如下
因?yàn)檫@里所有的加法運(yùn)算和減法運(yùn)算
都不允許直接對(duì)常數(shù)進(jìn)行
而我們一上來就需要做個(gè)預(yù)處理
對(duì)c+1 所有需要利用常數(shù)賦值語句
將這個(gè)增量1預(yù)先的存到一個(gè)寄存器
比如R[3]中去
所有接下來我們對(duì)R[0]
也就是最初輸入的c
加R[3]之后 實(shí)際上效果就是c自增
所以在經(jīng)過這樣的預(yù)處理之后
c+1確實(shí)被存放到R[0]中去了
那么接下來 從第二句開始
如果注意到這里有個(gè)goto第2個(gè)語句的話
我們就知道這實(shí)際上是構(gòu)成了一個(gè)循環(huán)
那么這個(gè)循環(huán)是做什么事呢
正如我們前面所說的那樣
它是不斷的需要從剛才那個(gè)量里頭去
刨除掉d
d本身也是作為輸入的一部分
已經(jīng)事先存放在1號(hào)寄存器中了
所以每次做的事情
就是從剛才經(jīng)過預(yù)處理以后
存放的實(shí)際上是c+1的
那個(gè)寄存器R[0]中減除掉d
不斷的減除 每減除一次
我們剛才說過
要相應(yīng)的把計(jì)數(shù)器累計(jì)
這個(gè)計(jì)數(shù)器在哪呢
在我們這里取做的就是R[2]
第2個(gè)寄存器 它的初值是0
所以每一次它都要自加
加一個(gè)1 而加的這個(gè)1
依然是通過我們預(yù)先賦值
那個(gè)常數(shù)存到R[3]中去來實(shí)現(xiàn)
經(jīng)過了這樣一次自減
經(jīng)過了一次計(jì)數(shù)器的累加之后
我們這個(gè)時(shí)候就要判斷 R[0]
也就是c+1初始的那個(gè)數(shù)
是否已經(jīng)不再是一個(gè)正數(shù)了
如果它還是正數(shù)
那就說明還沒有減除完
這個(gè)時(shí)候我們可以通過goto語句
像剛才所說的繼續(xù)執(zhí)行這一步
所以反過來說
如果我們有朝一日?qǐng)?zhí)行到了第5條語句
那就說明R[0]經(jīng)過若干次減除以后
已經(jīng)不再是一個(gè)正數(shù)
而這個(gè)時(shí)候呢
我們大致就可以返回這個(gè)x
當(dāng)然 通過精細(xì)的分析我們會(huì)發(fā)現(xiàn)
實(shí)際上這個(gè)數(shù)值是差一的
所以這里頭我們還要將R[3]
也就是原來存放的這個(gè)常數(shù)1
再減一次
經(jīng)過了這樣一次減法以后
再把這個(gè)數(shù)值返回回去
才會(huì)得到真正準(zhǔn)確的
我們所需要的那個(gè)向下取整的除法值
那么我們把這樣的一個(gè)
具體實(shí)例也羅列出來了
具體來說就是
對(duì)于c=12以及d=5來做的一個(gè)除法
不難發(fā)現(xiàn) 如果不取整的話是2.4
所以向下取整的話 應(yīng)該得到的是2
不出意外 在我們對(duì)照代碼
逐行逐條的將整個(gè)寄存器序列的內(nèi)容
作一羅列之后
我們會(huì)發(fā)現(xiàn) 最終在R[0]這個(gè)位置上
會(huì)得到并且返回我們
所需要的那個(gè)值 也就是2
那么這個(gè)算法的正確性
以及更多的例子的給出
留給同學(xué)們?cè)谡n后完成
而我們這里需要向大家
傳達(dá)的一個(gè)重要的概念
是這張表所暗示的
也就是說 我們不光可以把整個(gè)計(jì)算過程
逐次羅列出來
更重要的是 正像剛才所說的那樣
我們將整個(gè)計(jì)算過程所需要的計(jì)算成本
轉(zhuǎn)化為了這個(gè)表的規(guī)模 或者說它的高度
具體來說就是它的行數(shù)
其實(shí)就是執(zhí)行的基本操作的次數(shù)
按照我們剛才的推斷
實(shí)際上就是我們這個(gè)算法
所需時(shí)間的一個(gè)最客觀的度量
而這個(gè)度量是清晰的 明確的
可比較的 而且沒有歧義的
概括一下
我們通過圖靈機(jī)模型和RAM模型
給大家一個(gè)清晰的尺度
這個(gè)尺度確實(shí)可以用來對(duì)算法進(jìn)行度量
我們可以此判斷 哪個(gè)算法的性能更好
至少在什么情況下更好
當(dāng)然 也像我們開篇的時(shí)候所說的那樣
這只是一把尺子
我們這節(jié)只告訴你尺子是什么
那么更重要的一個(gè)問題就是
尺子怎么用 如何用好這把尺子
有什么樣的一些規(guī)則 有哪些技巧
那么我們要留待后續(xù)課節(jié)再向大家作介紹

總結(jié)

以上是生活随笔為你收集整理的RAM的一个实例，向下取整的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。