質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

Q&A

解決済

7回答

2142閲覧

C++ コードの添削

mentos109

総合スコア28

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

0グッド

0クリップ

投稿2016/09/27 15:27

編集2016/09/27 17:45

###前提・実現したいこと
すごく初歩的な質問かもしれませんが、下記のコードを実行すると、途中から計算結果が実際の数値と違ってきてしまいます。
どこがおかしいのでしょうか?
内容としては100の階乗を求めるプログラムです。
91の段階で結果がおかしくなります。
→検算したところ、9を掛けた時点でおかしくなるようです。

###該当のソースコード

C++#include

1#include <iomanip> 2#include <string> 3using namespace std; 4 5#define DIGIT_BUF 1000 6 7void ToArray(int number, int* num) 8{ 9 int count = 0; 10 11 while (number) { 12 num[count] = number % 10; 13 count++; 14 number = number / 10; 15 } 16} 17 18int Digit(int* num) 19{ 20 int count = DIGIT_BUF - 1; 21 while (1) { 22 if (num[count] != 0) 23 return count; 24 count--; 25 } 26} 27 28 29void ArrayMul(int* num1, int* num2, int* num) 30{ 31 int num1_digit = Digit(num1); 32 int num2_digit = Digit(num2); 33 for (int i = 0; i < DIGIT_BUF; i++) { 34 num[i] = 0; 35 } 36 for (int i = 0; i < num1_digit + 1; i++) { 37 for (int j = 0; j < num2_digit + 1; j++) { 38 num[j + i] += num1[i] * num2[j]; 39 } 40 } 41 for (int i = 0; i < Digit(num) + 1; i++) { 42 if (num[i] / 10) { 43 num[i + 1] += num[i] / 10; 44 num[i] = num[i] % 10; 45 } 46 } 47} 48 49void Factorial(int number, int* num) { 50 int hoge1[DIGIT_BUF] = {}, hoge2[DIGIT_BUF] = {}, hoge3[DIGIT_BUF] = {}; 51 ToArray(number, hoge3); 52 for (number; number > 1; number--) { 53 memcpy(hoge1, hoge3, sizeof(int) * DIGIT_BUF); 54 ToArray(number - 1, hoge2); 55 ArrayMul(hoge1, hoge2, hoge3); 56 int count = Digit(hoge3); 57 cout << number - 1 << " "; 58 while (count >= 0) { 59 cout << hoge3[count]; 60 count--; 61 } 62 cout << endl; 63 } 64 memcpy(num, hoge3, sizeof(int) * DIGIT_BUF); 65} 66int main() 67{ 68 int result[DIGIT_BUF] = {}; 69 70 Factorial(100, result); 71 72}

よろしくお願いします。

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答7

0

余分な桁をクリアするといけるかもしれません num[count] = 0;

c++

1void ToArray(int number, int* num) 2{ 3 int count = 0; 4 5 while (number) { 6 num[count] = number % 10; 7 count++; 8 number = number / 10; 9 } 10 num[count] = 0; 11}

投稿2016/09/28 02:59

A.Ichi

総合スコア4070

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

A.Ichi

2016/09/28 11:08

余分な消し忘れの1桁を削るように考えましたが、1000桁入力を想定してませんでした。
A.Ichi

2016/10/01 15:36

正しい結果となります。11でおかしくなるのを見つけるのに時間はかかりましたが・・・
guest

0

巨大整数の掛け算なら一年前にコラムを書きました。
<numeric>がらみの数値演算に触発されて、「巨大整数のかけ算」を行う方法

投稿2016/09/28 00:49

episteme

総合スコア16614

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

ベストアンサー

ToArray関数周辺の問題です。未使用桁をゼロクリアしていないため、桁数が2→1に減少したとき(10→9)に、9が19相当のデータに化けています。

C

