文档章节

回溯算法

bieguohuo
 bieguohuo
发布于 2017/04/11 10:35
字数 303
阅读 13
收藏 0

基本思想是:从一条路往前走,能进则进,不能进则退回来,换一条路再试。

一、将从1到n这n个整数围成一个圆环,若其中任意2个相邻的数字相加,结果均为素数,那么这个环就成为素数环

#include<iostream>

#include<cmath>

#include<cstdio>

using namespace std;

int ans[21] = {0}, tot = 0;

bool a[21] = {0};

void print(){

tot++;

cout << "No." << tot << ':';

for (int i = 1; i <= 20; i++)

cout << ans[i] << ' ';

cout << endl;

}

bool isprime(int x1, int x2){

int i = x1 + x2,f;

for (f = 2; f <= sqrt(i); f++)

if (i % f == 0)

return false;

return true;

}

int search(int t){

for (int i = 1; i <= 20; i++){

if (a[i] == false && isprime(ans[t - 1], i)){

ans[t] = i;

a[i] = true;

if (t == 20 && isprime(ans[1], ans[20]))

print();

else

search(t + 1);

a[i] = false;

}

}

}

int main() {

search(1);

printf("The total is %d", tot);

}

二、八皇后问题

    //检查皇后放置是否合法

  1. public bool  IsSafe(int r)  
  2.     {  
  3.         for (int i = 0; i < r; i++)//遍历该行之前  
  4.         {  
  5.             if (Math.Abs(x[r] - x[i]) == Math.Abs(r - i) || x[i] == x[r])  
  6.             {  
  7.                 return false;  
  8.             }  
  9.         }  
  10.         return true;  
  11.     }  
  12. public void Queen(int t)  
  13.     {  
  14.         if (t==8)  
  15.         {  
  16.             ListItem li=new ListItem();             
  17.             cout++;//sum为所有的可行解  
  18.             for (int i = 0; i < 8; i++)  
  19.             {             
  20.                 li.Text += x[i].ToString();                  
  21.             }  
  22.             lbo_res.Items.Add(li);  
  23.         }  
  24.         else   
  25.         {  
  26.             for (int i = 0; i < 8; i++)  
  27.             {  
  28.                 x[t] = i;  
  29.                 if (IsSafe(t)) {  
  30.                     Queen(t + 1);  
  31.                 }  
  32.             }  
  33.         }  
  34.     }  

© 著作权归作者所有

共有 人打赏支持
上一篇: 动态规划算法
bieguohuo
粉丝 3
博文 22
码字总数 7166
作品 0
丰台
高级程序员
私信 提问
游戏与常用的五大算法---下篇

前言: 心是一个人的翅膀,心有多大,世界就有多大。很多时候限制我们的,不是周遭的环境,也不是他人的言行,而是我们自己!看不开,放不下,忘不了,把自己囚禁在灰暗的记忆里;不敢想,不...

loving_forever_
2017/01/08
0
0
五大常用算法:分治、动态规划、贪心、回溯、分支限界

分治:把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并 http://www.cnblogs.com/ste...

毛朱
2015/09/11
2.5K
0
diff程序的算法

diff程序很重要,linux中的源代码补丁都是diff作出来的,diff在比较两个文本文件的不同方面很高效,它是基于行的,diff会将两个文件都按照行分成若干部分,然后计算这些行每一行的校验码,之...

晨曦之光
2012/04/10
1K
0
对求有向图强连通分量的tarjan算法原理的一点理解

先简单叙述一下tarjan算法的执行过程(其他诸如伪代码之类的相关细节可以自己网上搜索,这里就不重复贴出了): 用到两类数组: dfs[]:DFS过程中给定节点的深度优先数,即该节点在DFS中被访问的...

Kukucao
2018/08/21
0
0
算法的设计基本方法的理解

算法设计基本方法有什么好处? 了解常见的算法设计方法以及它们之间的区别,有利于构建算法思维的广度,有充分的理论知识。当然,如果算法思维的深度再好的话,将来你见识的算法越多,天下之...

qingliangdexiar
2017/05/31
0
0

没有更多内容

加载失败,请刷新页面

加载更多

C++ vector和list的区别

1.vector数据结构 vector和数组类似,拥有一段连续的内存空间,并且起始地址不变。 因此能高效的进行随机存取,时间复杂度为o(1); 但因为内存空间是连续的,所以在进行插入和删除操作时,会造...

shzwork
42分钟前
2
0
Spring之invokeBeanFactoryPostProcessors详解

Spring的refresh的invokeBeanFactoryPostProcessors,就是调用所有注册的、原始的BeanFactoryPostProcessor。 相关源码 public static void invokeBeanFactoryPostProcessors(Configu......

cregu
昨天
3
0
ibmcom/db2express-c_docker官方使用文档

(DEPRECIATED) Please check DB2 Developer-C Edition for the replacement. What is IBM DB2 Express-C ? ``IBM DB2 Express-C``` is the no-charge community edition of DB2 server, a si......

BG2KNT
昨天
2
0
Ubuntu 18.04.2 LTS nvidia-docker2 : 依赖: docker-ce (= 5:18.09.0~3-0~ubuntu-bionic)

平台:Ubuntu 18.04.2 LTS nvidia-docker2 版本:2.0.3 错误描述:在安装nvidia-docker2的时候报dpkg依赖错误 nvidia-docker2 : 依赖: docker-ce (= 5:18.09.0~3-0~ubuntu-bionic) 先看一下依......

Pulsar-V
昨天
4
0
学习笔记1-goland结构体(struct)

写在前面:若有侵权,请发邮件by.su@qq.com告知。 转载者告知:如果本文被转载,但凡涉及到侵权相关事宜,转载者需负责。请知悉! 本文永久更新地址:https://my.oschina.net/bysu/blog/3036...

不最醉不龟归
昨天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部