連結リストを用いて大きな桁数の掛け算を行う方法がわからない。

前提

入力で与えられる 2 つの文字列が表す正の整数に対し掛け算を行う問題を解いています。入力の長さは限定されていないため、節点の要素として各桁の数を含む連結リストを用いて表す必要があります。私は掛け算の筆算のやり方しか思い浮かばず、それぞれの桁の数を掛け合わせた後にどのようにすれば良いのかが分かりません。連結リストをどのように使えば掛け算をすることができるのか教えてください。ちなみに連結リストを用いた足し算や配列を用いた掛け算は出来ました。

jimbe

2022/11/21 16:40 編集

足し算が出来て掛け算が出来ないのはどういうことでしょう。足し算のコードを提示してみては如何ですか。 >掛け算の筆算のやり方しか思い浮かばず、それぞれの桁の数を掛け合わせた後にどのようにすれば良いのか筆算ではどのような手順だったか、もう当然過ぎて意識しなくなっているものと思います。意識して確認しては如何でしょうか。(『それぞれの桁の数を掛け合わせ』?) https://sugaku.fun/longhand-of-multiplication/

Zuishin

2022/11/21 23:38

足し算は順に足していくだけですが、掛け算は桁ごとに掛け算したものを足さなければいけないので少し難易度が上がります。と言っても、足し算と同じ手順で一桁目をかけたものと、同じ手順で二桁目をかけたものを桁を変えて足し算し、それを繰り返せばいいので、足し算ができるならそう難しくはありません。作るべき関数は、足し算関数と、大きな数値に一桁の数値を掛ける関数です。複数桁に対応した関数は、それらを呼び出すことで実現できます。配列を使ったものが作れるなら、これが作れない理由はないので、頑張ってみてください。

sawaawa

2022/11/21 23:57

了解です。やってみます。

行動規範の内容に同意します

回答2件

ベストアンサー

scanf の時点で長さに制限がかかってしまうので、 getc 使えみたいな条件があるのかもしれませんが。

