数字反转 NOIp普及组2011

栏目: IT技术 · 发布时间: 4年前

内容简介:当本文为使用右侧目录快速浏览文章

数字位数不确定 时,如何反转呢?

本文为 博客园ShyButHandsome 原创作品,转载请注明出处

使用右侧目录快速浏览文章

题目描述

给定一个整数,请将该数各个位上数字反转得到一个新数。

新数也应满足整数的常见形式,即 除非给定的原数为零,否则反转后得到的新数的最高位数字不应为零

输入格式

一个整数 \(N\)

输出格式

一个整数,表示反转后的新数。

说明/提示

\(-1,000,000,000 \leq N \leq 1,000,000,000\)

分析

这题虽然给出了 \(N\) 的范围,但 并没有给出确定的位数

没有说是一位数、两位数或者是三位数

如果给出位数那倒好办了 int hun, ten, sig 一气呵成

(可以将给出位数的每一位都用一个变量来储存,实在不行开个数组)

假如没有给出范围,你不知道该开多大的数组, 怎么办?

  • 方法一:给他一个无法拒绝的理由

    注:"给他一个无法拒绝的理由"——《教父》中的"经典台词"

    既然我不知道开多大,那我就使劲开咯

    开一个超级大的数组,每一个元素对应一位

    如: int very_very_big[9999999] // 记得开在函数外

    但这样就造成了 "假想无穷大"

    真遇上奇葩数据得凉

  • 方法二:"临时"和"总"

    使用一个变量临时地储存每一位

    然后 在循环外定义一个变量 用来累加(累乘)

    只要每次在存入当前这位数时

    将这个 定义在循环外的变量 \(\times 10\)

    来腾出一个 "个位" 给当前这位数就可以了

    比如:

    现在给你一个数(这是一个数,我用空格分开了每一位,方便观察)

\[ 3 \quad \color{red}{\huge 4} \]

int new_num = 0;
        now = 4;
        new_num = new_num * 10 + now         // new_num = 0 * 10 + 4 = 4

\[ \color{red}{\huge 4} \]

\[ \color{red}{\huge 3} \quad 4 \]

now = 3;
        new_num = 4 * 10 + 3;

\[ 4 \quad \color{red}{\huge 3} \]

但,似乎还有个问题

我不知道有多少位数,那我的循环怎么结束?

遇到循环次数不确定时

我们首先要考虑 while() 循环

但无论是什么循环,都需要找到一个跳出循环的条件

那,什么样的条件合适呢?

标志 flag ,就是一个合适的条件

flag 无特殊含义

当达到临界条件时,这个 flag 会改变

flag 就两种类型 true or flase

不要去关注它的值

  • 比如:

    • \(1\)\(9\)

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

    i > 9 时, flag 倒下,条件不成立

你乍一看可能觉得我这是废话,其实不然

只是这种计时器类型的临界条件比较好找罢了

你不用去找别的,答案十分明确

但,别的类型呢?

关键就是要找,达到成你目的时会变化的 flag

就像CE找地址

CE: Cheat Engine的缩写,一款非常优秀的内存地址查找软件

你通过不断改变值,总能找到你想要的那个地址

CE 这里的 flag 就是 随着值变动而变动为正确值

比如:

- 你把那个值改为了 \(123\)

- 地址列表中没有改变的值、或者变化后值不是

\(123\)

的值就会被剔除

不满足条件则出局 out

这是排除法

好的,那么问题来了

现在给你一个数(这是一个数,我用空格分开了每一位,方便观察)

\[1 \quad 2 \quad 3 \quad 4 \quad 5 \quad 6 \quad 7 \quad 8 \quad \color{red}{\huge 9} \]

现在位数是 \(9\)

指向 \(9\)

\(9\)\(1\)

\(1\)\(9\)

每次到最高位/最低位的距离都在变化

那只要让距离最高位/最低位的距离一定

就改变了 距离到最高位/最低位的距离改变 这个 flag

欸,别忘了前导零的存在!

这玩意你加多少个都没问题

而当你指向前导零时

你到最高位/最低位的距离都是不变的

欧耶!条件找到了!

最终指向前导零的时候就是到达了最高位

可是问题又来了,这个 指向每一位的操作怎么模拟?

指向每一位的操作可以 /10%10 来模拟

对一个 整形 /10 可以减少一位

%10 可以取出最低位

特别说明: %

根据在 C++ 中取余运算的定义:

如果 \(m\)\(n\) 是整数且 \(n \neq 0\)

则表达式 \((m/n)*n + m%n\) 的运算结果与 \(m\) 相等

隐含的意思是:如果 \(m%n \neq 0\) ,则它的符号与 \(m\) 相同。

除了 \(-m\) 导致的溢出的特殊情况外,

其他时候

m % (-n) = m % n
(-m) % n = -(m % n)

也就是说,你可以不用担心负数的问题了

那,如何指向一位位地指向前导零呢?

因为每次 /10 距离都会减少一位

所以当数字长度不断减小直到为 \(0\) 时,此时指向前导零

即,已经从低到高一位位地遍历了整个数

任务完成,退出循环!

代码实现

// 来源:自己写的
// 作者:@ShyButHandsome
#include<bits/stdc++.h>
using namespace std;

int main(void)
{
    long long num;
    cin >> num;
    
    long long new_num = 0;
    int n = 1;
    
    int count = 0;
    while(num)
    {
        int each_bit = num % 10;
        new_num = new_num * 10 + each;
        num /= 10;
    }
    
    cout << new_num;
    
    return 0;
}

总结

这样思考下来

我们收获了什么?

  1. 将一个定义域内变量累加到定义域外的思想
  2. flag 的选择
  3. % 的使用和 / 一样,是带号的

参考资料

《C++ Primer》

我是ShyButHandsome,一个名字与实际截然相反的OI蒟蒻,如果你觉得这篇文章写的还行的话,不妨点点推荐?


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

The Everything Store

The Everything Store

Brad Stone / Little, Brown and Company / 2013-10-22 / USD 28.00

The definitive story of Amazon.com, one of the most successful companies in the world, and of its driven, brilliant founder, Jeff Bezos. Amazon.com started off delivering books through the mail. Bu......一起来看看 《The Everything Store》 这本书的介绍吧!

随机密码生成器
随机密码生成器

多种字符组合密码

Base64 编码/解码
Base64 编码/解码

Base64 编码/解码

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具