当前位置:   article > 正文

PTA 02-线性结构2 一元多项式的乘法与加法运算_给你两个一元多项式,输出这两个一元多项式的乘积。输入格式输入包含两行,每行一个

给你两个一元多项式,输出这两个一元多项式的乘积。输入格式输入包含两行,每行一个

设计函数分别求两个一元多项式的乘积与和。

输入格式:输入分2行,每行分别先给出多项式非零项的个数,再以指数递降方式输入一个多项式非零项系数和指数(绝对值均为不超过1000的整数)。数字间以空格分隔。

输出格式:输出分2行,分别以指数递降方式输出乘积多项式以及和多项式非零项的系数和指数。数字间以空格分隔,但结尾不能有多余空格。零多项式应输出0 0。

输入样例:
4 3 4 -5 2  6 1  -2 0
3 5 20  -7 4  3 1
输出样例:
15 24 -25 22 30 21 -10 20 -21 8 35 6 -33 5 14 4 -15 3 18 2 -6 1
5 20 -4 4 -5 2 9 1 -2 0

思路:一元多项式的指数不可重复,且一个指数对应一个系数,所以选择Map中的key-value进行存储,key存储指数,value存储系数。计算结果要求按指数降序输出,选择TreeMap存储,输入的多项式没有要求,可以用HashMap存储。

计算多项式乘积:用两重for循环实现,分别将多项式1中的每一项和多项式2相乘,再把所得的积求和。两项相乘所得的结果的指数是两个指数的和,系数是两个系数的积,若结果mulMap中没有该指数,直接把系数-指数对放到mulMap中,若有该指数,只要在原有的系数上加上这个系数。

计算多项式的和:先将多项式1放到结果addMap中,再遍历多项式2。对于多项式2的每一项,若结果addMap中没有该指数,直接把系数-指数对放到addMap中,若有该指数,只要在原有的系数上加上这个系数。

