（C言語） 10進数乗算 int型 100桁 配列

Question

２つの正の10進数を入力して、 その積を出力するプログラムを書いてください。 各10進数の桁数は100以下とします。 これはint型の値として表現できる範囲を超えています。 二つの数のそれぞれを配列を用いて表現することに なるでしょう。 入力は次の順で与えられます。

(1) 1番目の整数の桁数 n1

(2) 1番目の整数の各桁の数(0以上9以下)n1個を 上の桁から空白で区切った列

(3) 2番目の整数の桁数 n2

(4) 2番目の整数の各桁の数(0以上9以下)n2個を 上の桁から空白で区切った列

答えの10進数を入力と同じ形式で出力してください。つまり、最初に答えの整数の桁数を出力し、その後ろに答えの整数を、上の桁から空白で区切って出力します。

Sample Input 1
2 2 5 3 1 0 0
Sample Output 1
4 2 5 0 0

Sample Input 2
5 3 8 9 6 7 4 1 7 9 8
Sample Output 2
8 7 0 0 6 2 6 6 6

みなさんのヒントを元に自分でなんとか頑張ってみました
2次元配列を用意して筆算の過程を再現して、最後に各列足していく形にしました！
小さい値の計算なら値が合うのですが、サーバーのチェックのとき１００桁×１００桁の計算で正常な値にならないので何が原因なのか考えたのですがわからなかったので、どこがいけないのかの指摘をおねがいします！！

#include<stdio.h>
int main (void){
  int number1[100]={0};
  int number2[100]={0};
  int kari[100]={0};
  int hissan[100][200]={{0}};
  int total[200]={0};
  int n1,n2,i,j,t,up,temp,k,sum,n,s,p;
  scanf("%d",&n1);
  for(i=n1-1;i>=0;i--)
    scanf("%d",&number1[i]);
  scanf("%d",&n2);
  for(i=n2-1;i>=0;i--)
    scanf("%d",&number2[i]);
  if(n1<n2){
    p=n1;
    n1=n2;
    n2=p;
    for(i=0;i<100;i++){
      kari[i]=number1[i];
      number1[i]=number2[i];
      number2[i]=kari[i];
    }
  }
  for(i=0;i<n2;i++){
    up=0;
    k=n1+n2-1-i;
    for(j=0;j<=n1;j++){
      temp = t = number2[i]*number1[j]+up;
      if(temp>=10){
	temp = t%10;
	up = t/10;
      }else{
	up=0;
      }
      hissan[i][k]=temp;
      k--;
    }
  }
  /*
  for(i=0;i<n2;i++){
    for(j=0;j<n1+n2;j++){
      printf("%2d",hissan[i][j]);
    }
    printf("\n");
  }
  printf("------------------\n");
  */
  for(i=n1+n2-1;i>=0;i--){
    sum=0;
    for(j=0;j<n2;j++){
      sum += hissan[j][i];
    }
    sum = sum + up;
    if(sum>=10){
      temp = sum%10;
      up = sum/10;
    }else{
      temp = sum;
      up = 0;
    }
    total[i] = temp;
  }
  if(total[0]==0){
    printf("%d",n1+n2-1);
    for(i=1;i<n1+n2;i++)
      printf("%2d",total[i]);
  }else{
    printf("%d",n1+n2);
    for(i=0;i<n1+n2;i++)
      printf("%2d",total[i]);
  }
  printf("\n");
  return(0);
}

Input
100 8 2 8 9 9 2 8 7 8 0 0 0 0 2 9 3 7 6 4 9 0 9 0 2 6 0 1 2 8 1 5 9 3 0 5 5 4 0 5 3 1 7 4 4 3 9 8 8 9 8 6 9 3 0 2 2 8 1 8 9 3 6 9 2 4 6 4 8 0 4 2 9 0 4 4 8 8 9 3 9 3 1 5 2 4 9 8 8 9 8 6 8 3 6 6 2 3 7 1 3 100 9 2 6 3 4 4 3 9 0 4 6 2 3 7 8 8 3 6 6 4 3 9 7 1 8 7 0 7 2 9 1 2 9 4 7 2 5 6 5 8 0 5 3 1 1 0 9 4 9 3 2 3 9 0 9 9 3 6 3 5 1 9 7 8 2 4 9 9 3 1 1 5 7 8 5 2 5 0 6 4 2 4 0 9 7 4 7 1 8 6 2 7 0 3 5 1 4 1 3 5

