蓝桥杯老师讲递归

简介: 1 //正序打印自然数 0 -9 2 #include 3 #include 4 using namespace std; 5 6 void fun(int begin,int end) 7 { 8 cout
  1 //正序打印自然数 0 -9
  2 #include <iostream>
  3 #include <cstring>
  4 using namespace std;
  5 
  6 void fun(int begin,int end)
  7 {
  8      cout<<begin<<" ";
  9      if(begin!=end)//写成begin<end会更好 
 10           fun(begin+1,end);
 11 }
 12 int main()
 13 {
 14      int i,j,k;
 15      fun(0,9);
 16      cout<<endl;
 17      while(1);
 18      return 0;
 19 }
 20      
 21 
 22 
 23 //倒序打印自然数 9-0
 24 #include <iostream>
 25 #include <cstring>
 26 using namespace std;
 27 
 28 void fun(int begin,int end)
 29 {
 30     
 31      if(begin!=end)//写成begin<end会更好 
 32           fun(begin+1,end);
 33       cout<<begin<<" ";
 34 }
 35 int main()
 36 {
 37      int i,j,k;
 38      fun(0,9);
 39      cout<<endl;
 40      while(1);
 41      return 0;
 42 }
 43      
 44 
 45 //倒序打印自然数 0 -9 
 46 #include <iostream>
 47 #include <cstring>
 48 using namespace std;
 49 
 50 void fun(int begin,int end)
 51 {
 52      cout<<begin<<" ";
 53      if(begin>=end) //去掉等号是 0-10 
 54           return ;
 55      fun(begin+1,end);   
 56 }
 57 int main()
 58 {
 59      int i,j,k;
 60      fun(0,9);
 61      cout<<endl;
 62      while(1);
 63      return 0;
 64 }
 65      
 66 
 67 
 68 //无返回值的递归函数求累加和,有返回值时刚开始不会做 
 69 #include <iostream>
 70 #include <cstring>
 71 using namespace std;
 72 
 73 int sum = 0;
 74 void fun(int begin,int end)
 75 {
 76      sum += begin;
 77      if(begin<end)
 78           fun(begin+1,end);
 79 }
 80 
 81 int main()
 82 {
 83      fun(1,100);
 84      cout<<sum<<endl;
 85      while(1);
 86      return 0;
 87 }
 88 
 89 //刚开始没想明白怎么递归,盲目的使用全局sum 
 90 #include <iostream>
 91 #include <cstring>
 92 using namespace std;
 93 
 94 //系统问我1 - 100和为几?我问另一个人2到100和是几,然后用他的返回值加上 begin,不是1 
 95 int fun(int begin,int end)
 96 {
 97      if(begin == end) 
 98           return begin;
 99      return begin += fun(begin+1,end);
100 }
101 
102 int main()
103 {
104      int sum = fun(1,100);
105      cout<<sum<<endl;
106      while(1);
107      return 0;
108 }
109   
110 
111 
112 //递归实现串反转
113 #include <iostream>
114 #include <cstring>
115 using namespace std;
116 
117 char str[50];
118 
119 void fun(char *p,char *q)
120 {
121      char temp;//若定义成char *temp,发现无法实现反转,想了下或许因为原来p是低地址,交换后p>q,立马推出,
122       //虽然执行了一次 但貌似没一点影响 ,我认为执行n次也没用 ,可以分析下 :第二次递归时又换回来了 
123      if(p>=q)
124           return ;
125      temp = *p;
126      *p = *q;
127      *q = temp;
128      fun(p+1,q-1);     
129 }
130         
131 int main()
132 {
133      int i,j,k; 
134      memset(str,0,sizeof(str));
135      cin>>str;
136      int len = strlen(str);
137      i = 0, j = len-1;
138      fun(str+i,str+j);
139      cout<<str<<endl;
140      while(1);
141      return 0;
142 }   
143      

 

 1 // next_permutation会自动去重,而那个交换算法打印出来的不是按字典序排列的 
 2 #include <iostream>
 3 #include <string>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 int main()
 8 {
 9      int i,j,k;
10      char str[] = {'a','b','b','b'};//只打印四个 
11      do
12      {
13           cout<<str<<endl;
14      }while(next_permutation(str,str+4));
15      while(1);
16      return 0;
17 } 

 

 1 //找到相似性,设计出口 ,该算法是蓝桥杯老师讲的,也不是字典序,也不可去重 
 2 #include <iostream>
 3 #include <string>
 4 #include <vector> 
 5 using namespace std;
 6 
 7 vector <string > fun(string str)
 8 {
 9      int i,j,k;
10      char ch = str[0];
11      vector <string > r;
12      if(str.length()==1)
13      {
14           r.push_back(str);
15           return r;
16      }
17      string str1 = str.substr(1);
18      vector <string > x = fun(str1);
19      for(i=0; i<x.size(); i++)
20      {
21           for(j=0; j<x[i].length()+1; j++)//条件是长度加一 
22           {
23                string s =  x[i].substr(0,j) +ch + x[i].substr(j);//顺序不可反, 
24                r.push_back(s);
25           }
26      }
27      return r;
28 }
29 
30 int main()
31 {
32      int i,j,k;
33      string str = "";
34      while(cin>>str)
35      {
36           cout<<"-------------"<<endl;
37           vector <string >  v = fun(str);
38           for(i=0; i<v.size(); i++)
39           {
40                cout<<v[i].c_str()<<endl;
41           }
42           str.clear();
43           cout<<"--------------"<<endl;
44      }
45      return 0;
46 } 

 小任务和大任务有相似性并且可以解决 ,这是最重要的,第二就是设计出口。也就是先写递归主体再设计出口。

递归就是调用和自己同名的函数,可以任何时候都调用递归并且在进入递归的时候检查是否继续递归;或者满足条件的话才进行递归

递归一定要有参数,否则就无法划分子问题了

相似任务,简单任务,出口。

目录
相关文章
|
2月前
|
Java C语言 C++
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-449 递归输出数字三角形
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-449 递归输出数字三角形
61 0
|
10月前
|
存储 算法
蓝桥杯:递归 与 例题:斐波那契数列及优化与应用
蓝桥杯:递归 与 例题:斐波那契数列及优化与应用
61 0
|
6天前
【蓝桥杯】[递归]母牛的故事
蓝桥杯——[递归]母牛的故事
10 1
【蓝桥杯】[递归]母牛的故事
|
1月前
|
Java
蓝桥杯Java组暴力递归搜图
蓝桥杯Java组暴力递归搜图
22 4
|
2月前
|
Java C语言 C++
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-446 递归输出数字
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-446 递归输出数字
49 1
|
2月前
|
Java C语言 C++
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-150 6-1 递归求二项式系数值
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-150 6-1 递归求二项式系数值
49 1
|
9月前
|
算法
[蓝桥杯] 递归与递推习题训练
蓝桥杯比赛只有四十天左右啦,最近会按照模块更新一些有关蓝桥杯算法题。学习算法不仅仅是为了参见比赛,更是以后找工作的一个敲门砖。废话不多说,我们直接看题。
53 0
|
12月前
《蓝桥杯每日一题》递归·AcWing 1497. 树的遍历
《蓝桥杯每日一题》递归·AcWing 1497. 树的遍历
49 0
蓝桥杯AcWing 题目题解 - 递归与递推
蓝桥杯AcWing 题目题解 - 递归与递推
(蓝桥杯)递推与递归,前缀和,二分经典例题分析
(蓝桥杯)递推与递归,前缀和,二分经典例题分析
(蓝桥杯)递推与递归,前缀和,二分经典例题分析