一，数组：
1，定义：
数组是一个连续的存储空间，用一个统一的名字（数组名）来标识，用不同的下标来区分。
数组的定义：
数组在使用前务必要定义！
数据类型名 数组名[数组元素个数];
例如：
double a[10];//可以使用a[0]~a[9];
bool b[10];
数组的初始化
1.使用for循环初始化
2.memset(数组名，初始值，空间大小）;
初始值：0 -1 字符型常量
3.定义确定的常量数组后，用{}方式
int a[1500]={0};
注意事项：
1.下标范围：0~长度-1
2.数组的下标和长度必须是整数类型
例一：输入n个学生的考试成绩，计算平均分？计算高于平均分的人数？
输入：
5
60 70 90 100 80
输出：
80 2
#include <iostream>
using namespace std;
int main()
{
int n,i;
cin>>n;
int a[n];
for(i=0;i<n;i++)cin>>a[i];
int pj=0,js=0;
for(i=0;i<n;i++)
{pj=pj+a[i];}
pj=pj/n;
for(i=0;i<n;i++)
if(a[i]>pj)js++;
cout<<pj<<“ ”<<js<<endl;
system ("pause");
return 0;
}
1.灯的开关
【问题描述】有N盏电灯排成一行，依次编号为1，2，3，…,N。现各有一个开关，开始灯都亮着的。现在还有N个人，第一人走过来依次把1和1的倍数电灯的开关都拉一下。第三个人走过来依次把3和3的倍数的开关都拉一下，第五个人走过来依次把5和5的倍数的开关都拉一下（按奇数的规律），…问最后都有哪些灯是关着的？
【输入样例】10
【输出样例】1 2 4 8 9
2.校门外的树
【问题描述】
某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0，1，2，……，L，都种有一棵树。
由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。
【样例输入】
500 3
150 300
100 200
470 471
【样例输出】 298
答案：
1.#include <iostream>
using namespace std;
int main()
{
int i,j,n;
cin>>n;
int a[n+1];
for(i=1;i<=n;i++) a[i]=1;
for(i=1;i<=n;i=i+2)
for(j=1;j<=n;j++)
if(j %i==0)a[j]=1-a[j];
for(i=1;i<=n;i++)
if(a[i]==0)cout<<i<<endl;
system("pause");
return 0;
}
2.#include <iostream>
using namespace std;
int main()
{
int i,m,L,j,a1,b,js;
cin>>L>>m;
int a[L+1];
for(i=0;i<=L;i++) a[i]=1;
for(i=1;i<=m;i++)
{
cin>>a1>>b;
for(j=a1;j<=b;j++)a[j]=0;
}
js=0;
for(i=0;i<=L;i++)
if(a[i]==1)js++;
cout<<js<<endl;
system("pause");
return 0;
}
二维数组：
定义：类型说明符 数组名[常量表达式][常量表达式]；
例如：float a[3][4];
定义a为3 *4（3行4列）的二维数组。二维数组可以看为一种特殊的一维数组：它的元素又是一个一维数组。如：可以把a看为一个一维数组，它有3个元素a[0],a[1],a[2],每个元素又是一个包含4个元素的一维数组。
存储：float a[3][4]; 第一个下标范围是0～2（行下标）．第二个下标范围是0～3（列下标）。二维数组是按先行后列的顺序在内存中线性排列的。
一般来说，涉及到行和列的问题可以采用二维数组来处理。
最短路线（bestpath.cpp）
〖问题描述〗
某城市的街道是一个很规整的矩形网格，有m条南北向的纵街，n条东西向的横街。现要从西南角的A走到东北角的B，编程计算最短的走法共有多少种？
〖样例输入〗7 5
〖样例输出〗210
#include <iostream>
using namespace std;
int f[100][100];
int main()
{
int m,n;
cin>>m>>n;
int i,j;
for (i=1;i<=m;i++) f[i][1]=1;
for (i=1;i<=n;i++) f[i][i]=1;
for (j=2;j<=n;j++)
for (i=2;i<=m;i++) f[i][j]=f[i-1][j]+f[i][j-1];
for (i=1;i<=m;i++)
{
for (j=1;j<=n;j++) cout<<f[i][j]<<' ';
cout<<endl;
}
cout<<f[m][n]<<endl;
system("pause");
return 0;
}
二，排序
图示：http://blog.renren.com/share/442313448/11827960119
1.插入排序
核心思想：
将数据分为：有序部分和无序部分
有序部分：a[0]~a[i-1]
无序部分：a[i]~a[n-1]
处理过程：将a[i]取出，找到合适的位置
插入(腾空间)到有序部分中,有序元素增加1，无序元素减少1个!
#include <iostream>
using namespace std;
void insert(int a[],int n)
{
int i,j,x;
//a[0]默认有序
for(i=1;i<n;i++)
{
x=a[i];//待插入到有序序列的每一个数
//顺序查找插入的位置
for(j=i-1;j>=0 && x<a[j];j--)
{
a[j+1]=a[j];
}
//插入操作
a[j+1]=x;
}
}
int main()
{
int i,n;
cin>>n;
int a[n];
for(i=0;i<n;i++)cin>>a[i];
insert(a,n);
for(i=0;i<n;i++)cout<<a[i]<<" ";
system("pause");
return 0;
}
二分查找法
输入n个有序（小至大）数，再输入被查找的数据。
输出该数在原数中的位置，如不存在输出-1.
#include <iostream>
using namespace std;
int binsearch(int a[],int n,int x)
{
int i,left,right,mid;
left=0;right=n-1;
while(left<=right)
{
mid=(left+right)/2;//向下取整
if(x<a[mid])
right=mid-1;
else if(x>a[mid])
left=mid+1;
else
return mid;
}
return -1;
}
int main()
{
int i,n,x,p;
cin>>n;
int a[n];
for(i=0;i<n;i++)cin>>a[i];
cin>>x;
p=binsearch(a,n,x);
cout<<p<<endl;
system("pause");
return 0;
}
二分查找法实现插入排序。。。
#include <iostream>
using namespace std;
/*int binsearch(int a[],int n,int x)
{
int i,left,right,mid;
left=0;right=n-1;
while(left<=right)
{
mid=(left+right)/2;//向下取整
if(x<a[mid])
right=mid-1;
else if(x>a[mid])
left=mid+1;
else
return mid;
}
}
*/
void insert(int a[],int n)
{
int i,j,x,k,l,r,mid;
//a[0]默认有序
for(i=1;i<n;i++)
{
x=a[i];//待插入到有序序列的每一个数
//顺序查找插入的位置
l=0;r=i-1;
while(l<=r)
{
mid=(l+r)/2;
if(x<a[mid])
r=mid-1;
else
l=mid+1;
}
for(j=i-1;j>=l;j--) a[j+1]=a[j];
//插入操作
a[l]=x;
}
}
int main()
{
int i,n;
cin>>n;
int a[n];
for(i=0;i<n;i++)cin>>a[i];
insert(a,n);
for(i=0;i<n;i++)cout<<a[i]<<" ";
system("pause");
return 0;
}
快速排序：
#include <iostream>
using namespace std;
void quicksort(int a[],int l,int r)
{
int i,j,x;
i=l;j=r;
x=a[l];
if(i>=j) return ;
while(i<j)
{
while(a[j]>=x && i<j)j--;
swap(a[i],a[j]);
while(a[i]<=x && i<j)i++;
swap(a[i],a[j]);
}
quicksort(a,l,i-1);
quicksort(a,i+1,r);
}
int main()
{
int i,n;
cin>>n;
int a[n];
for(i=0;i<n;i++)cin>>a[i];
quicksort(a,0,n-1);
for(i=0;i<n;i++)cout<<a[i]<<" ";
system("pause");
return 0;
}
捷径：
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{int n,i;
cin>>n;
for(i=0;i<n;i++)cin>>a[i];
sort(a,a+n);
for(i=0;i<n;i++)cout<<a[i]<<" "；
return 0;
}