|
（注：本文章有部分代码及资料来源于其他作者，本文章只用作笔记整理，无商业用途，谢谢）
1.进制转换
%d?有符号10进制整数
%i?有符号10进制整数
%o?无符号8进制整数
%u?无符号10进制整数
%x?无符号的16进制数字，并以小写abcdef表示
%X?无符号的16进制数字，并以大写ABCDEF表示
%F/f?浮点数
%E/e?用科学表示格式的浮点数
%g?使用%f和%e表示中的总的位数表示最短的来表示浮点数?G?同g格式，但表示为指数
%c?单个字符
%s?字符串
?
2.大小写字母转换
?大写字母ascii码+32
3.%9.2f表示输出场宽为9的浮点数，其中小数位为2，整数位为6
对浮点数，若整数部分位数超过了说明的整数位宽度，将按实际整数位输出；若小数部分位数超过了说明的小数位宽度，则按说明的宽度以四舍五入输出。
4.利用Π先定义
#define PI 3.1415926
5.求三角函数
#include<math.h>//头文件
//角度转弧度 π/180×角度；弧度变角度 180/π×弧度
cos(弧度）
6.switch的使用
#include <stdio.h>
int main(){
double x,y,z;
char op;
scanf("%lf%c%lf",&x,&op,&y);
switch(op){
case '+':
z = x+y;
break;
case '-':
z = x-y;
break;
case '*':
z = x*y;
break;
case '/':
z = x/y;
break;
}
printf("%f%c%f=%f\n",x,op,y,z);
return 0;
}
7.求最大公约数
#include<stdio.h>
int G(int A,int B)
{
if(B==0)
return A;
else
return(B,A%B);
}//函数形式
int main()
{
int a,b,t；
while (b!=0)
{
t=b;
b=a%b;
a=t;
}
printf("%d",&a);//循环形式
}
8.求最小公倍数
? 实际上就是两个数的乘积再除以他们的最大公约数
? 例如求a，b的最小公倍数=a*b/a与b的最大公约数
9.求数比较小的阶乘的时候可以用递归实现
#include <stdio.h>
#define MOD 10007
int f(int n){
if(n==0) return 1;
return f(n-1)*(n%MOD)%MOD;
}
int main(){
int n;
scanf("%d",&n);
printf("%d\n",f(n));
return 0;
}
10.素数
? ?常用埃氏筛
#include<stdio.h>
#define N 100000;
int B[100000]={0};
int main()
{
int i,j;
B[0]=0;
B[1]=0;
for(i=2;i<=N;i++)
{
if(!B[i])
{
for(j=i*i;j<=N;j+=i)
{
B[j]=1;
}
}
}//1是质数，0是非质数
}
11.字母塔
采用循环
#include <stdio.h>
int main(){
char c,t;
int i,j,n;
while((c=getchar())!=EOF){
getchar(); //read return key
n = c-'A'+1;
for(i=0;i<n;i++){
for(j=0;j<n-i-1;j++) putchar(' ');
for(j=0,t='A';j<i+1;j++,t++) putchar(t);
for(j=0,t-=2;j<i;j++,t--) putchar(t);
putchar('\n');
}
}
return 0;
}
13.质因数分解
#include<stdio.h>
#include<math.h>
int main()
{
int n,m,i,j,sum;
while(scanf("%d",&n)!=EOF)
{
for(i=2;i<=sqrt(n);i++)
{
sum=0;
m=n;
while(n%i==0)
{
n/=i;
sum++;
}
if(m%i==0)
{
printf("%d",i);
if(sum>1) printf("^%d",sum);
if(i<=n) printf("*");
}
}
if(n>1) printf("%d",n);
printf("\n");
}
return 0;
}
14.组合数
用杨辉三角
#include<stdio.h>
int B[101][101];
int main()
{
int i,j;
B[0][0]=1;
B[1][1]=1;
B[1][0]=1;
for(i=2;i<=100;i++)
{
B[i][0]=1;
B[i][i]=1;
for(j=1;j<i;j++)
{
B[i][j]=B[i-1][j-1]+B[i-1][j];
}
}
}
15.判断闰年
#include <stdio.h>
int main(){
int y;
scanf("%d",&y);
if(y%400==0||y%100!=0&&y%4==0) puts("Yes");
else puts("No");
return 0;
}
16.几个比较常用的排序
（1）qsort排序
?
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int less(const void *a,const void *b){
int *pa,*pb;
pa = (int *)a;
pb = (int *)b;
return *pa - *pb;
}
int greater(const void *a,const void *b){
int *pa,*pb;
pa = (int *)a;
pb = (int *)b;
return *pb - *pa;
}
void prt(int *a,int n){
int i,j;
for(i=0;i<n;i++) printf("%d ",a[i]);
printf("\n");
}
int main(){
int a[10]={3,7,2,5,3,8,1,7,4,3};
prt(a,10);
qsort(a,10,sizeof(int),less);
prt(a,10);
qsort(a,10,sizeof(int),greater);
prt(a,10);
return 0;
}
对double排序
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#define EPS 1e-6
int less(const void *a,const void *b){
double *pa,*pb;
pa = (double *)a;
pb = (double *)b;
if(fabs(*pa-*pb) < EPS) return 0;
if(*pa-*pb >=EPS) return 1;
return -1;
}
int greater(const void *a,const void *b){
double *pa,*pb;
pa = (double *)a;
pb = (double *)b;
if(fabs(*pa-*pb) < EPS) return 0;
if(*pa-*pb >=EPS) return -1;
return 1;
}
void prt(double *a,int n){
int i;
for(i=0;i<n;i++) printf("%.2f ",a[i]);
printf("\n");
}
int main(){
double a[10]={1.3,1.7,1.2,1.5,2.3,1.8,1.1,2.7,1.4,3.3};
prt(a,10);
qsort(a,10,sizeof(double),less);
prt(a,10);
qsort(a,10,sizeof(double),greater);
prt(a,10);
return 0;
}
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int less(const void *a,const void *b){
char *pa,*pb;
pa = (char *)a;
pb = (char *)b;
return strcmp(pa,pb);
}
int greater(const void *a,const void *b){
char *pa,*pb;
pa = (char *)a;
pb = (char *)b;
return strcmp(pb,pa);
}
void prt(char (*a)[20],int n){
int i;
for(i=0;i<n;i++) puts(a[i]);
printf("\n");
}
int main(){
char a[10][20]={"Hello","Hell","Her","He","His","Hers","Helm","Heat","Heal","Heap"};
prt(a,10);
qsort(a,10,sizeof(a[0]),less);
prt(a,10);
qsort(a,10,sizeof(a[0]),greater);
prt(a,10);
return 0;
}
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define N 4
int less(const void *a,const void *b){
int *pa,*pb,i;
pa = (int *)a;
pb = (int *)b;
for(i=0;i<N&&*pa==*pb;i++,pa++,pb++);
if(i==N) return 0;
else return *pa - *pb;
}
int greater(const void *a,const void *b){
int *pa,*pb,i;
pa = (int *)a;
pb = (int *)b;
for(i=0;i<N&&*pa==*pb;i++,pa++,pb++);
if(i==N) return 0;
else return *pb - *pa;
}
void prt(int (*a)[N],int n){
int i,j;
for(i=0;i<n;i++){
for(j=0;j<N;j++) printf("%d ",a[i][j]);
printf("\n");
}
printf("\n");
}
int main(){
int a[5][N]={{1,7,3,4},{1,5,4,3},{2,5,3,7},{2,5,3,8},{1,7,4,3}};
prt(a,5);
qsort(a,5,sizeof(a[0]),less);
prt(a,5);
qsort(a,5,sizeof(a[0]),greater);
prt(a,5);
return 0;
}
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
struct node{
int x,y;
};
int less(const void *a,const void *b){
struct node *pa,*pb;
pa = (struct node*)a;
pb = (struct node*)b;
if(pa->x == pb->x) return pa->y - pb->y;
else return pa->x - pb->x;
}
int greater(const void *a,const void *b){
struct node *pa,*pb;
pa = (struct node*)a;
pb = (struct node*)b;
if(pa->x == pb->x) return pb->y - pa->y;
else return pb->x - pa->x;
}
void prt(struct node *p,int n){
int i;
for(i=0;i<n;i++) printf("%d %d\n",p[i].x,p[i].y);
printf("\n");
}
int main(){
struct node a[5]={{1,2},{2,3},{1,3},{2,5},{1,7}};
prt(a,5);
qsort(a,5,sizeof(struct node),less);
prt(a,5);
qsort(a,5,sizeof(struct node),greater);
prt(a,5);
return 0;
}
2）冒泡排序【比较注重过程】
#include <stdio.h>
#define N 100
int main(){
int a[N],n,i,j,k,t;
scanf("%d",&n);
for(i=0;i<n;i++) scanf("%d",a+i);
for(i=0;i<n-1;i++){
for(j=i;j<n-1;j++) if(a[j]<a[j+1]){
t = a[j];
a[j] = a[j+1];
a[j+1] = t;
}
t = a[i];
a[i] = a[j];
a[j] = t;
}
for(i=0;i<n-1;i++) printf("%d ",a[i]);
printf("%d\n",a[i]);
return 0;
}
17.两个矩形相交面积
#include <stdio.h>
#include <math.h>
int main() {
int k;
double x[5], y[5];
double x1, x2, y1, y2, s1, s2, x3, y3;
scanf("%d", &k);
while (k--) {
for (int i = 0; i < 4; i++)
scanf("%lf%lf", x + i, y + i);
x1 = (x[1] + x[0]) / 2;
x2 = (x[3] + x[2]) / 2;
y1 = (y[1] + y[0]) / 2;
y2 = (y[3] + y[2]) / 2;
s1 = abs(x[1] - x[0]) + abs(x[3] - x[2]);
s2 = abs(y[1] - y[0]) + abs(y[3] - y[2]);
if (abs(x1 - x2) < s1 / 2 && abs(y1 - y2) < s2 / 2)
printf("Yes\n");
else
printf("No\n");
}
return 0;
}
18.常用函数
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int putchar(int ch);
/*putchar输出一个char*/
int getchar(void);
/*getchar是从标准输入设备读取一个char。*/
char *gets(char *s);
/*功能：从标准输入读入字符，并保存到s指定的内存空间，直到出现换行符或读到文件结尾为止。
参数：
s：字符串首地址
返回值：
成功：读入的字符串
失败：NULL
*/
int puts(const char *string);
/*功能：标准设备输出s字符串，在输出完成后自动输出一个'\n'。
参数：
s：字符串首地址
返回值：
成功：非负数
失败：-1
*/
size_t strlen(const char *s);
/*功能：计算指定指定字符串s的长度，不包含字符串结束符‘\0’
参数：
s：字符串首地址
返回值：字符串s的长度，size_t为unsigned int类型
*/
/*char *strcpy(char *dest, const char *src);
功能：把src所指向的字符串复制到dest所指向的空间中，'\0'也会拷贝过去
参数：
dest：目的字符串首地址
src：源字符首地址
返回值：
成功：返回dest字符串的首地址
失败：NULL
注意：此函数不是一个安全的函数，因为没有指定copy的大小，可能会造成越界。推荐使用strcpy_s(char *dest,size_t size,const char *src)
*/
int strcmp(const char *s1, const char *s2);
/*功能：比较 s1 和 s2 的大小
参数：
s1：字符串1首地址
s2：字符串2首地址
返回值：
相等：0
大于：>0
小于：<0
*/
char *strcat(char *dest, const char *src);
/*功能：将src字符串连接到dest的尾部，‘\0’也会追加过去
参数：
dest：目的字符串首地址
src：源字符首地址
返回值：
成功：返回dest字符串的首地址
失败：NULL
*/
char *strstr(const char *haystack, const char *needle);
/*功能：在字符串haystack中查找字符串needle出现的位置
参数：
haystack：源字符串首地址
needle：匹配字符串首地址
返回值：
成功：返回第一次出现的needle地址
*/
char *strtok(char *str, const char *delim);
/*功能：来将字符串分割成一个个片段。当strtok()在参数s的字符串中发现参数delim中包含的分割字符时, 则会将该字符改为\0 字符，当连续出现多个时只替换第一个为\0。
参数：
str：指向欲分割的字符串
delim：为分割字符串中包含的所有字符
返回值：
成功：分割后字符串首地址
失败：NULL
注意：在第一次调用时：strtok()必需给予参数s字符串
往后的调用则将参数s设置成NULL，每次调用成功则返回指向被分割出片段的指针
void *memset(void *s, int c, size_t n);
/*功能：将s的内存区域的前n个字节以参数c填入
参数：
s：需要操作内存s的首地址
c：填充的字符，c虽然参数为int，但必须是unsigned char , 范围为0~255
n：指定需要设置的大小
返回值：s的首地址
*/
void *memcpy(void *dest, const void *src, size_t n);
/*功能：拷贝src所指的内存内容的前n个字节到dest所值的内存地址上。
参数：
dest：目的内存首地址
src：源内存首地址，注意：dest和src所指的内存空间不可重叠
n：需要拷贝的字节数
返回值：dest的首地址
*/
————————————————
版权声明：本文为CSDN博主「光明益生菌」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_34192115/article/details/80320447
————————————————
版权声明：本文为CSDN博主「光明益生菌」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_34192115/article/details/80320447
19.Fibonacci数
#include <stdio.h>
//fib(48) overflow int
#define N 48
int f[N]={1,1};
int fib(int n){
if(f[n]) return f[n];
f[n] = fib(n-1)+fib(n-2);
return f[n];
}
int main(){
int n;
scanf("%d",&n);
printf("%d",fib(n));
return 0;
}
动态规划（重要）
（1）备忘录法（自上而下）
public static int Fibonacci(int n)
{
if(n<=0)
return n;
int []Memo=new int[n+1];
for(int i=0;i<=n;i++)
Memo[i]=-1;
return fib(n, Memo);
}
public static int fib(int n,int []Memo)
{
if(Memo[n]!=-1)
return Memo[n];
//如果已经求出了fib（n）的值直接返回，否则将求出的值保存在Memo备忘录中。
if(n<=2)
Memo[n]=1;
else Memo[n]=fib( n-1,Memo)+fib(n-2,Memo);
return Memo[n];
}
（2）自底而上
public static int fib(int n)
{
if(n<=0)
return n;
int []Memo=new int[n+1];
Memo[0]=0;
Memo[1]=1;
for(int i=2;i<=n;i++)
{
Memo[i]=Memo[i-1]+Memo[i-2];
}
return Memo[n];
}
20.前缀和（经常会用到）
const int maxn = 1e5+10;
int a[maxn],pre[maxn];
for(int i=1;i<=n;i++){
pre[i]=pre[i-1]+a[i];//从1到i的累加和，等于从1到(i-1)的累加和，再加上a[i]的值。
}
21.dfs
例子
//问题：有一个100*100的迷宫，告诉你起点终点，以及障碍物的位置，问你至少需要几步从起点走到终点。
这里我们用dfs解决（也可以用bfs解决，bfs是广度优先搜索）。
void dfs(int step,int x,int y){
if((x,y)是终点，那么step就是最小的答案);
vis[x][y]=1;
/**
这里写往4个方向搜索的代码，如果那个点以前没有访问过，那么就往下搜
if(......)dfs(step+1,x+1,y);如果这个点不是障碍物，并且以前没有到达过，那么我们就往下走。
if(......)dfs(step+1,x-1,y);
if(......)dfs(step+1,x,y+1);
if(......)dfs(step+1,x,y-1);
**/
}
22.bfs
struct node{
int x,y,step;
node(int x,int y,int step):x(x),y(y),step(step){}
};
void bfs(){
int vis[100][100]={0};
queue<int> q;
q.push(node(起点坐标));
while(!q.empty()){
node now = q.front();q.pop();
vis[now.x][now.y]=1;
if(now这个点的坐标是终点坐标){ 答案就是now.step; }
if(......)q.push();如果这个点不是障碍物，并且以前没有到达过，那么我们就压入队列，等待访问。
if(......)q.push();
if(......)q.push();
if(......)q.push();
}
如果队列访问空了都没有找到答案，说明无解。
}
|