【NOIP普及组】 FBI树

【NOIP普及组】 FBI树

      • C语言版本
      • C++ 版本
      • Java版本
      • Python版本


💐The Begin💐点点关注,收藏不迷路💐

我们可以把由“0”和“1”组成的字符串分为三类:全“0”串称为B串,全“1”串称为I串,既含“0”又含“1”的串则称为F串。

FBI树是一种二叉树[1],它的结点类型也包括F结点,B结点和I结点三种。由一个长度为2N的“01”串S可以构造出一棵FBI树T,递归的构造方法如下:

1)T的根结点为R,其类型与串S的类型相同;
2)若串S的长度大于1,将串S从中间分开,分为等长的左右子串S1和S2;由左子串S1构造R的左子树T1,由右子串S2构造R的右子树T2。

现在给定一个长度为2N的“01”串,请用上述构造方法构造出一棵FBI树,并输出它的后序遍历[2]序列。

输入

第一行是一个整数N(0 <= N <= 10),第二行是一个长度为2N的“01”串。

输出

输出一行只包含一个字符串,即FBI树的后序遍历序列。

样例输入

3
10001011

样例输出

IBFBBBFIBFIIIFF

C语言版本

#include <stdio.h>
#include <string.h>// 判断字符串是否全为指定字符
int isAllSame(char *str, char ch) {int i;int len = strlen(str);for (i = 0; i < len; i++) {if (str[i]!= ch) {return 0;}}return 1;
}// 计算FBI类型
char fbi(char *str) {int len = strlen(str);// 如果字符串长度大于1,递归处理子串if (len > 1) {char leftStr[len / 2 + 1];char rightStr[len - len / 2 + 1];strncpy(leftStr, str, len / 2);leftStr[len / 2] = '\0';strncpy(rightStr, str + len / 2, len - len / 2);rightStr[len - len / 2] = '\0';printf("%c", fbi(leftStr));printf("%c", fbi(rightStr));}// 判断字符串是否全为0if (isAllSame(str, '0')) {return 'B';}// 判断字符串是否全为1else if (isAllSame(str, '1')) {return 'I';}return 'F';
}int main() {int n; // n:输入的整数N,表示后续输入字符串的长度相关信息scanf("%d", &n);char s[1024]; // s:存储输入的字符串scanf("%s", s);printf("%c", fbi(s));return 0;
}

C++ 版本

#include <iostream>
#include <string>// 判断字符串是否全为指定字符
bool isAllSame(const std::string &str, char ch) {for (char c : str) {if (c!= ch) {return false;}}return true;
}// 计算FBI类型
char fbi(const std::string &str) {int len = str.length();// 如果字符串长度大于1,递归处理子串if (len > 1) {std::string leftStr = str.substr(0, len / 2);std::string rightStr = str.substr(len / 2);std::cout << fbi(leftStr);std::cout << fbi(rightStr);}// 判断字符串是否全为0if (isAllSame(str, '0')) {return 'B';}// 判断字符串是否全为1else if (isAllSame(str, '1')) {return 'I';}return 'F';
}int main() {int n; // n:输入的整数N,表示后续输入字符串的长度相关信息std::cin >> n;std::string s; // s:存储输入的字符串std::cin >> s;std::cout << fbi(s) << std::endl;return 0;
}

Java版本

import java.util.Scanner;class Main {// 判断字符串是否全为指定字符static boolean isAllSame(String str, char ch) {// 遍历字符串中的每个字符for (int i = 0; i < str.length(); i++) {// 如果有任何一个字符与指定字符不同,返回falseif (str.charAt(i)!= ch) {return false;}}// 如果所有字符都与指定字符相同,返回truereturn true;}// 计算FBI类型static char fbi(String str) {int len = str.length();// 如果字符串长度大于1,递归处理子串if (len > 1) {String leftStr = str.substring(0, len / 2);String rightStr = str.substring(len / 2);// 先递归处理左子串并输出结果System.out.print(fbi(leftStr));// 再递归处理右子串并输出结果System.out.print(fbi(rightStr));}// 判断字符串是否全为0if (isAllSame(str, '0')) {return 'B';}// 判断字符串是否全为1else if (isAllSame(str, '1')) {return 'I';}return 'F';}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n; // n:输入的整数N,表示后续输入字符串的长度相关信息n = scanner.nextInt();String s = scanner.next(); // s:存储输入的字符串System.out.println(fbi(s));// 关闭Scanner,释放资源scanner.close();}
}

