淺談設(shè)計(jì)獲勝策略(存儲版)
【正文】 個限制的最后一次起作用。嵌套最深的（因而也是最慢的）循環(huán)支配著運(yùn)行時間，同時它也是在討論O( ) 符號時唯一考慮的循環(huán)。 /* increase the value of i by 1*/ 這樣的注釋是毫無意義的。 將調(diào)試輸出關(guān)閉。 競賽中的策略 首先通讀所有的題目；草擬出算法，復(fù)雜度，數(shù)量，數(shù)據(jù)結(jié)構(gòu)，微妙的細(xì)節(jié)，… 集體討論所有可能的算法 —— 然后選擇最“笨”但卻可行的算法。 心理上的準(zhǔn)備也很重要。 在你上交你的答案之前列出一個校驗(yàn)表： 在競賽結(jié)束前五分鐘凍結(jié)代碼？（？？原文是Code freeze five minutes before end of contest?） 將所有的聲明關(guān)閉。 盡量不要使用浮點(diǎn)數(shù)；如果你不得不使用，在所有使用的地方設(shè)置允許的誤差（絕對不要測試兩個浮點(diǎn)數(shù)相等） 對注釋的注釋： 不要寫得太長，簡潔的注解就可以了 解釋復(fù)雜的功能：++i。 一種推算一個程序的O( ) 運(yùn)行時間的方法是檢查它的循環(huán)。 640K確實(shí)是苛刻的內(nèi)存限制。 解決方案的范例 產(chǎn)生器 vs. 過濾器 產(chǎn)生大量可能的答案然后選擇其中正確的（比如8皇后問題的解答），這樣的程序叫做過濾器。競賽題經(jīng)常要用到素?cái)?shù)——生成一長串素?cái)?shù)在程序中某處使用通常是很實(shí)用的。 正向 vs. 逆向 令人驚訝地，許多競賽題用逆向法解決比正面突破要好得多。 time plexity, and plug in actual expected and worst case numbers) Try to break the algorithm use special (degenerate?) test cases Order the problems: shortest job first, in terms of your effort (shortest to longest: done it before, easy, unfamiliar, hard) Coding a problem For each, one at a time: Finalize algorithm Create test data for tricky cases Write data structures Code the input routine and test it (write extra output routines to show data?) Code the output routine and test it Stepwise refinement: write ments outlining the program logic Fill in code and debug one section at a time Get it working amp。t reuse variables, stepwise refinement, COMMENT BEFORE CODE. Avoid pointers if you can Avoid dynamic memory like the plague: statically allocate everything. Try not to use floating point。 here we will concentrate discussion on time. One deduces the O( ) run time of a program by examining its loops. The most nested (and hence slowest) loop dominates the run time and is the only one mentioned when discussing O( ) notation. A program with a single loop and a nested loop (presumably loops that execute N times each) is O(N 2), even though there is also a O(N) loop present. Of course, recursion also counts as a loop and recursive programs can have orders like O(b N), O(N!), or even O(N N). Rules of thumb When analyzing an algorithm to figure out how long it might run for a given dataset, the first rule of thumb is: modern (1999) puters can deal with 10M actions per second. In a five second time limit program, about 50M actions can be handled. Really well optimized programs might be able to double or even quadruple that number. Challenging algorithms might only be able to handle half that much. 640K is a really tight memory constraint. Happily, the 19992000 season is the last time this constraint applies. 210 ~approx~ 10 3 If you have k nested loops running about N iterations each, the program has O(N k) plexity. If your program is recursive with b recursive calls per level and has l levels, the program O(b l) plexity. Bear in mind that ther
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號-1