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