PAT 甲级1005【1005 Spell It Right】

这篇具有很好参考价值的文章主要介绍了PAT 甲级1005【1005 Spell It Right】。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

用JAVA可以用BigInteger解决。

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.HashMap;
import java.util.Map;

public class Main {
    @SuppressWarnings("unchecked")
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BigInteger big = new BigInteger(br.readLine());
        int sum = 0;

        BigInteger x = big.add(BigInteger.ZERO);
        while (x.compareTo(BigInteger.ZERO) > 0) {
            int digit = x.mod(BigInteger.valueOf(10l)).intValue();
            sum += digit;
            x = x.divide(BigInteger.valueOf(10l));
        }

        Map<Integer, String> map = new HashMap<>();
        map.put(0, "zero");
        map.put(1, "one");
        map.put(2, "two");
        map.put(3, "three");
        map.put(4, "four");
        map.put(5, "five");
        map.put(6, "six");
        map.put(7, "seven");
        map.put(8, "eight");
        map.put(9, "nine");

        String str = String.valueOf(sum);

        for (int j = 0; j < str.length(); j++) {
            int digit = str.charAt(j) - '0';
            if( j != 0){
                System.out.print(" ");
            }
            System.out.print(map.get(digit));
        }
        System.out.println();

        br.close();
    }

}

  

 

 

高精度计算

太长不看版:结尾自取模板……

定义

高精度计算(Arbitrary-Precision Arithmetic),也被称作大整数(bignum)计算,运用了一些算法结构来支持更大整数间的运算(数字大小超过语言内建整型)。

引入

高精度问题包含很多小的细节,实现上也有很多讲究。

所以今天就来一起实现一个简单的计算器吧。

任务

输入:一个形如 a <op> b 的表达式。

  • ab 分别是长度不超过 PAT 甲级1005【1005 Spell It Right】 的十进制非负整数;
  • <op> 是一个字符(+-* 或 /),表示运算。
  • 整数与运算符之间由一个空格分隔。

输出:运算结果。

  • 对于 +-* 运算,输出一行表示结果;
  • 对于 / 运算,输出两行分别表示商和余数。
  • 保证结果均为非负整数。

存储

在平常的实现中,高精度数字利用字符串表示,每一个字符表示数字的一个十进制位。因此可以说,高精度数值计算实际上是一种特别的字符串处理。

读入字符串时,数字最高位在字符串首(下标小的位置)。但是习惯上,下标最小的位置存放的是数字的 最低位,即存储反转的字符串。这么做的原因在于,数字的长度可能发生变化,但我们希望同样权值位始终保持对齐(例如,希望所有的个位都在下标 [0],所有的十位都在下标 [1]……);同时,加、减、乘的运算一般都从个位开始进行(回想小学的竖式运算),这都给了「反转存储」以充分的理由。

此后我们将一直沿用这一约定。定义一个常数 LEN = 1004 表示程序所容纳的最大长度。

由此不难写出读入高精度数字的代码:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
void clear(int a[]) {
  for (int i = 0; i < LEN; ++i) a[i] = 0;
}

void read(int a[]) {
  static char s[LEN + 1];
  scanf("%s", s);

  clear(a);

  int len = strlen(s);
  // 如上所述,反转
  for (int i = 0; i < len; ++i) a[len - i - 1] = s[i] - '0';
  // s[i] - '0' 就是 s[i] 所表示的数码
  // 有些同学可能更习惯用 ord(s[i]) - ord('0') 的方式理解
}

输出也按照存储的逆序输出。由于不希望输出前导零,故这里从最高位开始向下寻找第一个非零位,从此处开始输出;终止条件 i >= 1 而不是 i >= 0 是因为当整个数字等于 PAT 甲级1005【1005 Spell It Right】 时仍希望输出一个字符 0

1
2
3
4
5
6
7
void print(int a[]) {
  int i;
  for (i = LEN - 1; i >= 1; --i)
    if (a[i] != 0) break;
  for (; i >= 0; --i) putchar(a[i] + '0');
  putchar('\n');
}