1void ToArray(int number, int* num) 2{ 3 memset(num, 0, sizeof(int)*DIGIT_BUF); // 追加 4 // 後略 5}

投稿2016/09/28 00:42

yohhoy

総合スコア6189

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

mentos109

2016/09/28 00:58

これでした! ArrauMulに問題があるとばかり思っていて完全に盲点でした。 ありがとうございました。
yohhoy

2016/09/28 01:47

FYI: printfデバッグで見つけました。古典的ですがステップ毎の結果確認は重要ですね。
guest

0

机上で大体のあたりはつきましたが、確信が持てないので。
91のときの表示と、実際の数字はどのように違いますか?
Factorial関数内部の、数字を表示する部分、1桁おきにスペースを入れて表示して、スペースが表示されない桁はありませんか?
つまり、

C

1cout << number - 1 << ":"; 2while (count >= 0) { 3 cout << hoge3[count]; 4 cout << " "; 5 count--; 6} 7cout << endl;

としたときに、
2 5 93 1
の93のように、連続して表示されている桁はありませんか?
もし表示がバグっていれば、繰り上がりの計算に問題があります。
なければ…もう1つのオーバーフローだと思います。
あと1つ質問。使っている環境、16ビットだったりしませんか?

投稿2016/09/28 00:47

majiponi

総合スコア1720

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

Windows標準の電卓で、プログラマモードの場合は以下のようになります。

628156509555294720 * 90 = 1193853638847869952

関数電卓モードの場合、以下になります。

628156509555294720 * 90 = 56534085859976524800

6*9は54なので、後者が正しい答えのはずです。
プログラムの実行結果は後者のようですので、プログラムは正常と思います。

プログラマモードの場合に答えが違ってしまうのは…なんででしょうね?
桁あふれかなんかでしょうか?ちょっとわかりません。

--
補足。paiza.ioで実行してみて、以下の結果を得ています。

99 9900
(省略)
92 690281878632192000
91 62815650955529472000
90 5653408585997652480000
89 503153364153791070720000
(省略)

投稿2016/09/28 00:39

編集2016/09/28 00:42
tnd-.-b

総合スコア247

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

mentos109

2016/09/28 00:56

申し訳ありません、91では問題ないことは確認できたのですが、問題は別にあったようです。 お騒がせいたしました。 プログラマモードで数字がずれるのは、、、なぜなんでしょうね?
guest

0

C++

1void ArrayMul(int* num1, int* num2, int* num) 2{ 3 for (int i = 0; i < DIGIT_BUF; i++) { 4 num[i] = 0; 5 } 6 for (int i = 0; i < DIGIT_BUF; i++) { 7 for (int j = 0; j < DIGIT_BUF; j++) { 8 num[j + i] += num1[i] * num2[j]; // バッファオーパーラン 9 } 10 } 11 for (int i = 0; i < DIGIT_BUF; i++) { 12 if (num[i] / 10) { 13 num[i + 1] += num[i] / 10; // バッファオーパーラン 14 num[i] = num[i] % 10; 15 } 16 } 17}

コメントに書いたとおり、バッファオーバーランしている場所が2ケ所あります。最初の場合は、i, jの最大値は DIGIT_BUF-1 なので j+i は 2*DIGIT_BUF-2 が最大値になり、オーバーランします。2番目は、i + 1 が DIGIT_BUF になり、オーバーランします。

おそらく、このオーバーランで Factorial の中の hoge2 の中身が上書きされて結果がおかしくなっているのだと思います。hoge1 の値が小さいうちは hoge1 の上の桁が 0 ですので、hoge2 がおかしくても 0 と掛けているので問題が現れないのでしょう。

投稿2016/09/27 16:54

退会済みユーザー

退会済みユーザー

総合スコア0

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

mentos109

2016/09/27 17:28

回答有り難うございます。 初歩的なミスで恥ずかしいです。 なのですが、なんとなくこれが原因でもないような気がします。 というのも、計算結果を見てみるとこれ以降の掛け算は正しく行われているようなのです。 また、DIGIT_BUFの数を大きくしても結果が変わらず、ArrayMulの冒頭にnum1とnum2の桁数を示す変数を用意し、iとjがDIGIT_BUFまで繰り返していたのをそれぞれの桁数までで止めるように変え、後者も同じく桁数分だけ計算するよう書き換えたのですが結果が変わりませんでした。
mentos109

2016/09/27 17:35

すみません、正直余計訳がわからなくなってまいりまして・・・ 検算にWindows標準の計算機を使用していたのですが、同じ計算をgoogle検索を使用して計算してみたところ、91の段階では計算が正しいようなのです。 ちょっともう少し詳しく調べてから質問してみようと思います。。
mentos109

2016/09/27 17:47

質問文を新しく書き直したコードに直しました。 もし宜しければ添削よろしくお願いします。 ご迷惑おかけします。
guest

0

誤差…?
double で計算してみてはいかがでしょうか。

投稿2016/09/27 15:32

mugicya

総合スコア1046

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

mentos109

2016/09/27 15:38

doubleですと剰余の計算ができないようです。 また、大きな数値を扱うために数値を配列で表現して計算をしているつもりなので誤差というわけではないような気もします・・・
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問