Python版本

#  Python 3 风格的 print 函数
from __future__ import print_functiondef fbi(s):length = len(s)# 如果字符串长度大于1,递归处理子串if length > 1:left_str = s[:length // 2]right_str = s[length // 2:]print(fbi(left_str), end='')print(fbi(right_str), end='')# 判断字符串是否全为0if all(char == '0' for char in s):return 'B'# 判断字符串是否全为1elif all(char == '1' for char in s):return 'I'return 'F'n = int(input())  # n:输入的整数N,表示后续输入字符串的长度相关信息
s = input()  # s:存储输入的字符串print(fbi(s), end='')

在这里插入图片描述


💐The End💐点点关注,收藏不迷路💐

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/462204.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

大数据新视界 -- 大数据大厂之数据质量管理全景洞察:从荆棘挑战到辉煌策略与前沿曙光

&#x1f496;&#x1f496;&#x1f496;亲爱的朋友们&#xff0c;热烈欢迎你们来到 青云交的博客&#xff01;能与你们在此邂逅&#xff0c;我满心欢喜&#xff0c;深感无比荣幸。在这个瞬息万变的时代&#xff0c;我们每个人都在苦苦追寻一处能让心灵安然栖息的港湾。而 我的…

基于 webpack 项目接入 vite 你可能需要注意的点

前言 在之前的 如何优化你的 vue-cli 项目&#xff1f; 一文中介绍基于 webpack 进行的一些优化方法&#xff0c;本文的核心是基于一个 vue2 的项目&#xff08;也就是上篇文章中的项目&#xff09;来继续介绍一下如何接入 vite&#xff0c;以及这个过程中需要关注的点。 之前…

Python工具箱系列(五十七)

图像分割与人脸识别 众所周知图像是由若干有意义的像素组成的&#xff0c;图像分割作为计算机视觉的基础&#xff0c;对具有现有目标和较精确边界的图像进行分割&#xff0c;实现在图像像素级别上的分类任务。图像分割可分为语义分割和实例分割两类&#xff0c;区别如下&#x…

日志代码编写

&#x1f30e;日志代码编写 文章目录&#xff1a; 日志代码编写 了解日志 日志编写       日志等级       获取时间信息       获取文件名行号及处理可变参数列表       以宏的形式传参       日志加锁       日志消息输出方式 完整代码 …

告别繁琐统计,一键掌握微信数据

微信数据管理的挑战在数字时代&#xff0c;微信已成为我们日常沟通和商业活动的重要工具。然而&#xff0c;随着微信号数量的增加&#xff0c;手动统计每个账号的数据变得越来越繁琐。从好友数量到会话记录&#xff0c;再到转账和红包&#xff0c;每一项都需要耗费大量的时间和…

【第几小】

题目 代码 //分块可以AC 20个点的块长&#xff0c; sqrt(n)*5#include<bits/stdc.h> using namespace std;int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int n; cin>>n;vector<int> a(n1,0);//分块int len sqrt(n)*5; //块长int k (n%len…

详细分析Pytorch中的transpose基本知识(附Demo)| 对比 permute

目录 前言1. 基本知识2. Demo 前言 原先的permute推荐阅读&#xff1a;详细分析Pytorch中的permute基本知识&#xff08;附Demo&#xff09; 1. 基本知识 transpose 是 PyTorch 中用于交换张量维度的函数&#xff0c;特别是用于二维张量&#xff08;矩阵&#xff09;的转置操…

使用Docker构建和部署微服务

&#x1f493; 博客主页&#xff1a;瑕疵的CSDN主页 &#x1f4dd; Gitee主页&#xff1a;瑕疵的gitee主页 ⏩ 文章专栏&#xff1a;《热点资讯》 [TOC] Docker 是一个开源的容器化平台&#xff0c;可以帮助开发者轻松构建、打包和部署应用程序。本文将详细介绍如何使用 Dock…

Python+Appium+Pytest+Allure自动化测试框架-代码篇

文章目录 自动化测试框架工程目录示例测试代码示例结果查看allurepytest编写pytest测试样例的规则pytest conftest.py向测试函数传参 appium启动appium服务代码端通过端口与appium服务通信对设备进行操作在pytest测试用例中调用appium 更多功能 PythonAppiumPytestAllure自动化…

Elasticsearch Interval 查询:为什么它们是真正的位置查询,以及如何从 Span 转换