结果的输出:用一个flag表示是否有过非零项的输出。每次输出前先判断value,是0就看下一个元素,不是0就判断flag,如果flag是false就置为true但不输出空格,为true就输出一个空格,flag判断完之后,输出系数-指数对(这里flag用来控制第一次输出的系数-指数对前面没有空格,后面输出的系数-指数对的前面带有空格)。只要输出过一次非零项,flag就置为true,如果循环结束,flag仍为false,说明结果是零多项式,输出“0 0”。

  1. import java.util.*;
  2. public class Main {
  3. public static void main(String[] args) {
  4. Scanner scan = new Scanner(System.in);
  5. int value; //系数
  6. int key; //指数
  7. //以指数从大到小的顺序存储乘积结果
  8. Map<Integer,Integer> mulMap = new TreeMap<>(new Comparator<Integer>() {
  9. @Override
  10. public int compare(Integer o1, Integer o2) {
  11. return -o1.compareTo(o2);
  12. }
  13. }) ;
  14. //以指数从大到小的顺序存储加法结果
  15. Map<Integer,Integer> addMap = new TreeMap<>(new Comparator<Integer>() {
  16. @Override
  17. public int compare(Integer o1, Integer o2) {
  18. return -o1.compareTo(o2);
  19. }
  20. });
  21. //获取第一个多项式,指数作为key,系数作为value
  22. int n = scan.nextInt();
  23. Map<Integer,Integer> map1 = new HashMap<>(n);
  24. for (int i = 0; i < n; i++){
  25. value = scan.nextInt();
  26. key = scan.nextInt();
  27. map1.put(key,value);
  28. }
  29. //获取第二个多项式
  30. int m = scan.nextInt();
  31. Map<Integer,Integer> map2 = new HashMap<>(m);
  32. for (int i = 0; i < m; i++){
  33. value = scan.nextInt();
  34. key = scan.nextInt();
  35. map2.put(key,value);
  36. }
  37. //计算乘积
  38. for (int key1 : map1.keySet()){
  39. for (int key2 : map2.keySet()){
  40. int mulkey = key1 + key2;
  41. int mulValue = map1.get(key1) * map2.get(key2);
  42. if (mulMap.get(mulkey) == null){
  43. mulMap.put(mulkey,mulValue); //如果mulMap里没有mulkey,直接把mulkey,mulValue存入
  44. }else{
  45. mulMap.put(mulkey,mulMap.get(mulkey) + mulValue); //如果mulMap里已经有mulkey,在原有value上加上mulValue
  46. }
  47. }
  48. }
  49. //输出乘积
  50. Set<Integer> mulKeySet = mulMap.keySet();
  51. Iterator<Integer> iterator = mulKeySet.iterator();
  52. boolean flag = false; //控制空格的输出,并且用来判断结果是不是零多项式
  53. while (iterator.hasNext()){
  54. int next = iterator.next();
  55. if (mulMap.get(next) != 0) { //系数不为0才输出,为0就看下一个
  56. if (!flag) { //第一次遇到非0的系数,将flag置为true
  57. flag = true;
  58. } else { //不是第一次遇到非0的系数,输出空格
  59. System.out.print(" ");
  60. }
  61. System.out.print(mulMap.get(next) + " " + next); //输出“系数 指数”
  62. }
  63. }
  64. //如果循环结束flag还是false,说明没有遇到非0的系数,即结果为零多项书,输出"0 0"
  65. if (!flag){
  66. System.out.print("0 0");
  67. }
  68. System.out.println();
  69. //计算和
  70. addMap.putAll(map1); //复制多项式1
  71. for (int key2 : map2.keySet()){
  72. if (addMap.containsKey(key2)){
  73. int addValue = addMap.get(key2) + map2.get(key2);
  74. addMap.put(key2,addValue); //如果addMap里有addkey,在原有value基础上加上map2中对应的value
  75. }else{
  76. addMap.put(key2,map2.get(key2)); //如果addMap里没有addkey,直接把addkey,addValue存入
  77. }
  78. }
  79. //输出加法多项式
  80. Set<Integer> addKeySet = addMap.keySet();
  81. Iterator<Integer> iterator1 = addKeySet.iterator();
  82. boolean flag1 = false;
  83. while (iterator1.hasNext()){
  84. int next = iterator1.next();
  85. if (addMap.get(next) != 0) {
  86. if (!flag1) {
  87. flag1 = true;
  88. } else {
  89. System.out.print(" ");
  90. }
  91. System.out.print(addMap.get(next) + " " + next);
  92. }
  93. }
  94. if (!flag1){
  95. System.out.print("0 0");
  96. }
  97. }

注意:上面的代码中,即使某些项的系数为0,也存到了结果mulMap和addMap中,所以在输出的时候将其屏蔽。

如果不想让结果Map中存储系数为0的项,改为下面的代码:

  1. import java.util.*;
  2. public class Main {
  3. public static void main(String[] args) {
  4. Scanner scan = new Scanner(System.in);
  5. int value;
  6. int key;
  7. Map<Integer,Integer> mulMap = new TreeMap<>(new Comparator<Integer>() {
  8. @Override
  9. public int compare(Integer o1, Integer o2) {
  10. return -o1.compareTo(o2);
  11. }
  12. }) ;
  13. Map<Integer,Integer> addMap = new TreeMap<>(new Comparator<Integer>() {
  14. @Override
  15. public int compare(Integer o1, Integer o2) {
  16. return -o1.compareTo(o2);
  17. }
  18. });
  19. int n = scan.nextInt();
  20. Map<Integer,Integer> map1 = new HashMap<>(n);
  21. for (int i = 0; i < n; i++){
  22. value = scan.nextInt();
  23. key = scan.nextInt();
  24. map1.put(key,value);
  25. }
  26. int m = scan.nextInt();
  27. Map<Integer,Integer> map2 = new HashMap<>(m);
  28. for (int i = 0; i < m; i++){
  29. value = scan.nextInt();
  30. key = scan.nextInt();
  31. map2.put(key,value);
  32. }
  33. for (int key1 : map1.keySet()){
  34. for (int key2 : map2.keySet()){
  35. int mulkey = key1 + key2;
  36. int mulValue = map1.get(key1) * map2.get(key2);
  37. if (mulMap.get(mulkey) == null){
  38. if (mulValue != 0){
  39. mulMap.put(mulkey,mulValue);
  40. }
  41. }else{
  42. int sum = mulMap.get(mulkey) + mulValue;
  43. if (sum != 0){
  44. mulMap.put(mulkey,sum);
  45. }else{
  46. mulMap.remove(mulkey);
  47. }
  48. }
  49. }
  50. }
  51. Set<Integer> mulKeySet = mulMap.keySet();
  52. Iterator<Integer> iterator = mulKeySet.iterator();
  53. boolean flag = false;
  54. if (mulKeySet.size() != 0){
  55. while (iterator.hasNext()){
  56. int next = iterator.next();
  57. if (!flag) {
  58. flag = true;
  59. } else {
  60. System.out.print(" ");
  61. }
  62. System.out.print(mulMap.get(next) + " " + next);
  63. }
  64. }else{
  65. System.out.print("0 0");
  66. }
  67. System.out.println();
  68. addMap.putAll(map1);
  69. for (int key2 : map2.keySet()){
  70. if (addMap.containsKey(key2)){
  71. int addValue = addMap.get(key2) + map2.get(key2);
  72. if (addValue != 0){
  73. addMap.put(key2,addValue);
  74. }else{
  75. addMap.remove(key2);
  76. }
  77. }else{
  78. int value2 = map2.get(key2);
  79. if (value2 != 0){
  80. addMap.put(key2,value2);
  81. }
  82. }
  83. }
  84. Set<Integer> addKeySet = addMap.keySet();
  85. Iterator<Integer> iterator1 = addKeySet.iterator();
  86. boolean flag1 = false;
  87. if (addKeySet.size() != 0){
  88. while (iterator1.hasNext()){
  89. int next = iterator1.next();
  90. if (!flag1) {
  91. flag1 = true;
  92. } else {
  93. System.out.print(" ");
  94. }
  95. System.out.print(addMap.get(next) + " " + next);
  96. }
  97. }else{
  98. System.out.print("0 0");
  99. }
  100. }
  101. }

以乘法运算为例,我之前的想法是,计算mulMap时不判断系数是否为0,得到所有系数-指数对以后,再剔除value为0的元素(我是以keySet的foreach循环对mulMap中的元素进行遍历,遇到value为0的元素就调用remove(),但是会报ConcurrentModificationException,这个不知道怎么改。)

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Monodyee/article/detail/342824
推荐阅读
相关标签
  

闽ICP备14008679号