拼起来就是一个完整的复读机程序咯。

copycat.cpp

   

四则运算

四则运算中难度也各不相同。最简单的是高精度加减法,其次是高精度—单精度(普通的 int)乘法和高精度—高精度乘法,最后是高精度—高精度除法。

我们将按这个顺序分别实现所有要求的功能。

加法

高精度加法,其实就是竖式加法啦。

也就是从最低位开始,将两个加数对应位置上的数码相加,并判断是否达到或超过 PAT 甲级1005【1005 Spell It Right】。如果达到,那么处理进位:将更高一位的结果上增加 PAT 甲级1005【1005 Spell It Right】,当前位的结果减少 PAT 甲级1005【1005 Spell It Right】

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
void add(int a[], int b[], int c[]) {
  clear(c);

  // 高精度实现中,一般令数组的最大长度 LEN 比可能的输入大一些
  // 然后略去末尾的几次循环,这样一来可以省去不少边界情况的处理
  // 因为实际输入不会超过 1000 位,故在此循环到 LEN - 1 = 1003 已经足够
  for (int i = 0; i < LEN - 1; ++i) {
    // 将相应位上的数码相加
    c[i] += a[i] + b[i];
    if (c[i] >= 10) {
      // 进位
      c[i + 1] += 1;
      c[i] -= 10;
    }
  }
}

试着和上一部分结合,可以得到一个加法计算器。

adder.cpp

   

减法

高精度减法,也就是竖式减法啦。

从个位起逐位相减,遇到负的情况则向上一位借 PAT 甲级1005【1005 Spell It Right】。整体思路与加法完全一致。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
void sub(int a[], int b[], int c[]) {
  clear(c);

  for (int i = 0; i < LEN - 1; ++i) {
    // 逐位相减
    c[i] += a[i] - b[i];
    if (c[i] < 0) {
      // 借位
      c[i + 1] -= 1;
      c[i] += 10;
    }
  }
}

将上一个程序中的 add() 替换成 sub(),就有了一个减法计算器。

subtractor.cpp

   

试一试,输入 1 2——输出 /9999999,诶这个 OI Wiki 怎么给了我一份假的代码啊……

事实上,上面的代码只能处理减数 PAT 甲级1005【1005 Spell It Right】 大于等于被减数 PAT 甲级1005【1005 Spell It Right】 的情况。处理被减数比减数小,即 PAT 甲级1005【1005 Spell It Right】 时的情况很简单。

PAT 甲级1005【1005 Spell It Right】

要计算 PAT 甲级1005【1005 Spell It Right】 的值,因为有 PAT 甲级1005【1005 Spell It Right】,可以调用以上代码中的 sub 函数,写法为 sub(b,a,c)。要得到 PAT 甲级1005【1005 Spell It Right】 的值,在得数前加上负号即可。

乘法

高精度—单精度

高精度乘法,也就是竖……等会儿等会儿!

先考虑一个简单的情况:乘数中的一个是普通的 int 类型。有没有简单的处理方法呢?

一个直观的思路是直接将 PAT 甲级1005【1005 Spell It Right】 每一位上的数字乘以 PAT 甲级1005【1005 Spell It Right】。从数值上来说,这个方法是正确的,但它并不符合十进制表示法,因此需要将它重新整理成正常的样子。

重整的方式,也是从个位开始逐位向上处理进位。但是这里的进位可能非常大,甚至远大于 PAT 甲级1005【1005 Spell It Right】,因为每一位被乘上之后都可能达到 PAT 甲级1005【1005 Spell It Right】 的数量级。所以这里的进位不能再简单地进行 PAT 甲级1005【1005 Spell It Right】 运算,而是要通过除以 PAT 甲级1005【1005 Spell It Right】 的商以及余数计算。详见代码注释,也可以参考下图展示的一个计算高精度数 PAT 甲级1005【1005 Spell It Right】 乘以单精度数 PAT 甲级1005【1005 Spell It Right】 的过程。

