题目描述
题目地址为:https://pintia.cn/problem-sets/15/problems/710
设计函数分别求两个一元多项式的乘积与和。
输入格式
输入分2行，每行分别先给出多项式非零项的个数，再以指数递降方式输入一个多项式非零项系数和指数（绝对值均为不超过1000的整数）。数字间以空格分隔。
输出格式
输出分2行，分别以指数递降方式输出乘积多项式以及和多项式非零项的系数和指数。数字间以空格分隔，但结尾不能有多余空格。零多项式应输出0 0。
输入样式
1
2
| 4 3 4 -5 2 6 1 -2 0
3 5 20 -7 4 3 1
|
输出样式
1
2
| 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
|
法一 链表
思考
这是在数据结构书上出现过的一道题目，只不过书上没有说多项式的乘积。想来实现原理也应该大同小异。
关键就是链表，用链表来存储每个不同指数的项。看来我也好久没有写过代码，这点都想不到了。
具体代码
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
| #include <stdio.h>
#include <stdlib.h>
#include <math.h>
typedef struct Node {
int xishu;
int zhishu;
struct Node* next;
} List;
List* merge(List* l1,List* l2){
if(!l1->next && !l2->next) {
return NULL;
}
if (!l1->next) {
return l2;
}
if (!l2->next) {
return l1;
}
struct Node* head = (struct Node*)malloc(sizeof(struct Node));
struct Node* next = head;
l1 = l1->next;
l2 = l2->next;
while(l1 && l2) {
if (l1->zhishu == l2->zhishu) {
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->next = NULL;
node->zhishu = l1->zhishu;
node->xishu = l1->xishu + l2->xishu;
if (node->xishu == 0) {
l1 = l1->next;
l2 = l2->next;
continue;
}
next->next = node;
l1 = l1->next;
l2 = l2->next;
} else if(l1->zhishu > l2->zhishu) {
next->next = l1;
l1 = l1->next;
} else {
next->next = l2;
l2 = l2->next;
}
next = next->next;
}
if (!l1) {
next->next = l2;
}
if (!l2) {
next->next = l1;
}
return head;
}
List* chengji(List* l1,List* l2) {
if(!l1->next || !l2->next) {
return NULL;
}
List* head = (List*)malloc(sizeof(struct Node));
List* l1_loop = l1->next;
while(l1_loop) {
List* temp = (List*)malloc(sizeof(struct Node));
List* next = temp;
List* l2_loop = l2->next;
while(l2_loop) {
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->next = NULL;
node->zhishu = l1_loop->zhishu + l2_loop->zhishu;
node->xishu = l1_loop->xishu * l2_loop->xishu;
next->next = node;
next = next->next;
l2_loop = l2_loop->next;
}
head = merge(head,temp);
l1_loop = l1_loop->next;
}
return head;
}
void show(List* l1,List* l2) {
List* cj = chengji(l1,l2);
if(!cj) {
printf("0 0");
}else {
while(cj->next) {
printf("%d",cj->next->xishu);
printf(" ");
printf("%d",cj->next->zhishu);
if(cj->next->next) {
printf(" ");
}
cj = cj->next;
}
}
printf("\n");
List* sum = merge(l1,l2);
if(!sum->next) {
printf("0 0");
}else {
while(sum->next) {
printf("%d",sum->next->xishu);
printf(" ");
printf("%d",sum->next->zhishu);
if(sum->next->next) {
printf(" ");
}
sum = sum->next;
}
}
}
int main() {
int xishu;
int zhishu;
int row1_num;
scanf("%d", &row1_num);
struct Node* row1_head = (struct Node*)malloc(sizeof(struct Node));
struct Node* next = row1_head;
for(int i = 0 ; i < row1_num ; i++) {
scanf("%d",&xishu);
scanf("%d",&zhishu);
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->xishu = xishu;
node->zhishu= zhishu;
node->next = NULL;
next->next = node;
next = node;
}
int row2_num;
scanf("%d", &row2_num);
struct Node* row2_head = (struct Node*)malloc(sizeof(struct Node));
next = row2_head;
for(int i = 0 ; i < row2_num ; i++) {
scanf("%d",&xishu);
scanf("%d",&zhishu);
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->xishu = xishu;
node->zhishu= zhishu;
node->next = NULL;
next->next = node;
next = node;
}
show(row1_head,row2_head);
return 0;
}
|
不写注释是吧，还就那个不写。
法二 数组
思考
既然说了最大指数绝对值不超过1000，省去指数的存储用数组的下标来表示。
考虑到乘法，莫不是要1000000这么大？
比较精妙的地方就是用一个count来计数，表示合并之后是否为零多项式。
当count不为0表示不是零多项式。
具体代码
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
| #include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main() {
int list1[1001] = {0};
int list2[1001] = {0};
int xishu;
int zhishu;
int row1_num;
scanf("%d", &row1_num);
for(int i = 0 ; i < row1_num ; i++) {
scanf("%d",&xishu);
scanf("%d",&zhishu);
list1[zhishu] = xishu;
}
int row2_num;
scanf("%d", &row2_num);
for(int i = 0 ; i < row2_num ; i++) {
scanf("%d",&xishu);
scanf("%d",&zhishu);
list2[zhishu] = xishu;
}
int count = 0;
int c[1000001] = {0};
for(int i = 0 ; i <= 1000 ; i++) {
for(int j = 0 ; j <= 1000 ; j++) {
int xishu = list1[i] * list2[j];
int zhishu = i + j;
if (xishu != 0) {
c[zhishu] += xishu;
count++;
}
}
}
int flag = 1;
if(count == 0) {
printf("0 0\n");
} else {
for (int i = 1000000; i >= 0 ; i--) {
if ( c[i] != 0 ) {
if( flag == 0 ) {
printf(" ");
}
printf("%d %d",c[i],i);
flag = 0;
}
}
printf("\n");
}
flag = 1;
count = 0;
for(int i = 0; i < 1001 ; i++) {
list1[i] += list2[i];
if(list1[i] != 0) {
count++;
}
}
if(count == 0) {
printf("0 0\n");
} else {
for (int i = 1000; i >= 0 ; i--) {
if ( list1[i] != 0 ) {
if( flag == 0 ) {
printf(" ");
}
printf("%d %d",list1[i],i);
flag = 0;
}
}
printf("\n");
}
return 0;
}
|