C++回溯法实例分析_C 语言

本文实例讲述了C++的回溯法，分享给大家供大家参考之用。具体方法分析如下：

一般来说，回溯法是一种枚举状态空间中所有可能状态的系统方法，它是一个一般性的算法框架。

解向量a=(a1, a2, ..., an)，其中每个元素ai取自一个有限序列集Si，这样的解向量可以表示一个排列，其中ai是排列中的第i个元素，也可以表示子集S，其中ai为真当且仅当全集中的第i个元素在S中；甚至可以表示游戏的行动序列或者图中的路径。

在回溯法的每一步，我们从一个给定的部分解a={a1, a2, ..., ak}开始，尝试在最后添加元素来扩展这个部分解，扩展之后，我们必须测试它是否为一个完整解，如果是的话，就输出这个解；如果不完整，我们必须检查这个部分解是否仍有可能扩展成完整解，如果有可能，递归下去；如果没可能，从a中删除新加入的最后一个元素，然后尝试该位置上的其他可能性。

用一个全局变量来控制回溯是否完成，这个变量设为finished，那么回溯框架如下，可谓是回溯大法之精髓与神器

bool finished = false;

void backTack(int input[], int inputSize, int index, int states[], int stateSize)
{
 int candidates[MAXCANDIDATE];
 int ncandidates;

 if (isSolution(input, inputSize, index) == true)
 {
 processSolution(input, inputSize, index);
 }
 else
 {
 constructCandidate(input, inputSize, index, candidates, &ncandidates);
 for (int i = 0; i < ncandidates; i++)
 {
  input[index] = candidates[i];
  backTack(input, inputSize, index + 1);
  if (finished)
  return;
 }
 }
}

不拘泥于框架的形式，我们可以编写出如下代码：

#include <iostream>

using namespace std;

char str[] = "abc";
const int size = 3;

int constructCandidate(bool *flag, int size = 2)
{
 flag[0] = true;
 flag[1] = false;

 return 2;
}

void printCombine(const char *str, bool *flag, int pos, int size)
{
 if (str == NULL || flag == NULL || size <= 0)
 return;

 if (pos == size)
 {
 cout << "{ ";
 for (int i = 0; i < size; i++)
 {
  if (flag[i] == true)
  cout << str[i] << " ";
 }
 cout << "}" << endl;
 }
 else
 {
 bool candidates[2];
 int number = constructCandidate(candidates);
 for (int j = 0; j < number; j++)
 {
  flag[pos] = candidates[j];
  printCombine(str, flag, pos + 1, size);
 }
 }
}

void main()
{
 bool *flag = new bool[size];
 if (flag == NULL)
 return;
 printCombine(str, flag, 0, size);
 delete []flag;
}

采用回溯法框架来计算字典序排列：

#include <iostream>

using namespace std;

char str[] = "abc";
const int size = 3;

void constructCandidate(char *input, int inputSize, int index, char *states, char *candidates, int *ncandidates)
{
 if (input == NULL || inputSize <= 0 || index < 0 || candidates == NULL || ncandidates == NULL)
 return;

 bool buff[256];
 for (int i = 0; i < 256; i++)
 buff[i] = false;
 int count = 0;
 for (int i = 0; i < index; i++)
 {
 buff[states[i]] = true;
 }
 for (int i = 0; i < inputSize; i++)
 {
 if (buff[input[i]] == false)
  candidates[count++] = input[i];
 }
 *ncandidates = count;
 return;
}

bool isSolution(int index, int inputSize)
{
 if (index == inputSize)
 return true;
 else
 return false;
}

void processSolution(char *input, int inputSize)
{
 if (input == NULL || inputSize <= 0)
 return;

 for (int i = 0; i < inputSize; i++)
 cout << input[i];
 cout << endl;
}

