自從開始做公眾號開始,就一直在思考,怎么把算法的訓練做好,因為思海同學在算法這方面的掌握確實還不夠。因此,我現(xiàn)在想做一個“365算法每日學計劃”。
“計劃”的主要目的:
1、想通過這樣的方式監(jiān)督自己更努力的學習算法。
2、想和小伙伴們“組團”一起來學習交流學習算法過程中的點點滴滴。 “
計劃”的主要內容:
1、數(shù)據(jù)結構和算法的基礎知識鞏固。
2、逐步進階的oj算法訓練。 “計劃”的時間安排:每周三和周六 文章有點長,希望能耐心的看完。
——說在前面
“算法每日學”計劃01打卡:
問題描述
已知一個正整數(shù)N,問從1~N中任選出三個數(shù),他們的最小公倍數(shù)大可以為多少。 輸入格式
輸入一個正整數(shù)N。 輸出格式 輸出一個整數(shù),表示你找到的最小公倍數(shù)。 樣例輸入 9 樣例輸出 504 數(shù)據(jù)規(guī)模與約定
1 <= N <= 106。
解題思路與實現(xiàn)
下面這個思路是“算法每日學交流社區(qū)”的小伙伴給出的,感謝小伙伴們的支持與關注。
思路分析:
大 最小公倍數(shù),聯(lián)想到兩個數(shù)的求大最小公倍數(shù),即兩個數(shù)的乘積(注:連續(xù)的兩個自然數(shù)是互斥的)。
同樣,我們可以拿最后三個數(shù)來做考慮。
1.當n為奇數(shù)時,n,n-1,n-2為奇偶奇,里面只有一個偶數(shù),所以不會有2這個因子。這三個數(shù)相差不到3,所以也不會有因子3,故符合題意。
2.當n為偶數(shù)時,n,n-1,n-2為偶奇偶,此時n,n-2肯定含有因子2,所以除于2不值得。所以考慮將n-2 換成n-3,變成奇偶奇,此時也有一個問題,
n和n-3,如果n%3==0,則除于3更不值得。仍根據(jù)奇偶奇的原則,變動偶數(shù)n為n-2,此時換成n-1,n-2,n-3和1情況一樣。故此時符合題意。
所以根據(jù)上面的分析,我們可以寫出下面的代碼:
1import java.util.Scanner; 2public class Main{ 3 public static void main(String[] args) { 4 Scanner scanner = new Scanner(System.in); 5 long n = scanner.nextLong(); 6 long result; 7 if(n<3) 8 result=n; 9 else{ 10 if(n%2!=0) 11 result=n*(n-1)*(n-2); 12 else if(n%3!=0) 13 result=n*(n-1)*(n-3); 14 else 15 result=(n-1)*(n-2)*(n-3); 16 } 17 System.out.println(result); 18 } 19}
其實,上面的算法是用到了貪心的思想,大概是這樣的思路:
從大的三個數(shù)開始考慮,如果大的數(shù)為奇數(shù),那么相鄰的三個數(shù)中有兩個奇數(shù),大公約數(shù)為1,最小公倍數(shù)就為n(n-1)(n-2). 如果為偶數(shù),那么往后移,考慮n(n-1)(n-3),這時n和n-3相差3,式子滿足條件的前提是n不能被3整除,否則結果只能是(n-1)(n-2)(n-3).
這個題目因為用到了貪心的思想,所以下面介紹一下貪心算法。
所謂貪心算法是指,在對問題求解時,總是做出在當前看來是最好的選擇。也就是說,不從整體最優(yōu)上加以考慮,他所做出的僅是在某種意義上的局部最優(yōu)解。
貪心算法沒有固定的算法框架,算法設計的關鍵是貪心策略的選擇。必須注意的是,貪心算法不是對所有問題都能得到整體最優(yōu)解,選擇的貪心策略必須具備無后效性,即某個狀態(tài)以后的過程不會影響以前的狀態(tài),只與當前狀態(tài)有關。
所以對所采用的貪心策略一定要仔細分析其是否滿足無后效性。
1.建立數(shù)學模型來描述問題。 2.把求解的問題分成若干個子問題。 3.對每一子問題求解,得到子問題的局部最優(yōu)解。 4.把子問題的解局部最優(yōu)解合成原來解問題的一個解。
貪心策略適用的前提是:局部最優(yōu)策略能導致產生全局最優(yōu)解。
實際上,貪心算法適用的情況很少。一般,對一個問題分析是否適用于貪心算法,可以先選擇該問題下的幾個實際數(shù)據(jù)進行分析,就可做出判斷。
1 從問題的某一初始解出發(fā); 2 while (能朝給定總目標前進一步) 3 { 4 利用可行的決策,求出可行解的一個解元素; 5 } 6 由所有解元素組合成問題的一個可行解;
因為用貪心算法只能通過解局部最優(yōu)解的策略來達到全局最優(yōu)解,因此,一定要注意判斷問題是否適合采用貪心算法策略,找到的解是否一定是問題的最優(yōu)解。
下面是一個可以試用貪心算法解的題目,貪心解的確不錯,可惜不是最優(yōu)解。
例題① [背包問題]有一個背包,背包容量是M=150。有7個物品,物品可以分割成任意大小。 要求盡可能讓裝入背包中的物品總價值大,但不能超過總容量。 物品 A B C D E F G 重量 35 30 60 50 40 10 25 價值 10 40 30 50 35 40 30
分析:目標函數(shù):∑pi大約束條件是裝入的物品總重量不超過背包容量:∑wi<=M( M=150)(1)根據(jù)貪心的策略,每次挑選價值大的物品裝入背包,得到的結果是否最優(yōu)? (2)每次挑選所占重量最小的物品裝入是否能得到最優(yōu)解? (3)每次選取單位重量價值大的物品,成為解本題的策略。
值得注意的是,貪心算法并不是完全不可以使用,貪心策略一旦經過證明成立后,它就是一種高效的算法。 貪心算法還是很常見的算法之一,這是由于它簡單易行,構造貪心策略不是很困難。
可惜的是,它需要證明后才能真正運用到題目的算法中。
一般來說,貪心算法的證明圍繞著:整個問題的最優(yōu)解一定由在貪心策略中存在的子問題的最優(yōu)解得來的。 對于例題中的3種貪心策略,都是無法成立(無法被證明)的,解釋如下:
(1)貪心策略:選取價值大者。反例:
W=30 物品:A B C 重量:28 12 12 價值:30 20 20
根據(jù)策略,首先選取物品A,接下來就無法再選取了,可是,選取B、C則更好。
(2)貪心策略:選取重量最小。它的反例與第一種策略的反例差不多。 (3)貪心策略:選取單位重量價值大的物品。反例:
W=30 物品:A B C 重量:28 20 10 價值:28 20 10
根據(jù)策略,三種物品單位重量價值一樣,程序無法依據(jù)現(xiàn)有策略作出判斷,如果選擇A,則答案錯誤。
例題②[均分紙牌]有N堆紙牌,編號分別為1,2,…,n。每堆上有若干張,但紙牌總數(shù)必為n的倍數(shù).可以在任一堆上取若干張紙牌,然后移動。移牌的規(guī)則為:在編號為1上取的紙牌,只能移到編號為2的堆上;在編號為n的堆上取的紙牌,只能移到編號為n-1的堆上;其他堆上取的紙牌,可以移到相鄰左邊或右邊的堆上。現(xiàn)在要求找出一種移動方法,用最少的移動次數(shù)使每堆上紙牌數(shù)都一樣多。例如:n=4,4堆紙牌分別為:① 9 ② 8 ③ 17 ④ 6 移動三次可以達到目的:從③取4張牌放到④ 再從③區(qū)3張放到②然后從②去1張放到①。
輸入輸出樣例:4
9 8 17 6
屏幕顯示:3
算法分析:設a[i]為第I堆紙牌的張數(shù)(0<=I<=n),v為均分后每堆紙牌的張數(shù),s為最小移動次數(shù)。
我們用貪心算法,按照從左到右的順序移動紙牌。如第I堆的紙牌數(shù)不等于平均值,則移動一次(即s加1),分兩種情況移動:
1.若a[i]>v,則將a[i]-v張從第I堆移動到第I+1堆; 2.若a[i]<v,則將v-a[i]張從第I+1堆移動到第I堆。
為了設計的方便,我們把這兩種情況統(tǒng)一看作是將a[i]-v從第I堆移動到第I+1堆,移動后有a[i]=v; a[I+1]=a[I+1]+a[i]-v
.
在從第I+1堆取出紙牌補充第I堆的過程中可能回出現(xiàn)第I+1堆的紙牌小于零的情況。
如n=3,三堆指派數(shù)為1 2 27 ,這時v=10,為了使第一堆為10,要從第二堆移9張到第一堆,而第二堆只有2張可以移,這是不是意味著剛才使用貪心法是錯誤的呢?
我們繼續(xù)按規(guī)則分析移牌過程,從第二堆移出9張到第一堆后,第一堆有10張,第二堆剩下-7張,在從第三堆移動17張到第二堆,剛好三堆紙牌都是10,最后結果是對的,我們在移動過程中,只是改變了移動的順序,而移動次數(shù)不便,因此此題使用貪心法可行的。
Java源程序
1public class Greedy { 2 public static void main(String[] args) { 3 int n = 0, avg = 0, s = 0; 4 Scanner scanner = new Scanner(System.in); 5 ArrayList<Integer> array = new ArrayList<Integer>(); 6 System.out.println("Please input the number of heaps:"); 7 n = scanner.nextInt(); 8 System.out.println("Please input heap number:"); 9 for (int i = 0; i < n; i++) { 10 array.add(scanner.nextInt()); 11 } 12 for (int i = 0; i < array.size(); i++) { 13 avg += array.get(i); 14 } 15 avg = avg / array.size(); 16 System.out.println(array.size()); 17 System.out.println(avg); 18 for (int i = 0; i < array.size() - 1; i++) { 19 s++; 20 array.set(i + 1, array.get(i + 1) + array.get(i) - avg); 21 } 22 System.out.println("s:" + s); 23 } 24}
利用貪心算法解題,需要解決兩個問題:
一是問題是否適合用貪心法求解。我們看一個找?guī)诺睦?,如果一個貨幣系統(tǒng)有三種幣值,面值分別為一角、五分和一分,求最小找?guī)艛?shù)時,可以用貪心法求解;如果將這三種幣值改為一角一分、五分和一分,就不能使用貪心法求解。用貪心法解題很方便,但它的適用范圍很小,判斷一個問題是否適合用貪心法求解,目前還沒有一個通用的方法,在信息學競賽中,需要憑個人的經驗來判斷。
二是確定了可以用貪心算法之后,如何選擇一個貪心標準,才能保證得到問題的最優(yōu)解。在選擇貪心標準時,我們要對所選的貪心標準進行驗證才能使用,不要被表面上看似正確的貪心標準所迷惑,如下面的例子。
例題③[大整數(shù)]設有n個正整數(shù),將它們連接成一排,組成一個大的多位整數(shù)。
例如:n=3時,3個整數(shù)13,312,343,連成的大整數(shù)為34331213。
又如:n=4時,4個整數(shù)7,13,4,246,連成的大整數(shù)為7424613。
輸入:n N個數(shù) 輸出:連成的多位數(shù)
算法分析:此題很容易想到使用貪心法,在考試時有很多同學把整數(shù)按從大到小的順序連接起來,測試題目的例子也都符合,但最后測試的結果卻不全對。按這種標準,我們很容易找到反例:12,121應該組成12121而非12112,那么是不是相互包含的時候就從小到大呢?也不一定,如12,123就是12312而非12123,這種情況就有很多種了。是不是此題不能用貪心法呢?
其實此題可以用貪心法來求解,只是剛才的標準不對,正確的標準是:先把整數(shù)轉換成字符串,然后在比較a+b和b+a,如果a+b>=b+a,就把a排在b的前面,反之則把a排在b的后面。
java源程序
1public static void main(String[] args) { 2 String str = ""; 3 ArrayList<String> array = new ArrayList<String>(); 4 Scanner in = new Scanner(System.in); 5 System.out.println("Please input the number of data:"); 6 int n = in.nextInt(); 7 System.out.println("Please input the data:"); 8 while (n-- > 0) { 9 array.add(in.next()); 10 } 11 for (int i = 0; i < array.size(); i++) 12 for (int j = i + 1; j < array.size(); j++) { 13 if ((array.get(i) + array.get(j)).compareTo(array.get(j) + array.get(i)) < 0) { 14 String temp = array.get(i); 15 array.set(i, array.get(j)); 16 array.set(j, temp); 17 } 18 } 19 for (int i = 0; i < array.size(); i++) { 20 str += array.get(i); 21 } 22 System.out.println("str=:" + str); 23 } 24}
貪心算法所作的選擇可以依賴于以往所作過的選擇,但決不依賴于將來的選擇,也不依賴于子問題的解,因此貪心算法與其他算法相比具有一定的速度優(yōu)勢。如果一個問題可以同時用幾種方法解決,貪心算法應該是最好的選擇之一。
這就是貪心的一些思想和基本的應用了,如果還有什么問題,可以留言或者私信我!
https://blog.csdn.net/a925907195/article/details/41314549
往期推薦
“面試不敗計劃”: java語言基礎面試題(二)
”365算法每日學計劃”:02打卡-線性表(贈書活動第①期預告)
并發(fā)基礎篇(一): 線程介紹
創(chuàng)新互聯(lián)www.cdcxhl.cn,專業(yè)提供香港、美國云服務器,動態(tài)BGP最優(yōu)骨干路由自動選擇,持續(xù)穩(wěn)定高效的網(wǎng)絡助力業(yè)務部署。公司持有工信部辦法的idc、isp許可證, 機房獨有T級流量清洗系統(tǒng)配攻擊溯源,準確進行流量調度,確保服務器高可用性。佳節(jié)活動現(xiàn)已開啟,新人活動云服務器買多久送多久。
網(wǎng)頁題目:“365算法每日學計劃”:03打卡-貪心算法-創(chuàng)新互聯(lián)
文章位置:http://www.muchs.cn/article46/dhjeeg.html
成都網(wǎng)站建設公司_創(chuàng)新互聯(lián),為您提供營銷型網(wǎng)站建設、商城網(wǎng)站、軟件開發(fā)、品牌網(wǎng)站建設、手機網(wǎng)站建設、虛擬主機
聲明:本網(wǎng)站發(fā)布的內容(圖片、視頻和文字)以用戶投稿、用戶轉載內容為主,如果涉及侵權請盡快告知,我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場,如需處理請聯(lián)系客服。電話:028-86922220;郵箱:631063699@qq.com。內容未經允許不得轉載,或轉載時需注明來源: 創(chuàng)新互聯(lián)