|
其他相對(duì)比較常用的數(shù)學(xué)相關(guān)內(nèi)容有：表達(dá)式求值、最大公約數(shù)與最小公倍數(shù)問題、質(zhì)數(shù)與質(zhì)因數(shù)分解問題等。 表達(dá)式求值，即用字符串給定一個(gè)表達(dá)式，然后求解表達(dá)式的值。表達(dá)式求解的方式大致有兩種：一種為模擬，一種為分治。 模擬法進(jìn)行表達(dá)式求值時(shí)，建立兩個(gè)棧，一個(gè)存放數(shù)值，一個(gè)存放運(yùn)算符。掃描表達(dá)式，如果遇到數(shù)值，直接存入數(shù)值棧，遇到運(yùn)算符，判斷與棧頂運(yùn)算符優(yōu)先級(jí)，如果高于棧頂運(yùn)算符，則存入運(yùn)算符棧，否則，執(zhí)行下面操作，直到當(dāng)前運(yùn)算符優(yōu)先級(jí)高于棧頂運(yùn)算符或棧為空。具體操作為：彈出當(dāng)前棧頂運(yùn)算符，并在數(shù)據(jù)棧中彈出相應(yīng)數(shù)據(jù)（一般為兩個(gè)，特殊情況如階乘只有一個(gè)），做運(yùn)算后，將運(yùn)算結(jié)果存入數(shù)值棧。最后，依次彈出并執(zhí)行運(yùn)算符棧中的運(yùn)算符，完成后，數(shù)據(jù)棧中僅存的數(shù)據(jù)，即為最終結(jié)果。需要注意的是，括號(hào)的棧外優(yōu)先級(jí)和棧內(nèi)優(yōu)先級(jí)不同，一般運(yùn)算優(yōu)先級(jí)見下表。 分治法進(jìn)行表達(dá)式求值時(shí)，對(duì)于表達(dá)式進(jìn)行掃描，找出優(yōu)先級(jí)最低的運(yùn)算法，遞歸處理該運(yùn)算符左右的表達(dá)式，然后進(jìn)行該運(yùn)算符的運(yùn)算。 求解最大公約數(shù)用的是輾轉(zhuǎn)相除法。用的依據(jù)是，如果正整數(shù)c是a和b的公約數(shù)，那么c也是b和a mod b的公約數(shù)。公式如下：最小公倍數(shù)即兩數(shù)相乘除以它們的最大公約數(shù)。? 質(zhì)數(shù)與質(zhì)因數(shù)分解： 質(zhì)數(shù)又稱素?cái)?shù)。指在一個(gè)大于1的自然數(shù)中，除了1和此整數(shù)自身外，不能被其他自然數(shù)整除的數(shù)。判斷數(shù)k是否為質(zhì)數(shù)，一般是掃描2到根號(hào)k內(nèi)的整數(shù)，看是否能整除k，如果有，則k不是質(zhì)數(shù)，否則k為質(zhì)數(shù)。也可建立2到根號(hào)k的質(zhì)數(shù)表用來掃描。找出區(qū)間2~n之間的所有質(zhì)數(shù)，即建立2~n的質(zhì)數(shù)表時(shí)，從小到大掃描，當(dāng)遇到質(zhì)數(shù)時(shí)，將其倍數(shù)刪去，最后剩余的數(shù)即為質(zhì)數(shù)表上的數(shù)。質(zhì)因數(shù)分解一般有兩種方法：方法一：產(chǎn)生一個(gè)從2到根號(hào)k的質(zhì)數(shù)表，然后從2開始除。在除干凈之后換下一個(gè)因數(shù)。方法二：不產(chǎn)生質(zhì)數(shù)表，直接從2開始除。在除干凈之后換下一個(gè)因數(shù)。（注：n是素?cái)?shù)時(shí)速度會(huì)非常慢）2.1 表達(dá)式求值，需要先做出運(yùn)算符優(yōu)先級(jí)表，再進(jìn)行代碼編寫。2.2 表達(dá)式求值有時(shí)需要配合高精度，建議寫成模塊形式，方便操作。2.3 表達(dá)式求值、最大公約數(shù)、質(zhì)數(shù)問題等，基本只需要套用模板即可，平時(shí)注意整理此類模板，會(huì)省力很多。例題3-1：等價(jià)表達(dá)式（NOIP2005） 【問題描述】明明進(jìn)了中學(xué)之后，學(xué)到了代數(shù)表達(dá)式。有一天，他碰到一個(gè)很麻煩的選擇題。這個(gè)題目的題干中首先給出了一個(gè)代數(shù)表達(dá)式，然后列出了若干選項(xiàng)，每個(gè)選項(xiàng)也是一個(gè)代數(shù)表達(dá)式，題目的要求是判斷選項(xiàng)中哪些代數(shù)表達(dá)式是和題干中的表達(dá)式等價(jià)的。這個(gè)題目手算很麻煩，因?yàn)槊髅鲗?duì)計(jì)算機(jī)編程很感興趣，所以他想是不是可以用計(jì)算機(jī)來解決這個(gè)問題。假設(shè)你是明明，能完成這個(gè)任務(wù)嗎？這個(gè)選擇題中的每個(gè)表達(dá)式都滿足下面的性質(zhì)：1． 表達(dá)式只可能包含一個(gè)變量‘a(chǎn)’。2． 表達(dá)式中出現(xiàn)的數(shù)都是正整數(shù)，而且都小于10000。3． 表達(dá)式中可以包括四種運(yùn)算‘+’（加），‘-’（減），‘*’（乘），‘^’（乘冪），以及小括號(hào)‘(’，‘)’。小括號(hào)的優(yōu)先級(jí)最高，其次是‘^’，然后是‘*’，最后是‘+’和‘-’?！?’和‘-’的優(yōu)先級(jí)是相同的。相同優(yōu)先級(jí)的運(yùn)算從左到右進(jìn)行。（注意：運(yùn)算符‘+’，‘-’，‘*’，‘^’以及小括號(hào)‘(’，‘)’都是英文字符）4． 冪指數(shù)只可能是1到10之間的正整數(shù)（包括1和10）。5． 表達(dá)式內(nèi)部，頭部或者尾部都可能有一些多余的空格。【輸入】輸入的第一行給出的是題干中的表達(dá)式。第二行是一個(gè)整數(shù)n (2≤n≤26)，表示選項(xiàng)的個(gè)數(shù)。后面n行，每行包括一個(gè)選項(xiàng)中的表達(dá)式。這n個(gè)選項(xiàng)的標(biāo)號(hào)分別是A，B，C，D……輸入中的表達(dá)式的長(zhǎng)度都不超過50個(gè)字符，而且保證選項(xiàng)中總有表達(dá)式和題干中的表達(dá)式是等價(jià)的。【輸出】輸出僅一行，這一行包括一系列選項(xiàng)的標(biāo)號(hào)，表示哪些選項(xiàng)是和題干中的表達(dá)式等價(jià)的。選項(xiàng)的標(biāo)號(hào)按照字母順序排列，而且之間沒有空格。a^2 + 2 * a * 1 + 1^2 + 10 -10 +a -a【分析】這道題目拿到手后，一般可以想到的方法就是可不可以將所有的表達(dá)式全部轉(zhuǎn)化為最簡(jiǎn)形式，這時(shí)，你就想到了一種一般的解決方案。即將所有的表達(dá)式全部化為最簡(jiǎn)，然后再計(jì)算，這種方法是一種準(zhǔn)確的方法。但要在考場(chǎng)上實(shí)現(xiàn)，有一些麻煩，需要一些時(shí)間。這種方法的解決過程是：先將階乘化乘，再展開。計(jì)算同時(shí)合并同類項(xiàng)，留下一個(gè)數(shù)組。然后比較每一個(gè)表達(dá)式的數(shù)組與題目數(shù)組是否相同，時(shí)間效率也并不高。那么怎么辦呢？即兩個(gè)表達(dá)式如果等價(jià)，那么無論a為何值，兩個(gè)表達(dá)式計(jì)算出的值都相等。這時(shí)，我們以不同的a值代入各式，可以快速排斥那些不同的表達(dá)式，留下的便是等價(jià)的了。1）取隨機(jī)函數(shù)生成的數(shù)列。這種方法比較有效，無規(guī)律。2）取偽隨機(jī)數(shù)列。這是一種比較便于人工控制的手段。3）取實(shí)數(shù)。由于其他皆為整數(shù)，小數(shù)部分便成為判斷的優(yōu)越條件。對(duì)于1、2兩種情況，有時(shí)表達(dá)式求解出的解會(huì)很大，應(yīng)考慮對(duì)一個(gè)大素?cái)?shù)取余數(shù)比較（由于沒有除法，所以取余不會(huì)出錯(cuò)）。一般情況下取4~7組值便可通過極大部分情況。如果取更多組的值，便可以通過幾乎所有的情況。在上述分析完成后，剩下就是表達(dá)式求解的過程?？捎媚M法或者分治法求解，此處略過。例題3-2：Hankson的趣味題（NOIP2009） 【問題描述】Hanks博士是BT（Bio-Tech，生物技術(shù)）領(lǐng)域的知名專家，它的兒子明教Hankson。現(xiàn)在，剛剛放學(xué)回家的Hankson正在思考一個(gè)有趣的問題。 今天在課堂上，老師講解了如何求兩個(gè)正整數(shù)c1和c2的最大公約數(shù)和最小公倍數(shù)?，F(xiàn)在Hankson認(rèn)為自己已經(jīng)熟練地掌握了這些知識(shí)，它開始思考一個(gè)“求公約數(shù)”和“求公倍數(shù)”之類問題的“逆問題”，這個(gè)問題是這樣的：已經(jīng)正整數(shù)a0, a1, b0, b1，設(shè)某未知正整數(shù)x滿足：Hankson的“逆問題”就是求出滿足條件的正整數(shù)x。但稍加思索后，它發(fā)現(xiàn)這樣的x并不唯一，甚至可能不存在。因此他轉(zhuǎn)而開始考慮如何求解滿足條件的x的個(gè)數(shù)。請(qǐng)你幫助他編程求解這個(gè)問題。【輸入】第一行為正整數(shù)n，表示有n組數(shù)據(jù)。接下來，的n行，每行一組數(shù)據(jù)，為四個(gè)正整數(shù)a0, a1, b0, b1，每?jī)蓚€(gè)整數(shù)之間用一個(gè)空格隔開。輸入數(shù)據(jù)保證a0能被a1整除，b1能被b0整除。【輸出】共n行。每行只有一個(gè)整數(shù)，即該組數(shù)據(jù)的結(jié)果。對(duì)于每組數(shù)據(jù)，輸出滿足條件的x的個(gè)數(shù)，若不存在這樣的x，則輸出0。【分析】這道題的思路就是分解質(zhì)因數(shù)。首先，不難得到gcd(x/a1,a0/a1)=1以及gcd(b1/x,b1/b0)=1。假設(shè)對(duì)于一個(gè)質(zhì)因數(shù)y，a0含有a0c個(gè)y，a1含有a1c個(gè)y，b0含有b0c個(gè)y，b1含有b1c個(gè)y。那么不難得到，如果a0c<a1c，那么就無解；如果a0c=a1c，那么x至少含有a1c個(gè)y；如果a0c>a1c，那么x只可能含有a1c個(gè)y。同理，如果b1c<b0c，那么就無解；如果b1c=b0c，那么x至多含有b1c個(gè)y；如果b1c>b0c，那么x只可能含有b1c個(gè)y。由此，可以求出對(duì)于每一個(gè)質(zhì)數(shù)，x可能含有幾個(gè)它，并求出一共有多少種選擇方式。然后根據(jù)乘法原理，將每一個(gè)質(zhì)數(shù)的選擇方案數(shù)乘起來，就得到了答案。有任何問題請(qǐng)留言給我們或者直接回復(fù)本公眾號(hào)~歡迎與我們互動(dòng)。
|