c
1#include <stdio.h>
2#include <stdlib.h>
3
4typedef struct node {
5  struct node *next, *prev;
6  int value;
7} NODE;
8
9/** 新たな NODE を返す. node が NULL で無ければその node の後にリンクし、 NULL なら自身にリンクする */
10NODE *create_node(NODE *node, int value) {
11  NODE *p = malloc(sizeof(NODE));
12  p->value = value;
13  if(node) {
14    p->next = node->next;
15    p->prev = node;
16    p->next->prev = p;
17    p->prev->next = p;
18  } else {
19    p->next = p->prev = p;
20  }
21  return p;
22}
23
24//正規化. head を返す
25NODE *normalize_list(NODE *head) {
26  if(head->next == head) {
27    create_node(head, 0);
28  } else {
29    //ゼロサプレス
30    for(NODE *p=head->next, *next; p->value==0 && p->next!=head; p=next) {
31      next = p->next;
32      p->next->prev = p->prev;
33      p->prev->next = p->next;
34      free(p);
35    }
36  }
37  return head;
38}
39
40/** 数字列から、桁毎を NODE としたリストを返す */
41NODE *create_list(char *str) {
42  NODE *head = create_node(NULL, 0);
43  for(char c; (c=*str++); ) create_node(head->prev, c-'0');
44  return normalize_list(head);
45}
46
47/** node を含めた全 NODE 解放 */
48void free_list(NODE *node) {
49  for(NODE *p=node->next, *next; p!=node; p=next) {
50    next = p->next;
51    free(p);
52  }
53  free(node);
54}
55
56/** 加算して新たなリストを返す */
57NODE *addition_list(NODE *augend, NODE *addend) {
58  NODE *answer = create_node(NULL, 0);
59  int carry = 0;
60  for(NODE *p1=augend->prev, *p2=addend->prev; p1!=augend || p2!=addend || carry; ) {
61    int v1 = p1 != augend ? p1->value : 0;
62    int v2 = p2 != addend ? p2->value : 0;
63    int a = v1 + v2 + carry;
64    carry = a / 10;
65    create_node(answer, a % 10);
66    if(p1 != augend) p1 = p1->prev;
67    if(p2 != addend) p2 = p2->prev;
68  }
69  return normalize_list(answer);
70}
71
72/** リストに 1 桁値を乗算して新たなリストを返す. multiplier: 0 ～ 9 */
73NODE *multiplication_list_sub(NODE *multiplicand, int multiplier) {
74  NODE *answer = create_node(NULL, 0);
75  int carry = 0;
76  for(NODE *p=multiplicand->prev; p!=multiplicand || carry; ) {
77    int a = p->value * multiplier + carry;
78    carry = a / 10;
79    create_node(answer, a % 10);
80    if(p != multiplicand) p = p->prev;
81  }
82  return normalize_list(answer);
83}
84
85/** 乗算して新たなリストを返す */
86NODE *multiplication_list(NODE *multiplicand, NODE *multiplier) {
87  NODE *answer = create_node(NULL, 0);
88  int digits = 0;
89  for(NODE *p=multiplier->prev; p!=multiplier; p=p->prev, digits++) {
90    NODE *sub = multiplication_list_sub(multiplicand, p->value);
91    for(int i=0; i<digits; i++) create_node(sub->prev, 0); //桁合わせ
92    NODE *a = addition_list(answer, sub);
93    free_list(answer);
94    free_list(sub);
95    answer = a;
96  }
97  return normalize_list(answer);
98}
99
100/** リストを表示する(テキスト・改行付き) */
101void print_list(NODE *head, char *pretext) {
102  if(pretext != NULL) printf(pretext);
103  for(NODE *p=head->next; p!=head; p=p->next) printf("%d", p->value);
104  printf("\n");
105}
106
107char buf[2][1024]; //スタックフレームサイズに制限されないようグローバル
108
109int main(int argc, char *argv[]) {
110  scanf("%s %s", buf[0], buf[1]);
111
112  NODE *list1 = create_list(buf[0]);
113  print_list(list1, "list1: ");
114  NODE *list2 = create_list(buf[1]);
115  print_list(list2, "list2: ");
116
117  NODE *add = addition_list(list1, list2);
118  print_list(add, "add: ");
119  free_list(add);
120
121  NODE *multi = multiplication_list(list1, list2);
122  print_list(multi, "multi: ");
123  free_list(multi);
124
125  free_list(list1);
126  free_list(list2);
127
128  return 0;
129}

plain
1123456789
29876543210
3list1: 123456789
4list2: 9876543210
5add: 9999999999
6multi: 1219326311126352690

scanf で無く getc でちゃんと(?)制限無しにするなら

c
1/** file から(数字で無い文字をスキップ後、数字で無い文字が現れるまでの)数字列を読み込み、桁毎を NODE としたリストを返す */
2NODE *create_list_from_file(FILE *file) {
3  NODE *head = create_node(NULL, 0);
4  for(int c; (c=getc(file)) != EOF; ) {
5    if(c < '0' || '9' < c) {
6      if(head->next == head) continue;
7      break;
8    }
9    create_node(head->prev, c-'0');
10  }
11  if(head->next == head && feof(file)) return NULL; //何も無いまま EOF は許さない
12  return normalize_list(head);
13}

を追加して main を

c
1//char buf[2][1024]; //不要
2
3int main(int argc, char *argv[]) {
4  NODE *list1 = create_list_from_file(stdin);
5  if(list1 == NULL) { fprintf(stderr, "error: list1 が見つからない."); return -1; }
6  NODE *list2 = create_list_from_file(stdin);
7  if(list2 == NULL) { fprintf(stderr, "error: list2 が見つからない."); return -1; }
8
9  print_list(list1, "list1: ");
10  print_list(list2, "list2: ");
11
12  NODE *add = addition_list(list1, list2);
13  print_list(add, "add: ");
14  free_list(add);
15
16  NODE *multi = multiplication_list(list1, list2);
17  print_list(multi, "multi: ");
18  free_list(multi);
19
20  free_list(list1);
21  free_list(list2);
22
23  return 0;
24}