一把無限長的直尺，如何用最少的刻度將所有的整數長度（cm）都能畫出來？
一把無限長的直尺，有0刻度，1cm處有刻度，這樣就可以畫1cm長的線段了，在3cm處有刻度，就可以畫1cm，2cm，3cm長的線段了，如此類推，怎麼畫刻度可以用最少的刻度線一次性畫出所有整數長度（cm）的線段？
謝謝邀請。
一個簡單的方法是：用貪心演算法，每個新刻度和上個刻度的間隔都是之前所有刻度所不能表示出來的最小正整數，於是，我們得到一個數列：1,3,7,12,20,30……
實際上，可以查到，這是一個已經存在的數列：
A002049： Prime numbers of measurement.（A002049 - OEIS）
1, 3, 7, 12, 20, 30, 44, 59, 75, 96, 118, 143, 169, 197, 230, 264, 299, 335, 373, 413, 455, 501, 549, 598, 648, 701, 758, 818, 880, 944, 1009, 1079, 1156, 1236, 1317, 1400, 1485, 1571, 1661, 1752, 1844, 1944, 2048, 2155, 2263, 2379, 2498, 2622, 2749, 2881……在文獻： G. E. Andrews, MacMahon"s prime numbers of measurement, Amer. Math. Monthly, 82 (1975), 922-923. 中，Andrews 推斷：
這表述還是有點問題吧，想要一次量出所有整數刻度需要無限的刻度，所以最少這一概念就無從談起了。我擅自理解下題主的意思，是對於長度為n的直尺，最少需要f(n)個刻度來量出1到n這n個整數刻度。當n趨於無窮時給出f(n)關於的n的階數以及策略。
之前的貪心演算法直觀上階數應該是比較小的吧，不過同樣的階數我猜測絕對有很多策略來實現。想找到最小的感覺是硬骨頭。。。事實上只要在1厘米有刻度的話，就已經可以畫所有整數厘米的長度了。
emmm， @曾加 所說方法固然不錯，但不一定最優解。由於題目問的是最少，那麼就是問的就是最優解，從這個角度來說，貪心演算法的使用時需要證明的。
比如說我在一根直尺上假設有 個刻度，那麼理論上能表示長度的上限是
個。從另一個角度來說，也就是每增加一個刻度盡量不要產生重複的長度。
但如果使用貪心演算法是會產生重複的長度的，如圖中52. 我代碼生成的第 行就是從第
個刻度與它後面的所有刻度依次產生的長度。
也就是說貪心演算法沒有到達理論（可能的）最優，但這並不是說貪心演算法一定是錯的，只是說不一定是對的。
以及，我有一點關於題目的疑問，如果是要將所有整數長度表示出來，那麼就需要無窮多的刻度，而無窮多在簡單意義上是不可比的，又何來最少？一定要一個最少的話，那就是 .
感覺樓主的問題描述不清晰。如果是最少的，那麼只要一個1cm就可以了
按照題主的意思，怕是要［無限個］刻度才能辦到這件事情。事實上不管你怎麼設置刻度，最終需要的刻度［個數］基本上都是［阿列夫］個。
這裡涉及到如何計算無限集合的元素個數的問題。具體地說，把所有你需要設置的刻度視作一個集合，這個集合肯定是個無限集。我們考慮無限集的元素個數的時候，必須要用一種特殊的計數方式。(不知道題主有沒有聽說過「整數和奇數一樣多」這種說法呢？)剛剛的［阿列夫］可以認為是這種計數方式下的［計量單位］。
我瞬間想到一個可行解，可能從小考試太多，答題卡上的數字1,2,4,8 依此推算,但 這應該不是最優解
建議修改成天平，用最少個數的砝碼測量整數重量
題主，這個尺子很不好用啊。
你如果用這個尺子去量東西，難道是去匹配尺子上某個區間跟這個一樣長? 然後做減法?
你如果是要用這個尺子畫固定長度的線段，計算如何找區間繪畫也是很麻煩的。話說這不是用時間換空間嗎? 尺子操作頻繁的話，當然還是選擇空間大耗時短的呀。首先直線沒有長度
另外如果你是想用最少的刻度畫出所有正整數長度的線段的話
1單位長度就夠了(逃推薦閱讀：
※一道阿里筆試題，思路應該是怎樣？
※如何計算std::vector的push_back方法插入一個對象的平均時間（要寫出計算式）？
※JDK源碼DualPivotQuicksort類中利用移位求除7近似值？
※一個與矩陣有關的演算法問題？
※將一個稀疏圖平均切分成 k 個子圖的時間複雜度是多少？