作者&#xff1a;来自 Elastic Mayya Sharipova 解释 span 查询如何成为真正的位置查询以及如何从 span 查询过渡到它们。 长期以来&#xff0c;Span 查询一直是有序和邻近搜索的工具。这些查询对于特定领域&#xff08;例如法律或专利搜索&#xff09;尤其有用。但相对较新的 …

IoTDB时序数据库使用

简介 Apache IoTDB 是一款低成本、高性能的物联网原生时序数据库。它可以解决企业组建物联网大数据平台管理时序数据时所遇到的应用场景复杂、数据体量大、采样频率高、数据乱序多、数据处理耗时长、分析需求多样、存储与运维成本高等多种问题。 IoTDB官网 1. 连接数据库 官方…

河北冠益荣信科技公司洞庭变电站工程低压备自投装置的应用

摘 要&#xff1a;随着电力需求增长&#xff0c;供电可靠性变得至关重要&#xff0c;许多系统已有多回路供电。备用电源自动投入装置能提升供电可靠性&#xff0c;它能在主电源故障时迅速切换到备用电源。本文介绍的AM5-DB低压备自投装置&#xff0c;为洞庭变电站提供多种供电方…

STM32实现IAP串口升级含源码(HAL库)

文章目录 一. 关于IAP升级二. IAP升级的分类二. IAP升级原理2.1 正常启动流程2.2 IAP启动流程 三. Ymodem协议3.1 传输过程3.2 帧命令3.3 起始帧3.4 数据帧3.5 结束帧 四. IAP代码实现4.1 Boot 程序4.2 App 程序4.3 展示效果 五. Demo源码六. Qt 上位机 一. 关于IAP升级 IAP&am…

【Hello World 】

【Hello World 】! C语言实现C实现Java实现Python实现 &#x1f490;The Begin&#x1f490;点点关注&#xff0c;收藏不迷路&#x1f490; 几乎每一个程序员都是从Hello World!开始自己的程序人生&#xff0c;作为一个初学编程的小朋友&#xff0c;也需要先编程来输出Hello Wo…

LabVIEW程序员赚钱不仅限于上班

LabVIEW程序员拥有多种途径来实现财富增值&#xff0c;而不仅仅局限于传统的全职工作。以下是一些他们可以利用自身技能和专业知识实现更高财务收益的方法&#xff1a; 1. 专注领域的自由职业与合同工作 制造、科研、医疗技术等行业都需要LabVIEW的专业知识。通过自由职业&…

vue3项目中el-tooltip实现内容溢出时再显示,并设置tip的最大宽度

html代码 <el-tooltip :disabled"!textIsOverflow" placement"top"><template #content><div class"tooltip-div">tootip的内容</div></template><div class"textOverflow" ref"textRef"…

文案语音图片视频管理分析系统-视频矩阵

文案语音图片视频管理分析系统-视频矩阵 1.产品介绍 产品介绍方案 产品名称&#xff1a; 智驭视频矩阵深度分析系统&#xff08;SmartVMatrix&#xff09; 主要功能&#xff1a; 深度学习驱动的视频内容分析多源视频整合与智能分类高效视频检索与编辑实时视频监控与异常预警…

HTML 基础标签——分组标签 <div>、<span> 和基础语义容器

文章目录 1. `<div>` 标签特点用途示例2. `<span>` 标签特点用途示例3. `<fieldset>` 标签特点用途示例4. `<section>` 标签特点用途示例5. `<article>` 标签特点用途示例总结HTML中的分组(容器)标签用于结构化内容,将页面元素组织成逻辑区域…

安防被动红外和主动红外

被动红外探测器是依靠被动的吸收热能动物活动时身体散发出的红外热能进行报警的&#xff0c;也称热释红外探头&#xff0c;其探测器本身是不会发射红外线的。 被动红外探测器中有2个关键性元件&#xff0c;一个是菲涅尔透镜&#xff0c;另一个是热释电传感器。**自然界中任何高…

Windows下将网盘挂载到本地使用(Docker+AList+RaiDrive)

文章目录 安装安装Docker安装Alist安装RaiDrive 安装 安装Docker Windows下安装Docker网上有很多教程&#xff0c;也可以参考我写的博客链接 3.1章节 安装Alist 官网 “切换中文”并找到“使用指南” ”安装“–>"使用Docker” 打开cmd执行如下命令启动容器 do…