目录
1.向量点积计算
https://www.luogu.com.cn/problem/B2091
题目描述
在线性代数、计算几何中，向量点积是一种十分重要的运算。
给定两个 nn 维向量 a=(a1,a2,⋯ ,an) 和 b=(b1,b2,⋯ ,bn)，求点积 a · b=a1b1+a2b2+⋯+anbn。
输入格式
第一行是一个整数 n。1≤n≤1000。
第二行包含 nn 个整数 a1,a2,⋯ ,an。
第三行包含 nn 个整数 b1,b2,⋯ ,bn。
相邻整数之间用单个空格隔开。每个整数的绝对值都不超过 1000。
输出格式
一个整数，即两个向量的点积结果。
输入输出样例
输入 #1
3 1 4 6 2 1 5输出 #1
36
分析
思路:先用两个数组来接收{a1,a2,⋯ ,an}和{b1,b2,⋯ ,bn}(两个循环),再借助一个循环来计算向量点积的结果
思考:有没有时间和空间复杂度都较低的算法?
优化:可以只借助两个循环,第一个循环接收{a1,a2,⋯ ,an},第二个循环读取一个bk就为sum+-=bk,即让读取和计算一起进行
经过计算,可用int类型来存储向量点积的结果
代码
#include <iostream>
using namespace std;
int arr[1010];
int main()
{
int n = 0;
int m = 0;
int sum=0;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> arr[i];
}
for (int i = 0; i < n; i++)
{
cin >> m;
sum += arr[i] * m;
}
cout << sum << endl;
return 0;
}提交结果
2.开关灯
https://www.luogu.com.cn/problem/B2092
题目描述
假设有 N 盏灯（N 为不大于 5000 的正整数），从 1 到 N 按顺序依次编号，初始时全部处于开启状态；第一个人（1 号）将灯全部关闭，第二个人（2 号）将编号为 2 的倍数的灯打开，第三个人（3 号）将编号为 3 的倍数的灯做相反处理（即，将打开的灯关闭，将关闭的灯打开）。依照编号递增顺序，以后的人都和 3 号一样，将凡是自己编号倍数的灯做相反处理。问当第 N 个人操作完之后，有哪些灯是关闭着的？
输入格式
输入为一行，一个整数 N，为灯的数量。
输出格式
输出为一行，按顺序输出关着的灯的编号。编号与编号之间间隔一个空格。
输入输出样例
输入 #1
10输出 #1
1 4 9输入 #2
5输出 #2
1 4
分析
这里推荐用0表示开,1表示关,因为全局变量默认初始化为0
注意数组元素从下标为1处开始,方便处理
#include <iostream>
#include <iomanip>
using namespace std;
int n,a[5010];
int main()
{
//0为开,1为关
cin>>n;
for (int i=1;i<n+1;i++)
{
for (int j=1;j<n+1;j++)
{
if (j%i==0)
a[j]=~a[j];//直接取反比嵌套if判断更快
}
}
for (int k=1;k<n+1;k++)
{
if (a[k])
cout<<k<<" ";
}
return 0;
} 注意:将变量取反的结果赋值给原变量的写法a[j]=~a[j];不是a[j]~=a[j];!!!
写成a[j]=!a[j]也可以
提交结果
3.杨辉三角
题目描述
给出 n(1≤n≤20)，输出杨辉三角的前 n 行。
如果你不知道什么是杨辉三角，可以观察样例找找规律。
输入格式
无
输出格式
无
输入输出样例
输入 #1
6输出 #1
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1
分析
每一行的第1个数字一定是1,每一个结尾的数字也是1
从图上看,是打印二维数组的下三角部分,而且第0列和对角线上的元素全为1
数值特点
每个数是它左上方和右上方的数的和
代码
#include <iostream>
#include <cstring>
using namespace std;
int main()
{
short n;
cin>>n;
int arr[n][n];
//下三角元素全部初始化为1
for (int i = 0; i < n; i++)
{
for (int j = 0; j < i+1; j++)
{
arr[i][j]=1;
}
}
//修改元素值
for (int i = 2; i < n; i++)
{
for (int j = 1; j < i; j++)
{
arr[i][j]=arr[i-1][j-1]+arr[i-1][j];
}
}
//打印下三角
for (int i = 0; i < n; i++)
{
for (int j = 0; j < i+1; j++)
{
cout<<arr[i][j]<<" ";
}
cout<<endl;
}
return 0;
} 提交结果
