當前位置:首頁 > 芯聞號 > 充電吧
[導讀]算法描述?算法思想: ? 對所有可能是解的眾多候選解按某種順序進行逐一枚舉和檢驗,并從眾找出那些符合要求的候選解作為問題的解。?算法特點: ??算法簡單,但執(zhí)行效率低。因此枚舉法的關鍵在于提高編程效率

算法描述?

算法思想: ? 對所有可能是解的眾多候選解按某種順序進行逐一枚舉和檢驗,并從眾找出那些符合要求的候選解作為問題的解。?

算法特點: ??算法簡單,但執(zhí)行效率低。因此枚舉法的關鍵在于提高編程效率。
對于可預先確定元素的個數(shù),并且元素所在的區(qū)間是連續(xù)的情況非常適合。
對于類似的求abcd /ef=xy的這類問題,一般枚舉用的比較多,經典的例子比如求水仙花數(shù)目,也是枚舉,下面是一個小學時代的百雞百錢問題對枚舉的應用案例,來分析對枚舉應用過程中運算的改進
百雞百錢 設母雞每只5元,公雞每只3元,小雞1元3只。現(xiàn)用100元買100只雞,求出所有可能的解。
設母雞x,公雞y,小雞z,滿足x+y+z=100 5*x+3*y+z/3==100這兩個關系式子
這種枚舉效率很低,3層循環(huán),每層100次

#includeint?main()
{	int?x,y,z;
	for?(x=0;?x<=100;x++)
		for?(y=0;?y<=100;?y++)
		????for?(z=0;?z<=100;?z++)
		?	if?(?x+y+z==100?&&?5*x+3*y+z/3==100&&z%3==0?)//因為現(xiàn)實總z必須是3的整數(shù)倍,比如進行判斷
				printf("%10d,%20d,%dn",x,y,z);
}

利用x,y,z之間的關系可以減少一層循環(huán)

#includeint?main()
{	int?x,y,z;
	for?(x=0;?x<=100;x++)
		for?(y=0;?y<=100;?y++)
		{	z=100-x-y;
			if?(z%3==0?&&??5*x+3*y+z/3==100)
				printf("%d,%d,%dn",x,y,z);
		}
}
根據(jù)y可能出現(xiàn)的最大值進行限制y的范圍,上面那個y循環(huán),從34-100之間的都是無用功,如果把y循環(huán)改成對z的循環(huán)就不好了,循環(huán)次數(shù)更多了
#includeint?main()
{	int?x,y,z;
	for?(x=0;?x<=20;x++)
		for?(y=0;?y<=33;?y++)
		{	z=100-x-y;
			if?(?z%3==0?&&?5*x+3*y+z/3==100)
				printf("%d,%d,%dn",x,y,z);
		}
}

01背包問題 有不同價值、不同重量的物品n件,求從這n件物品中選取一部分物品的選擇方案,使選中物品的總重量不超過指定的限制重量,但選中物品的價值之和最大。例如:設限制重量為7,現(xiàn)有4件物品,它們的重量和價值見下表,問如何物品的價值之和最大?

#include#define?N?100
typedef?struct?product/**結構體用來保存物品信息*/
{
????int?weight;
????int?value;
}PRO;
PRO?pro[N];/**存儲物品的數(shù)組*/
int?a[N],b[N];/**a是保存的最大值物品選擇信息,b是每次的物品選擇與否的信息*/
PRO?tem,max;???/**tem保存臨時計算的物品信息,max保存最大值時的信息*/
int?zuheshu(int?n)/**根據(jù)排列組合的規(guī)則,n個物品0表示不選擇,1表示選擇,有2^n種選擇*/
{
????int?i,s=1;
????for(i=0;i<n;i++)
????{
????????s*=2;
????}
????return?s;
}
void?jisuan_1(int?num,int?n)/**根據(jù)組合數(shù)的范圍,把在組合數(shù)范圍內的數(shù)字num,和物品選擇與否對應起來*/
{
????int?j;
????for(j=0;j<n;j++)/**把num換成2進制,而且二進制的位數(shù)和商品的總數(shù)n相同*/
????{
????????b[j]=num%2;
????????num=num/2;
????}
}
void?jisuan_2(int?n,int?lim)
{
????int?i,k,t;
????for(i=0;i<zuheshu(n);i++)/**對組合范圍內的數(shù)字進行逐個枚舉*/
????{
????????jisuan_1(i,n);/**進行信息對應*/
????????tem.value=0;/**用前要先清零*/
????????tem.weight=0;/**用前要先清零*/
????????for(t=0;tmax.value)&&(tem.weight<lim))/**確定是否滿足條件,不超過限制*/
????????{
????????????max.value=tem.value;
????????????max.weight=tem.weight;
????????????for(k=0;k<n;k++)/**更新下數(shù)組a*/
????????????????a[k]=b[k];
????????}
????}
}
int?main()
{
????int?n,i,lim;
????printf("輸入數(shù)目和限制:n");
????scanf("%d",&n);
????scanf("%d",&lim);
????printf("%輸入重量和價值:n");
????for(i=0;i<n;i++)
????{
???????scanf("%d?%d",&pro[i].weight,&pro[i].value);
????}
????jisuan_2(n,lim);
????printf("輸出最大價值和重量n");
????printf("%d?%dn",max.value,max.weight);
????for(i=0;i<n;i++)
????{
????????if(a[i]==1)
????????{
????????????printf("%d?",i);//看編號范圍,從1開始,輸出i+1就行
????????}
????}
????return?0;
}