void backTack(char *input, int inputSize, int index, char *states, int stateSize)
{
 if (input == NULL || inputSize <= 0 || index < 0 || states == NULL || stateSize <= 0)
 return;

 char candidates[100];
 int ncandidates;
 if (isSolution(index, inputSize) == true)
 {
 processSolution(states, inputSize);
 return;
 }
 else
 {
 constructCandidate(input, inputSize, index, states, candidates, &ncandidates);
 for (int i = 0; i < ncandidates; i++)
 {
  states[index] = candidates[i];
  backTack(input, inputSize, index + 1, states, stateSize);
 }
 }
}

void main()
{
 char *candidates = new char[size];
 if (candidates == NULL)
 return;
 backTack(str, size, 0, candidates, size);
 delete []candidates;
}

对比上述两种情形，可以发现唯一的区别在于全排列对当前解向量没有要求，而字典序对当前解向量是有要求的，需要知道当前解的状态！
八皇后回溯法求解：

#include <iostream>

using namespace std;

int position[8];

void constructCandidate(int *input, int inputSize, int index, int *states, int *candidates, int *ncandidates)
{
 if (input == NULL || inputSize <= 0 || index < 0 || candidates == NULL || ncandidates == NULL)
 return;

 *ncandidates = 0;
 bool flag;
 for (int i = 0; i < inputSize; i++)
 {
 flag = true;
 for (int j = 0; j < index; j++)
 {
  if (abs(index - j) == abs(i - states[j]))
  flag = false;
  if (i == states[j])
  flag = false;
 }

 if (flag == true)
 {
  candidates[*ncandidates] = i;
  *ncandidates = *ncandidates + 1;
 }
 }
/*
 cout << "ncandidates = " << *ncandidates << endl;
 system("pause");*/

 return;
}

bool isSolution(int index, int inputSize)
{
 if (index == inputSize)
 return true;
 else
 return false;
}

void processSolution(int &count)
{
 count++;
}

void backTack(int *input, int inputSize, int index, int *states, int stateSize, int &count)
{
 if (input == NULL || inputSize <= 0 || index < 0 || states == NULL || stateSize <= 0)
 return;

 int candidates[8];
 int ncandidates;
 if (isSolution(index, inputSize) == true)
 {
 processSolution(count);
 }
 else
 {
 constructCandidate(input, inputSize, index, states, candidates, &ncandidates);
 for (int i = 0; i < ncandidates; i++)
 {
  states[index] = candidates[i];
  backTack(input, inputSize, index + 1, states, stateSize, count);
 }
 }
}

void main()
{
 //初始化棋局
 for (int i = 0; i < 8; i++)
 position[i] = i;

 int states[8];
 int count = 0;
 backTack(position, 8, 0, states, 8, count);
 cout << "count = " << count << endl;
}

希望本文所述对大家C++程序算法设计的学习有所帮助。

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索c++
回溯法
装载问题 回溯法c语言、c语言 回溯法、n皇后问题回溯法c语言、r语言聚类分析实例、r语言数据分析实例，以便于您获取更多的相关知识。

时间： 2024-10-14 01:06:19

C++回溯法实例分析_C 语言的相关文章

C++结构体用法实例分析_C 语言

本文实例讲述了C++结构体用法.分享给大家供大家参考.具体分析如下: C++结构体提供了比C结构体更多的功能,如默认构造函数,复制构造函数,运算符重载,这些功能使得结构体对象能够方便的传值. 比如,我定义一个简单的结构体,然后将其作为vector元素类型,要使用的话,就需要实现上述三个函数,否则就只能用指针了. 复制代码 代码如下: #include <iostream>  #include <vector>   using namespace std;  struct ST  {

C语言的递归思想实例分析_C 语言

本文实例分析C语言的递归思想,分享给大家供大家参考之用.具体方法如下: 通俗点来说,递归就是自己调用自己. 递归的难点一是理解递归的执行调用过程,二是设置一个合理的递归结束条件. 下面来看一段摘自书中的简单程序: #include <STDIO.H> long fact(int n); long rfact(int n); int main(void) { int num; printf("This program calculates factorials.\n"); p

