知識點(diǎn)積累(一)

一、NYOJ 最小公倍數(shù)

解題思路：1~n 的最小公倍數(shù)為小于 n 的所有質(zhì)數(shù)的最大冪（值小于n）的乘積。

比如 n=10 小于 10 的質(zhì)數(shù)有 2 3 5 7 對應(yīng)的最大冪是： 3 ?2? 1? 1 ，所以最小公倍數(shù)是： 2^3?* 3^2 * 5^1 * 7^1 = 2520?。

優(yōu)代碼~~>

二、NYOJ Digit Problem

解題思路：由遞推思想可以推出到某一位的總位數(shù)（由各個(gè)數(shù)的位數(shù)遞推相加得到），如果求第 n?位，用二分查找下界得到下標(biāo) x ，如果相等則是當(dāng)前查找到的下標(biāo)的個(gè)位，否則用 n?減 x-1 的總位數(shù)?，再用二分查找從 1 到單個(gè)數(shù)字?再減去比它小的一個(gè)。最后分解第二次返回的下標(biāo) 。

思路有可能解釋的不太清晰：代碼（1）代碼（2）。

三、NYOJ 階乘的0?||階乘因式分解（二）

解題思路：這兩個(gè)題思路一樣在這只說階乘的0的思路，計(jì)算 N ！最后 0 的個(gè)數(shù)就等于計(jì)算 2 和 5 的個(gè)數(shù)，有于 2 總是比 5 多所以直接計(jì)算 包含 5 的個(gè)數(shù)。

代碼~~>

四、STL之 string

string是在做一道搜索題時(shí)了解到的，如果不用就會超內(nèi)存。使用string必須包含頭文件? #include，?string??類的字符串對象的使用方法與其他對象一樣，也必須先定義才可以使用。

定義：string?? 對象1 ，對象2…… ；

例如：string?? str1，str2? ；??? string str3（“china”）；//定義string類對象str3同時(shí)對其初始化。

基本運(yùn)算（只列舉幾種）：

s1 = s2 ?; 用s2給s1賦值 ;????????s1 + s2??; ?用s1和s2連接成一個(gè)串?;??????s1 + = s2?; 等價(jià)于 s1 = s1 + s2?;

s1 == s2 ；判斷s1是否與s2相等 ；???????????s1[i]? ； 訪問串對象s1中下標(biāo)為i的字符 ；

cin >> s1?；從鍵盤輸入一個(gè)字符串給串對象s1 ；???????????????????? cout << s1?；? 將串對象s1輸出 ；（用c++格式輸入輸出）。

五、STL之map

map也是在做一道題時(shí)想不出方法來了，聽說map可以搞定，于是……

頭文件： #include

#include

#include

#include

using namespace std;

int main(int argc, char *argv[])

{

// 構(gòu)造

map m1, m2;

mapm1,m2 ;

mapm1,m2 ;

mapm1,m2 ;

map::iterator start; // 用于遍歷 map

// 插入兩種方法

m1.insert(pair("1", "hello"));

m1.insert(pair("2", "world"));

m2["3"] = "test";

m2["4"] = "swap";

// 交換

swap(m1, m2);

// 遍歷 start->first 代表 map 中第一個(gè)值，start->second 代表 map 中第二個(gè)值

for (start = m1.begin(); start != m1.end(); start++)

{

cout << start->second << endl;

}

cout << endl;

m2.clear(); // 清空

if (m2.empty()) // 判斷是否為空，空為真

cout << "m2 is empty" << endl << endl;

//擦除

m1.erase("3");

m1.erase("3");

m1.erase("H");

// 在 map 中尋找 “4”

start = m1.find("4");

if (start != m1.end())

cout << start->first << " is in m1, and the value is "

<< start->second << endl << endl;

else

cout << "cannot find the key" << endl << endl;

cout << "m1 has " << m1.count("4") << " value(s) with the key 4" << endl << endl;

system("PAUSE");

return EXIT_SUCCESS;

}

六、篩法||線性篩法

相關(guān)題目~~>

篩法思想：一個(gè)素?cái)?shù)的倍數(shù)（大于2倍）一定是合數(shù)，只要把所有的素?cái)?shù)的倍數(shù)都標(biāo)記就可以。復(fù)雜度：O（long long（n）*n）。

代碼：

for(i=2 ;i

if(!prime[2])

for(j=i+i ;j

prime[j]=true ;

線性篩法思想：上面那個(gè)篩法一個(gè)合數(shù)可能標(biāo)記許多次，線性篩法只標(biāo)記一次，一個(gè)合數(shù)一定可以分解一個(gè)素?cái)?shù)與另一個(gè)數(shù)的乘積，標(biāo)記合數(shù)時(shí)用那個(gè)合數(shù)最小的素因子標(biāo)記。例如：標(biāo)記 30 用 2 *?15 標(biāo)記，即 i = 15 ，而不用 3 * 10 去標(biāo)記，可以用 if ( ! ( i % prime [ j ] )?)?????break ; 來解決。如果 i = 10 ;執(zhí)行到 2 時(shí)，如果繼續(xù)用 3 與 10 相乘就多余了，因?yàn)?10 可以分解出素?cái)?shù) 2 ，2 比 3 小，所以用 2 去標(biāo)記 30 。也可以求出每個(gè)合數(shù)的最小素因子。復(fù)雜度：O（n）。