当然,也是出于这个原因,这个方法需要特别关注乘数 PAT 甲级1005【1005 Spell It Right】 的范围。若它和 PAT 甲级1005【1005 Spell It Right】(或相应整型的取值上界)属于同一数量级,那么需要慎用高精度—单精度乘法。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
void mul_short(int a[], int b, int c[]) {
  clear(c);

  for (int i = 0; i < LEN - 1; ++i) {
    // 直接把 a 的第 i 位数码乘以乘数,加入结果
    c[i] += a[i] * b;

    if (c[i] >= 10) {
      // 处理进位
      // c[i] / 10 即除法的商数成为进位的增量值
      c[i + 1] += c[i] / 10;
      // 而 c[i] % 10 即除法的余数成为在当前位留下的值
      c[i] %= 10;
    }
  }
}

高精度—高精度

如果两个乘数都是高精度,那么竖式乘法又可以大显身手了。

回想竖式乘法的每一步,实际上是计算了若干 PAT 甲级1005【1005 Spell It Right】 的和。例如计算 PAT 甲级1005【1005 Spell It Right】,计算的就是 PAT 甲级1005【1005 Spell It Right】

于是可以将 PAT 甲级1005【1005 Spell It Right】 分解为它的所有数码,其中每个数码都是单精度数,将它们分别与 PAT 甲级1005【1005 Spell It Right】 相乘,再向左移动到各自的位置上相加即得答案。当然,最后也需要用与上例相同的方式处理进位。

注意这个过程与竖式乘法不尽相同,我们的算法在每一步乘的过程中并不进位,而是将所有的结果保留在对应的位置上,到最后再统一处理进位,但这不会影响结果。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
void mul(int a[], int b[], int c[]) {
  clear(c);

  for (int i = 0; i < LEN - 1; ++i) {
    // 这里直接计算结果中的从低到高第 i 位,且一并处理了进位
    // 第 i 次循环为 c[i] 加上了所有满足 p + q = i 的 a[p] 与 b[q] 的乘积之和
    // 这样做的效果和直接进行上图的运算最后求和是一样的,只是更加简短的一种实现方式
    for (int j = 0; j <= i; ++j) c[i] += a[j] * b[i - j];

    if (c[i] >= 10) {
      c[i + 1] += c[i] / 10;
      c[i] %= 10;
    }
  }
}

除法

高精度除法的一种实现方式就是竖式长除法。

竖式长除法实际上可以看作一个逐次减法的过程。例如上图中商数十位的计算可以这样理解:将 PAT 甲级1005【1005 Spell It Right】 减去三次 PAT 甲级1005【1005 Spell It Right】 后变得小于 PAT 甲级1005【1005 Spell It Right】,不能再减,故此位为 PAT 甲级1005【1005 Spell It Right】

为了减少冗余运算,我们提前得到被除数的长度 PAT 甲级1005【1005 Spell It Right】 与除数的长度 PAT 甲级1005【1005 Spell It Right】,从下标 PAT 甲级1005【1005 Spell It Right】 开始,从高位到低位来计算商。这和手工计算时将第一次乘法的最高位与被除数最高位对齐的做法是一样的。

参考程序实现了一个函数 greater_eq() 用于判断被除数以下标 last_dg 为最低位,是否可以再减去除数而保持非负。此后对于商的每一位,不断调用 greater_eq(),并在成立的时候用高精度减法从余数中减去除数,也即模拟了竖式除法的过程。文章来源地址https://www.toymoban.com/news/detail-711392.html

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
// 被除数 a 以下标 last_dg 为最低位,是否可以再减去除数 b 而保持非负
// len 是除数 b 的长度,避免反复计算
bool greater_eq(int a[], int b[], int last_dg, int len) {
  // 有可能被除数剩余的部分比除数长,这个情况下最多多出 1 位,故如此判断即可
  if (a[last_dg + len] != 0) return true;
  // 从高位到低位,逐位比较
  for (int i = len - 1; i >= 0; --i) {
    if (a[last_dg + i] > b[i]) return true;
    if (a[last_dg + i] < b[i]) return false;
  }
  // 相等的情形下也是可行的
  return true;
}

