知识点积累(一)
解题思路：1~n 的最小公倍数为小于 n 的所有质数的最大幂（值小于n）的乘积。
比如 n=10 小于 10 的质数有 2 3 5 7 对应的最大幂是： 3 2 1 1 ，所以最小公倍数是： 2^3 * 3^2 * 5^1 * 7^1 = 2520 。
解题思路：由递推思想可以推出到某一位的总位数（由各个数的位数递推相加得到），如果求第 n 位，用二分查找下界得到下标 x ，如果相等则是当前查找到的下标的个位，否则用 n 减 x-1 的总位数 ，再用二分查找从 1 到单个数字 再减去比它小的一个。最后分解第二次返回的下标 。
解题思路：这两个题思路一样在这只说阶乘的0的思路，计算 N ！最后 0 的个数就等于计算 2 和 5 的个数，有于 2 总是比 5 多所以直接计算 包含 5 的个数。
四、STL之 string
string是在做一道搜索题时了解到的，如果不用就会超内存。使用string必须包含头文件 #include<string>， 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<map> .
-
#include <cstdlib>
-
#include <iostream>
-
#include <map>
-
using namespace std;
-
int main(int argc, char *argv[])
-
{
-
// 构造
-
map<string, string> m1, m2;
-
map<int , int>m1,m2 ;
-
map<string , int>m1,m2 ;
-
map<int , string>m1,m2 ;
-
map<string, string>::iterator start; // 用于遍历 map
-
// 插入两种方法
-
m1.insert(pair<string, string>("1", "hello"));
-
m1.insert(pair<string, string>("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<n ;i++)
-
if(!prime[2])
-
for(j=i+i ;j<n ;j+=i )
-
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<M ;i++)
-
{
-
if(!is_prime[i]) prime[num++]=i ;
-
for(j=0 ;(j<num&&i*prime[j]<M) ;j++)
-
{
-
is_prime[i*prime[j]]=true ;
-
if(!(i%prime[j]))
-
break ;
-
}
-
}
七、用函数测试程序的运行时间
不再多说直接上代码：
-
#include<iostream>
-
#include<time.h>
-
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 ;
-
}
-
做题感悟：这题是上次比赛的题，伤心啊！开始做这题时如果排一下序就对了（当时自认为已经排序），做完题后看别人的代码基本上都是一种方法，为什么自己做题时没想到呢！也许是高看这题了，也许是做的题太少，也许是思想太狭小。
解题思路:（1）找到一个最大的值，最大公约数一定小于等于最大值，让最大值每次减一，看是否被 1 ~ n 中的两个数整除，如果可以就找到解了。
（2）先把素数表打出来，排一下序，从小到大开始遍历，找最大公约数，如果这个数是素数不变历（还要判断一下是否与前一个数相等），否则遍历。
做题感悟：刚复习了一下矩阵+快速幂，于是练习了一下。定义变量定义错了，开始定义为全局变量执行完后没有重新初始化。第二次定义为局部变量也没有初始化
。
十、关于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 .
文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/nyist_zxp/article/details/16921407
- 点赞
- 收藏
- 关注作者
评论（0）