for(i=2 ;i

{

if(!is_prime[i]) prime[num++]=i ;

for(j=0 ;(j

{

is_prime[i*prime[j]]=true ;

if(!(i%prime[j]))

break ;

}

}

七、用函數(shù)測試程序的運(yùn)行時(shí)間

不再多說直接上代碼：

#include

#include

using namespace std ;

int main()

{

clock_t start,finish ;

start=clock() ;

// 中間放程序

finish=clock() ;

cout<< (double)(finish - start) / CLOCKS_PER_SEC ;//運(yùn)行時(shí)間:

// 除以 CLOCKS_PER_SEC 是讓時(shí)間轉(zhuǎn)化成秒（原先是以毫秒為單位）

return 0 ;

}

八、NYOJ Max Gcd

做題感悟：這題是上次比賽的題，傷心啊！開始做這題時(shí)如果排一下序就對了（當(dāng)時(shí)自認(rèn)為已經(jīng)排序），做完題后看別人的代碼基本上都是一種方法，為什么自己做題時(shí)沒想到呢！也許是高看這題了，也許是做的題太少，也許是思想太狹小。

解題思路:（1）找到一個(gè)最大的值，最大公約數(shù)一定小于等于最大值，讓最大值每次減一，看是否被 1 ~ n 中的兩個(gè)數(shù)整除，如果可以就找到解了。

（2）先把素?cái)?shù)表打出來，排一下序，從小到大開始遍歷，找最大公約數(shù)，如果這個(gè)數(shù)是素?cái)?shù)不變歷（還要判斷一下是否與前一個(gè)數(shù)相等），否則遍歷。

本人代碼~>?優(yōu)代碼~>

九、HDU 1575 Tr A

做題感悟：剛復(fù)習(xí)了一下矩陣+快速冪，于是練習(xí)了一下。定義變量定義錯(cuò)了，開始定義為全局變量執(zhí)行完后沒有重新初始化。第二次定義為局部變量也沒有初始化。

代碼~>

十、關(guān)于Fibonacci

如果一個(gè)為 Fibonacci 序列知道前兩項(xiàng) x ，y 就可以用公式求出第 N 項(xiàng) 先把原? Fibonacci ?數(shù)列打印出來F[ 1 ]=1 ,?F[ 2 ]=1 , ?F[ 3 ]=2?,F[ 4 ]=3 , F[ 5 ]=5 。。。。。然后求當(dāng)前數(shù)列第 N 項(xiàng)??? ?f [ N ] = F[ N-1 ] * y + F[ N-2 ] * x? ；

十一、關(guān)于對數(shù)

定義、? 令 b 是大于 1 的實(shí)數(shù)，x 是實(shí)數(shù)。如果對某些正實(shí)數(shù) y ,有 y = b ^ x ,那么 x 稱為 y 以 b 為底的對數(shù)，記為： x = log b ( y ) .其中，b?稱為對數(shù)的底數(shù)，y?稱為真數(shù)。

關(guān)于對數(shù)的公式有下列性質(zhì)：

（1）、負(fù)數(shù)和零沒有對數(shù).

（2）、1 的對數(shù)是 0 ，即 logb (1) = 0 .

（3）、底數(shù)的對數(shù)是 1 ，即log b（b）= 1 .

（4）、logb( b ^ n ) = n .

（5）、b ^ ( logb( n ) ) = n .

（6）、logb( m * n ) = logb( m ) + logb( n ) .

（7）、logb( m / n ) = logb( m ) - logb( n ) .

（8）、logb( m ^ n ) =n * logb( m ) .

特殊對數(shù)：以 10 為底的對數(shù)稱為常數(shù)對數(shù)，即 N 的常數(shù)對數(shù)記做 lgN .以無理數(shù) e ( e = 2.71828…… ) 為底的對數(shù)稱為自然對數(shù)，N 的自然對數(shù)記做 ln N ;?以 2 為底的對數(shù)記為?log N .

深度學(xué)習(xí)

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實(shí)的內(nèi)容，請聯(lián)系我們jiasou666@gmail.com 處理，核實(shí)后本網(wǎng)站將在24小時(shí)內(nèi)刪除侵權(quán)內(nèi)容。

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實(shí)的內(nèi)容，請聯(lián)系我們jiasou666@gmail.com 處理，核實(shí)后本網(wǎng)站將在24小時(shí)內(nèi)刪除侵權(quán)內(nèi)容。