C++算法系列-递归

简介: 笔记

一. 递归的定义


第一部分称为基例,列出了产生集合中其他元素的基本元素。

第二部分给出由基本元素或已有对象产生新对象的构造规则。

例如要构造自然数集合,取0为基本元素,然后给出累加1的操作即可。


二. 递归的要点


在运用递归的时候,一定不要忘记了递归的终止条件,所谓递归,递归,归去来兮,否则就会永远递归下去。

在递归时,我们经常说是自己调用自己,其实是一个函数调用同一个函数的另外一个实例。

递归操作虽然清晰明了,但是它会消耗更多的内存,更多的时间。


三. 递归的分类


尾递归:函数的末尾只使用一个递归的调用

非尾递归


四. 利用递归实现回溯算法应用于八皇后问题


回溯算法思想:走一步,看一步,不行的话,退回到上一步,另辟蹊径。

5.jpg
#include<iostream>
using namespace std;
class ChessBoard
{
private:
  int map[9][9];
  int count = 0;
  int sum = 0;
public:
  void inits();
  bool check(int, int);
  void putChess(int);
  void print();
};
void ChessBoard::inits()
{
  for (int i = 1; i < 9; i++)
    for (int j = 1; j < 9; j++)
    {
      map[i][j] = 0;
    }
}
bool ChessBoard::check(int x, int y)
{
  int a=x, b=y;
  for (int j = 1; j < 9; j++) {
    if (map[x][j] == 1 || map[j][y] == 1)
      return false;
    a = x + j;
    b = y + j;
    if (map[a][b] == 1 && a <= 8 && b <= 8)
      return false;
    a = x - j;
    b = y - j;
    if (map[a][b] == 1 && a >= 1 && b >= 1)
      return false;
    a = x - j;
    b = y + j;
    if (map[a][b] == 1 && a >= 1 && b <=8)
      return false;
    a = x + j;
    b = y - j;
    if (map[a][b] == 1 && a <= 8 && b >=1)
      return false;
  }
  return true;
}
void ChessBoard::putChess(int n)
{
  if (n > 8 && count == 8)
  {
    sum += 1;
    print();
    return;
  }
  if (n > 8)
    return;
  for (int i = 1; i < 9; i++)
  {
    if (check(n, i))
    {
      map[n][i] = 1;
      count += 1;
      putChess(n + 1);
      map[n][i] = 0;
      count -= 1;
    }
  }
}
void ChessBoard::print()
{
  for (int i = 1; i < 9; i++)
  {
    for (int j = 1; j < 9; j++)
    {
      cout << map[i][j] << " ";
    }
    cout << endl;
  }
  cout << endl << endl;
  cout << sum;
}
int main(void)
{
  ChessBoard a;
  a.inits();
  a.putChess(1);
  return 0;
}

Thank for your reading!!!

公众号:FPGA之旅

目录
相关文章
|
24天前
|
算法 搜索推荐 Shell
数据结构与算法学习十二:希尔排序、快速排序(递归、好理解)、归并排序(递归、难理解)
这篇文章介绍了希尔排序、快速排序和归并排序三种排序算法的基本概念、实现思路、代码实现及其测试结果。
15 1
|
24天前
|
存储 算法 C++
高精度算法(加、减、乘、除,使用c++实现)
高精度算法(加、减、乘、除,使用c++实现)
287 0
高精度算法(加、减、乘、除,使用c++实现)
|
21天前
|
算法 数据处理 C++
c++ STL划分算法;partition()、partition_copy()、stable_partition()、partition_point()详解
这些算法是C++ STL中处理和组织数据的强大工具,能够高效地实现复杂的数据处理逻辑。理解它们的差异和应用场景,将有助于编写更加高效和清晰的C++代码。
16 0
|
24天前
|
算法 定位技术
数据结构与算法学习九:学习递归。递归的经典实例:打印问题、阶乘问题、递归-迷宫问题、八皇后问题
本文详细介绍了递归的概念、重要规则、形式,并展示了递归在解决打印问题、阶乘问题、迷宫问题和八皇后问题等经典实例中的应用。
30 0
|
1月前
|
存储 算法 决策智能
【算法】博弈论(C/C++)
【算法】博弈论(C/C++)
|
1月前
|
存储 算法 C++
【算法】哈希映射(C/C++)
【算法】哈希映射(C/C++)
|
1月前
|
机器学习/深度学习 人工智能 算法
【算法】最长公共子序列(C/C++)
【算法】最长公共子序列(C/C++)
|
1月前
|
人工智能 算法 BI
一篇带你速通差分算法(C/C++)
一篇带你速通差分算法(C/C++)
|
1月前
|
人工智能 算法 C++
一篇带你速通前缀和算法(C/C++)
一篇带你速通前缀和算法(C/C++)
|
1月前
|
存储 算法 C++
弗洛伊德(Floyd)算法(C/C++)
弗洛伊德(Floyd)算法(C/C++)