# 基础 计算机的最小存储单位 bit 比特 位 比特位 计算机存储数据的基本单位 Byte 字节 1bit 存放:0或1 1Byte = 8bit 1B 8格子的数据 char 1字节 -128 - 127 ascii 0-127 short 2字节 -32768 - 32767 int 4字节 -2147483647 - 2147483648 long long 8字节 float 4字节 double 8字节 字节数由电脑的系统而定,默认是上面的数据 sizeof(数据) 获取该数据占用的字节数 int a; cout<<sizeof(a); 输入输出: 1、基本 cin cont 2、格式 scanf() printf() %d int %lld long long %lf double %f float %s 字符数组 string s; printf("%s",s.c_str());//将字符串转换成字符数组再输出 cin cout 通常使用方便 scanf 与 printf 执行时间较少,可以节省时间 scanf可以控制输入格式 scanf("%d:%d:%d",&a,&b,&c); printf可以控制输出格式 % [标记] [长度] [精度] 类型 标记: 空格 默认的 + 输出正数时,带正号 '+' - 左对齐 0 默认右对齐,左边空余位置补零 长度: 标记当前数据占用的最小长度 printf("%8d",8);// 8 printf("%4d",12345678);//12345678 精度: .num 代表保留小数点后几位,四舍五入 scanf 一定不要忘记 & 3、专项 字符专用 char c; c=getchar();//输入 putchar(c);//输出 括号里的内容(以字符形式) putchar(97);//a 字符数组专用 char c[1000]; cin>>c;//输入整行,以空格或换行作为分隔 cout<<c; cin.getline(c,1000);//可以有空格的整行输入 字符串专用 string s; cin>>s;//无空格输入 cout<<s; getline(cin,s);//有空格输入 数组 int a[5]; cout<<a<<" "<<&a[0]<<" "<<&a[1]; & 引用符号 取地址符 设数据存放范围:1~n 冒泡 : 从头至尾依次比较相邻的两个元素 for(int i=1;i<n;i++){ for(int j=1;j<=i;j++){ if(a[j]>a[j+1]) swap(a[j],a[j+1]); } } 选择 : 从未排序的数组内,选择最小,与开头交换位置 for(int i=1;i<n;i++){ int k=i;//假设目前的开头就是最小的 for(int j=i;j<=n;j++){ if(a[j]<a[k]) k=j; } swap(a[i],a[k]); } 插入 : 从未排序数组中依次获取数据,放入有序数组中(默认第一个数字有序) 放入过程:从后往前依次比较 for(int i=2;i<=n;i++){ int num=a[i]; for(int j=i-1;j>=1;j--){ if(num<a[j]){ a[j+1]=a[j]; if(j==1) a[j]=num; } else{ a[j+1]=num; break; } } } # 素数筛 如果这个数字是素数,那么他的倍数一定不是素数 1、假设求的范围内,全都是素数 bool isp[10050]={1,1};//false代表是质数 2、从2开始,到sqrt(n)开始遍历 for(int i=2;i<=sqrt(n);i++){ if(!isp[i]){ for(int j=i*i;j<10050;j+=i){ if(!isp[j]) isp[j]=true; } } } # 自定义函数 1、函数格式 函数类型 函数名(参数){ 主体 返回值(类型与函数类型一致) } 2、参数:可以有多个,可以有多种 引用传递(地址) 值传递 手写swap void swap(int &a,int &b){ int t=a; a=b; b=t; } 3、作用域 全局变量 主函数外 局部变量 各个函数内
先后顺序,先创建全局变量,再创建自定函数 4、递归函数 斐波那契数列 做递归问题,方案一,推导 1、列数据(8~15) n=1 f=1 n=2 f=1 n=3 f=2 ... 2、规律 f(i)=f(i-1)+f(i-2) 3、特殊情况 n=1 n=2 4、写代码 int f(int n){ if(n==1||n==2) return 1; return f(n-1)+f(n-2); } 做递归问题,方案二,回看 爬楼梯:一共有n级楼梯,每次可以爬1级或2级
f(n) 最后一步 爬1级 f(n-1)种 爬2级 f(n-2)种 f(n)=f(n-1)+f(n-2) 找特殊条件 特殊条件,控制递归结束用 汉诺塔 首要目标是把第n号挪到右边 1、把n上面的清空,n-1挪到中间 2、n挪到右边 3、把n-1挪到右边 特殊情况:当n上面没有东西的时候 void f(int n,char a,char b,char c){ if(n==1) printf("把%d号盘子从%c挪到%c上去\n",n,a,c); else { f(n-1, a, c, b); printf("把%d号盘子从%c挪到%c上去\n",n,a,c); f(n-1, b, a, c); } } int main(){ f(3,'A','B','C'); } 全排列 输入 "abc" 输出 abc acb bac bca cab cba 把每个字符作为开头,然后排列剩下的 for(int i=0;i<s.size();i++){ swap(s[0],s[i]); f(0+1~size) } string s; void f(int st,int en){ if(st==en){ cout<<s<<endl; return ; } for(int i=st;i<=en;i++){ swap(s[i],s[st]); f(st+1,en); swap(s[i],s[st]);//恢复数据 } } 5、递归优化(记忆化) 已经计算出的数据,就直接返回,不进行递归, 没计算出的数据,先计算,再存放返回; int a[100]={0,1,1}; int f(int n){ if(a[n]!=0) return a[n]; if(n==1||n==2) return 1; a[n]=f(n-1)+f(n-2); return a[n]; } |