|
前6章题要刷完，课下完成3级题 递归函数、递归算法 斐波那契数列，正向推导 爬楼梯： 一共有n级楼梯，每次爬楼1级或2级 问：输入n，输出一共有多少种爬法 5 8:11111 1112 1121 1211 2111 122 212 221 逆向思维 如果n级楼梯，f(n)种爬法 最后一步：1级，f(n-1) 最后一步：2级，f(n-2) f(n)=f(n-1)+f(n-2) 汉诺塔： 输入n，输出n层盘子的最优解决方案 逆向思维： 如果要挪走n号盘子，先得把n-1号盘子挪开 void f(int n,char a,char b,char c){ //将n号盘子从a挪到b上 if(n==1) cout<<n<<a<<b; else{ f(n-1,a,c,b); cout<<n<<a<<b; f(n-1,c,b,a); } } f(3,'A','B','C'); 全排列： 输入一个字符串，将这个字符串的所有排列情况输出 ABC ABC ACB BAC BCA CAB CBA 逆向思维： 如果排列n个字母，将n个字母依次当作开头，排列剩下的部分 void f(string str,int s,int e){ if(s==e){ cout<<str<<endl; } else{ for(int i=s;i<=e;i++){ swap(str[i],str[s]); f(str,s+1,e); } } } f("abc",0,2); 递归函数在调用运行后，会因为自身的运行逻辑占用大量栈内存，导致内存溢出（出问题） 所以递归函数适用于数据量较小的情况 在执行递归函数时，因为涉及到大量的重复计算，因此，递归常与记忆化联用 //普通递归斐波那契 int f(int n){ if(n<2) return 1; return f(n-1)+f(n-2); } //记忆化递归斐波那契 int feb[1000]={1,1}; int f(int n){ if(feb[n]) return feb[n]; feb[n]=f(n-1)+f(n-2); return feb[n]; } 递归函数优先，如果有额外时间，做递归算法。 全排列函数： is_permutation();//判断一个序列是否是另一个序列的全排列子项 abc cab 是 abc caa 不是 next_permutation(); 把当前的序列，推导出下一组序列 abc -> acb -> bac -> bca prev_permutation(); 把当前的序列，推导出上一组序列 //函数求全排列 #include <algorithm> string s="dbca"; sort(s.begin(),s.end()); while(next_permutation(s.begin(),s.end())){ cout<<s; } 结构体 struct node{ string name; int a; } a[100],b,c,d; struct node{ string name; int a; int add(){ a*=2; } void say(int a){ while(a--) cout<<"my name is"<<name; } }; node a[100],b,c,d; b.name="5"; b.a=8; b.add(); cout<<b.a;//16 b.say(3);//输出3次 结构体：一种自定义的数据类型，通常不能直接进行输入输出， 需要通过 对象.成员变量 或 对象.成员函数 来使用。 struct node a;//struct 可以省略 node k[100]; k[i].name; 构造函数：与类名相同，没有类型，创建数据时自动调用 struct student{ string name; int age; int rank; //构造函数 student(string k,int a,int b){ name=k; age=a; rank=b; } student(string k){ name=k; age=0; rank=0; } }; student a={"sdg",1,2};//按照顺序一一对应 student b=new student("hh",5,2); //new 创建一个新空间，存放student数据，并传入"hh",5,2赋值给对应的成员变量 student c=new student("oo"); //string 的构造函数 string a; string a(b); string a(3,'6'); 结构体排序 输入n，输入n名同学的信息，按照成绩的分数从高到低排序，输出他们的名字 struct student{ string name; int sc; } s[1000]; bool cmp(int a,int b){ //参数是比较的主体 return a>b;//返回值：什么情况下，第一个参数可以排在第二个参数的前面 } bool cmp2(student a,student b){ return a.sc>b.sc; } int main(){ int n; cin>>n; for(int i=0;i<n;i++){ cin>>s[i].name>>s[i].sc; } //sort(地址开头,地址结尾+1,排序规则);//不填排序规则，默认从小到大 sort(s,s+n,cmp2); for(int i=0;i<n;i++) cout<<s[i].name<<" "; int a[5]={4,2,5,1,7}; sort(a,a+5);//12457 sort(a,a+5,cmp);//75421 int b[10]={1,2,3,4,5,6,7,8,9,0}; sort(b+3,b+7,cmp);//1237654890 } 学生信息：年，月，日 按照学生的年龄从高到低排序 bool cmp(student a,student b){ if(a.y!=b.y) return a.y<b.y; if(a.m!=b.m) return a.m<b.m; if(a.d!=b.d) return a.d<b.d; return a.name<b.name; } 联合体 union 语法规则与结构体相同，内存构造完全不同 union内部的成员变量使用的是同一个空间 union stu{ string name; int age; int sc; } s; //此时只有一个空间 cin>>s.name;//"hha" cin>>s.age;//5 此时5会占用空间 覆盖字符串的部分空间 cout<<s.name;//不一定输出什么 cin>>s.sc;//8 cout<<s.age;//不一定是什么 多个人穿一条裤子 联合体的空间默认大小为最大的成员变量大小 指针 定义一个指针 用* 解析一个指针 用& 指针指的是一个变量，用于存放另一个变量的地址（内存位置）； 存放一个整数型的地址 int a; int *p=&a; int *q; q=&a; cout<<*q;//输出地址对应的值 int *h=nullptr;//定义空指针 int *g=NULL;//空指针 int *c;//没赋值的指针：野指针，可能会导致数据错误 定义指针时，指针的类型，需要与变量的类型一致 char c; char *p=&c; bool b; bool *o=&b; 指针是指向地址，指针可以通过+ -来获取上一个或下一个地址的值 int a=5; int *p=&a;//此时p指向a的地址 p++;//p指向a的下一个地址 p+=5;//从当前位置向后移动5位 指针指向一个数组 int a[5]={5,2,6,3,7}; int *p=a;//不需要& cout<<a; cout<<p; for(int i=0;i<5;i++){ cout<<a[i]; } for(int i=0;i<5;i++){ cout<<p[i]; } for(int i=0;i<5;i++){ cout<<*(p+i); } 指针指向函数 int* getp(){ static int x=10; x++; return &x; } cout<<*getp(); 指针指向字符串 string 字符串 char c[10] 字符数组知道长度 char *c 字符数组不知道长度 string s="abc"; string *p=&s; char *p=s; new 创建空间 delete 删除空间 //静态创建：编译程序后，运行自动占用空间 student a=student{"haha",3,5}; //动态创建：运行到当前代码时，临时申请空间 student *p=new student("haha"); delete p;//将p对应的空间删除，此时p内的地址消失，变成野指针 p=nullptr;//处理野指针 指针指向结构体 调用成员变量或成员函数 *p相当于变量名 静态：a.name; 动态：(*p).name; 如果用指针调用成员变量或成员函数，可以使用 -> p->name;//指针调用语法 p->add(); 文件操作：文件输入输出流，输入输出重定向 重定向 freopen("名","权限",stdin);//r读取 freopen("名","权限",stdout);//w写入 a追加写入 具体代码：cin和cout的功能方向指向具体的文件，重定向 fclose(stdin); fclose(stdout); 文件流 <fstream> file ifstream filein("文件名");//filein指令用来读取文件的内容 ofstream fileout("文件名");//fileout指令用来写入文件的内容 //ofstream fileout("文件名",ios::app);//fileout指令用来追加写入文件的内容 int a,b; filein>>a>>b; fileout<<a+b; filein.close(); fileout.close(); (责任编辑：admin) |