




版權(quán)說(shuō)明:本文檔由用戶(hù)提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
論C++語(yǔ)言在信息學(xué)競(jìng)賽中的應(yīng)用浙江省余姚中學(xué)韓文弢關(guān)于信息學(xué)競(jìng)賽信息學(xué)競(jìng)賽一般要求在一定的時(shí)間內(nèi),理解并分析題意,設(shè)計(jì)符合給定時(shí)間和空間復(fù)雜度要求的算法,并在計(jì)算機(jī)上使用一定的程序設(shè)計(jì)語(yǔ)言正確地實(shí)現(xiàn)算法。由于整個(gè)競(jìng)賽存在時(shí)間限制,因此所使用的程序設(shè)計(jì)語(yǔ)言能否正確、快速地實(shí)現(xiàn)算法對(duì)競(jìng)賽的成績(jī)影響頗大。關(guān)于信息學(xué)競(jìng)賽所以,編程復(fù)雜度成為和算法的時(shí)間以及空間復(fù)雜度同等重要的因素。編程復(fù)雜度在很大程度上與所選用的程序設(shè)計(jì)語(yǔ)言有關(guān)。一般信息學(xué)競(jìng)賽中比較常用的程序設(shè)計(jì)語(yǔ)言有BASIC、Pascal、C++、Java等。信息學(xué)競(jìng)賽中常用語(yǔ)言的特點(diǎn)BASICPascalC++Java學(xué)習(xí)難度容易一般較難較難語(yǔ)言特點(diǎn)簡(jiǎn)單嚴(yán)謹(jǐn)靈活高度面向?qū)ο筮\(yùn)行速度慢較快快慢庫(kù)的功能弱一般很強(qiáng)強(qiáng)中學(xué)信息學(xué)競(jìng)賽的語(yǔ)言現(xiàn)狀BASIC語(yǔ)言正逐漸被淘汰。 ↘Pascal語(yǔ)言使用較為廣泛,基本保持穩(wěn)定。 →C++語(yǔ)言憑借其本身所具有的高度的靈活性,以及它所帶的庫(kù)的強(qiáng)大功能,被越來(lái)越多的選手所使用。 ↗本文的目的和結(jié)構(gòu)目的:使讀者在掌握Pascal語(yǔ)言的前提下,能盡快地掌握C++語(yǔ)言,并在此基礎(chǔ)上進(jìn)一步深入C++語(yǔ)言的高級(jí)應(yīng)用。結(jié)構(gòu):1從Pascal到C++2深入C++語(yǔ)言3STL簡(jiǎn)介3STL簡(jiǎn)介閱讀本章的必要條件:了解C++面向?qū)ο蟪绦蛟O(shè)計(jì)的基礎(chǔ)知識(shí)、了解一定的算法知識(shí)本章的結(jié)構(gòu):3.1STL概述3.2迭代器3.3算法3.4容器3.5本章小結(jié)3.1STL概述一般化編程一般化編程(genericprogramming)的提出void
swap(int&
x,
int&
y)
{
int
t
=
x;
x
=
y;
y
=
t;
}模板函數(shù)模板函數(shù)template<class
T>
void
swap(T&
x,
T&
y)
{
T
t
=
x;
x
=
y;
y
=
t;
}模板函數(shù)的調(diào)用模板函數(shù)的調(diào)用隱式調(diào)用swap(x,
y);顯式調(diào)用swap<int>(x,
y);模板類(lèi)模板類(lèi)template<class
T,
int
max>
struct
c_array
{
typedef
T
value_type;
typedef
T&
reference;
typedef
const
T&
const_reference;
T
v[max];
operator
T*();
reference
operator
[](size_t
i);
const_reference
operator
[](size_t
i)
const;
size_t
size()
const;
};模板類(lèi)的使用模板類(lèi)的使用c_array<int,
100>
a;c_array<double,
20>
b;c_array<c_array<int,
10>,
10>
c;STL概述STL就是建立在模板函數(shù)和模板類(lèi)基礎(chǔ)之上的功能強(qiáng)大的庫(kù)模板函數(shù)可以實(shí)現(xiàn)一般化的常用算法(如統(tǒng)計(jì)、排序、查找等)模板類(lèi)可以實(shí)現(xiàn)支持幾乎所有類(lèi)型的容器,用來(lái)實(shí)現(xiàn)常用的數(shù)據(jù)結(jié)構(gòu)(如鏈表、棧、隊(duì)列、平衡二叉樹(shù)等)STL頭文件一覽頭文件內(nèi)容頭文件內(nèi)容<iterator>迭代器<vector>向量<utility>輔助功能<deque>雙頭隊(duì)列<memory>內(nèi)存管理<list>鏈表<algorithm>算法<set>集合與多重集合<functional>函數(shù)對(duì)象<map>映射與多重映射<numeric>數(shù)值運(yùn)算<stack>棧<queue>隊(duì)列與優(yōu)先隊(duì)列3.2迭代器迭代器的定義和種類(lèi)迭代器(iterator)實(shí)際上是一種一般化的指針類(lèi)型,是對(duì)指針類(lèi)型的抽象。根據(jù)所支持操作的不同,迭代器被分為五大類(lèi):輸出迭代器(inputiterator)輸入迭代器(outputiterator)前向迭代器(forwarditerator)雙向迭代器(bidirectionaliterator)隨機(jī)迭代器(randomaccessiterator)各種迭代器的功能迭代器類(lèi)型輸出迭代器輸入迭代器前向迭代器雙向迭代器隨機(jī)迭代器縮寫(xiě)OutInForBiRan讀取不支持x=*px=*px=*px=*p操作不支持p->xp->xp->xp->xp[i]寫(xiě)入*p=x不支持*p=x*p=x*p=x迭代++++++++--++--+-+=-=比較不支持==!===!===!===!=<><=>=更多關(guān)于迭代器的信息指針類(lèi)型就是一種特殊的隨機(jī)迭代器類(lèi)型。對(duì)于一般的迭代器,這些功能都是通過(guò)操作符重載來(lái)實(shí)現(xiàn)的。更多關(guān)于迭代器的信息各種迭代器類(lèi)型之間的關(guān)系:迭代器的作用訪(fǎng)問(wèn)元素算法與容器之間的紐帶輸出迭代器輸入迭代器前向迭代器雙向迭代器隨機(jī)迭代器模板類(lèi)pairtemplate<class
T1,
class
T2>
struct
pair
{
typedef
T1
first_type;
typedef
T2
second_type;
T1
first;
T2
second;
pair()
:
first(T1()),
second(T2())
{
}
pair(const
T1&
x,
const
T2&
y)
:
first(x),
second(y)
{
}
template<class
U,
class
V>
pair(const
pair<U,
V>&
p)
:
first(p.first),
second(p.second)
{
}
};模板類(lèi)pairtemplate<class
T1,
class
T2>
pair<T1,
T2>
make_pair(const
T1&
x,
const
T2&
y)
{
return
pair<T1,
T2>(x,
y);
}作用儲(chǔ)存一對(duì)密切相關(guān)的值使用在當(dāng)算法需要返回兩個(gè)值時(shí)作為映射的元素類(lèi)型(關(guān)鍵字和被映射的值)3.3算法與算法有關(guān)的知識(shí)算法(algorithm)每個(gè)算法都是一個(gè)或者一組模板函數(shù),用來(lái)完成一項(xiàng)特定的操作。序列(sequence)序列用兩個(gè)迭代器來(lái)描述,表示一組連續(xù)的元素;其中,第一個(gè)迭代器指向序列中的第一個(gè)元素,第二個(gè)迭代器指向序列最后一個(gè)元素的后一個(gè)位置。與算法有關(guān)的知識(shí)函數(shù)對(duì)象(functionobject)函數(shù)對(duì)象重載了函數(shù)調(diào)用操作符(operator()),可以像普通函數(shù)一樣被使用。謂詞(predicate)返回值類(lèi)型為bool的函數(shù)對(duì)象函數(shù)對(duì)象舉例template<class
T>
class
Sum
{
T
res;
public:
Sum(T
i
=
T())
:
res(i)
{
}
void
operator
()(const
T&
x)
{
res
+=
x;
}
T
result
const
{
return
res;
}
};常用函數(shù)對(duì)象STL在頭文件<functional>中提供了一些常用運(yùn)算的函數(shù)對(duì)象。類(lèi)名類(lèi)型作用equal_to雙目arg1==arg2not_equal_to雙目arg1!=arg2greater雙目arg1>arg2less雙目arg1<arg2greater_equal雙目arg1>=arg2less_equal雙目arg1<=arg2logical_and雙目arg1&&arg2logical_or雙目arg1||arg2logical_not單目!argplus雙目arg1+arg2minus雙目arg1-arg2multiplies雙目arg1*arg2divides雙目arg1/arg2modulus雙目arg1%arg2negate單目-argSTL算法一覽訪(fǎng)問(wèn)元素類(lèi)for_each(),transform()順序查找類(lèi)find(),find_if(),find_first_of(),adjacent_find(),search(),find_end(),search_n()統(tǒng)計(jì)類(lèi)count(),count_if()STL算法一覽比較類(lèi)mismatch(),equal(),lexicographical_compare()復(fù)制類(lèi)copy(),copy_backward()交換類(lèi)swap(),iter_swap(),swap_ranges()STL算法一覽替換類(lèi)replace(),replace_if(),replace_copy(),replace_copy_if()填充發(fā)生類(lèi)fill(),fill_n(),generate(),generate_n()刪除類(lèi)remove(),remove_if(),remove_copy(),remove_copy_ifSTL算法一覽去重類(lèi)unique(),unique_copy()反轉(zhuǎn)類(lèi)reverse(),reverse_copy()旋轉(zhuǎn)類(lèi)rotate(),rotate_copy()隨機(jī)打亂類(lèi)random_shuffle()STL算法一覽排序類(lèi)sort(),stable_sort(),partial_sort(),partial_sort_copy(),nth_element()二分查找類(lèi)lower_bound(),upper_bound(),equal_range(),binary_search()合并類(lèi)merge(),inplace_merge()STL算法一覽分區(qū)類(lèi)partition(),stable_partition()集合運(yùn)算類(lèi)includes(),set_union(),set_intersection(),set_difference(),set_symmetric_difference()堆操作類(lèi)make_heap(),push_heap(),pop_heap(),sort_heap()STL算法一覽最大最小類(lèi)min(),max(),min_element(),max_element()排列類(lèi)next_permutation(),prev_permutation()數(shù)值運(yùn)算類(lèi)accumulate(),inner_product(),partial_sum(),adjacent_difference()常用算法介紹(排序)排序算法原型template<class
Ran>
void
sort(Ran
first,
Ran
last);
template<class
Ran,
class
Cmp>
void
sort(Ran
first,
Ran
last,
Cmp
cmp);時(shí)間復(fù)雜度:平均O(nlogn),最壞O(n2)使用舉例sort(a,
a
+
n);sort(b,
b
+
m,
greater<int>());常用算法介紹(二分查找)二分查找算法原型:template<class
For,
class
T>
bool
binary_search(For
first,
For
last,
const
T&
val);template<class
For,
class
T>
For
lower_bound(For
first,
For
last,
const
T&
val);template<class
For,
class
T>
For
upper_bound(For
first,
For
last,
const
T&
val);template<class
For,
class
T>
pair<For,
For>
equal_range(For
first,
For
last,
const
T&
val);時(shí)間復(fù)雜度:隨機(jī)迭代器O(logn),其他O(n)常用算法介紹(二分查找)算法的要求序列有序查找的謂詞與排序的謂詞相同算法的作用binary_search()返回val是否在序列中。lower_bound()返回指向序列中第一個(gè)大于或等于val的元素的迭代器。upper_bound()返回指向序列中第一個(gè)大于val的元素的迭代器。equal_range()返回一個(gè)pair,表示序列中與val相等的元素所構(gòu)成的子序列。算法的組合使用例如,要對(duì)一組范圍較大的整數(shù)進(jìn)行離散化,步驟如下:用sort()排序;用unique()去掉重復(fù)的元素;對(duì)于每個(gè)整數(shù),用lower_bound()查找在序列中的位置。例題:最長(zhǎng)單調(diào)遞增子序列題目描述給定一個(gè)長(zhǎng)度為n的整數(shù)序列A={a1,a2,...,an},求一個(gè)最大的整數(shù)m,使得存在另一個(gè)序列P={p1,p2,...,pm},滿(mǎn)足,且。約束條件n不超過(guò)30,000ai在[0,1,000,000,00)的區(qū)間內(nèi)思路分析原算法設(shè)fi表示結(jié)尾元素為原序列中第i個(gè)元素的最長(zhǎng)單調(diào)遞增序列的長(zhǎng)度(為了簡(jiǎn)便,設(shè)a0=-∞,f0=0),狀態(tài)轉(zhuǎn)移方程如下:時(shí)間復(fù)雜度O(n2),不符合要求。思路分析改進(jìn)后的算法設(shè)gi表示到目前為止,所有長(zhǎng)度為i的單調(diào)遞增子序列中最后一個(gè)元素的最小值。易知,gi-1≤gi。當(dāng)?shù)降趇-1個(gè)字符為止的{gi}已知時(shí),fi就等于在{gi}中第一個(gè)大于或等于ai的元素的位置j。此時(shí),令gj=ai,更新{gi}。一開(kāi)始,gi=∞。時(shí)間復(fù)雜度O(nlogn),符合要求。改進(jìn)算法運(yùn)行實(shí)例n=10i12345678910ai3141592653figi1112233344∞∞∞∞∞∞∞∞∞∞31425396核心代碼原算法(O(n2)):for(int
i
=
0;
i
<
n;
i++)
{
f[i]
=
1;
for(int
j
=
0;
j
<
i;
j++)
if(a[j]
<
a[i])
f[i]
=
max(f[i],
f[j]
+
1);
}改進(jìn)后的算法(O(nlogn)):fill(g,
g
+
n,
infinity);
for(int
i
=
0;
i
<
n;
i++)
{
int
j
=
lower_bound(g,
g
+
n,
a[i])
-
g;
f[i]
=
j
+
1;
g[j]
=
a[i];
}3.4容器與容器有關(guān)的知識(shí)容器(container)是以一定的形式存儲(chǔ)一組相同類(lèi)型的數(shù)據(jù)的對(duì)象。STL中的容器都是用模板類(lèi)來(lái)實(shí)現(xiàn)的。STL中的容器提供了幾乎相同的接口。容器的成員函數(shù)迭代器操作begin(),end(),rbegin(),rend()元素操作front(),back(),operator[]()列表操作insert(),erase(),clear()容器的成員函數(shù)棧和隊(duì)列操作push_back(),pop_back(),push_front(),pop_front()其它操作size(),empty(),resize()關(guān)聯(lián)容器操作find(),lower_bound(),upper_bound(),equal_range()常用STL容器名稱(chēng)描述所在頭文件迭代器類(lèi)型vector向量<vector>隨機(jī)迭代器deque雙頭隊(duì)列<deque>隨機(jī)迭代器list鏈表<list>雙向迭代器stack棧<stack>不提供迭代器queue隊(duì)列<queue>不提供迭代器priority_queue優(yōu)先隊(duì)列<queue>不提供迭代器set集合<set>雙向迭代器multiset多重集合<set>雙向迭代器map映射<map>雙向迭代器multimap多重映射<map>雙向迭代器一般容器vectordequelist元素多余空間元素指針多余空間多余空間元素元素元素元素哨兵節(jié)點(diǎn)元素節(jié)點(diǎn)元素節(jié)點(diǎn)容器適配器棧stack隊(duì)列queue優(yōu)先隊(duì)列priority_queue關(guān)聯(lián)容器元素有序用平衡二叉樹(shù)實(shí)現(xiàn)類(lèi)名:set,multiset,map,multimap分類(lèi)按元素構(gòu)成來(lái)分集合:元素本身就是關(guān)鍵字,直接參與排序映射:元素由關(guān)鍵字和被映射的值構(gòu)成,只有關(guān)鍵字參與排序按關(guān)鍵字能否重復(fù)來(lái)分普通:關(guān)鍵字不能重復(fù)多重:關(guān)鍵字允許重復(fù)關(guān)聯(lián)容器的特殊成員函數(shù)查找類(lèi)find()lower_bound()upper_bound()equal_range()復(fù)合類(lèi)operator[]()例題:支付帳單題目描述比爾最近遇到了一件麻煩事。每天上午
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 設(shè)備投資計(jì)劃
- 建筑規(guī)劃保安工作計(jì)劃
- 航空領(lǐng)域保安工作的創(chuàng)新計(jì)劃
- 會(huì)計(jì)信息與決策的關(guān)系探討計(jì)劃
- 2025年媒體經(jīng)營(yíng)項(xiàng)目建議書(shū)
- 2025年中國(guó)夜游經(jīng)濟(jì)行業(yè)供需態(tài)勢(shì)、競(jìng)爭(zhēng)格局及投資前景分析報(bào)告(智研咨詢(xún))
- 2025年超硬材料項(xiàng)目合作計(jì)劃書(shū)
- 2025年特種大型鋁合金型材項(xiàng)目發(fā)展計(jì)劃
- 構(gòu)建直觀易用的用戶(hù)操作面板
- 2025年子宮收縮藥項(xiàng)目發(fā)展計(jì)劃
- 《發(fā)展?jié)h語(yǔ)(第二版)中級(jí)綜合(Ⅰ)》第11課+課件
- 醫(yī)師簽名(簽章)留樣備案表
- 0~6歲兒童眼保健和視力檢查標(biāo)準(zhǔn)技術(shù)操作
- 新會(huì)中集:集裝箱ISO尺寸要求
- 項(xiàng)目7選購(gòu)機(jī)箱和atx電源學(xué)習(xí)資料
- 實(shí)施鄉(xiāng)村振興戰(zhàn)略要求鞏固和完善農(nóng)村基本經(jīng)營(yíng)制度
- 護(hù)士長(zhǎng)護(hù)理管理質(zhì)量評(píng)價(jià)表
- ISO45001職業(yè)健康安全管理體系培訓(xùn)
- 骨科檢查法檢查要點(diǎn)
- 漢語(yǔ)言文學(xué)論文6000字
- 電子商務(wù)概論-課件
評(píng)論
0/150
提交評(píng)論