深夜寫的,代碼都還沒來得及跑一便,可能有錯誤,歡迎指出,后續會檢驗一遍并修改錯誤.
本題是浙江理工大學ACM入隊200題第四套中的A題,同時給出了冒泡排序和選擇排序演算法
我們先來看一下這題的題面.
由于是比較靠前的題目,這里插一句.各位新ACMer朋友們,請一定要養成仔細耐心看題的習慣,尤其是要利用好輸入和輸出樣例.
- 樣例相當于給你舉了個具體的例子,可以幫助你更好的理解題目
- 樣例會告訴你輸入和輸出的格式,你必須要在程式里以這樣的格式輸入和輸出,否則會出問題
- 樣例可以在你本地寫完代碼之后用作測驗,來檢查你的代碼能否正常地運行(不過樣例運行正確并不代表完全對了,可能輸入其他的資料會出現別的問題)
題面
題目描述
輸入3個整數，將它們從大到小輸出，思路提示：假設輸入a b c三個數，可以先找出最大數和a交換，確保a最大； 然后剩下兩數中找出最大數和b交換，確保b最大；剩下的c就是最小數；輸出a b c就是從大到小排列了（注意：自己和自己不交換，如a本身就是最大，就不需要和a交換的），
輸入
輸入3個整數，
輸出
從大到小輸出，中間用空格隔開
樣例輸入
2 5 1
樣例輸出
5 2 1
題目分析
這題對于新朋友們來說應該是道hard的題目.一道題目往往可以追溯(或者說抽象)成某一個或幾個演算法模型,這題之所以會讓你無所下手是因為你無法準確定位到應該使用什么演算法,這不怪大家,因為這道題的演算法模型其實是排序演算法,不過是簡化過的.這里我們先介紹這道題的兩種做法,然后會在提高模塊中推廣之為兩種泛用的排序演算法,即冒泡排序和選擇排序.
一些復雜的問題往往可以分解成較小的規模,先把小規模的問題解決,然后逐步推廣到大問題,分而治之,這是很重要的分治思想,這題便可以從兩個數從大到小(下稱為降序)輸出入手.
實作兩個數的降序非常容易,如果a本身比b大,那么我們不需要做處理(已經降序),如果b比a大,那我們將a和b交換即可,區域代碼如下:
// 定義兩個變數a,b并輸入,此處略,下同
if(a < b)
{
// 如果a比b小,那么交換a和b,使得a比b大,完成降序
// 如果你無法理解交換,可以想象a是一杯可樂而b是一杯橙汁,你想要把可樂倒在橙汁杯子里并且把橙汁倒在可樂被子里
int t = a; // 現實中不可能實作直接互倒(在程式中部分資料型別可以做到,但用代碼中的這種實作更好理解),先再取一個杯子,把可樂倒在空杯子里
a = b; // 此時可樂杯子已空,把橙汁倒在可樂杯子里
b = t; // 此時橙汁杯子已空,把可樂倒在橙汁杯子里
// 此時已然完成互倒,即a,b變數成功交換
}
// 輸出a,b,此處略,下同
相信此處兩數降序大家都可以很容量理解吧,那么接下來我們從這里出發推出三數降序吧!注意跟著一起想哦!
思路一
我們先仔細回想一下我們兩數交換的程序,我們在兩數不滿足降序的時候,將大的數向前交換,使得這兩個數形成降序,那么對于三個數,我們一樣可以通過不斷將大數向前交換,使得三個數形成升序.
為了保證交換到最前面的是最大的數,我們需要從后往前兩兩比較(即先比較c和b,在交換完成后比較a和b),只有這樣才能保證每次都是當前的一個數和后面部分的最大數進行比較和交換,一次性將最大數交換到第一個位置上(可以在紙上試試分別從前往后和從后往前分別交換3 4 5,你便明白了),此時便回到了前面兩數降序的問題,我們用同樣的方法實作之即可,區域代碼如下:
if(c < b)
{
int t= c;
c = b;
b = t;
}
// 此時b為原本b和c中的最大值
// 將a和原本b和c中的最大值(即現在的b)比較并交換
if(a < b)
{
int t = a;
a = b;
b = t;
}
// 此時a為3個數中的最大值
此時a已然是最大值,對于a而言已經完成區域降序了,接下來只要讓b和c降序即可(此時b可能已經不是之前的b了,因為a可能已經與b交換了,而原本的a可能比c小,所以需要在操作一下),這個就很容易了,因為此時又轉化為了兩個數降序的問題了.
參考代碼
下面給出了我自己用這種思路做這道題時候的完整代碼:
(僅作為參考,一定要自己寫一下奧,作弊沒意思,害人又害己)
#include <stdio.h>
int main()
{
// 如果b比c小,那么交換b和c,使得b比c大,將大的數向前移動
if(b < c)
{
// 如果你無法理解交換,可以想象b是一杯可樂而c是一杯橙汁,你想要把可樂倒在橙汁杯子里并且把橙汁倒在可樂被子里
int t = b; // 現實中不可能實作直接互倒(在程式中部分資料型別可以做到,但用代碼中的這種實作更好理解),先再取一個杯子,把可樂倒在空杯子里
b = c; // 此時可樂杯子已空,把橙汁倒在可樂杯子里
c = t; // 此時橙汁杯子已空,把可樂倒在橙汁杯子里
// 此時已然完成互倒,即b,c變數成功交換
}
// 此時b為原本b和c中的最大值
// 將a和原本b和c中的最大值(即現在的b)比較并交換
if(a < b)
{
int t = a;
a = b;
b = t;
}
// 此時a為3個數中的最大值,已區域降序
// 接著對現在的b和c進行同樣的操作
if(b < c)
{
int t = b;
b = c;
c = t;
}
printf("%d %d % d", a, b, c);
return 0;
}
思路二
當然,我們可以換一種角度理解我們之前的兩數交換,我們之所以在a小于b的時候把b換到a上去,是希望我們能在a(即第一個數)上保存當前最大的元素.
同樣,對于三個元素,我們也可以做這樣的操作,我們不斷把a后面的元素b和c和a進行比較并交換(在這里從后往前還是從前往后就無所謂啦,因為每個元素都是單獨和a(比較這個元素之前的區域最大值)比較的),這樣完成這一輪比較后,a中保存的便是三個數中的最大值了,區域代碼如下:
if(a < b)
{
int t = a;
a = b;
b = t;
}
// 此時a為a和b中的最大值
if(a < c)
{
int t = a;
a = c;
c = t;
}
// 此時a為a(a為a和b中的最大值)和c中的最大值,即三個數中的最大值
此時對于a而言同樣已經完成區域降序了,接下來同樣也只要讓b和c降序即可(此時b可能已經不是之前的b了,因為a可能已經與b交換了,而原本的a可能比c小,所以需要在操作一下),此時又轉化為了兩個數降序的問題了,這里同樣直接沿用前面的兩數降序的方法即可.
參考代碼
下面給出了我自己用這種思路做這道題時候的完整代碼:
(僅作為參考,一定要自己寫一下奧,作弊沒意思,害人又害己)
#include <stdio.h>
int main()
{
if(a < b)
{
int t = a;
a = b;
b = t;
}
// 此時a為a和b中的最大值
if(a < c)
{
int t = a;
a = c;
c = t;
}
// 此時a為a(a為a和b中的最大值)和c中的最大值,即三個數中的最大值
// 接著對現在的b和c進行同樣的操作
if(b < c)
{
int t = b;
b = c;
c = t;
}
return 0;
}
提高
我們從簡單的兩數降序,根據不同的理解推出了兩種三數降序的方法,那我們可以把這兩個方法推廣到對n個數排序嘛?答案是肯定的.事實上,這里介紹的兩種思路正是最基礎的兩種排序演算法————冒泡排序和選擇排序的基礎思路(此處為了簡化,選擇排序使用了不設k的非標準版,如果想看標準的選擇排序可以去谷歌或百度搜索).
冒泡排序演算法
先來推廣思路一,我們將會將其推廣為冒泡排序演算法.
我們先在三數的基礎上變為四數,記為a,b,c,d,我們同樣可以用思路1來處理,我們從d開始逐個向前比較,將大的數向前交換,完成這一輪交換后,就和三數交換一樣,最大的數被交換到了a的位置,此時a區域有序.
之后,無序的便是后三個元素了,就回到了前面的三數降序了,我們使用同樣的方法,從d開始逐個向前比較,將大的數向前交換,此時只要比到b即可,因為a已然區域有序,無需再操作了.此時a,b區域有序.
在之后便變成了兩個數降序了,相信朋友們應該很熟悉了,此處省略.
由此我們可以發現,我們這種從后往前不斷把最大數向前交換的思路可以對2個數起效,同時在n個數起效時可以保證對n+1個數也起效,根據數學歸納法,我們得出了一種可以適用于n個數的降序排序演算法,我們稱之為冒泡排序演算法.
所謂冒泡,便是我們將最大值不斷向前交換的程序,它就像水里的氣泡冒的水面那樣,很形象吧!
不過,保存n個數我們不采用n個變數,而是使用一個叫陣列的東西,同樣對這n個數我們也不會分別寫出各個if陳述句,而是使用回圈陳述句.或許看到這里的朋友還不會上述兩個東西,不過不要緊,只要理解上述的思路,代碼還是很好寫的,下面給出區域參考代碼:
// len為陣列a的長度,下同
// 外回圈表示當前冒泡排序的操作已完成幾次,同時也是已區域有序部分的長度
for (int i = 0; i < len; i++)
{
// 內回圈即為前面所說的冒泡操作了,每次從陣列尾部開始與前一個元素比較,將較大元素不斷向前交換
for(int j = len - 1;j > i;j--)
{
if(a[j] < a[j - 1])
{
int t = a[j];
a[j] = a[j - 1];
a[j - 1] = t;
}
}
}
如果要實作升序(從小到大排序),也可以使用同樣的格式,大家可以自己寫寫看哦!
后面的諸如第十套的A,B題等都可以使用這種演算法來完成,大家可以試試看.
選擇排序演算法
同樣可以推廣思路二,我們將會將其推廣為選擇排序演算法.
我們同樣先在三數的基礎上變為四數,記為a,b,c,d,我們同樣可以用思路2來處理,將除了a以外的每個數同a比較,如果比a大就交換,這樣當一輪操作結束后,a中已然是所有數中的最大的那個了,此時a區域有序.
之后,無序的同樣是后三個元素了,也就回到了前面的三數降序了,我們使用同樣的方法,將除了a和b以外的(即b后面的)每個數同b比較,如果比b大就交換,這樣當一輪操作結束后,b中已然是剩下的所有數中的最大的那個了,此時a,b區域有序.
在之后便變成了兩個數降序了,相信朋友們應該很熟悉了,同樣此處省略.
由此我們同樣可以發現,我們這種不斷和當前無序資料區域的第一個元素比較并交換的思路可以對2個數起效,同時在n個數起效時可以保證對n+1個數也起效,同樣根據數學歸納法,我們又得出了一種可以適用于n個數的降序排序演算法,我們稱之為選擇排序演算法.
不過這里的選擇排序并非標準的選擇排序,而是不設k的版本,目的是便于大家理解推出的程序.建議大家理解之后去看一看這種演算法的標準寫法,可以加深對"選擇"二字的理解.
同樣保存n個數我們不采用n個變數,而是使用陣列,也同樣對這n個數我們也不會分別寫出各個if陳述句,而是使用回圈陳述句.或許看到這里的朋友還不會上述兩個東西,不過不要緊,只要理解上述的思路,代碼還是很好寫的,下面給出區域參考代碼:
// len為陣列a的長度,下同
// 外回圈表示當前冒泡排序的操作已完成幾次,同時也是當前需要和那個元素比較
for (int i = 0; i < len; i++)
{
// 內回圈即為將i后面的所有元素和i這里的元素比較并交換,使得i位置儲存這些數的最大值
for(int j = i + 1;j < len;j++)
{
if(a[i] < a[j])
{
int t = a[i];
a[i] = a[j];
a[j] = t;
}
}
}
如果要實作升序(從小到大排序),也可以使用同樣的格式,大家可以自己寫寫看哦!
后面的諸如第十套的A,B題等都可以使用這種演算法來完成,大家可以試試看.
補充
上述介紹的兩種排序演算法都是平方階的排序演算法,在實際寫演算法題和軟體開發中是很少使用的,在第十套的E題中會要求大家寫一種叫插入排序的演算法,這是對于數量較少的元素通常采用的演算法,而對于較多元素我們會選擇其他的線性對數階的演算法(比如快速排序、歸并排序等),感興趣的同學們可以在網上搜索相關的檔案了解一下哦!
"正是我們每天反復做的事情，最終造就了我們，優秀不是一種行為，而是一種習慣" ---亞里士多德
這篇題解就到這里了,各位朋友如果有問題歡迎到acm成員群中提問哦!
這里是浙江理工大學22屆ACM集訓隊的成員一枚鴨!
本文首發于博客園，作者：星雙子，除了我自己的轉載請注明原文鏈接：https://www.cnblogs.com/gemini-star/p/zstuACM200_4A.html
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/509353.html
標籤：其他
下一篇：移動端滲透