计算机竞赛蓝桥杯有关知识.doc

1. 入门训练Fibonacci数列
斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递归的方法定义：F(0)=0，F(1)=1, F(n)=F(n-1)+F(n-2)（n>=2，n∈N*）在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用，为此，美国数学会从1963起出版了以《斐波纳契数列季刊》为名的一份数学杂志，用于专门刊载这方面的研究成果。
值得注意的是运算符%的左右操作数必须都为int型。
运算符%最基本的应用就是判断奇偶性（a%2），还有就是用在循环链表和循环队列中，用于判断节点的位置。
问题描述：Fibonacci数列的递推公式为：Fn=Fn-1+Fn-2，其中F1=F2=1。当n比较大时，Fn也非常大，现在我们想知道，Fn除以10007的余数是多少。
输入格式：输入包含一个整数n。
输出格式：输出一行，包含一个整数，表示Fn除以10007的余数。
说明：在本题中，答案是要求Fn除以10007的余数，因此我们只要能算出这个余数即可，而不需要先计算出Fn的准确值，再将计算的结果除以10007取余数，直接计算余数往往比先算出原数再取余简单。
#include
int main()
{
int n;
scanf("%d",&n);
double a[n];
a[0]=0;
a[1]=a[2]=1;
for(int i=3;i<=n;i++)
{
a[i]=a[i-1]+a[i-2];
}
printf("%d",(int)a[n]%10007);
return 0;
}

#include
int main()
{
unsigned long s=0,f1=1,f2=1,f3=1,n=0;
scanf("%d",&n);

if(n>2)
for(s=3;s<=n;s++)
{
f3=(f2+f1)%10007;
f1=f2;
f2=f3;
}

printf("%d",f3);
return 0;
}

a与b的和除以c的余数（a、b两数除以c在没有余数的情况下除外），等于a，b分别除以c的余数之和（或这个和除以c的余数）。a与b的乘积除以c的余数，等于a，b分别除以c的余数之积（或这个积除以c的余数）。

2. 入门训练 圆的面积
后缀应该是.c而不是.cpp后果：不准确；
const double pi=4*atan(1.0);╳应该去掉const
tan(PI/4)=1 PI=4*arctan(1); arctan()在C语言里表示为atan() 即pi=4.0*atan(1.0) 这里保证了精度。
3. 入门训练 序列求和
Scanf中不能有\n
long long类型输出格式%I64d(是I大写i不是1)
4. 入门训练 A+B问题
5. 基础练习V矩阵乘法——二维数组 循环 矩阵
memset是计算机中C/C++语言函数。将s所指向的某一块内存中的前n个 字节的内容全部设置为ch指定的ASCII值， 第一个值为指定的内存地址，块的大小由第三个参数指定，这个函数通常为新申请的内存做初始化工作， 其返回值为指向s的指针。memset(void *s, int ch,size_tn);中key实际范围应该在0~~255，因为该函数只能取ch的后八位赋值给你所输入的范围的每个字节，比如int a[5]赋值memset（a,-1,sizeof(int )*5）与memset（a,511,sizeof(int )*5） 所赋值的结果是一样的都为-1；因为-1的二进制码为（11111111 11111111 11111111 11111111）而511的二进制码为（00000000 00000000 00000001 11111111）后八位都为（11111111)，所以数组中每个字节，如a[0]含四个字节都被赋值为（11111111），其结果为a[0]（11111111 11111111 11111111 11111111），及a[0]=-1，因此无论ch多大只有后八位二进制有效，而八位二进制[2]  的范围（0~255）YKQ改。而对字符数组操作时则取后八位赋值给字符数组，其八位值作为ASCII[3]  码。
void *memset(void *s, int ch, size_t n);
函数解释：将s中当前位置后面的n个字节 typedef unsigned int size_t ）用 ch 替换并返回 s 。
memset：作用是在一段内存块中填充某个给定的值，它是对较大的结构体或数组进行清零操作的一种最快方法。
基础练习 十六进制转八进制

6. 基础练习V矩形面即交——判断 线段交
Max和min函数在stdio.h中一般以宏的形式声明
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
7. 基础练习V完美的代价——贪心算法 外文名 greedy algorithm
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。
贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。
性质 一种改进了的分级处理方法 核心 根据题意选取一种量度标准
DP指动态规划.可以理解为通过状态最优解得到全局最优解。
7.1 基本要素：
① 贪心选择
贪心选择是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。贪心选择是采用从顶向下、以迭代的方法做出相继选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题。对于一个具体问题，要确定它是否具有贪心选择的性质，我们必须证明每一步所作的贪心选择最终能得到问题的最优解。通常可以首先证明问题的一个整体最优解，是从贪心选择开始的，而且作了贪心选择后，原问题简化为一个规模更小的类似子问题。然后，用数学归纳法证明，通过每一步贪心选择，最终可得到问题的一个整体最优解。
② 最优子结构
当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。运用贪心策略在每一次转化时都取得了最优解。问题的最优子结构性质是该问题可用贪心算法或动态规划算法求解的关键特征。贪心算法的每一次操作都对结果产生直接影响，而动态规划则不是。贪心算法对每个子问题的解决方案都做出选择，不能回退；动态规划则会根据以前的选择结果对当前进行选择，有回退功能。动态规划主要运用于二维或三维问题，而贪心一般是一维问题。
7.2 基本思路：
① 思想
贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行，根据某个优化测度，每一步都要确保能获得局部最优解。每一步只考虑一个数据，他的选取应该满足局部优化的条件。若下一个数据和部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加算法停止。
② 过程
建立数学模型来描述问题；
把求解的问题分成若干个子问题；
对每一子问题求解，得到子问题的局部最优解；
把子问题的解局部最优解合成原来解问题的一个解。
7.3 贪婪算法可解决的问题通常大部分都有如下的特性：
① 随着算法的进行，将积累起其它两个集合：一个包含已经被考虑过并被选出的候选对象，另一个包含已经被考虑过但被丢弃的候选对象。
② 有一个函数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑此时的解决方法是否最优。
③ 还有一个函数检查是否一个候选对象的集合是可行的，也即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个函数一样，此时不考虑解决方法的最优性。
④ 选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解。
⑤ 最后，目标函数给出解的值。
⑥ 为了解决问题，需要寻找一个构成解的候选对象集合，它可以优化目标函数，贪婪算法一步一步的进行。起初，算法选出的候选对象的集合为空。接下来的每一步中，根据选择函数，算法从剩余候选对象中选出最有希望构成解的对象。如果集合中加上该对象后不可行，那么该对象就被丢弃并不再考虑；否则就加到集合里。每一次都扩充集合，并检查该集合是否构成解。如果贪婪算法正确工作，那么找到的第一个解通常是最优的。
基础练习V回形取数
void *memset(void *s, int ch, size_t n);
函数解释：将s中当前位置后面的n个字节 （typedef unsigned int size_t ）用 ch 替换并返回 s 。
memset：作用是在一段内存块中填充某个给定的值，它是对较大的结构体或数组进行清零操作的一种最快方法。
算法训练最大最小公倍数——贪心
根据数论知识：任意大于1的两个相邻的自然数都是互质的.
n*(n-1)*(n-5) = n^3 -6*n^2 + 5*n 而如果这个可以
那个其值肯定要小于(n-1)*(n-2)*(n-3) = n^3 -6*n^2+11n-6(对于n>1来说都成立),