基础算法--高精度数据(2)

2024-08-24 16:52
文章标签 算法 基础 数据 高精度

本文主要是介绍基础算法--高精度数据(2),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

本节继续上节内容:高精度数据处理。本节主题是回文数。

一、判断方法

什么是回文数:一个数字从左往右读与从右往左读是一样的,那么这个数就是回文数。例如:121,6226,3333、12121等。简单的判断回文数的方式有很多,第一种:字符串存储,逆置判断是否相等;第二种,求取数位,折半循环,每次将最左面与最右面的数值进行比较,如果有一次不等,那这就不是回文数。

代码如下:

将数字转化为字符串(利用现成的函数),然后将逆置字符串与原字符串进行比较

//转成字符串
bool isHWS(int n){string st = to_string(n);string str=st;//将正序数据存下reverse(st.begin(),st.end());//逆序if(str==st)return true;//如果逆序后还与逆序前相等,就返回truereturn false;
}

 将数字的每一位放在数组中维护,后期设置左右指针(两个变量,表示相对位置)向中间逼近判断

//两边往中间夹判断
bool isHWS(int n){vector<int> v;while(n!=0){v.push_back(n%10);//取末尾存储n/10;//取掉的数位丢弃}int length=v.size();//代表数有多少位int i=0,j=length-1;for(;i<=j;i++,j--){if(v[i]!=v[j])return false;}return true;
}

二、主讲内容

题目要求

本节题目: 信息学奥赛一本通(C++版)在线评测系统 (ssoier.cn)

【题目描述】:

若一个数(首位不为零)从左向右读与从右向左读都是一样,我们就将其称之为回文数。例如:给定一个 10进制数 56,将 56加 65(即把56从右向左读),得到 121是一个回文数。又如,对于10进制数87:

STEP1: 87+78= 165 STEP2: 165+561= 726

STEP3: 726+627=1353 STEP4:1353+3531=4884

在这里的一步是指进行了一次N进制的加法,上例最少用了4步得到回文数4884。

写一个程序,给定一个N(2<N<=10或N=16)进制数 M.求最少经过几步可以得到回文数。如果在30步以内(包含30步)不可能得到回文数,则输出“Impossible” 。

【输入】:

第1行,给定一个N(2<N≤10或N=16)表示进制;

第2行,一个N进制数M。

【输出】:

最少几步。如果在30步以内(包含30步)不可能得到回文数,则输出“Impossible”。

题目分析

进制:C语言的操作符-CSDN博客 (在这里,我曾经讲过进制的知识,大家可以回去看一下)。

这里,我们最多可以包含30步回文数化的操作,随着次数的增多,得到的数字对的位数也越多,如果只使用int和long long类型的数据恐怕有些不妥,而且为了培训大家对高精度数据的处理方法,本节要求使用数组维护数位进行解答(貌似用整型家族的数据类型存储都不能保证全部测试用例通过,没试过)。

来吧,正式编码来了,让我们进行编码四部曲

第一步:搭建主函数

将必要的变量维护在全局区,真的真的特别的方便。为了不让我们在一个数组内进行各种操作,我们建立一个镜像数组,用来代表数字逆置后,数字的数位情况。由于题意要求最多30步,我们定义一个变量记录步数。

我们的逻辑就是:初始化数据,按照题目要求输入数据,并根据合适的方法进行处理,放入合适的变量进行维护。然后进行循环,每次循环走一步回文化操作,操作结束我们需要判断当前数字是否是回文数字,如果是就输出当前的 步数,然后结束循环就ok了。如果外层循环30次还不是回文数,按照题意输出不可能就行了。

#include <bits/stdc++.h>
using namespace std;const long long limit = 1e9;
int X;//X代表进制数 2~10 / 16
int M_numbers[limit];//X进制数m
int Mirroring[limit];//镜像
int length;//当前数字位数-长度
int step_cnt;//记录步数int main() {init();while (step_cnt < 30) {step();//进行一次回文化操作if (isEnd()) {//如果成了,结束cout << step_cnt << endl;return 0;}}cout << "Impossible" << endl;return 0;
}
第二步:初始化数据 

之后我就把思路逻辑写到代码中了,方便大家对照理解。

