複製鏈接
請複製以下鏈接發送給好友

打表

鎖定
打表,是一個信息學專用術語,意指對一些題目,通過打表技巧獲得一個有序表或常量表,來執行程序某一部分,優化時間複雜度。這種算法也可用於在對某種題目沒有最優解法時,用來得到分數的一種策略。
打表還可以指出租車開計價器,你要求打表(打開計價器)的話,會顯示出你所經過的里程和所應支付價格,對司機而言就意味着一張發票和費用;所以問你打不打表就是問你要不要發票。如果你和司機是商談了打車的價格,比較便宜的話,一般是不會給你打表的。正常情況下你應該堅持打表,這樣如果有意外事情發生,你可以通過發票追查到你乘坐過的車輛。
中文名
打表
外文名
Make Charts
概    念
手算出一個有序表或常量表來優化程序時間複雜度
用    途
OI競賽

打表打表一般步驟

打表找到答案的方式

一、通過暴力搜索,找出對於數據的答案,適用於數據較大,題目簡單的情況;
二、通過手算,找出每個數據的答案,適用於數據較小且題目較難的情況;
三、在某些題目中,因為考慮到預處理出所有答案的時間複雜度可能會比依次讀入再求更優,所以就在讀入數據前進行對所有可能的詢問的答案或部分必要條件的預處理。這種方法雖然也是打表,但編程複雜度不亞於其他程序,而且一般是題目的正解。

打表輸出答案的方式

一、直接在程序內打表,如果打表複雜度較大則不可用。
二、提前打表,然後複製放入程序。
直接帶入數據的打表佔用空間大 直接帶入數據的打表佔用空間大

打表打表的技巧

1、可把一些相差不大的數據化為與上一段之差:
例如: f[i]儲存為f[i]-f[i-1]
輸出時以前綴和形式輸出。
2、分段打表。
把數據分為幾段,每段根據輸入數據,找到相應倍數進行輸出。