這個題目最大的感觸就是把二進制和枚舉聯(lián)系在一起了。 棋盤問題 在4×4的棋盤上放置8個棋,要求每一行,每一列上只能放置2個。找出所有可能的解并輸出解的個數(shù)
枚舉思想1:
用二維數(shù)組a[4][4]存放所有可能的解,1表示存放,0表示不存放。

#include#include#define?N?4

int?a[N][N];
char?b[]={3,5,6,9,10,12};//0011?0101?0110?1001?1010?1100?每行必須有兩個,4行,這些就夠了,也是二進制數(shù)的運用
void?tc_h(int?row,int?num)//填充第i行,n為列數(shù)
{
????int?j,t;
????t=b[num];
????for(j=0;j<N;j++)
????{
????????a[row][j]=t%2;
????????t=t/2;
????}
}
int?panduan_l(int?cle)//檢查每一列是否合格,m為行總數(shù)
{
????int?i,count=0;
????for(i=0;i2)
????????????return?0;
????}
????return?count;
}
int?main()
{
????int?count=0;
????int?i,j,k,s,b,c;
????for(i=0;i<6;i++)
????{
????????tc_h(0,i);
?????????for(j=0;j<6;j++)//每行進行填充
?????????{
?????????????tc_h(1,j);
??????????????for(k=0;k<6;k++)
??????????????{
???????????????????tc_h(2,k);
???????????????????for(s=0;s<6;s++)
???????????????????{
???????????????????????tc_h(3,s);
???????????????????????if?((panduan_l(0)&&panduan_l(1)&&panduan_l(2)&&panduan_l(3))&&(panduan_l(0)+
????????????????????????panduan_l(1)+panduan_l(2)+panduan_l(3)==8))//對于每種情況逐列判斷是否符合情況
???????????????????????{
???????????????????????????count++;
????????????????????????????for(b=0;b<N;b++)
????????????????????????????{
????????????????????????????????for(c=0;c<N;c++)
????????????????????????????????{
????????????????????????????????????printf("%d?",a[b][c]);//符合就輸出
????????????????????????????????}
????????????????????????????????printf("n");
????????????????????????????}
????????????????????????????printf("n");
???????????????????????}
???????????????????}
??????????????}
?????????}
????}
????printf("%d?",count);
????return?0;
}

另一種方法

#include#include#define?N?4
int?a[N][N];/**這里用的方法是一次填充完16個,然后在判斷是否滿足條件*/
int?one(int?num)
{
????int?i,count=0;
????for(i=0;i<16;i++)
????{
???????count+=num%2;
???????num=num/2;
????}
????return?count;
}
int?panduan(int?(*a)[N])
{
????int?i,j,count=0;
????int?count2=0;
????for(i=0;i<N;i++)
????{
????????count=0;
????????count2=0;
????????for(j=0;j2||count2>2)
????????return?0;
????}
????return?1;
}
int?main()
{
????int?i,j,k,t,num,*p,count=0;

????for(num=0;num<65535;num++)
????{
????????if(one(num)==8)//判斷下,減少次數(shù)
????????{
????????????t=num;
????????????p=a;
????????????for(j=0;j<16;j++)
????????????{
????????????????*p++=t%2;
?????????????????t=t/2;
????????????}
????????????if(panduan(a)==1)
????????????{
????????????????count++;
????????????????for(i=0;i<N;i++)
????????????????{
????????????????????for(k=0;k<N;k++)
????????????????????{
????????????????????????printf("%d?",a[i][k]);
????????????????????}
?????????????????????printf("n");
????????????????}
????????????????printf("n");
????????????}
????????}
????}
????printf("%d?",count);
}


互不相同的平方數(shù) 求個數(shù)
給定的正整數(shù),再給定一個條件:一個數(shù)的平方數(shù)為1個9位數(shù),并且其各數(shù)互不相同。 統(tǒng)計出小于等于X的整數(shù)中滿足此條件的數(shù)的個數(shù) Input 每一行為一個數(shù)字,為5位正整數(shù)x Output 對應每個數(shù)字輸出滿足條件的個數(shù) Sample Input 10000 Sample Output 0