void init() {cin >> X;//输入进制数string m; cin >> m;//先用字符串存下数字length = m.size();//计算初始长度for (int i = 0; i < length; i++) {//循环放入数位数组//考虑到题目中有说明,进制数可能是16进制//16进制的特点就是:0123456789ABCDEF代表0-15,也就是会存在字符代表数字的情况//为此需要进行条件判断if ('0' <= m[i] && m[i] <= '9')Mirroring[i + 1] = m[i] - '0';//如果是数字,那么就将将数字字符放入数组else  Mirroring[i + 1] = m[i] - 'A' + 10;//如果是A,则‘A’-‘A’+10=10;如果是B,则‘B’-‘A’+10=11//悟了嘛M_numbers[length - i] = Mirroring[i + 1];//将镜像数组的存的数字倒着放到原数组中}
}
 第三步:判断回文数

为什么我们不先写核心过程,而是先写如何判断回文数。因为简单,哈哈,不管中间怎么变,我们前面的工作做完之后,就已经确定了判断的条件与方式了。

我们本题为了维护数位和逆置数位多建立了一个镜像数组,只要判断这两个数组元素是否相等就可以了。其实循环条件终止可以写成i<=length/2+1(+1是为了保险起见),如果中间遇到不相等的,返回false代表不是回文数,不结束。循环截止都没有返回说明各个位置都满足条件了,那么我就可以返回true,告诉主函数可以结束了。

bool isEnd() {//如果是回文数,true,结束for (int i = 1; i <= length; i++) {if (M_numbers[i] != Mirroring[i])return false;//不回文了已经}return true;
}
第四步:写核心步骤

 每次我们都要从第一位个位开始加起,初始时没有进位信息,设置为0即可,当前位置的数字也设为0,在循环内部进行更新即可。

当前位置应该留下的数字number=两个数各位相加后对进制X取余的结果

当前位置下一位的进位数Output=两个数各位相加后对进制数X相除的结果

将进位加到下一位中,进行过操作的数位信息在原数组中进行修改,依次进行。

完毕之后看看最高位的数字top是否还能进位,如果不能不要管,如果能,需要额外加一位有效空间存储数位。

然后将镜像数组进行更新。最后步骤走一步+1。

void step() {int cur_idx = 1;//从第一位开始加int Output = 0;//当前位进位信息int number = 0;//当前位取余数据while (cur_idx <= length) {number = (M_numbers[cur_idx] + Mirroring[cur_idx]) % X;//余位=(a+b+进位数)%XOutput = (M_numbers[cur_idx] + Mirroring[cur_idx]) / X;//进位数=(a+b)/进制数M_numbers[cur_idx + 1] += Output;M_numbers[cur_idx] = number;++cur_idx;//下一位}if (M_numbers[cur_idx] > 0)length++;//更新镜像数组:for (int i = 1; i <= length; i++) {Mirroring[i] = M_numbers[length + 1 - i];}++step_cnt;//步数加一
}

三、参考答案