void div(int a[], int b[], int c[], int d[]) {
  clear(c);
  clear(d);

  int la, lb;
  for (la = LEN - 1; la > 0; --la)
    if (a[la - 1] != 0)

到了这里,关于PAT 甲级1005【1005 Spell It Right】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 1028 List Sorting (PAT甲级)

    Excel can sort records according to any column. Now you are supposed to imitate this function. Input Specification: Each input file contains one test case. For each case, the first line contains two integers N (≤105) and C, where N is the number of records and C is the column that you are supposed to sort the records with. Then N lines follow, eac

    2024年02月15日
    浏览(40)
  • 1072 Gas Station (PAT甲级)

    A gas station has to be built at such a location that the minimum distance between the station and any of the residential housing is as far away as possible. However it must guarantee that all the houses are in its service range. Now given the map of the city and several candidate locations for the gas station, you are supposed to give the best recommendatio

    2024年02月09日
    浏览(41)
  • 菜鸟记录PAT甲级1003--Emergency

    久违的PAT,由于考研408数据结构中有一定需要,同时也是对先前所遗留的竞赛遗憾进行一定弥补 ,再次继续PAT甲级1003.。 As an emergency rescue team leader of a city, you are given a special map of your country. The map shows several scattered cities connected by some roads. Amount of rescue teams in each city and the l

    2023年04月13日
    浏览(42)
  • 1111 Online Map (PAT甲级)

    这道题我读题不仔细导致踩了个大坑,一个测试点过不了卡了好几个小时:第二个dijkstra算法中,题目要求是“In case the fastest path is not unique, output the one that passes through the fewest intersections”,我却想当然地认为在fastest path is not unique的时候,判断标准是最短距离…… Input our

    2024年02月07日
    浏览(42)
  • pat甲级 1022 Digital Library

    A Digital Library contains millions of books, stored according to their titles, authors, key words of their abstracts, publishers, and published years. Each book is assigned an unique 7-digit number as its ID. Given any query from a reader, you are supposed to output the resulting books, sorted in increasing order of their ID\\\'s. Input Specification: Each inp

    2024年04月15日
    浏览(35)
  • 1114 Family Property (PAT甲级)

    This time, you are supposed to help us collect the data for family-owned property. Given each person\\\'s family members, and the estate(房产)info under his/her own name, we need to know the size of each family, and the average area and number of sets of their real estate. Input Specification: Each input file contains one test case. For each case, the fir

    2024年02月06日
    浏览(49)
  • 1083 List Grades (PAT甲级)

    Given a list of N student records with name, ID and grade. You are supposed to sort the records with respect to the grade in non-increasing order, and output those student records of which the grades are in a given interval. Input Specification: Each input file contains one test case. Each case is given in the following format: where  name[i]  and  ID[i

    2024年02月08日
    浏览(48)
  • PAT甲级图论相关题目

    PAT甲级图论相关题目: 分数 25 As an emergency rescue team leader of a city, you are given a special map of your country. The map shows several scattered cities connected by some roads. Amount of rescue teams in each city and the length of each road between any pair of cities are marked on the map. When there is an emergency call to you from some o

    2024年01月21日
    浏览(52)
  • 1021 Deepest Root (PAT甲级)

    1021. Deepest Root (25)-PAT甲级真题(图的遍历,dfs,连通分量的个数)_柳婼的博客-CSDN博客 柳婼的解法在这里,两次dfs,还是挺好玩的。 我的解法比较暴力,就是先用并查集算连通分量(这个其实还是dfs来算会更方便),如果只有一个连通分量,那deepest root一定在仅有一条arc的

    2024年02月15日
    浏览(32)
  • PAT 甲级【1007 Maximum Subsequence Sum】

    本题是考察动态规划与java的快速输入: max[i]表示第i个结尾的最大的连续子串和。b begin[i]表示第[begin[i],i]为最大和的开始位置 超时代码: 未超时: 能用动态规划解决的问题,需要满足三个条件:最优子结构,无后效性和子问题重叠。 具有最优子结构也可能是适合用贪心的

    2024年02月08日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包