#includeint?panduan(int?num)
{
????int?i;
????int?date[10]={0};
????for(i=0;i<10;i++)//取9位數(shù)的每一位
????{
????????date[num%10]++;
????????num=num/10;
????}
????for(i=0;i1)//9位數(shù),沒有重復的情況下不會大于1,不能用date[i]!=1判斷,因為0-9十個數(shù)字,有可能為0
????????????return?0;
????}
????return?1;
}
int?main()
{
????int?num;//不會溢出
????int?num2;
????int?i,j,k;
????while(scanf("%d",&num)!=EOF)
????{
????????num=num>33000?33000:num;//不會超過33000,否則就不是9位數(shù)據(jù)了
????????for(i=10000;i<num;i++)
????????{
????????????num2=i*i;
????????????if(panduan(num2)==1)
????????????{
????????????????printf("%d*%d=%dn",i,i,num2);
????????????}

????????}
????????printf("END");

????}

????return?0;
}
本站聲明: 本文章由作者或相關機構授權發(fā)布,目的在于傳遞更多信息,并不代表本站贊同其觀點,本站亦不保證或承諾內容真實性等。需要轉載請聯(lián)系該專欄作者,如若文章內容侵犯您的權益,請及時聯(lián)系本站刪除。
換一批
延伸閱讀

9月2日消息,不造車的華為或將催生出更大的獨角獸公司,隨著阿維塔和賽力斯的入局,華為引望愈發(fā)顯得引人矚目。

關鍵字: 阿維塔 塞力斯 華為

加利福尼亞州圣克拉拉縣2024年8月30日 /美通社/ -- 數(shù)字化轉型技術解決方案公司Trianz今天宣布,該公司與Amazon Web Services (AWS)簽訂了...

關鍵字: AWS AN BSP 數(shù)字化

倫敦2024年8月29日 /美通社/ -- 英國汽車技術公司SODA.Auto推出其旗艦產品SODA V,這是全球首款涵蓋汽車工程師從創(chuàng)意到認證的所有需求的工具,可用于創(chuàng)建軟件定義汽車。 SODA V工具的開發(fā)耗時1.5...

關鍵字: 汽車 人工智能 智能驅動 BSP

北京2024年8月28日 /美通社/ -- 越來越多用戶希望企業(yè)業(yè)務能7×24不間斷運行,同時企業(yè)卻面臨越來越多業(yè)務中斷的風險,如企業(yè)系統(tǒng)復雜性的增加,頻繁的功能更新和發(fā)布等。如何確保業(yè)務連續(xù)性,提升韌性,成...

關鍵字: 亞馬遜 解密 控制平面 BSP

8月30日消息,據(jù)媒體報道,騰訊和網(wǎng)易近期正在縮減他們對日本游戲市場的投資。

關鍵字: 騰訊 編碼器 CPU

8月28日消息,今天上午,2024中國國際大數(shù)據(jù)產業(yè)博覽會開幕式在貴陽舉行,華為董事、質量流程IT總裁陶景文發(fā)表了演講。

關鍵字: 華為 12nm EDA 半導體

8月28日消息,在2024中國國際大數(shù)據(jù)產業(yè)博覽會上,華為常務董事、華為云CEO張平安發(fā)表演講稱,數(shù)字世界的話語權最終是由生態(tài)的繁榮決定的。

關鍵字: 華為 12nm 手機 衛(wèi)星通信

要點: 有效應對環(huán)境變化,經營業(yè)績穩(wěn)中有升 落實提質增效舉措,毛利潤率延續(xù)升勢 戰(zhàn)略布局成效顯著,戰(zhàn)新業(yè)務引領增長 以科技創(chuàng)新為引領,提升企業(yè)核心競爭力 堅持高質量發(fā)展策略,塑強核心競爭優(yōu)勢...

關鍵字: 通信 BSP 電信運營商 數(shù)字經濟

北京2024年8月27日 /美通社/ -- 8月21日,由中央廣播電視總臺與中國電影電視技術學會聯(lián)合牽頭組建的NVI技術創(chuàng)新聯(lián)盟在BIRTV2024超高清全產業(yè)鏈發(fā)展研討會上宣布正式成立。 活動現(xiàn)場 NVI技術創(chuàng)新聯(lián)...

關鍵字: VI 傳輸協(xié)議 音頻 BSP

北京2024年8月27日 /美通社/ -- 在8月23日舉辦的2024年長三角生態(tài)綠色一體化發(fā)展示范區(qū)聯(lián)合招商會上,軟通動力信息技術(集團)股份有限公司(以下簡稱"軟通動力")與長三角投資(上海)有限...

關鍵字: BSP 信息技術
關閉
關閉