枚舉算法

枚舉算法

枚舉算法是我們在日常中使用到的最多的一個算法,它的核心思想就是:枚舉所有的可能。 枚舉法的本質就是從所有候選答案中去搜尋正確的解,使用該算法需要滿足兩個條件:(1)可預先確定候選答案的數量;(2)候選答案的範圍在求解之前必須有一個確定的集合。

概述

枚舉算法簡單粗暴,他暴力的枚舉所有可能,儘可能地嘗試所有的方法。雖然枚舉算法非常暴力,而且速度可能很慢,但確實我們最應該優先考慮的!因為枚舉法變成實現最簡單,並且得到的結果總是正確的。

在實際問題中, 有些變數的取值被限定在一個有限的範圍內。例如,一個星期內只有七天,一年只有十二個月, 一個班每周有六門課程等等。如果把這些量說明為整型, 字元型或其它類型顯然是不妥當的。 為此,C語言提供了一種稱為“枚舉”的類型。在“枚舉”類型的定義中列舉出所有可能的取值, 被說明為該“枚舉”類型的變數取值不能超過定義的範圍。應該說明的是,枚舉類型是一種基本數據類型,而不是一種構造類型, 因為它不能再分解為任何基本類型 。

定義

枚舉的定義枚舉類型定義的一般形式為:

enum 枚舉名

{ 枚舉值表 };

在枚舉值表中應羅列出所有可用值。這些值也稱為枚舉元素。

例如: enum weekday

{ sun,mou,tue,wed,thu,fri,sat };

該枚舉名為weekday,枚舉值共有7個,即一周中的七天。 凡被說明為weekday類型變數的取值只能是七天中的某一天。

基本思想

枚舉也稱作窮舉,指的是從問題所有可能的解的集合中一一枚舉各元素。

用題目中給定的檢驗條件判定哪些是無用的,哪些是有用的。能使命題成立。即為其解 。

基本框架

設a—狀態元素a的最小值;a—狀態元素a的最大值(1≤i≤n),即a≤a≤a,a≤a≤a, a≤a≤a,……,a≤a≤a

for a1←a11 to a1k do

for a2←a21 to a2k do

……………………

for ai←ai1 to aik do

……………………

for an←an1 to ank do

if 狀態(a1,…,ai,…,an)滿足檢驗條件

then 輸出問題的解;

優缺點

•優點:算法簡單,在局部地方使用枚舉法,效果十分的好

•缺點:運算量過大,當問題的規模變大的時候,循環的階數越大,執行速度越慢

說明

如同結構和聯合一樣,枚舉變數也可用不同的方式說明, 即先定義後說明,同時定義說明或直接說明。設有變數a,b,c被說明為上述的weekday,可採用下述任一種方式:

enum weekday

{

......

};

enum weekday a,b,c;或者為: enum weekday

{

......

}a,b,c;或者為: enum

{

......

}a,b,c;

使用

枚舉類型在使用中有以下規定:

枚舉值是常量,不是變數。不能在程式中用賦值語句再對它賦值。例如對枚舉weekday的元素再作以下賦值: sun=5;mon=2;sun=mon; 都是錯誤的。

枚舉元素本身由系統定義了一個表示序號的數值,從0 開始順序定義為0,1,2…。如在weekday中,sun值為0,mon值為1, …,sat值為6。

例如:

#include<stdio.h>

int main()

{

enum weekday{sun,mon,tue,wed,thu,fri,sat };

weekday a,b,c; //將a,b,c定義為枚舉變數

a=sun;

b=mon;

c=tue;

printf("%d,%d,%d",a,b,c);

return 0;

}

運行結果為:0,1,2

枚舉值也可以用來做判斷比較。如:if(mon>sun) …

枚舉變數的值可以由程式設計師自己定。如:

enum weekday{sun=7,mon=1,tue,wed,thu,fri,sat};

定義sun為7,mon為1,以後按順序加1,即wed=3 。

賦值

只能把枚舉值賦予枚舉變數,不能把元素的數值直接賦予枚舉變數。如: a=sum;b=mon; 是正確的。而: a=0;b=1; 是錯誤的。如一定要把數值賦予枚舉變數,則必須用強制類型轉換,如: a=(enum weekday)2;其意義是將順序號為2的枚舉元素賦予枚舉變數a,相當於: a=tue; 還應該說明的是枚舉元素不是字元常量也不是字元串常量, 使用時不要加單、雙引號。

main(){

enum body

{ a,b,c,d } month[31],j;

int i;

j=a;

for(i=1;i<=30;i++){

month =j;

j++;

if (j>d) j=a;

}

for(i=1;i<=30;i++){

switch(month)

{

case a:printf(" %2d %c\t",i,'a'); break;

case b:printf(" %2d %c\t",i,'b'); break;

case c:printf(" %2d %c\t",i,'c'); break;

case d:printf(" %2d %c\t",i,'d'); break;

default:break;

}

}

printf("\n");

}

相關詞條

相關搜尋

熱門詞條

聯絡我們