【正文】 磁卡。對于任何一個工作人員來說，其余 m－ 1個人中任意 n－ 1個人在場，至少缺少一個這個工作人員磁卡上具有的特征而無法打開鎖。要求輸出的電子鎖的總特征數(shù)最少。 m個工作人員每人發(fā)一張磁卡，卡上有開鎖的密碼特征。要準確計算 Ramsey數(shù)，只要將程序返回的整數(shù)值逐一遞減。 ? end。 ? Begin ? for i:=2 to a do r[I,2]:=I。 ? readln(b)。 ? repeat write(‘a(chǎn)=’)。 ? Var r: rtype。 ? 確定 Ramsey數(shù)是很難的問題。 數(shù)學描述： m（ m=1）個元素分成 n個組，那么總有一個組至少含有元素個數(shù)為[m/n]。 作為練習 ? 一個售貨亭前排著 2N個人的隊伍等候購物，假定他們都購買價值 5元的同一貨物。 ? Var … ? Begin ? make(L+1)。 棧 — 重要的數(shù)據(jù)結構 ? 遞歸過程 make（ L） ? 1 分配一個連續(xù)的數(shù)組區(qū)域stack[1..maxdepth]順序存放棧中表目，即當前路徑的節(jié)點。檢查 t的節(jié)點是否對應問題的目標狀態(tài)。 Var stack： array[1。 3。 N皇后問題 ? 例子，一個 n n的國際象棋棋盤上放置 n個皇后，使其不能相互攻擊，即任何兩個皇后都不能處在棋盤的同一行同一列同一條斜線上，試問有多少中擺法？ ? 一 如何求 n皇后問題 1 狀態(tài)（ state） 狀態(tài)是指問題求解過程中每一步的狀況。 2。 區(qū)域總數(shù)為 C（ n， 4）＋ C（ n－ 1， 2） ? 各區(qū)域頂點總數(shù)（包括重復計數(shù)） ? 角度 1： ? 角度 2：所有區(qū)域的內(nèi)角和的總和的等式 ? 兩邊同除以 180度得 ? 兩式相減得區(qū)域總數(shù) 4 數(shù)論方法 ? 運用奇偶性，整除性等數(shù)論性質進行存在性問題的分析與推理。用一個排列 a1， a2， … ， a8，對應于一個安全狀態(tài)，使 ai表示第 i行的 ai列上放置一個車。主要用于解那些需要獨立思考見解獨到和有所創(chuàng)新的問題。 4。 信息學競賽中一般分為兩種類型：一種是計算某種特性的對象有多少；另一種是枚舉類型，把所有具有某種特性的對象都列舉出來。 ? 例如，將 8個“車”放在 8 8的國際象棋棋盤上，如果他們兩兩不能互吃，那么稱 8個“車”處于一個安全狀態(tài)。 ? 競賽時不可能出現(xiàn)專門判定某個問題有解或無解的試題。 1。 這種安排是否存在，即存在性問題； 2。 i 201。 ? t[j + 1]。 j++) ? t[al2 j] = b[bl j]。 ? for(i = 0。 i 0。 i 0。 i++) ? { c[i] = 0。 ? } 除法運算 ? void division(int a[301], int b[201], int c[301], int d[201]) ? //除法函數(shù)， 300位除 200位 ,c為商， d為余數(shù) ? { ? int al, bl, t[301]。 ? } ? if(a[ab i] b[bb i]) ? { result = 1。 i bb。 ? for(i = 300。 ? } ? return 0。i301。 ? } ? for (k=j。s++) ? sum2[s]=m[s]+sum1[s]。 //sum1所有位置零 ? for (i=1。j201。 // sum2 、 sum1中間過渡量 ? for (i=1。i++) ? p[i]=rand()*10/RAND_MAX。 ? (x^y1)/(x1) = x^(y1)+x^(y2)+x^(y3)+….+x^0 ? 將這個值算出來 . 例子 討論： ? 這題目一定要先判斷位數(shù)，如果大於100位就不用算了，不然會超過時間，且要用比較好的方法算真正的值，若用大數(shù)除法，會太慢，所以改成 ? (x^y1)/(x1) = x^(y1)+x^(y2)+x^(y3)+….+x^0 ，這樣的方式來算，比較快 ! 隨機產(chǎn)生一個 200位的數(shù) ? int random(int p[201]) //隨機產(chǎn)生一個 200位的數(shù) ? { ? p[1]=1。 大整數(shù)的乘法 A C D B X= Y= ).()()(2)))(((2).()(2)(2)2)(2(,2,2 og2/22/2/2/2/2/nOnOnTBDBDACCDBAACXYnOnTBDCBADACDCBAXYDCYBAXnnnnnnnn?????????????????????例子 ? 題意： ? 本題目給三個數(shù)字 t,a,b(都比 2147483647小 )，問 (t^a 1)/(t^b 1)是大小於 100位數(shù)或是否為整數(shù)，若小於 100位數(shù)，就印該值。 c=1。 for(i=0。ij。大 數(shù)運算與組合數(shù)學 －－ ACM國際大學生程序設計競賽 主講：王樹林 問題 ? 當有一個很大的整數(shù)要運算時 , 如何算 ? ? 例如 : 一個一佰位數(shù)的數(shù)字 . ? int 最大只能到 232 約十個位數(shù)的十進位數(shù)字 . 最簡單的方法 ? 先看大數(shù)加法 . ? 就是改成手動去算加法 , 而不是由電腦算 . 123456789123 + 234123467890 寫成電腦程式 ? 方法一 : 使用陣列 (array) ? 例如 : int a[100], b[100], sum[100]。 for(i=0。 c=0。 if(sum[i]=10){ sum[i]=sum[i]10。 ? 大數(shù)取模運算的算法實現(xiàn) ? 在取模運算中用到了上面的除法運算，只需返回余數(shù)即可。 ? Log10(x^(y1)) = log10(t^(ab)) = (ab)*log10(t) ? ∴ if((ab)*log10(t) =99),就一定會大於 100位數(shù) ? 若沒有大於 100位數(shù)，有可能等於 100位數(shù)，所以要算出來。i=200。 ? } 乘法運算 ? int multiply(int m[101],int n[201],int product[301])//兩因子 m 、 n，乘積 product ? { int sum1[102],sum2[102],i,j,k,s。}// sum2所有位置零 ? for (j=1。i++)sum1[i]=0。s101。 k++) ? sum1[k]=sum2[k]。//即是實現(xiàn)了乘法過程中的加法 ? } ? for (i=1。 ? product[i]=j*10。