失敗したOutput
200-1708835137-1334178314 2-2001267461 9 5-2001267446-1708835094 2 7 8-1334178276-2001267439-374656782-1041745919-1041745937-2001267411 0 8 3-2001267397-1708835049-374656751-667089064-1041745883-374656716 6-374656733-1334178213-1708835058-667089053-1334178193-1708835032 7-374656674-1334178157 5 7 7-1041745811 6 0-2001267328-667088989-667088982 0-1708834924 9-1708834945-2001267285-1334178100-2001267263-1708834886 9-1708834950-1708834918-2001267237 4-2001267225 7-667088928-1708834901-374656571-1041745724-1334178030 5-1708834871-1708834864-2001267218-667088866-667088840 5-374656531-1041745637 1-1334177978 0 9 8 5-1334177966 2 2-1708834783-374656434 7-374656481-667088809-1041745568 7-1334177900-374656385 9-2001267103 3-667088733 5-667088776-2001267011 0 5 6 4 2 1 0 6 1 8 6 9 7 9 5 8 8 3 6 7 3 9 0 4 7 1 3 2 6 5 0 2 8 9 7 7 8 3 8 1 5 7 8 0 6 7 7 5 7 5 2 0 5 6 9 6 5 9 3 2 3 3 9 9 2 0 5 6 8 8 2 6 4 6 8 2 3 2 4 3 3 7 3 0 5 8 3 5 7 3 2 3 7 7 1 6 8 3 2 5 5

Answer 1

問題文に、

二つの数のそれぞれを配列を用いて表現することに なるでしょう。

と書いてあるとおりに数を表現して、
かけ算を筆算でできますよね？それと同じロジックをプログラミングします。

Comments

[tsuruchan]

ロジックはわかったのですが、筆算をコードに出来ないです...
1桁×○○桁なら出来るんですが、桁が増えると具体的にどのように書けばいいのでしょうか

[otn]

for(1番目の桁数){
　for(2番目の桁数){
　　x = 1番目の10**iの位 x 2番目の10**jの位
　　x の1の位を結果の10**(i+j)の位に足し込む
　　x の10の位を結果の10**(i+j+1)の位に足し込む
　}
}

Answer 2

  for(i=0;i<n2;i++){
    up=0;
    k=n1+n2-1-i;
    for(j=0;j<=n1;j++){
      temp = t = number2[i]*number1[j]+up;
      if(temp>=10){
    temp = t%10;
    up = t/10;
      }else{
    up=0;
      }
      hissan[i][k]=temp;
      k--;
    }
  }

各配列，インデックスの大きいほうが大きな位の数字を表していると思うのですが，
ここにおけるhissanの並びが逆になっているような気がします．

Answer 3

問題を解く前に実装上の話をします．
この問題に限らず他のプログラムを書く上で重要になるためです．
C言語の配列を使うならば，あらかじめ長さを指定しないといけません．
さて，100桁以下の2つの数をかけると，答えは何桁以下になるでしょうか．
（これが答えを表現するために用意するべき配列のサイズになります）

すでにotnさんがシンプルなコードの書き方を書いていらっしゃるので，別解を書いておきます．
3桁以下で考えたとき，整数AとBが以下のように表現できるとします．
A = a[0]*1 + a[1]*10 + a[2]*100
B = b[0]*1 + b[1]*10 + b[2]100
AとBの積は１回だけ式を展開して，
AB = (a[0]*1 + a[1]*10 + a[2]*100)*b[0]*1
+(a[0]*1 + a[1]*10 + a[2]*100)*b[1]*10
+(a[0]*1 + a[1]*10 + a[2]*100)*b[2]100
となることは分かると思います．
これを変形して
AB = (a[0]*1 + a[1]*10 + a[2]*100)*b[0]
+(a[0]*10 + a[1]*100 + a[2]*1000)*b[1]
+(a[0]*100 + a[1]*1000 + a[2]*10000)*b[2]
とします．
「1桁×○○桁なら出来る」のであれば，この形がわかりやすいと思います．
もちろん100桁同士のかけ算の展開式を書くわけにはいかないので，otnさんのご指摘通りfor文を使ってコーディングした方が良いと思います．

もう一つ実装上のヒントを出すとすれば
void mul_num_ary(char *res, char num, char *array) 1桁×○○桁を行う関数
void pow_10_ary(char *res, int n, char *array) ○○桁の配列をn桁ずらす関数
void add_ary_ary(char *res, char *in1, char *in2) ○○桁+○○桁を行う関数
くらいは作っておいた方がコードがきれいになると思います．
関数名などは適当につけているので，tsuruchanさんのお好みで付けてください．

補足になりますが，配列で表現された整数の演算をするときは，桁数がわかっているとfor文のループ回数を減らすことができます．
しかし考えなければ毎回最大桁分計算しなければならないことになります．
これは，繰り上がりを処理するために通常は下位の桁から計算すると思いますが，そうすると何桁まであるのかわからなくて最大桁数まで見なければならないためです．
余力があれば，高速なプログラムを作ることにも挑戦してみてください．
確実に実力が向上します．

Answer 4

1 2 3
4 5 6
１つ目の配列
①→６×３→１８→８を１桁目に
②→６×２→１２→２と①の繰り上がり(1)を足して２桁目に・・・
以下同様にして１２３×６を求める
２つ目の配列
１桁目は０を入れる
③→５×３→１５→５を２桁目に
②→５×２→１０→０と③の繰り上がり(1)を足して３桁目に・・・
以下同様にして１２３×５を求める
・・・これを桁数分おこなう。
最後に、１２３×６、１２３×５、１２３×４の結果を加算する