知识点积累(一)

一、NYOJ 最小公倍数

解题思路：1~n 的最小公倍数为小于 n 的所有质数的最大幂（值小于n）的乘积。

比如 n=10 小于 10 的质数有 2 3 5 7 对应的最大幂是： 3  2  1  1 ，所以最小公倍数是： 2^3 * 3^2 * 5^1 * 7^1 = 2520 。

优代码~~>

二、NYOJ Digit Problem

解题思路：由递推思想可以推出到某一位的总位数（由各个数的位数递推相加得到），如果求第 n 位，用二分查找下界得到下标 x ，如果相等则是当前查找到的下标的个位，否则用 n 减 x-1 的总位数 ，再用二分查找从 1 到单个数字 再减去比它小的一个。最后分解第二次返回的下标 。

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

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

解题思路：这两个题思路一样在这只说阶乘的0的思路，计算 N ！最后 0 的个数就等于计算 2 和 5 的个数，有于 2 总是比 5 多所以直接计算 包含 5 的个数。

代码~~>

四、STL之 string

string是在做一道搜索题时了解到的，如果不用就会超内存。使用string必须包含头文件  #include， string  类的字符串对象的使用方法与其他对象一样，也必须先定义才可以使用。

定义：string   对象1 ，对象2…… ；

例如：string   str1，str2  ；    string str3（“china”）；//定义string类对象str3同时对其初始化。

基本运算（只列举几种）：

s1 = s2  ; 用s2给s1赋值 ;        s1 + s2  ;  用s1和s2连接成一个串 ;      s1 + = s2 ; 等价于 s1 = s1 + s2 ;

s1 == s2 ；判断s1是否与s2相等 ；           s1[i]  ； 访问串对象s1中下标为i的字符 ；

cin >> s1 ；从键盘输入一个字符串给串对象s1 ；                     cout << s1 ；  将串对象s1输出 ；（用c++格式输入输出）。

五、STL之map

map也是在做一道题时想不出方法来了，听说map可以搞定，于是……

头文件： #include

#include

#include

#include

using namespace std;

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

{

// 构造

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 中第一个值，start->second 代表 map 中第二个值

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;

}

六、筛法||线性筛法

相关题目~~>

筛法思想：一个素数的倍数（大于2倍）一定是合数，只要把所有的素数的倍数都标记就可以。复杂度：O（long long（n）*n）。

代码：

for(i=2 ;i

if(!prime[2])

for(j=i+i ;j

prime[j]=true ;

线性筛法思想：上面那个筛法一个合数可能标记许多次，线性筛法只标记一次，一个合数一定可以分解一个素数与另一个数的乘积，标记合数时用那个合数最小的素因子标记。例如：标记 30 用 2 * 15 标记，即 i = 15 ，而不用 3 * 10 去标记，可以用 if ( ! ( i % prime [ j ] ) )     break ; 来解决。如果 i = 10 ;执行到 2 时，如果继续用 3 与 10 相乘就多余了，因为 10 可以分解出素数 2 ，2 比 3 小，所以用 2 去标记 30 。也可以求出每个合数的最小素因子。复杂度：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 ;

}

}

七、用函数测试程序的运行时间

不再多说直接上代码：

#include

#include

using namespace std ;

int main()

{

clock_t start,finish ;

start=clock() ;

// 中间放程序

finish=clock() ;

cout<< (double)(finish - start) / CLOCKS_PER_SEC ;//运行时间:

// 除以 CLOCKS_PER_SEC 是让时间转化成秒（原先是以毫秒为单位）

return 0 ;

}

八、NYOJ Max Gcd

做题感悟：这题是上次比赛的题，伤心啊！开始做这题时如果排一下序就对了（当时自认为已经排序），做完题后看别人的代码基本上都是一种方法，为什么自己做题时没想到呢！也许是高看这题了，也许是做的题太少，也许是思想太狭小。

解题思路:（1）找到一个最大的值，最大公约数一定小于等于最大值，让最大值每次减一，看是否被 1 ~ n 中的两个数整除，如果可以就找到解了。

（2）先把素数表打出来，排一下序，从小到大开始遍历，找最大公约数，如果这个数是素数不变历（还要判断一下是否与前一个数相等），否则遍历。

本人代码~> 优代码~>

九、HDU 1575 Tr A

做题感悟：刚复习了一下矩阵+快速幂，于是练习了一下。定义变量定义错了，开始定义为全局变量执行完后没有重新初始化。第二次定义为局部变量也没有初始化。

代码~>

十、关于Fibonacci

如果一个为 Fibonacci 序列知道前两项 x ，y 就可以用公式求出第 N 项 先把原  Fibonacci  数列打印出来F[ 1 ]=1 , F[ 2 ]=1 ,  F[ 3 ]=2 ,F[ 4 ]=3 , F[ 5 ]=5 。。。。。然后求当前数列第 N 项     f [ N ] = F[ N-1 ] * y + F[ N-2 ] * x  ；

十一、关于对数

定义、  令 b 是大于 1 的实数，x 是实数。如果对某些正实数 y ,有 y = b ^ x ,那么 x 称为 y 以 b 为底的对数，记为： x = log b ( y ) .其中，b 称为对数的底数，y 称为真数。

关于对数的公式有下列性质：

（1）、负数和零没有对数.

（2）、1 的对数是 0 ，即 logb (1) = 0 .

（3）、底数的对数是 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 ) .

特殊对数：以 10 为底的对数称为常数对数，即 N 的常数对数记做 lgN .以无理数 e ( e = 2.71828…… ) 为底的对数称为自然对数，N 的自然对数记做 ln N ; 以 2 为底的对数记为 log N .

深度学习

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。