目錄
第一篇? ? 分治法
●前言
●一、分治法是什么？
1.簡(jiǎn)要介紹
2.生活實(shí)例
●二、分治法的典型案例——硬幣問(wèn)題
1.具體問(wèn)題
2.代碼展示（C++）
3.程序代碼結(jié)果展示
●總結(jié)
簡(jiǎn)單的來(lái)說(shuō)，算法就是用計(jì)算機(jī)程序代碼來(lái)實(shí)現(xiàn)數(shù)學(xué)思想的一種方法。學(xué)習(xí)算法就是為了了解它們?cè)谟?jì)算機(jī)中如何演算，以及在當(dāng)今的信息時(shí)代，它們是如何在各個(gè)層面上影響我們的日常生活的，從而提高我們的邏輯思維能力和處理實(shí)際問(wèn)題的能力。善用算法、巧用算法，是培養(yǎng)程序設(shè)計(jì)邏輯的重中之重，許多實(shí)際的問(wèn)題都可用多個(gè)可行的算法來(lái)解決， 但是要從中找出最優(yōu)的解決算法卻是一項(xiàng)挑戰(zhàn)。
? 分治法是一種很重要的算法，我們可以用分治法去逐一拆解復(fù)雜的問(wèn)題，使復(fù)雜問(wèn)題簡(jiǎn)單化。它的核心思想就是將一個(gè)難以直接解決的復(fù)雜問(wèn)題依照相同的概念將其分為多個(gè)子問(wèn)題，從而各個(gè)擊破解決問(wèn)題。
2.生活實(shí)例? ① 如果有一幅畫它由八部分組成，但是如果直接把這八塊看成一個(gè)整體的話是很難直接畫出實(shí)現(xiàn)的，所以我們可以先將其分為2組各四幅來(lái)完成。如果還是比較復(fù)雜，就再將其分成4組各兩幅畫去完成...... 直到最終畫出每一幅畫再將其拼接完整即可
? ②一個(gè)部門被公司去委派去做一個(gè)項(xiàng)目規(guī)劃，這個(gè)規(guī)劃需要8個(gè)章節(jié)的主題，如果只靠一個(gè)人去完成，不僅耗費(fèi)較長(zhǎng)的時(shí)間還可能會(huì)因?yàn)闆](méi)有去集思廣益，從而最終導(dǎo)致項(xiàng)目沒(méi)有什么亮點(diǎn)而失敗。這時(shí)我們?nèi)ビ玫椒种畏ǖ暮诵乃枷耄块T經(jīng)理將這個(gè)大項(xiàng)目分給兩個(gè)子項(xiàng)目負(fù)責(zé)人去完成。不過(guò)，為了讓這個(gè)規(guī)劃更快完成，又能去找到合適的分類，每個(gè)子項(xiàng)目負(fù)責(zé)人再分別將其分派給兩個(gè)小團(tuán)隊(duì)，小團(tuán)隊(duì)從而分配給不同的成員去完成。通過(guò)這種方法，我們將所需時(shí)間縮減到原先一個(gè)人獨(dú)立完成時(shí)間的1/8，項(xiàng)目每個(gè)章節(jié)主題內(nèi)容也集思廣益，從而為企業(yè)創(chuàng)造了更大的價(jià)值。
在下面我們將硬幣分為1和0兩個(gè)值，1為真硬幣，0為假硬幣。分兩種情況，偶數(shù)枚硬幣和奇數(shù)枚硬幣，并將其隨機(jī)排成一列，其中有一個(gè)假硬幣（假硬幣位置隨機(jī)），用分治算法尋找出這枚假硬幣所在的位置，如下圖所示。
① 當(dāng)硬幣個(gè)數(shù)為偶數(shù)時(shí)（10枚）：
② 當(dāng)硬幣個(gè)數(shù)為奇數(shù)時(shí)（13枚）：
? 用程序代碼去實(shí)現(xiàn)一個(gè)功能：輸入20枚硬幣，其中有一枚假硬幣并且位置隨機(jī)，用分治法的核心思想去找到該枚假硬幣所在的位置。
重慶分公司
重慶分公司
#includeusing namespace std;
#define maxsize 20 //硬幣的數(shù)目
class fenzhi {
public:
int falsecoin(int low, int high);
void showresult();
int num;
int coin[maxsize];
int result;
};
int fenzhi::falsecoin(int low, int high)
{
int sum1=0;
int sum2=0;
int sum3=0;
if (low + 1 == high) //只有兩枚硬幣
{
if (coin[low]< coin[high])
{
result = low + 1;
return result;
}
else
{
result = high + 1;
return result;
}
}
//分治算法
if((high-low+1)%2==0) //n是偶數(shù)
{
for (int i = low; i<= low+(high-low)/2; i++)
{
sum1 += coin[i];//前半段和
}
for (int j = low + (high - low) / 2+1; j<= high; j++)
{
sum2 += coin[j];//后半段和
}
if (sum1 >sum2)
{
result = falsecoin(low + (high - low) / 2 + 1, high); //遞推后半段
return result;
}
else if(sum1< sum2)
{
result = falsecoin(low, low + (high - low) / 2); //遞推前半段
return result;
}
}
else //n是奇數(shù)
{
for (int i = low;i<=low+(high-low)/2-1;i++)
{
sum1 += coin[i]; //中位數(shù)的前半段和
}
for (int j = low + (high - low) / 2+1; j<= high; j++)
{
sum2 += coin[j]; //中位數(shù)的后半段和
}
sum3 = coin[low + (high - low) / 2]; //中位數(shù)
if (sum1 >sum2) //前半段和大于后半段和
{
result = falsecoin(low + (high - low) / 2 + 1, high);//遞推后半段
return result;
}
else if (sum1< sum2) //前半段和小于后半段和
{
result = falsecoin(low, low + (high - low) / 2 - 1);//遞推前半段
return result;
}
if (sum1 + sum3 == sum2 + sum3) //前半段和加中位數(shù)等于后半段和加中位數(shù)，所以中位數(shù)為目標(biāo)尋找值
{
result = low + (high - low) / 2+1;
return result;
}
}
}
void fenzhi::showresult()
{
cout<< "假幣所在的位置："<< this->result<< endl;
}
void text()
{
fenzhi fz;
cout<< "輸入硬幣的總數(shù)目："<< endl;
cin >>fz.num;
cout<< "請(qǐng)輸入硬幣的真假（1真/0假）："<< endl;
for (int i = 0; i< fz.num; i++)
{
cin >>fz.coin[i];
}
fz.falsecoin(0, fz.num - 1);
fz.showresult();
}
int main()
{
text();
} 
? 通過(guò)分治法可以讓原來(lái)無(wú)序、復(fù)雜的問(wèn)題變成一個(gè)規(guī)則、簡(jiǎn)單，數(shù)量少，速度快并且更容易解決的小問(wèn)題。其實(shí)任何一種可以用程序來(lái)求解的問(wèn)題，所需的計(jì)算時(shí)間都與其規(guī)模和復(fù)雜度有關(guān)，問(wèn)題規(guī)模越小，越容易直接去進(jìn)行求解，從而可以去不斷分解問(wèn)題，使子問(wèn)題規(guī)模去不斷縮小，讓這些子問(wèn)題簡(jiǎn)單到可以直接解決，? ?最終進(jìn)行合并從而解決整個(gè)問(wèn)題。? ??
????????????????????????????????????<您的三連和關(guān)注是我大的動(dòng)力>
?🚀 文章作者：Keanu Zhang? ? ? ? 分類專欄：算法之美（C++系列文章）
你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧
