貪心算法antiprime數(shù)解題報告

1、試題： 正整數(shù)n是一個Antiprime數(shù)，如果這個數(shù)的約數(shù)個數(shù)超過比n小的任何數(shù)的約數(shù)個數(shù)。例如：下列Antiprime數(shù)1，2，4，6，12和24。【任務(wù)】編寫程序： 1從文件ANT.IN讀入正整數(shù)n； 2指出不超過n的最大的Antiprime數(shù)； 3將這個數(shù)輸?shù)轿募嗀NT.OUT；【輸入】： 在輸入文件ANT.IN有一個整數(shù)n。1n2000000000【輸出】：輸出文件ANT.OUT應(yīng)該有一個正整數(shù)：不超過n的最大Antiprime數(shù)。試題分析：設(shè)不超過的最大Antiprime數(shù)為。實際上就是1到的個正整數(shù)中，正約數(shù)個數(shù)最多的數(shù)中最小的一個。設(shè)為互不相等的質(zhì)數(shù)，則的正約數(shù)個數(shù)為:用反證法

2、不難證得: 必是最小的個質(zhì)數(shù)。不妨設(shè)又我們只需搜索序列的值了。有沒有剪枝條件呢？是1到的個正整數(shù)中，正約數(shù)個數(shù)最多的數(shù)中最小的一個。時,，即序列是非遞增的。 反證法:當(dāng)時,若則另又，,故不是Antiprime數(shù)。故假設(shè)不成立。根據(jù)這個性質(zhì)，又可以大大的減少搜索量了。算法設(shè)計：有了前面的分析后，算法就很容易得到了。只要一個很簡單的深搜就能夠?qū)崿F(xiàn)。性能分析：根據(jù)實踐證明：K序列的個數(shù)最多為1456，因此速度非?？??？臻g需求：啟發(fā)與總結(jié)：求質(zhì)樹個數(shù)、分解質(zhì)因數(shù)、輾轉(zhuǎn)相除法等有關(guān)質(zhì)數(shù)的題目在比賽中出現(xiàn)的次數(shù)是較多的。解決這類問題需要有一些基本的數(shù)學(xué)知識，比如說質(zhì)因子個數(shù)的計算公式和整除的一些基本性質(zhì)等

3、等。有了這些基本知識，做起本題來就變得非常容易了。程序清單：$O-,P-,Q-,R-,S-$M 65521,0,655360program Lic;const Fn1 = Lic.In; Fn2 = Lic.Out; T = 9; PrimeNum: array1 . T of Longint = (2, 3, 5, 7, 11, 13, 17, 19, 23);var N, Max, Min: Longint;procedure Init;begin Assign(Input, Fn1); Reset(Input); Readln(N); Close(Input)end;輸入procedur

4、e Try(Step, k, M: Integer; j: Longint);Step為表示搜索到第幾個質(zhì)數(shù),表示前表示有多少個約數(shù),即:表示var i: Integer;begin if (Step T) or (M = 0) then begin if k = Max then begin if j Max then begin Max := k; Min := j end; Exit end;判斷新狀態(tài)是否更優(yōu) i := 0; repeat Try(Step + 1, k * (i + 1), i, j); if j M then Exit until Falseend;procedure Print;begin Assign(Output, Fn2); Rewrite(Output); Writeln