#include <bits/stdc++.h>
using namespace std;
#define Long long longint X;//X代表进制数 2~10 / 16
int M_numbers[35];//X进制数m
int Mirroring[35];//镜像
int length;//当前数字位数-长度
int step_cnt;//记录步数void init() {cin >> X;string m; cin >> m;length = m.size();for (int i = 0; i < length; i++) {if ('0' <= m[i] && m[i] <= '9')Mirroring[i + 1] = m[i] - '0';else  Mirroring[i + 1] = m[i] - 'A' + 10;M_numbers[length - i] = Mirroring[i + 1];}
}
void step() {int cur_idx = 1;//从第一位开始加int Output = 0;//当前位进位信息int number = 0;//当前位取余数据while (cur_idx <= length) {number = (M_numbers[cur_idx] + Mirroring[cur_idx]) % X;//余位=(a+b+进位数)%XOutput = (M_numbers[cur_idx] + Mirroring[cur_idx]) / X;//进位数=(a+b)/进制数M_numbers[cur_idx + 1] += Output;M_numbers[cur_idx] = number;++cur_idx;//下一位}if (M_numbers[cur_idx] > 0)length++;//更新镜像数组:for (int i = 1; i <= length; i++) {Mirroring[i] = M_numbers[length + 1 - i];}++step_cnt;//步数加一
}bool isEnd() {//如果是回文数,true,结束for (int i = 1; i <= length; i++) {if (M_numbers[i] != Mirroring[i])return false;//不回文了已经}return true;
}int main() {init();while (step_cnt < 30) {step();//进行一次回文化操作if (isEnd()) {//如果成了,结束cout << step_cnt << endl;return 0;}}cout << "Impossible" << endl;return 0;
}

 

 


难吗?没有吧。初始化数据不知道吗?也许你只是差一点思路,不知道怎么维护而已,但上节我们讲了,这节也讲了,下次你还不会吗?不能吧。如何判断回文数不会吗?这么简单的对称判断问题而已。核心步骤之所以称之为核心步骤,是因为最后的结果是由这个步骤进行决定的,每一次的数据变化都是有规律可以寻找的,我们习惯了十进制,我们写个X进制的,不管写没写出来,那这就是进步。你比那些只看不动手的人强多了。

这篇关于基础算法--高精度数据(2)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

大模型研发全揭秘:客服工单数据标注的完整攻略

在人工智能(AI)领域,数据标注是模型训练过程中至关重要的一步。无论你是新手还是有经验的从业者,掌握数据标注的技术细节和常见问题的解决方案都能为你的AI项目增添不少价值。在电信运营商的客服系统中,工单数据是客户问题和解决方案的重要记录。通过对这些工单数据进行有效标注,不仅能够帮助提升客服自动化系统的智能化水平,还能优化客户服务流程,提高客户满意度。本文将详细介绍如何在电信运营商客服工单的背景下进行

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

基于MySQL Binlog的Elasticsearch数据同步实践

一、为什么要做 随着马蜂窝的逐渐发展,我们的业务数据越来越多,单纯使用 MySQL 已经不能满足我们的数据查询需求,例如对于商品、订单等数据的多维度检索。 使用 Elasticsearch 存储业务数据可以很好的解决我们业务中的搜索需求。而数据进行异构存储后,随之而来的就是数据同步的问题。 二、现有方法及问题 对于数据同步,我们目前的解决方案是建立数据中间表。把需要检索的业务数据,统一放到一张M

关于数据埋点,你需要了解这些基本知识

产品汪每天都在和数据打交道,你知道数据来自哪里吗? 移动app端内的用户行为数据大多来自埋点,了解一些埋点知识,能和数据分析师、技术侃大山,参与到前期的数据采集,更重要是让最终的埋点数据能为我所用,否则可怜巴巴等上几个月是常有的事。   埋点类型 根据埋点方式,可以区分为: 手动埋点半自动埋点全自动埋点 秉承“任何事物都有两面性”的道理:自动程度高的,能解决通用统计,便于统一化管理,但个性化定

使用SecondaryNameNode恢复NameNode的数据

1)需求: NameNode进程挂了并且存储的数据也丢失了,如何恢复NameNode 此种方式恢复的数据可能存在小部分数据的丢失。 2)故障模拟 (1)kill -9 NameNode进程 [lytfly@hadoop102 current]$ kill -9 19886 (2)删除NameNode存储的数据(/opt/module/hadoop-3.1.4/data/tmp/dfs/na

异构存储(冷热数据分离)

异构存储主要解决不同的数据,存储在不同类型的硬盘中,达到最佳性能的问题。 异构存储Shell操作 (1)查看当前有哪些存储策略可以用 [lytfly@hadoop102 hadoop-3.1.4]$ hdfs storagepolicies -listPolicies (2)为指定路径(数据存储目录)设置指定的存储策略 hdfs storagepolicies -setStoragePo

Hadoop集群数据均衡之磁盘间数据均衡

生产环境,由于硬盘空间不足,往往需要增加一块硬盘。刚加载的硬盘没有数据时,可以执行磁盘数据均衡命令。(Hadoop3.x新特性) plan后面带的节点的名字必须是已经存在的,并且是需要均衡的节点。 如果节点不存在,会报如下错误: 如果节点只有一个硬盘的话,不会创建均衡计划: (1)生成均衡计划 hdfs diskbalancer -plan hadoop102 (2)执行均衡计划 hd

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