算法笔记:递归(c++实现)

简介: 算法笔记:递归(c++实现)

递归定义

递归定义是一种直接或者间接引用自身的定义方法。

递归包括两部分:

   基础部分(直接形式列举)

   递归部分(给出方法)

斐波那契数列的递归定义

{ f0 = 0, f1 = 1

{f(n) = f(n-1)+f(n-2) n>1

递归算法

使用递归定义的算法

long Fib(long n)
 
{
 
  if(n<=1) return n;
 
  else return (Fib(n-2) +Fib(n-1));
 
}


递归的优点是简洁。缺点是耗时长
(尤其是在递归次数多的时候)。

(使用如下代码可以得到运行时间)

#include<ctime>
 
clock_t start_t, end_t;
 
start_t = clock();
 
.............
 
end_t = clock();
 
std::cout << "Spend " << (double)(end_t - start_t)/1000.0 << " s\n";

其他的一些递归例子:

问题1 :逆序输出正整数的各位数

设有正整数n = 12345,

输出各位数的逆序形式(54321)。


分析(使用递归):

1. 首先输出末位数

2. 然后输出剩下的逆序形式


c++实现:

void print_digit(unsigned n)
 
{
 
std::cout << n%10;    //1.输出末位数,使用求余(%),
 
if (n >= 10)  //递归条件,非常重要,是递归停止的条件。
 
print_digit(n / 10); //2. 输出剩下的数的逆序形式,使用/ 得到剩下的。
 
}
 

问题2: 汉诺塔问题

假设有3个塔座:x,y,z.

塔座x上有从小到大编号为1,2,...n的n个圆盘,

要求把x的圆盘全部搬到z上,且:1.每次只能移动一个圆盘。2.大的盘子不能放在小的盘子上。


分析:

1.把第n个盘子移动到z上(先把n-1个盘子移动到y上

2.把剩下的(n-1)盘子移动到z上

c++实现:

#include<iostream>
 
int count = 0;
//将第n个塔从a移动到b
void move_tower(int n, char a, char b)
{
  std::cout << n << ": "<<char(a) << "->" << char(b);
  std::cout<< "\n";
  count++;
}
 
//移动n个塔,从x移动倒z,以y为中间点
void hanio(int n, char x, char z, char y)
{
  if (n)
  {
    hanio(n - 1, x, y, z);
    move_tower(n, x, z);
    hanio(n - 1, y, z, x);
  }
}
 
int main()
{
  int active = 1;
  while (active)
  {
    count = 0;
    std::cout << "输入塔的层数: ";
    int n;
    std::cin >> n;
    if (n < 1)
    {
      std::cout<<"无效输入,即将退出\n";
      break;
    }
    hanio(n , 'x', 'z', 'y');
    std::cout << "用了" << count << "次\n";
  }
  system("pause");
  return 0;

问题3: 排列组合问题。

问题,设有n个自然数的集合,输出集合产生的各种排列(有序)。

如集合{0,1,2}的排列有

0,1,2; 0,2,1;

1,0,2; 1,2,0;

2,0,1; 2,1,0;

问题分析:可以分为两步

1.确定排列的开头

2.排剩下的集合


c++实现:

#include<iostream>
 
void perm(int a[], int k, int n)
{
  if (k == n-1)         //当k=n-1时,即已经排列完了,进行输出。
  {
    for (int i = 0;i < n; i++)
      std::cout << a[i] << " ";
    std::cout << "\n";
  }
  else
  {
    for (int i = k; i < n; i++)       
    {
      int t = a[k]; a[k] = a[i]; a[i] = t;  //排第k位
      perm(a, k+1, n);          //剩下的 从(k+1)开始排
      t = a[k]; a[k] = a[i]; a[i] = t;  //还原
    }
  }
}
int main()
{
  int  a[10] = { 0,1,2,3,4,5,6,7,8,9 };
  perm(a, 0, 6);
  system("pause");
  return 0;
}


相关文章
|
16天前
|
搜索推荐 算法 C++
|
16天前
|
存储 算法 Serverless
|
16天前
|
存储 算法 搜索推荐
|
21天前
|
存储 算法 Java
技术笔记:JVM的垃圾回收机制总结(垃圾收集、回收算法、垃圾回收器)
技术笔记:JVM的垃圾回收机制总结(垃圾收集、回收算法、垃圾回收器)
17 1
|
23天前
|
算法 数据中心 C++
基于C++雪花算法工具类Snowflake -来自chatGPT
基于C++雪花算法工具类Snowflake -来自chatGPT
15 1
|
13天前
|
存储 算法 C语言
软考中级之数据库系统工程师笔记总结(二)数据结构与算法
软考中级之数据库系统工程师笔记总结(二)数据结构与算法
9 0
|
16天前
|
机器学习/深度学习 算法 搜索推荐
|
17天前
|
存储 算法 程序员
|
21天前
|
机器学习/深度学习 算法 数据可视化
技术心得记录:机器学习笔记之聚类算法层次聚类HierarchicalClustering
技术心得记录:机器学习笔记之聚类算法层次聚类HierarchicalClustering
22 0
|
21天前
|
Java BI C#
技术笔记:SM4加密算法实现Java和C#相互加密解密
技术笔记:SM4加密算法实现Java和C#相互加密解密
15 0

热门文章

最新文章