一、一维数组的知识
#### 扩:setw(输出的宽度) C++ 中的格式化函数，用于指定输出流的宽度。不能用于输入流
#### 一维数组：一组相同类型的变量
## 格式：类型标识符 数组名[常量表达式]; eg: int a[5];
-- 类型标识符(基本数据类型/结构体等构造类型)
## 引用数组格式：数组名[下标]
eg: h[5]、h[i*2+1]等。
注意1：下标只能为整型常量或整型表达式 √√√
-- 整型表达式而不是整形变量 √√√
注意二：下标值必须在数组定义的下标范围内
注意三：不能一次引用整个数组，只能逐个引用数组的单个元素。
注意四：单输出数组名，返回数组的首地址
## sizeof会返回数据类型的(字节)大小 int = 4字节 =（4*8）32位 1字节 = 1字符 = 1/2汉字 √√√
eg:int a[3]={1,2,3};
int b=12;
cout << sizeof(a) << endl;
cout << sizeof(b) << endl;
## system("pause") -- 暂停程序的执行(暂停命令行窗口) 目的:为了查看程序的结果/错误信息
## 数组在计算机内存单元中是连续存储的
## 数组的插入思路：从最后开始往后移动直到插入后的位置逐步加一，然后开始插入x √√√
## 数组的删除思路：从删除的位置之后开始往前i减一(直接进行覆盖，不用再删除) √√√
## 数组的查找x:
# 查找操作的结果：可能是一个没找到、找到一个或者找到很多个
# 常见的查找：顺序查找和二分查找
# 顺序查找：按照从前往后的顺序，将数组中的元素依次与要查找的数x进行比较。
# 二分查找(折半查找)：√√√
要求：数据是递增或递减排序的。数据是有序的。
left right mid=(left+right)/2 循环：mid跟查找x比较，找到输出位置；
若没找到，若在左面，right=mid-1，若在右面，left=mid+1
优点：比较次数少、查找速度快。
## 数组的排序问题：通过数组中的元素比较和交换来实现的，关键是数组下标的分析 √√√
# 选择排序：从小到大：假设一个最小的，依次每个与最小的进行比较(获取最小的) 放在第一个位置(依次放到第二个位置.... )
# 冒泡排序：从小到大：每一轮依次两两进行比较，大的交换到后面(依次第二后，第三后...)
# 插入排序:
思想：把所有待排序元素分成前后两段，前一段是已经排好序的，后一段是待排序的。
每一趟都是把后一段的第一个数“插入”到前一段的某一个位置，保证前一段仍然是有序的。
开始时，第 1 个数作为前一段肯定是有序的；第一趟，把第 2 个数插入进去，保证前 2个数有序；
第二趟，把第 3 个数插入进去，保证前 3 个数有；……第 n-1 趟，把第 n 个数插入进去，保证 n 个数都有序。
二、数组的整体赋值
整体赋值(统一赋值)：给数组按字节整体赋值，按元素整体赋值：
## fill(d,d+5,8); //给d数组的前5个元素赋值为8
## memset(c,0,5); //给数组前5个字节都赋值为 0
## memset(b,1,sizeof(b)); //将b数组所有元素均赋值，按照sizeof(int) = 4字节 = 每一字节按8位计算2^0+2^8+2^16+2^24
## 示例：
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int main(){
int a[10],b[10],c[10],d[10],i;
memset(a,0,sizeof(a)); // 将a数组所有元素均赋值为0
for(i = 0; i < 9; i++) cout << a[i] << " " ;
cout << a[9] << endl;
memset(b,1,sizeof(b));// 将 b 数组所有元素均赋值
//二进制数 2^0+2^8+2^16+2^24=16843009
for(i = 0; i < 9; i++) cout << b[i] << " " ;
cout << b[9] << endl;
memset(c,0,5);
//将 c 数组前 5 个字节都赋值为 0，所以只能确定 c[0]
//等于0，其他元素值不确定
for(i = 0; i < 9; i++) cout << c[i] << " " ;
cout << c[9] << endl;
fill(d,d+5,8);
//将 d 数组前 5 个元素都赋值为 8，其他元素值不确定
for(i = 0; i < 9; i++) cout << d[i] << " " ;
cout << d[9] << endl;
return 0;
}
三、下楼梯问题
【问题描述】
一个楼梯有 n 级，小苏同学从下往上走，一步可以跨一级，也可以跨两级。问：他走到第 n 级楼梯有多少种走法？
【输入格式】
一行一个整数 n，0<n≤30。
【输出格式】
一行 n 个整数，之间用一个空格隔开，表示走到第 1 级、第 2 级、……第 n 级分别有多少种走法。
【输入样例】
2
【输出样例】
1 2
#### 【问题分析】
假设 f (i) 表示走到第 i 级楼梯的走法，则走到第 i (i>2)级楼梯有两种可能：一种是从第 i-1级楼梯走过来；另一种是从第 i-2 级楼梯走过来。
根据加法原理，f (i) = f (i-1) + f (i-2)，边界条件为：f (1) = 1，f (2) = 2。
具体实现时，定义一维数组 f，用赋值语句从前往后对数组的每一个元素逐个赋值。本质上，f (i) 构成了斐波那契数列
#### 解法：
#include<cstdio>
using namespace std;
int main(){
int n,i,f[31];
scanf( " %d " ,&n);
f[1] = 1; f[2] = 2;
for(i = 3; i <= n; i++) f[i] = f[i-1] + f[i-2];
for(i = 1; i < n; i++) printf( " %d ",f[i]);
printf( " %d\n " ,f[n]);
return 0;
}
四、幸运数问题：
【问题描述】
判断一个正整数 n 是否能被一个“幸运数”整除。幸运数是指一个只包含 4 或 7 的正整数，如 7、47、477 等都是幸运数，17、42 则不是幸运数。
【输入格式】
一行一个正整数 n，1≤n≤1000。
【输出格式】
一行一个字符串，如果能被幸运数整除输出“YES”；否则，输出“NO”。
【输入样例】
47
【输出样例】
YES
#### 【问题分析】
分析发现，1~1000 范围内的幸运数只有 14 个。于是，将这 14 个幸运数直接存储到一个数组 lucky 中，再穷举判断其中有没有一个数能整除 n。
#### 代码：
//p5-2-3
#include<cstdio>
using namespace std;
int main(){
int n,lucky[14] = {4,7,44,47,74,77,444,447,474,477,744,747,
774,777};// 在数组定义时给数组赋值
scanf( " %d " , &n);
bool flag = false;
for(int i = 0; i < 14; i++)
if(n % lucky[i] == 0) flag = true;
if(flag) printf( " YES\n " );
else printf( " NO\n " );
return 0;
}
五、插队问题(数组的插入x)：
(数组的插入)思路：从最后开始往后移动，直到插入后的位置，然后开始插入
【问题描述】
有 n 个人（每个人有一个唯一的编号，用 1~n 之间的整数表示）在一个水龙头前排队准备接水，
现在第 n 个人有特殊情况，经过协商，大家允许他插队到第 x 个位置。输出第 n 个人插队后的排队情况。
【输入格式】
第一行 1 个正整数 n，表示有 n 个人，2<n≤100。
第二行包含 n 个正整数，之间用一个空格隔开，表示排在队伍中的第 1~ 第 n 个人的编号。
第三行包含 1 个正整数 x，表示第 n 个人插队的位置，1≤x<n。
【输出格式】
一行包含 n 个正整数，之间用一个空格隔开，表示第 n 个人插队后的排队情况。
【输入样例】
7
7 2 3 4 5 6 1
3
【输出样例】
7 2 1 3 4 5 6
#### 【问题分析】
n个人的排队情况可以用数组 q 表示，q[i]表示排在第 i 个位置上的人。
定义数组时多定义一个位置，然后重复执行：q[i+1] = q[i]，其中，i 从 n ~ x。
最后再执行 q[x] = q[n+1]，输出 q[1] ~ q[n]。
#### 代码：
#include<cstdio>
using namespace std;
int main(){
int n,i,x,q[102];
scanf( " %d " ,&n);
for(i = 1; i <= n; i++) scanf( " %d " ,&q[i]);
scanf( " %d " ,&x);
for(i = n; i >= x; i--) q[i+1] = q[i];
q[x] = q[n+1];
for(i = 1; i < n; i++) printf( " %d " ,q[i]);
printf( " %d\n " ,q[n]);
return 0;
}
六、队伍调整：有一个人离开队伍(数组的删除x)
【问题描述】
有 n 个人（每个人有一个唯一的编号，用 1~n 之间的整数表示）在一个水龙头前排队准备接水，现在第 x 个人有特殊情况离开了队伍，求第 x 个人离开队伍后的排队情况。
【输入格式】
第一行 1 个正整数 n，表示有 n 个人，2<n≤100。
第二行包含n个正整数，之间用一个空格隔开，表示排在队伍中的第1个到第n个人的编号。
第三行包含 1 个正整数 x，表示第 x 个人离开队伍，1≤x≤n。
【输出格式】
一行包含 n-1 个正整数，之间用一个空格隔开，表示第 x 个人离开队伍后的排队情况。
【输入样例】
7
7 2 3 4 5 6 1
3
【输出样例】
7 2 4 5 6 1
#### 代码：
#include<cstdio>
using namespace std;
int main(){
int n,i,x,q[102];
scanf( " %d " ,&n);
for(i = 1; i <= n; i++) scanf( " %d " ,&q[i]);
scanf( " %d " ,&x);
for(i = x; i < n; i++) q[i] = q[i+1];
n--;
for(i = 1; i < n; i++) printf( " %d " ,q[i]);
printf( " %d\n " ,q[n]);
return 0;
}
七、数组的二分查找(前提数据是有序的)：
int left = 0，right = n - 1;
int find = n;//find标记找到的位置，初始化为n，表示没找到
while(left <= right){
int mid = (left + right) / 2;
if(a[mid] == x){//找到了，就标记位置，并退出循环
find = mid;
break;
}
if(x < a[mid]) right = mid - 1;//x只能在左半部分
if(a[mid] < x) left = mid + 1; //x只能在右半部分
}
if(find != n) printf("%d\n",find);
else printf("not find\n");
八、选择排序(从小到大)：
选择排序的基本思想是：每一趟从待排序的数据中，通过“打擂台”比较选出最小元素，放在这些数据的最前面。
这样，第一趟把 n 个数中（第 1 个到第 n 个）最小的放在第一个位置，
第二趟把剩余的 n-1 个数中（第 2 个到第 n 个）最小的放在第二个位置，
第三趟把剩余的 n-2 个数中（第 3 个到第 n 个）最小的放在第三个位，……
第 n-1 趟把剩下的 2 个数中（第 n-1 个到第 n 个）最小的放在第 n-1 个位置，
剩下的最后一个数（第 n 个）一定最大，自然落在了第 n个位置。
#### 选择排序代码：(从小到大)
#include<iostream>
using namespace std;
int main(){
int n,i,j,k,temp,h[101];
cin >> n;
for(i = 1; i <= n; i++) cin >> h[i];
for(i = 1; i <= n; i++){
k = i; // 定义k为最小的位置
for(j = i+1; j <= n; j++)
if(h[j] < h[k]) k = j;// 在 i~n 之间的最小元素
temp = h[i];
h[i] = h[k]; // 把最小的放到第一个位置i ，依次第二个位置...
h[k] = temp;// 将 i~n 之间的最小元素放到第 i 个位置
}
for(i = 1; i < n; i++) cout << h[i] << " " ;
cout << h[n] << endl;
return 0;
}
九、冒泡排序(从小到大)：
冒泡排序的基本思想是：从第一个数开始，依次不断比较相邻的两个元素，如果“逆序”就交换。
这样，一趟排序结束后，最大的元素就放在了第 n 个位置了。
第二趟把剩余的前 n-1 个数中最大的交换到第 n-1 个位置，
第三趟把剩余的前 n-2 个数中最大的交换到第 n-2 个位置，……
经过 n-1 趟，排序结束。
#### 冒泡排序代码：(从小到大)
#include<iostream>
using namespace std;
int main(){
int n,i,j,temp,h[101];
cin >> n;
for(i = 1; i <= n; i++) cin >> h[i];
for(i = 1; i < n; i++)
for(j = 1; j <= n-i; j++)
if(h[j] > h[j+1]){
temp = h[j];
h[j] = h[j+1];
h[j+1] = temp;
}
for(i = 1; i < n; i++) cout << h[i] << " " ;
cout << h[n] << endl;
return 0;
}
十、对于冒泡排序，我们还可以做些算法“优化”。
如果一趟排序下来，都没有任何“逆序”数对，即没有发生“交换”操作，
则说明已经排好序了。此时，就可以立刻退出循环。
#### 优化后的冒泡排序：
#include<iostream>
using namespace std;
int main(){
int n,i,j,temp,h[101];
cin >> n;
for(i = 1; i <= n; i++) cin >> h[i];
for(i = 1; i < n; i++){
bool flag = true;
for(j = 1; j <= n-i; j++)
if(h[j] > h[j+1]){
temp = h[j];
h[j] = h[j+1];
h[j+1] = temp;
flag = false;
}
if(flag) break;
}
for(i = 1; i < n; i++) cout << h[i] << " " ;
cout << h[n] << endl;
return 0;
}
十一、插入排序(从小到大):
插入排序的基本思想是：把所有待排序元素分成前后两段，前一段是已经排好序的，后一段是待排序的。
每一趟都是把后一段的第一个数“插入”到前一段的某一个位置，保证前一段仍然是有序的。
开始时，第 1 个数作为前一段肯定是有序的；第一趟，把第 2 个数插入进去，保证前 2个数有序；
第二趟，把第 3 个数插入进去，保证前 3 个数有；……
第 n-1 趟，把第 n 个数插入进去，保证 n 个数都有序。
#### 插入排序的代码(从小到大)：
#include<iostream>
using namespace std;
int main(){
int n,i,j,k,temp,h[101];
cin >> n;
for(i = 1; i <= n; i++) cin >> h[i];
for(i = 2; i <= n; i++){
temp = h[i];
k = 1;
while(h[k] <= temp && k < i) k++;
for(j = i-1; j >= k; j--) h[j+1] = h[j];
h[k] = temp;
}
for(i = 1; i < n; i++) cout << h[i] << " " ;
cout << h[n] << endl;
return 0;
}