C++基本算法思想之窮舉法
窮舉算法(Exhaustive Attack method)是最簡(jiǎn)單的一種算法,其依賴于計(jì)算機(jī)的強(qiáng)大計(jì)算能力來(lái)窮盡每一種可能性,從而達(dá)到求解問(wèn)題的目的。窮舉算法效率不高,但是適應(yīng)于一些沒有規(guī)律可循的場(chǎng)合。
窮舉算法基本思想
窮舉算法的基本思想就是從所有可能的情況中搜索正確的答案,其執(zhí)行步驟如下:
(1)對(duì)于一種可能的情況,計(jì)算其結(jié)果。
(2)判斷結(jié)果是否符合要求,如果不滿足則執(zhí)行第(1)步來(lái)搜索下一個(gè)可能的情況;如果符合要求,則表示尋找到一個(gè)正確答案。
在使用窮舉法時(shí),需要明確問(wèn)題的答案的范圍,這樣才可以在指定的范圍內(nèi)搜索答案。指定范圍之后,就可以使用循環(huán)語(yǔ)句和條件語(yǔ)句逐步驗(yàn)證候選答案的正確性,從而得到需要的正確答案。
窮舉算法舉例
雞兔同籠問(wèn)題最早記載于1500年前的《孫子兵法》,這是一個(gè)非常有名的問(wèn)題。雞兔同籠的原文如下:
今有雞兔同籠,上有三十五頭,下有九十四足,問(wèn)雞兔各幾只?
這個(gè)問(wèn)題的大致意思是:在一個(gè)籠子里關(guān)著若干只雞和若干只兔,從上面數(shù)共有35個(gè)頭,從下面數(shù)共有94只腳。問(wèn)籠中雞和兔的數(shù)量各是多少?
窮舉算法
這個(gè)問(wèn)題需要計(jì)算雞的數(shù)量和兔的數(shù)量,我們通過(guò)分析可以知道雞的數(shù)量應(yīng)該在1~35之間。這樣我們可以使用窮舉法來(lái)逐個(gè)判斷是否符合,從而搜索答案。
采用窮舉法求解雞兔同籠問(wèn)題的程序示例代碼如下:
/*
輸入?yún)?shù)head是籠中頭的總數(shù),foot是籠中腳的總數(shù),chicken的總數(shù),rabbit是兔的總數(shù)
返回結(jié)果為0,表示沒有搜索到符合條件的結(jié)果;
返回結(jié)果為1,表示搜索到了符合條件的結(jié)果
*/
int qiongju(int head,int foot,int *chicken,int * rabbit)
{
int re,i,j;
re=0;
for(i=0;i<=head,i++) //進(jìn)行循環(huán)
{
j=head-i;
if(i*2+j*4==foot) //進(jìn)行判斷
{
re=1; //找到答案
*chicken=i;
*rabbit=j;
}
}
return re;
}
窮舉算法求解雞兔同籠問(wèn)題
完整的瓊劇算法求解雞兔同籠問(wèn)題的程序代碼如下:
#include<iostream>
using namespace std;
/*
輸入?yún)?shù)head是籠中頭的總數(shù),foot是籠中腳的總數(shù),chicken的總數(shù),rabbit是兔的總數(shù)
返回結(jié)果為0,表示沒有搜索到符合條件的結(jié)果;
返回結(jié)果為1,表示搜索到了符合條件的結(jié)果
*/
int qiongju(int head,int foot,int *chicken,int * rabbit)
{
int re,i,j;
re=0;
for(i=0;i<=head;i++) //進(jìn)行循環(huán)
{
j=head-i;
if(i*2+j*4==foot) //進(jìn)行判斷
{
re=1; //找到答案
*chicken=i;
*rabbit=j;
}
}
return re;
}
int main()
{
int chicken,rabbit,head,foot;
int re;
cout<<"窮舉法求解雞兔同籠問(wèn)題:"<<endl;
cout<<"請(qǐng)輸入頭數(shù):";
cin>>head;
cout<<"請(qǐng)輸入腳數(shù):";
cin>>foot;
re=qiongju(head,foot,&chicken,&rabbit);
if(re==1)
{
cout<<"雞有"<<chicken<<"只,兔有"<<rabbit<<"只。"<<endl;
}
else
{
cout<<"無(wú)法求解!"<<endl;
}
return 0;
}
程序中,首先由用戶輸入頭的總數(shù)和腳的總數(shù),然后調(diào)用窮舉法求解雞兔同籠問(wèn)題的函數(shù),最后輸出結(jié)果。
執(zhí)行該程序,按照題目的要求輸入數(shù)據(jù),輸出結(jié)果。
相關(guān)文章
C++實(shí)現(xiàn)圖形界面時(shí)鐘表盤代碼
這篇文章主要介紹了C++實(shí)現(xiàn)圖形界面時(shí)鐘表盤代碼,涉及坐標(biāo)函數(shù)的應(yīng)用及圖形界面程序設(shè)計(jì),需要的朋友可以參考下2014-10-10C++ 數(shù)字的反轉(zhuǎn)實(shí)現(xiàn)實(shí)例
這篇文章主要介紹了C++ 數(shù)字的反轉(zhuǎn)實(shí)現(xiàn)實(shí)例的相關(guān)資料,需要的朋友可以參考下2017-06-06C++11 std::shared_ptr總結(jié)與使用示例代碼詳解
這篇文章主要介紹了C++11 std::shared_ptr總結(jié)與使用,本文通過(guò)示例代碼給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2020-06-06C語(yǔ)言之整數(shù)劃分問(wèn)題(遞歸法)實(shí)例代碼
這篇文章主要介紹了C語(yǔ)言之整數(shù)劃分問(wèn)題(遞歸法)實(shí)例代碼的相關(guān)資料,需要的朋友可以參考下2017-02-02C++ 實(shí)現(xiàn)旋轉(zhuǎn)蛇錯(cuò)覺的詳細(xì)代碼
這篇文章主要介紹了C++ 實(shí)現(xiàn)旋轉(zhuǎn)蛇錯(cuò)覺的詳細(xì)代碼,代碼簡(jiǎn)單易懂,對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2021-09-09