- 判断闰年
bool IfLeap(int n)
{
if(n%100==0)
{
if(n%400==0)
return true;
}
if(n%4==0)
return true;
return false;
}
- 判断素数(易错)
bool isPrime(int n)
{
if(n==1) //1不是素数
return false;
int sqr=(int)sqrt(1.0*n);
for(int i=2;i<=sqr;i++)
{
if(n%i==0)
return false;
}
return true;
}
- 获取100以内素数，存于数组prime
#include <iostream>
#include<cstring>
using namespace std;
const int maxn=101;
int prime[maxn],pNum=0;
bool p[maxn];
void Find_Prime()
{
for(int i=2;i<maxn;i++)
{
if(p[i]==false)
{
prime[pNum++]=i;
for(int j=i+i;j<maxn;j+=i)
{
p[j]=true;
}
}
}
}
int main()
{
memset(p,false,sizeof(p));
Find_Prime();
for(int i=0;i<pNum;i++)
{
printf("%d ",prime[i]);
//2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
}
return 0;
}
- 将n进行质因数分解，结果存于fac数组(易错)
/*质因数一定是素数*/
//详见算法笔记P168
#include <iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100010;
int prime[maxn],pNum=0;
bool p[maxn];
void Find_Prime()
{
for(int i=2; i<maxn; i++)
{
if(p[i]==false)
{
prime[pNum++]=i;
for(int j=i+i; j<maxn; j+=i)
{
p[j]=true;
}
}
}
}
struct factor
{
int x;
int cnt;
} fac[10];
int fNum=0;
void getFac(int n)
{
int sqr=(int)sqrt(1.0*n);
for(int i=0; i<pNum&&prime[i]<=sqr; i++)//在素数范围内查找质因数
{
if(n%prime[i]==0)
{
fac[fNum].x=prime[i];
fac[fNum].cnt=0;
while(n%prime[i]==0)
{
fac[fNum].cnt++;
n/=prime[i];
}
fNum++;
}
if(n==1)
return;
}
if(n!=1)
{
fac[fNum].x=n;
fac[fNum].cnt=1;
fNum++;
}
}
int main()
{
memset(p,false,sizeof(p));
Find_Prime();
getFac(180);
cout<<"对于180"<<endl;
for(int i=0; i<fNum;i++)
{
cout<<"质因子"<<fac[i].x<<"个数为"<<fac[i].cnt<<endl;
}
return 0;
}
/*
对于180
质因子2个数为2
质因子3个数为2
质因子5个数为1
*/
- 找一个数的约数，存于divs数组
#include<iostream>
#include<cstring>
using namespace std;
int divs[100],dnum=0;
void getDiv(int n)
{
memset(divs,0,100);
for(int i=1; i<=n/2; i++)//是n/2,不是n
{
if(n%i==0)
{
divs[dnum]=i;//注意没有n/=i这句
dnum++;
}
}
}
int main()
{
//这两句用于重置dnum和divs，常用于while(cin>>n){}内
dnum=0;
memset(divs,0,100);
getDiv(220);
cout<<220<<"的约数为";
for(int j=0; j<dnum; j++)
{
cout<<divs[j]<<" ";
}
return 0;
}
//220的约数为1 2 4 5 10 11 20 22 44 55 110
//详见算法笔记P185
#include<iostream>
#include<cstring>
using namespace std;
int C(int n,int m)
{
int ans=1;//注意
for(int i=1;i<=m;i++)
{
ans*=(n-m+i)/i;
}
return ans;
}
int main()
{
cout<<C(3,2)<<endl;//3
return 0;
}
- 统计单词个数-输入数据有多行，遇到#终止(易错)
#include<iostream>
#include<vector>
#include<string>
using namespace std;
int main()
{
string str;
vector<string> words;
while(getline(cin,str))
{
if(str[0]=='#')
return 0;
int count=0;
bool new_w=false,still=false;
for(int i=0; i<str.length(); i++)
{
if(str[i]!=' '&&new_w==false&&still==false)
{
count++;
new_w=true;////出现新单词
still=true;//目前在单词中
}
else
{
if(str[i]!=' ')
still=true;
else
still=false;
new_w=false;
}
}
cout<<count<<endl;
}
return 0;
}
/*输入: you are my friend */
/*输出:4
- 最大公约数(易错)
//辗转相除法
int gcd(int n,int m)
{
return gcd(m,n%m);
}
- 最小公倍数(易错)
int lcm(int n,int m)
{
int res=gcd(n,m);
return m*n/res;
}
- 将十进制数n转换为Q进制,结果存于数组z(易错)
#include<iostream>
#include<cstring>
using namespace std;
int z[100],num;
void changRadix(int n,int Q)
{
num=0;
memset(z,0,100);
while(n!=0)
{
z[num++]=n%Q;
n/=Q;
}
}
int main()
{
int n,Q;
while(cin>>n>>Q)
{
if(n<0)
{
cout<<"-";
n=-n;
}
changRadix(n,Q);
for(int i=num-1; i>=0; i--)
{
if(z[i]>=10)
cout<<char(z[i]-10+'A');
else
cout<<z[i];
}
cout<<endl;
}
return 0;
}
/*
输入:7 2
输出:111
输入:23 12
输出:1B
输入:-4 3
输出:-11
*/
- 给定⼀个数值和⼀个进制，将它转化为10进制(易错)
#include <iostream>
#include<cctype>
#include<cstring>
#include<algorithm>
#include<math.h>
using namespace std;
int z[5]= {2,2,1,2,1};
int num=5;
//将z[]所存radix进制数转为10进制数(比如3进制数22121,则z[5]={2,2,1,2,1},convert(3)返回232)
/*注意用changRadix得到的z数组是逆序的,比如changRadix(23,2),得到的是2进制数是10111,但z[5]={1,1,1,0,1}
如果要将10111转换为十进制数,要先将z数组逆置回来
*/
int convert(int radix)
{
int ans=0;
for(int i=0; i<num; i++)
{
ans=ans*radix+z[i];
}
return ans;
}
int main()
{
cout<<convert(3)<<endl;
return 0;
}
- 输出从数组num中从A到B的数；
每 10 个数字占 1 行，其间以空格分隔；
但行末不得有多余空格。(易错)
/*
11 13 17 19 23 29 31 37 41 43
47 53 59 61 67 71 73 79 83 89
97 101 103
*/
for(int i=A-1;i<B;i++)
{
count++;
count%=10;
if(count!=0)
{
if(count!=1)
cout<<" ";
cout<<num[i];
}
else
cout<<" "<<num[i]<<endl;
}
- 错排(2048,2049)
错排公式：Dn=(n-1)(Dn-1+Dn-2),其中D0=0,D1=0,D2=1,D3=2,
错排概率：Dn/n!
//2048
#include<iostream>
using namespace std;
int main()
{
long long a[51];
a[0]=0;a[1]=0;a[2]=1;a[3]=2;
for(int i=4; i<=50; i++)
{
a[i]=(i-1)*(a[i-1]+a[i-2]);
}
int T;
cin>>T;
for(int j=0;j<T;j++)
{
int n;
cin>>n;
long long m=1;
for(long long i=2;i<=n;i++)//计算n!
{
m*=i;
}
printf("%.2f",a[n]*1.00/m*100);
printf("%\n");
}
return 0;
}
- 输入输出十六进制数
#include<iostream>
using namespace std;
int main()
{
long long a,b,sum;
while(scanf("%I64X%I64X",&a,&b))
{
sum=a+b;
if(sum>=0)
printf("%I64X\n",sum);
else
printf("-%I64X\n",-sum);
}
return 0;
}
/*
输入:
+A -A
1A -9
-1A -12
1A -AA
输出:
0
11
-2C
-90
*/
- 四舍五入为整数
#include<iostream>
#include<math.h>
using namespace std;
int main()
{
int res=round(4.8);
cout<<res<<endl;
return 0;//5
}
- 向上/下取整
#include<iostream>
#include<math.h>
using namespace std;
int main()
{
int res1=floor(5.6);
printf("%d ",res1);
int res2=ceil(5.6);
printf("%d\n",res2);
return 0;
}
/*输出:5 6*/
str[i]类型判断
#include<cctype>
if(isdigit(str[i]))//str[i]为数字
if(isalpha(str[i]))//str[i]为字母(不区分大小写)
if(islower(str[i]))//str[i]为小写字母
if(isupper(str[i]))//str[i]为大写字母
- 字符串，数组逆置
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main()
{
string str="abcde";
reverse(str.begin(), str.end());
int arr[4]={2,3,1,4};
reverse(arr, arr+4);
cout<<str<<endl;//edcba
for(int i=0;i<4;i++)
{
cout<<arr[i]<<" ";////4132
}
return 0;
}
字符串,查找子串
#include<iostream>
#include<string>
#include<stdio.h>
#include<algorithm>
using namespace std;
int main()
{
string str="abcdefgh";
cout<<str.find("bc")<<endl;//1
cout<<str.find("poi")<<endl;//4294967295,大于str.size()的一个值
return 0;
}
- 大整数相加(易错)
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
string add(string s1, string s2) {
string s = s1;//这一句是为了让s拥有和s1相同的长度
int carry = 0;//carry表示进位
for (int i = s1.size() - 1; i >= 0; i--) {
s[i] = (s1[i] - '0' + s2[i] - '0' + carry) % 10 + '0';
carry = (s1[i] - '0' + s2[i] - '0' + carry) / 10;
}
if (carry > 0)//如果最高位相加有进位
s = "1" + s;
return s;
}
int main()
{
string A;
cin>>A;
string B=A;
reverse(A.begin(),A.end());
cout<<add(A,B)<<endl;
return 0;
}
/*输入:9865298697593927335572439430173
输出13575648040349264629530408355862*/
- vector复制
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> v1,v2;
int main()
{
for(int i=9; i>0; i--)
{
v1.push_back(i);
}
v2=v1;
for(int i=0;i<v2.size();i++)
{
cout<<v2[i]<<" ";//9 8 7 6 5 4 3 2 1
}
return 0;
}
- 一维数组复制
#include<iostream>
#include<cstring>
using namespace std;
int main()
{
int A[3];
int B[3];
for(int i=0; i<3; i++)
{
int num;
cin>>num;
A[i]=num;
}
memcpy(B,A,sizeof(A));
for(int i=0; i<3; i++)
{
cout<<B[i]<<" ";
}
return 0;
}
/*输入:1 2 3
输出: 1 2 3*/
- 二维数组复制
#include<iostream>
#include<cstring>
using namespace std;
int main()
{
int A[3][3];
int B[3][3];
for(int i=0;i<3;i++)
{
for(int j=0;j<3;j++)
{
int num;
cin>>num;
A[i][j]=num;
}
}
memcpy(B,A,sizeof(A));
for(int i=0;i<3;i++)
{
for(int j=0;j<3;j++)
{
cout<<" "<<B[i][j];
}
cout<<endl;
}
return 0;
}
/*输入:1 2 3 4 5 6 7 8 9
输出: 1 2 3
4 5 6
7 8 9*/
- 插入char数组
#include<iostream>
#include<cstring>
using namespace std;
int n,m,mat[101][101];
int main()
{
cin>>n>>m;
for(int i=0; i<n; i++)
{
char c=getchar();
for(int j=0; j<m; j++)
{
cin>>c;
if(c=='*')
mat[i][j]=0;
else
mat[i][j]=1;
}
}
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
cout<<mat[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
/*
输入:
5 5
.....
.*.*.
.*S*.
.***.
...T*
输出:
1 1 1 1 1
1 0 1 0 1
1 0 1 0 1
1 0 0 0 1
1 1 1 1 0
*/
- 如何生成一个随机三位数
int randnum=rand()%900+100;
- 判断矩阵旋转角度
/*顺时针90:(i,j)与(j,n-1-i)
顺时针180:(i,j)与(n-1-i,n-1-j)
顺时针270:(i,j)与(n-j-1,i)
*/
#include <iostream>
#include <string>
using namespace std;
const int MAXV=101;
int a[MAXV][MAXV],b[MAXV][MAXV];
int main()
{
int n;
cin>>n;
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
cin>>a[i][j];
}
}
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
cin>>b[i][j];
}
}
bool flag[4]= {true,true,true,true};
int angle[4]= {0,90,180,270};
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
if(a[i][j]!=b[i][j])
flag[0]=false;
if(a[i][j]!=b[n-1-i][n-1-j])
flag[1]=false;
if(a[i][j]!=b[i][j])
flag[2]=false;
if(a[i][j]!=b[n-j-1][i])
flag[3]=false;
}
}
if(!flag[0]&&!flag[1]&&!flag[2]&&!flag[3])
cout<<-1<<endl;
else
{
for(int i=0; i<4; i++)
{
if(flag[i])
cout<<angle[i]<<endl;
}
}
return 0;
}
