回溯 航电ACM1016题(数据结构之深度优先搜索)

2023-10-27 21:40

本文主要是介绍回溯 航电ACM1016题(数据结构之深度优先搜索),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1. 原题

Prime Ring Problem

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 83554 Accepted Submission(s): 34353

Problem Description
A ring is compose of n circles as shown in diagram. Put natural number 1, 2, …, n into each circle separately, and the sum of numbers in two adjacent circles should be a prime.

Note: the number of first circle should always be 1.

在这里插入图片描述

Input
n (0 < n < 20).

Output
The output format is shown as sample below. Each row represents a series of circle numbers in the ring beginning from 1 clockwisely and anticlockwisely. The order of numbers must satisfy the above requirements. Print solutions in lexicographical order.

You are to write a program that completes above process.

Print a blank line after each case.

Sample Input
6
8

Sample Output
Case 1:
1 4 3 2 5 6
1 6 5 2 3 4

Case 2:
1 2 3 8 5 6 7 4
1 2 5 8 3 4 7 6
1 4 7 6 5 8 3 2
1 6 7 4 3 8 5 2

Source
Asia 1996, Shanghai (Mainland China)

Recommend
JGShining | We have carefully selected several similar problems for you: 1010 1241 1312 1072 1242

2.题目解析

Created with Raphaël 2.2.0 开始(寻找t位置上符合的数字)i=1 i<= N? 数字i是否被使用? 数字i与t-1位置的数字之和是否为素数? 第I号位置赋值,标识第i个数字 符合条件,继续搜索第t+1位置上的值 继续判断下一个数字i+1是否符合 byebye yes no yes no yes no

3.代码

#include <stdio.h>
#include <math.h>
#include <stdbool.h>
int circle[21] = {0};//初始化
bool tell[21] = {false};//初始化
void circle_print(int n){int i;for (i = 1; i < n; i++)printf("%d ",circle[i]);printf("%d\n",circle[i]);
}//按照格式打印出数据
bool isprime(int x1, int x2){int i = x1 + x2,f;for (f = 2; f <= sqrt(i); f++)if (i % f == 0)return true;return false;
}//前一位和当前位置之和是否为素数
void next_search(int n,int t){//n表示搜索的环数int i; for (i = 2; i <= n; i++){if (tell[i] == false && isprime(circle[t - 1], i)==false){//数字i没有被使用  且 与前一直数字之和为素数circle[t] = i;//符合第t位置上面的值,给第t位赋值tell[i] = true;//表示第i个位置已经使用if (t == n && isprime(circle[1], circle[n])==false)circle_print(n);	//如果已经搜到环的最后一个数字且最后最后一位与第一位之和为素数,那么就先输出else next_search(n,t + 1); //继续搜索第t+1的位置tell[i] = false;//从t+1的那个房间返回到t的这号房间,标识着要开始重新赋值,这组数据已经用过了}}
}
int main() {int n,num=1;circle[1]=1;while(scanf("%d",&n)!=EOF){printf("Case %d:\n",num++);next_search(n,2);printf("\n");}
}
结语:其实做这个题的时候也是碰巧,随便瞎写,就想一定要把这个题目给做出来(一开始我也没有想到回溯)
只要自己肯努努力,一切终将成功

这篇关于回溯 航电ACM1016题(数据结构之深度优先搜索)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/288577

相关文章

Python使用DeepSeek进行联网搜索功能详解

《Python使用DeepSeek进行联网搜索功能详解》Python作为一种非常流行的编程语言,结合DeepSeek这一高性能的深度学习工具包,可以方便地处理各种深度学习任务,本文将介绍一下如何使用P... 目录一、环境准备与依赖安装二、DeepSeek简介三、联网搜索与数据集准备四、实践示例:图像分类1.

Redis 内存淘汰策略深度解析(最新推荐)

《Redis内存淘汰策略深度解析(最新推荐)》本文详细探讨了Redis的内存淘汰策略、实现原理、适用场景及最佳实践,介绍了八种内存淘汰策略,包括noeviction、LRU、LFU、TTL、Rand... 目录一、 内存淘汰策略概述二、内存淘汰策略详解2.1 ​noeviction(不淘汰)​2.2 ​LR

Python与DeepSeek的深度融合实战

《Python与DeepSeek的深度融合实战》Python作为最受欢迎的编程语言之一,以其简洁易读的语法、丰富的库和广泛的应用场景,成为了无数开发者的首选,而DeepSeek,作为人工智能领域的新星... 目录一、python与DeepSeek的结合优势二、模型训练1. 数据准备2. 模型架构与参数设置3

Java深度学习库DJL实现Python的NumPy方式

《Java深度学习库DJL实现Python的NumPy方式》本文介绍了DJL库的背景和基本功能,包括NDArray的创建、数学运算、数据获取和设置等,同时,还展示了如何使用NDArray进行数据预处理... 目录1 NDArray 的背景介绍1.1 架构2 JavaDJL使用2.1 安装DJL2.2 基本操

最长公共子序列问题的深度分析与Java实现方式

《最长公共子序列问题的深度分析与Java实现方式》本文详细介绍了最长公共子序列(LCS)问题,包括其概念、暴力解法、动态规划解法,并提供了Java代码实现,暴力解法虽然简单,但在大数据处理中效率较低,... 目录最长公共子序列问题概述问题理解与示例分析暴力解法思路与示例代码动态规划解法DP 表的构建与意义动

Go语言中三种容器类型的数据结构详解

《Go语言中三种容器类型的数据结构详解》在Go语言中,有三种主要的容器类型用于存储和操作集合数据:本文主要介绍三者的使用与区别,感兴趣的小伙伴可以跟随小编一起学习一下... 目录基本概念1. 数组(Array)2. 切片(Slice)3. 映射(Map)对比总结注意事项基本概念在 Go 语言中,有三种主要

Go中sync.Once源码的深度讲解

《Go中sync.Once源码的深度讲解》sync.Once是Go语言标准库中的一个同步原语,用于确保某个操作只执行一次,本文将从源码出发为大家详细介绍一下sync.Once的具体使用,x希望对大家有... 目录概念简单示例源码解读总结概念sync.Once是Go语言标准库中的一个同步原语,用于确保某个操

五大特性引领创新! 深度操作系统 deepin 25 Preview预览版发布

《五大特性引领创新!深度操作系统deepin25Preview预览版发布》今日,深度操作系统正式推出deepin25Preview版本,该版本集成了五大核心特性:磐石系统、全新DDE、Tr... 深度操作系统今日发布了 deepin 25 Preview,新版本囊括五大特性:磐石系统、全新 DDE、Tree

Node.js 中 http 模块的深度剖析与实战应用小结

《Node.js中http模块的深度剖析与实战应用小结》本文详细介绍了Node.js中的http模块,从创建HTTP服务器、处理请求与响应,到获取请求参数,每个环节都通过代码示例进行解析,旨在帮... 目录Node.js 中 http 模块的深度剖析与实战应用一、引言二、创建 HTTP 服务器:基石搭建(一

C# ComboBox下拉框实现搜索方式

《C#ComboBox下拉框实现搜索方式》文章介绍了如何在加载窗口时实现一个功能,并在ComboBox下拉框中添加键盘事件以实现搜索功能,由于数据不方便公开,作者表示理解并希望得到大家的指教... 目录C# ComboBox下拉框实现搜索步骤一步骤二步骤三总结C# ComboBox下拉框实现搜索步骤一这