C++编译器无法捕捉到的8种错误实例分析_C 语言

本文实例分析了C++编译器无法捕捉到的8种错误,分享给大家供大家参考之用.有助于深入理解C++运行原理,具体分析如下: 众所周知,C++是一种复杂的编程语言,其中充满了各种微妙的陷阱.在C++中几乎有数不清的方式能把事情搞砸.幸运的是,如今的编译器已经足够智能化了,能够检测出相当多的这类编程陷阱并通过编译错误或编译警告来通知程序员.最终,如果处理得当的话,任何编译器能检查到的错误都不会是什么大问题,因为它们在编译时会被捕捉到,并在程序真正运行前得到解决.最坏的情况下,一个编译器能够捕获到的错误只

C++线程同步实例分析_C 语言

本文实例分析了C++线程同步问题,分享给大家供大家参考.具体分析如下: 该实例设置全局变量g_bContinue,在主线程中设置全局变量g_bContinue,工作线程检测该全局变量,实现主线程控制工作线程的目的. 打印出的g_cnt1与g_cnt2的数值不同,是因为线程调试时时间片的切换. 具体代码如下: // countError.cpp : 定义控制台应用程序的入口点. // #include "stdafx.h" #include <Windows.h> DWORD

C++二进制翻转实例分析_C 语言

本文实例讲述了C++二进制翻转的方法,将常用的几种解决方法罗列出来供大家比较选择.具体如下: 首先来看看一个相对笨拙的算法: #include <iostream> using namespace std; void printBinary(unsigned char str, int size = 1) { int flag = 0x01; for (int i = 0; i < size; i++) { for (int i = 0; i < 8; i++) { if (str

C语言创建链表错误之通过指针参数申请动态内存实例分析_C 语言

本文实例讲述了C语言创建链表中经典错误的通过指针参数申请动态内存,分享给大家供大家参考之用.具体实例如下: #include <stdio.h> #include <stdlib.h>// 用malloc要包含这个头文件 typedef struct node { int data; struct node* next;// 这个地方注意结构体变量的定义规则 } Node; void createLinklist(Node* pHder, int length) { int i =

C语言中自动隐式转换与类型强制转换实例分析_C 语言

本文通过一个C程序实例对C语言中自动隐式转换与类型强制转换的注意点进行深入分析,详情如下: 先看一个C程序: #include<stdlib.h> #include<stdio.h> #include<conio.h> double proc(int q){ int n; double sum,t;//本例的关键就在这几个变量的类型上 sum = 2.0; while(sum<=q){ t=sum; //sum = sum+(n+1)/n;//自动隐式转换 sum

websocket++简单使用及实例分析_C 语言

前言 html5支持使用websocket协议与服务器保持一个长连接,方便双方互相传输数据,而且服务器也能主动发送信息给客户端,而在这之前使用HTTP是很难做到的.下面介绍使用C++实现的websocket++的简单使用.websocket++更详细介绍点此. websocket++需要boost的支持,所以工程中需要包含boost的头文件和库.boost在VS中的如何使用参考此文章. C++代码 #include "stdafx.h" #include <iostream>

C++虚函数表实例分析_C 语言

多态是C++面向对象程序设计的一个重要特性.以前看到虚函数觉得很神奇,为什么就能实现多态了呢.最初的时候曾设想,要实现运行时多态,应该让对象的某个部分始终指向一个固定的地址,子类继承的时候,就修改这个地址的内容.这样,父类和子类都是到同一个固定地址去读取内容,在运行时就能表现不同行为. 在看了<深度探索c++对象模型>之后,发现思路是类似的.在对象中,有一个指针指向一张虚函数表,里面按照次序存放了每一个虚函数,当子类继承的时候,即到虚函数表的指定位置去修改函数地址.当我们通过父类指针来操作一个